×

zbMATH — the first resource for mathematics

On classification of groups generated by 3-state automata over a 2-letter alphabet. (English) Zbl 1164.20004
Summary: We show that the class of groups generated by 3-state automata over a 2-letter alphabet has not more than 122 members. For each group in the class we provide some basic information, such as short relators, a few initial values of the growth function, a few initial values of the sizes of the quotients by level stabilizers (congruence quotients), and histogram of the spectrum of the adjacency operator of the Schreier graph of the action on level 9. In most cases we provide more information, such as whether the group is contracting, self-replicating, or (weakly) branch group, and exhibit elements of infinite order (we show that no group in the class is an infinite torsion group). A GAP package, written by Muntyan and Savchuk, was used to perform some necessary calculations. For some of the examples, we establish that they are (virtually) iterated monodromy groups of post-critically finite rational functions, in which cases we describe the functions and the limit spaces. There are exactly 6 finite groups in the class (of order not greater than 16), two free Abelian groups (of rank 1 and 2), and only one free nonabelian group (of rank 3). The other examples in the class range from familiar (some virtually Abelian groups, lamplighter group, Baumslag-Solitar groups \(BS(1,\pm 3)\), and a free product \(C_2*C_2*C_2\)) to enticing (Basilica group and a few other iterated monodromy groups).

MSC:
20E08 Groups acting on trees
20F05 Generators, relations, and presentations of groups
20F65 Geometric group theory
68Q70 Algebraic theory of languages and automata
37F10 Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets
Software:
AutomGrp; GAP
PDF BibTeX XML Cite