BGSMATH: Stallings Automata and Applications

17/1/23 (2h): Introduction: Free groups. We will introduce free groups (from several points of view, algebraic, combinatorial, and categoric) and its first algebraic properties. We will present some natural questions and examples motivating the course.

19/1/23 (2h): Automata and languages. We will set up the connection between automata (i.e., graphs with certain decorations), languages, and (subgroups of) the free group. This includes several relevant (graph-theoretical) definitions together with the proof of a few technical lemmas crucial to establish this connection.

24/1/23 (2h): The Stallings bijection. This session is devoted to the central result in Stallings theory: there is a bijection between a certain kind of automata and the lattice of subgroups of the free group. We will stress the computability of this map when restricted to finitely generated subgroups (corresponding to finite graphs). As a corollary, we obtain the Nielsen-Schreier and the computabity of bases, among other results.

26/1/23 (2h): First applications. In this session we will consider the first natural applications of the Stallings bijection: the membership problem (including explicit rewriting in terms of the given generators) and the conjugacy problem for subgroups. We will stress some similarities and some (big) differences between the behaviour of the lattice of subgroups of the free group, the lattice of subspaces of a vector space.

31/1/23 (2h): Index and Marshall Hall Theorem. We will explain the relation between vertices of the automata and cosets of the subgroup. We will obtain a graphical characterization for finite index subgroups, and the Schreier index formula relating index and rank. As a corollary we obtain also a proof of Marshall Hall Theorem, and the residual finiteness of free groups.

2/2/23 (2h) Intersection of subgroups. We introduce the product of automata and see the relation with the intersection of subgroups. This will allow us to deduce the Howson property for free groups (intersections of finitely generated subgroups are always finitely generated), and the Hanna-Neumann inequality (removing the coefficient 2 has been a famous problem solved recently with the help of other techniques out of the scope of this course). On the way, we will be able to compute a basis for the intersection of two finitely generated subgroups. Almost at the same price, we will be able to compute intersections of cosets, and understand malnormality.

7/2/23 (2h) Algebraic extensions and quotients of automata. We define the notion of algebraic extension between subgroups of a free group and prove (a modern version of) Takahasi’s Theorem saying that finitely generated subgroups have finitely many algebraic extensions, and they are all computable. From this result, we will deduce several interesting algebraic applications. 

9/2/23 (2h): Counting automata and counting subgroups. We’ll introduce a recent technique developed to count (or asymptotically estimate) the amount of subgroups satisfying certain properties. This is done by counting automata, which can be seen via partial injections (they form an inverse monoid generalizing the classical symmetric group in an interesting way).

14/2/23 (1h): Sage. A brief introduction to the Stallings_graphs package for SageMath, a nice piece of software meant to experiment with finitely generated subgroups of (finite rank) free groups.

14/2/23 (1h): Enriched Stallings automata I. We will introduce and briefly describe a recent extension of Stallings automata: by decorating the automata with integral vectors in an appropriate way, we obtain a bijection (similar to the Stallings one) between a certain kind of enriched automata and the lattice of subgroups of $F_n \times Z^m$, the direct product of a free and a free abelian group. Of course, the algebraic questions related to the free abelian part usually become systems of equations, but the interplay between the two parts is interesting and sometimes highly non-trivial.

16/2/23 (2h): Enriched Stallings automata II: Despite the apparent similarity, the lattices of subgroups of $F_n$ and $F_n \times Z^m$ behave very differently, especially when we consider intersections. A big difference is that the second one does not satisfy the Howson property: it admits pairs of finitely generated subgroups whose intersection is not fnitely generated. By looking carefully at the pull-back of (enriched) Stallings automata, we’ll explain how to decide when the corresponding intersection is finitely generated and, if so, how to compute a set of generators for it. 

1. L. Bartholdi and P.V. Silva, “Rational subsets of groups”, Chapter 23 from J.E. Pin “Handbook on automata theory”, EMS Publishing House (2021), 1608 pages. Available at arXiv:1012.1532.
2. J. Delgado, E. Ventura, “Autòmats de Stallings, un camí d’anada i tornada” (in catalan). To appear at Butlletí de la Societat Catalana de Matemàtiques. Available at https://arxiv.org/pdf/2202.07642.pdf
3. J. Delgado and E.Ventura, “Stallings automata for free-times-abelian groups: intersections and index”. Publicacions Matemàtiques 66 (2022), 789–830.
4. J. Delgado, E. Ventura, “A list of applications of Stallings automata”, Transactions on Combinatorics 11(3) (2022), 181—235. Available at https://arxiv.org/pdf/2109.01268.pdf
5. I. Kapovich and A. Myasnikov. “Stallings foldings and subgroups of free groups”. Journal of Algebra 248.2 (Feb. 2002), pp. 608–668.
6. A. Miasnikov, E. Ventura, and P. Weil. “Algebraic extensions in free groups”. In: Geometric Group Theory. Ed. by G.N. Arzhantseva, J. Burillo, L. Bartholdi, and E.Ventura. Trends in Mathematics. Birkhäuser Basel, Jan. 2007, pp. 225–253.
7. J.R. Stallings. “Topology of finite graphs”. Inventiones Mathematicae 71 (Mar. 1983), pp. 551–565.
8. N.W.M. Touikan, “A fast algorithm for Stallings’ folding process”. International Journal of Algebra and Computation 16(06) (Dec. 2006), pp. 1031–1045.