Finitely generated subgroups of free groups as formal languages and their cogrowth (Q6566726)

Let \(F_{m}\) be the free group of rank \(m \geq 2\) and let \(H\) be a subgroup of \(F_{m}\). The cogrowth series of \(H\) is\N\[\NH(z)=\sum_{w \in H} z^{|w|}=\sum_{n=0}^{\infty} \big |H_{n} \big |z^{n},\N\]\Na rational function, where \(|w|\) denotes the length of \(w \in H\) and \(H_{n}\) denotes the set of the reduced elements of length \(n\) in \(H\) with respect to a fixed basis of \(F_{m}\) (see the paper of the second author [Adv. Probab. relat. Top. 6, 285--325 (1980; Zbl 0475.60007)]). If \(H\) is finitely generated, then the fact that \(H(z)\) is rational was proven in [loc. cit.] using Nielsen system of generators for \(H\). An alternative approach to proving the rationality of \(H(z)\) is via the theory of formal languages. The classical hierarchy of languages of N. Chomsky begins with the class of regular languages, that is, languages recognizable by finite-automata acceptors. \textit{N. Chomsky} and \textit{M. P. Schützenberger} were aware that the rationality of a language \(L \subset \Sigma^{\ast}\) (where \(\Sigma\) is finite alphabet and \(\Sigma^{\ast}\) denotes the set of finite words over \(\Sigma\)) implies rationality of the growth series \(L(z)=\sum_{n=0}^{\infty} \big |B_{n}(L) \big|z^{n}\), where \(B_{n}(L)\) is the set of words in \(L\) of length \(n\) [Kibern. Sb., Nov. Ser. 3, 195--242 (1966; Zbl 0166.26504)].\N \NFor a fixed free basis \(A\) of \(F_{m}\), let \(L_{H}\) be the set of all reduced finite words in \((A \cup A^{-1})^{\ast}\) that represent an element of \(H\). The fact that regularity of the language \(L_{H}\) is equivalent to the finite generation of \(H\) was observed by \textit{A. W. Anissimov} and \textit{F. D. Seifert} [Elektron. Inform.-verarb. Kybernetik 11, 695--702 (1975; Zbl 0322.68047)]. Since the intersection of two regular languages is regular, a direct consequence of the theorem of Anissimov and Seifert is that the intersection of two finitely generated subgroups of \(F_{m}\) is again finitely generated. The last observation is in fact a well-known theorem of \textit{A. G. Howson} [J. Lond. Math. Soc. 29, 428--434 (1954; Zbl 0056.02106)].\N\NIn the paper under review, using the (extended) core of the Schreier graph of \(H\), the authors construct the minimal deterministic finite automaton that recognizes \(L_{H}\). Then they characterize finitely generated subgroups \(H \leq F_{m}\) for which \(L_{H}\) is irreducible and for each such \(H\) they explicitly construct an ergodic automaton that recognizes \(L_{H}\). Such a construction provides an efficient way to compute the cogrowth series \(L_{H}(z)\) as well as the entropy of \(L_{H}\). The last part of the paper contains several very instructive examples that illustrate the method devised by the authors.