2018/10/01 by Jérémie Brieussel, Brieussel, Jérémie, Thibault Godin +3
Computer Science · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Formal Languages and Automata Theory (cs.FL) #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1810.00544
openalex publication_date 2018/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The growth of a finitely generated group is an important geometric invariant which has been studied for decades. It can be either polynomial, for a well-understood class of groups, or exponential, for most groups studied by geometers, or intermediate, that is between polynomial and exponential. Despite recent spectacular progresses, the class of groups with intermediate growth remains largely mysterious. Many examples of such groups are constructed using Mealy automata. The aim of this paper is to give an algorithmic procedure to study the growth of such automata groups, and more precisely to provide numerical upper bounds on their exponents. Our functions retrieve known optimal bounds on the famous first Grigorchuk group. They also improve known upper bounds on other automata groups and permitted us to discover several new examples of automata groups of intermediate growth. All the algorithms described are implemented in GAP, a language dedicated to computational group theory.