On classification of groups generated by 3-state automata over a 2-letter alphabet

• Main Authors: Bondarenko, I., Grigorchuk, R., Kravchenko, R., Muntyan, Y., Nekrashevych, V., Savchuk, D., Sunic, Z.
• Format: Article
• Language: English
• Published: Інститут прикладної математики і механіки НАН України 2008
• Series: Algebra and Discrete Mathematics
• Online Access: http://dspace.nbuv.gov.ua/handle/123456789/152389

We show that the class of groups generated by 3-state automata over a 2-letter alphabet has no 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 hystogram 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 no 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±3), and a free product C2 ∗ C2 ∗ C2) to enticing (Basilica group and a few other iterated monodromy groups).