Formal language theory and the geometry of 3-manifolds (Q1354823)

As explained by the authors, ``in the last several years there has been a remarkable interplay between topology, geometry, group theory, and the theory of formal languages. Thurston's work on the classification problem has shown that the topology of 3-dimensional manifolds is inextricably linked with the study of rigid geometries; in a series of essays Gromov introduced powerful geometric techniques into combinatorial group theory; and the work of Epstein et al., and earlier that of Muller and Schupp showed that the geometry of the Cayley graph of a group is intimately connected with the properties of associated formal languages. In this article we focus on a point of intersection of these three bodies of knowledge: normal forms for 3-manifold groups. We shall give upper and lower bounds on the logical complexity of the languages associated to geometrically efficient normal forms for elements in the fundamental group of any compact 3-manifold that satisfies Thurston's geometrization conjecture.'' The formal languages arise as combings of the fundamental groups of 3-manifolds. A choice of generators for a finitely generated group \(G\) may be regarded as a surjective monoid homomorphism \(\mu\colon\Sigma^*\to G\) where \(\Sigma^*\) is the free monoid on the finite alphabet \(\Sigma\). The words in \(\Sigma^*\) are thought of as paths beginning at the identity in the Cayley graph of \(G\) (with respect to the generating set \(\Sigma\)). A combing for \(G\) is just a selection of one such path from the identity to \(g\) for each \(g\in G\). Ideally one would like to construct combings which have a simple description as a formal language (i.e. a subset of \(\Sigma^*\)) and are efficient in the sense that routes to nearby points are uniformly close. The latter property can be made precise in various ways. The combing is said to have the fellow-traveler property if there is a uniform \(k\) such that travelers starting from the identity and moving at unit speed along the paths to any two elements which are adjacent vertices in the Cayley graph stay within a distance \(k\). Weaker is the asynchronous fellow-traveler property, in which the paths may be reparameterized to achieve the fellow-traveler condition. The relevant formal languages are, in decreasing order of restrictiveness, regular, context-free, and indexed. These properties refer to the flexibility of the rules by which one is allowed to generate the words of the language. A group is automatic (respectively, asynchronously automatic) if it admits a combing which satisfies the fellow-traveler property (respectively, the asynchronous fellow-traveler property) and forms a regular language. By work of \textit{D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy}, \textit{M. S. Paterson} and \textit{W. P. Thurston} [Word processing in groups, Jones and Bartlett, Boston (1992; Zbl 0764.20017)], the fundamental group of a compact geometrizable 3-manifold \(M\) is automatic if and only if none of the factors in the prime decomposition of \(M\) is a closed manifold modelled on one of the geometries \(Nil\) or \(Sol\), while the fundamental group of a closed \(Nil\) manifold is not even asynchronously automatic. The latter holds also for \(Sol\) manifolds, by \textit{N. Brady} [The geometry of asynchronous automatic structures (Ph. D. Thesis, UC Berkeley 1993)]. On the other hand, if one does not restrict the language, then the fundamental group of every compact geometrizable 3-manifold admits a combing that satisfies the asynchronous fellow-traveler property [\textit{M. Bridson}, Geom. Funct. Anal. 3, No. 3, 263-278 (1993; Zbl 0783.20020)]. Therefore the question is to determine just how restrictive a language can still provide an efficient combing for the fundamental groups of geometrizable 3-manifolds. The main theorems of the paper provide a sharp answer to this question. The authors prove that given any generating set \(\mu\colon\Sigma^*\to\pi_1(M)\), where \(M\) is a compact 3-manifold satisfying Thurston's geometrization conjecture, there exists a combing \(L\subseteq\Sigma^*\) which satisfies the asynchronous fellow-traveler property and is an indexed language. On the other hand, if \(M\) is a closed 3-manifold modelled on the geometry \(Nil\) and \(L\) is a combing of \(\pi_1(M)\) that satisfies the asynchronous fellow-traveler property, then \(L\) is not context-free.