Factorizations of the Thompson-Higman groups, and circuit complexity

2006/07/14 by Jean-Camille Birget, Birget, Jean-Camille
Computer Science · Mathematics · #20F10 #68Q15 #Complexity and Algorithms in Graphs #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0607349

openalex publication_date 2006/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the subgroup lpG_k,1 of length preserving elements of the Thompson-Higman group G_k,1 and we show that all elements of G_k,1 have a unique lpG_k,1.F_k,1 factorization. This applies to the Thompson-Higman group T_k,1 as well. We show that lpG_k,1 is a ``diagonal'' direct limit of finite symmetric groups, and that lpT_k,1 is a kⁱnfinity Pr"ufer group. We find an infinite generating set of lpG_k,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 F_k,1 cannot be one-way functions. We show that describing an element of G_k,1 by a generalized bijective circuit is equivalent to describing the element by a word over a certain infinite generating set of G_k,1; word length over these generators is equivalent to generalized bijective circuit size. We give some coNP-completeness results for G_k,1 (e.g., the word problem when elements are given by circuits), and #P-completeness results (e.g., finding the lpG_k,1.F_k,1 factorization of an element of G_k,1 given by a circuit).

Related

• The word problem of the Brin-Higman-Thompson groups
• Circuits, coNP-completeness, and the groups of Richard Thompson
• The Thompson-Higman monoids M_k,i: the J-order, the D-relation, and their complexity
• The word problem of the Brin-Thompson group is coNP-complete
• The groups of Richard Thompson and complexity