The triviality problem for profinite completions (Q894233)

The basic decision problems for finitely presented groups, beginning with classical Dehn's core word, conjugacy and isomorphism problems, provided a guiding theme for combinatorial and geometric group theory throughout the twentieth century. Main results in this area were obtained in the classical papers by Novikov, Adyan, Boone, Rabin, B. Neumann, G. Baumslag and some other mathematicians. Most questions about general finitely presented groups were proved to be algorithmically unsolvable. Later in the 1990s, the study of decision problems shifted towards more refined questions concerning the existence of algorithms within specific classes of groups (solvable, hyperbolic and so on). One could think that this theme with general finitely presented groups was over. It turns out that certain basic decision problems about general finitely presented groups are not covered by the techniques developed in mid-century and did not succumb to the geometric techniques in the 1990s. In this brilliant and important paper, the authors prove probably the most obvious of not covered in good, old fascioned techniques problems: can one decide whether or not a group has a proper subgroup of finite index? They settle this question by the following result. Theorem A. There is no algorithm that can determine whether or not a finitely presented group has a proper subgroup of finite index. In fact, it is proved that there is a recursive sequence of finitely presented groups \(G_n\) with the property that the set of positive integers \(\{n \in \mathbb{N} \mid \exists H \leq G_n, H \not= G_n, |G_n:H| < \infty \}\) is recursively enumerable but not recursive. Moreover, the authors strengthen Theorem A by proving that the existence of finite index subgroups remains undecidable in classes of groups where other basic decision problems are decidable, such as biautomatic groups and fundamental groups of compact, non-positively curved square complexes. The last refinement can be rephrased in the following form: there is no algorithm that can determine if a compact square complex of non-positive curvative has a non-trivial, connected, finite-sheeted covering. Theorem A has other natural reformulations, each with its own specific emphasis. One could rephrase this theorem as a soution of the ``triviality problem'' for profinite completions of finitely presented groups. It means, that there is no algorithm that, given, a finitely presented group \(G\), can decide whether the profinite completion \(\hat{G}\) is trivial. The authors attack the triviality problem, deducing Theorem A from the known Slobodskoi's construction of a finitely presented group \(G\) in which there is no algorithm to determine which words in the generators represent such elements that have a trivial image in every finite quotient of \(G.\) The key technical result in this paper concerning the deducing mentioned above is the following encoding theorem. Theorem C. There is an algorithm that takes as input a finite presentation \(\langle A | R \rangle\) for a group \(G\) and a word \(w\in F(A)\) and outputs a presentation for a finitely presented group \(G_w\) such that \(\hat{G}_w \simeq 1\) if and only if \(w = 1\) in \(G.\) It follows from Theorems A and C that various other properties of finitely presented groups are undecidable. It should be noted that these properties, beginning with the property \(\hat{G} = 1\) itself, are neither Markov nor co-Markov, so their undecidability cannot be established using the Adyan-Rabin method. Theorem A allows one to establish various new undecidable phenomena for hyperbolic groups. Namely, for hyperbolic groups, there cannot exists algorithms to determine largeness, the existence of a linear representation with infinite image (over any infinite field), or the rank of the profinite completion. The authors finish with the following conjecture. Conjecture 9.5. There is no algorithm that can determine whether or not a given hyperbolic group \(\Gamma \) has \(\hat{\Gamma} \simeq 1.\) Note, that \textit{I. Kapovich} and \textit{D. T. Wise} [J. Algebra 223, No. 2, 562--583, (2000; Zbl 0951.20029)] proved that every non-trivial (torsion-free) hyperbolic group \(\Gamma \) has \(\hat{\Gamma }\simeq 1\) if and only if every (torsion-free) hyperbolic group is residually finite. The authors prove that the existence of an algorithm that, given a finite presentation of a hyperbolic group, will determine whether or not the profinite completion of that group is trivial is equivalent to the well-known conjecture that every non-trivial hyperbolic group has a proper subgroup of finite index. Moreover, the last statement is true even in the torsion-free case.