Abstract
We consider the subgroup lpGk,1 of length preserving elements of the Thompson–Higman group Gk,1 and we show that all elements of Gk,1 have a unique lpGk,1 · Fk,1 factorization. This applies to the Thompson–Higman group Tk,1 as well. We show that lpGk,1 is a "diagonal" direct limit of finite symmetric groups, and that lpTk,1 is a k∞ Prüfer group. We find an infinite generating set of lpGk,1 which is related to reversible boolean circuits.
We further investigate connections between the Thompson–Higman groups, circuits, and complexity. We show that elements of Fk,1 cannot be one-way functions. We show that describing an element of Gk,1 by a generalized bijective circuit is equivalent to describing the element by a word over a certain infinite generating set of Gk,1; word length over these generators is equivalent to generalized bijective circuit size.
We give some coNP-completeness results for Gk,1 (e.g., the word problem when elements are given by circuits), and
$\#\mathcal{P}$
-completeness results (e.g., finding the lpGk,1 · Fk,1 factorization of an element of Gk,1 given by a circuit).