Asymptotic Aspects and Automata in Group Theory

The research project is about exploring several topics in the Mathematical field of geometric group theory. In the spirit of modern research in geometric group theory, mainly influenced by the work of Gromov from the 1980`s and on, one of our purposes is to explore the possible connections between these topics, as such connections have recently led to some very interesting results. An interesting class of groups in which graphs appear in an algebraic context is that of automaton groups. These groups are generated by automata and act by automorphisms on rooted trees. They were introduced in the early 1980`s when Grigorchuk constructed the first example of a group of intermediate growth (a problem posed by Milnor). It was discovered that very simple automata may generate groups with exotic properties that are hard to be found in classically-defined groups. Nekrashevych highlighted a very surprising connection between such groups and complex dynamics, consequently solving difficult dynamics problems by algebraic methods. We plan to find conditions under which an automaton group is finitely presented and to characterize some geometrical properties of the corresponding Schreier graphs (in terms of growth, number of ends, isomorphism problem). By interpreting the Schreier graphs in terms of complete automata, we want to study the class of languages recognized by them. When given a presentation of a group, one can associate with it a graph (the Cayley graph) and study geometric, algorithmic and dynamical aspects of the group through this graph. The asymptotic isoperimetric functions on Cayley graphs refer to the asymptotic behavior of the ratio between the boundaries or diameters of subgraphs and their volumes. We want to explore one of these less studied asymptotic functions, mean Dehn function, through random walks. Another asymptotic function, Cheeger constant, which has applications in computer networking, is defined on graphs analogously to its definition on Riemannian manifolds. However, the definition refers to presentations of groups and our aim is to define and compute it on groups. We also want to explore what types of languages and automata have good algorithmic properties and are suited for extending the class of graph automatic groups.

The problems addressed in the present project have their origin in geometric group theory. The goal was a better description of the interaction between algebraic properties of structures such as groups and semigroups (typically generated by finite automata) and their combinatorial description using graphs (typically Schreier graphs or orbital graphs) in relation to the properties of the language generated by such automata. In particular, it has focused its attention on research topics that can be attacked from algebraic, combinatorial and probabilistic point of views and involved members coming from various backgrounds. All project members collaborated in the main research of the project, i.e. the study of the synchronization (with high probability) of circular automata in the context of the Cerny conjecture. In 1964 Cerny conjectured an explicit bound on the shortest length of a synchronizing word in a synchronizing automaton (i.e., an automaton that admits reset words), in relation to the number of states of the automaton itself. This conjecture is still open in its most general form and in recent years, faced with the evident difficulty of a definite answer to the Cerny conjecture, attempts have been made to tackle this problem from a probabilistic point of view. Two possible questions come to mind: 1. Given a random automaton, is it synchronizing with high probability? 2. Within the class of synchronizing automata, is the Cerny conjecture valid with high probability? The main result of the present project gives a partial answer to these questions within the class of circular automata. More precisely, we proved that circular automata are synchronizing with high probability. The problem of providing a more accurate estimate of the synchronization speed of automata can be further studied. The result obtained highlights the possibility to translate this problem into a graph coloring problem and thus opens the door to further developments. Alongside this central theme, interesting results have been obtained in other closely related areas: in the theory of Schreier and orbital graphs of automata groups and semigroups and related decision problems, in the context of applications of Markov chains to the study of practical problems of determination of broken machines in industrial production, in the study of timed automata, and in the study of gain graphs. The project was actively developed by the research unit composed by Dr. D. D'Angeli, Dr. A. Rosenmann, Dr. A. Gutierrez-Sanchez and saw the participation of researchers, among the leading international experts in the disciplines studied. The research themes were intensively discussed during a workshop, that was organized within the project in February 2019, which saw the participation of important international researchers. Project members had the opportunity to disseminate their results through communications and presentations at numerous institutes.