×

The triviality problem for profinite completions. (English) Zbl 1360.20020

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 I. Kapovich and 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.

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F67 Hyperbolic groups and nonpositively curved groups
57M07 Topological methods in group theory
20E18 Limits, profinite groups
20F65 Geometric group theory

Citations:

Zbl 0951.20029
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Adyan, S.I.: Algorithmic unsolvability of problems of recognition of certain properties of groups. Dokl. Akad. Nauk SSSR (N.S.) 103, 533-535 (1955) · Zbl 0065.00901
[2] Adyan, S.I.: Unsolvability of some algorithmic problems in the theory of groups. Trudy Moskov. Mat. Obšč. 6, 231-298 (1957) · Zbl 1223.20021
[3] Agol, I.: The virtual Haken conjecture. Doc. Math. 18, 1045-1087 (2013) (with an appendix by Ian Agol, Daniel Groves and Jason Manning) · Zbl 1286.57019
[4] Bajpai, J.: Omnipotence of surface groups. Masters Thesis, McGill University (2007) · Zbl 1040.20024
[5] Baumslag, G., Boone, W.W., Neumann, B.H.: Some unsolvable problems about elements and subgroups of groups. Math. Scand. 7, 191-201 (1959) · Zbl 0104.00704
[6] Belegradek, I., Osin, D.: Rips construction and Kazhdan property (T). Groups Geom. Dyn. 2(1), 1-12 (2008) · Zbl 1152.20039
[7] Bestvina, M.: Questions in geometric group theory. http://www.math.utah.edu/ bestvina/eprints/questions-updated · Zbl 1286.57013
[8] Bhattacharjee, M.: Constructing finitely presented infinite nearly simple groups. Commun. Algebra 22(11), 4561-4589 (1994) · Zbl 0834.20020 · doi:10.1080/00927879408825087
[9] Boone, W.W.: The word problem. Ann. Math. 2(70), 207-265 (1959) · Zbl 0102.00902 · doi:10.2307/1970103
[10] Bridson, M.R., Haefliger, A.: Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Berlin (1999) · Zbl 0988.53001
[11] Bridson, M.R., Wilton, H.: The isomorphism problem for profinite completions of finitely presented, residually finite groups. Groups Geom. Dyn. 8, 733-745 (2014) · Zbl 1309.20025
[12] Bridson, M.R., Wilton, H.: Undecidability and the developability of permutoids and rigid pseudogroups. arXiv:1405.4368 (2014) · Zbl 1471.20045
[13] Burger, M., Mozes, S.: Finitely presented simple groups and products of trees. C. R. Acad. Sci. Paris Sér. I Math. 324(7), 747-752 (1997) · Zbl 0966.20013 · doi:10.1016/S0764-4442(97)86938-8
[14] Button, J.O.: Largeness of LERF and 1-relator groups. Groups Geom. Dyn. 4(4), 709-738 (2010) · Zbl 1248.20033 · doi:10.4171/GGD/102
[15] Cameron, P.: Extending partial permutations. http://www.maths.qmul.ac.uk/ pjc/odds/partial (2004) · JFM 42.0508.03
[16] Corlette, K.: Archimedean superrigidity and hyperbolic geometry. Ann. Math. (2) 135(1), 165-182 (1992) · Zbl 0768.53025
[17] Dehn, M.: Über unendliche diskontinuierliche Gruppen. Math. Ann. 71(1), 116-144 (1911) · JFM 42.0508.03 · doi:10.1007/BF01456932
[18] Gersten, S.M., Short, H.B.: Small cancellation theory and automatic groups. Invent. Math. 102(2), 305-334 (1990) · Zbl 0714.20016 · doi:10.1007/BF01233430
[19] Gromov, M., Schoen, R.: Harmonic maps into singular spaces and \[p\] p-adic superrigidity for lattices in groups of rank one. Inst. Hautes Études Sci. Publ. Math. 76, 165-246 (1992) · Zbl 0896.58024
[20] Kan, D.M., Thurston, W.P.: Every connected space has the homology of a \[K(\pi,1)K\](π,1). Topology 15(3), 253-258 (1976) · Zbl 0355.55004 · doi:10.1016/0040-9383(76)90040-9
[21] Kapovich, M.: Representations of polygons of finite groups. Geom. Topol. 9:1915-1951 (2005) (electronic) · Zbl 1163.20029
[22] Kapovich, I., Wise, D.T.: The equivalence of some residual properties of word-hyperbolic groups. J. Algebra 223(2), 562-583 (2000) · Zbl 0951.20029 · doi:10.1006/jabr.1999.8104
[23] Kharlampovich, O.G.: The universal theory of the class of finite nilpotent groups is undecidable. Mat. Zametki 33(4), 499-516 (1983) · Zbl 0516.20018
[24] Kharlampovich, O., Myasnikov, A.: Decidability of the elementary theory of a torsion-free hyperbolic group. arXiv:1303.0760v4 (2013) · Zbl 1282.20021
[25] Leary, I.J.: A metric Kan-Thurston theorem. J. Topol. 6(1), 251-284 (2013) · Zbl 1343.20044 · doi:10.1112/jtopol/jts035
[26] Makanin, G.S.: Decidability of the universal and positive theories of a free group. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya 48(4), 735-749 (1984)
[27] Miller, C.F., III: Decision problems for groups-survey and reflections. In: Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), number 23, Math. Sci. Res. Inst. Publ., pp. 1-59. Springer, New York (1992) · Zbl 0752.20014
[28] Niblo, G.A., Reeves, L.D.: The geometry of cube complexes and the complexity of their fundamental groups. Topology 37(3), 621-633 (1998) · Zbl 0911.57002 · doi:10.1016/S0040-9383(97)00018-9
[29] Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. im. Steklov. no. 44. Izdat. Akad. Nauk SSSR, Moscow (1955)
[30] Osin, D.: Small cancellations over relatively hyperbolic groups and embedding theorems. Ann. Math. (2) 172(1), 1-39 (2010) · Zbl 1203.20031
[31] Papasoglu, P.: An algorithm detecting hyperbolicity. In: Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), volume 25 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 193-200. American Mathematical Society, Providence (1996) · Zbl 0857.20017
[32] Pride, S.J.: The concept of “largeness” in group theory. In: Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), volume 95 of Stud. Logic Foundations Math., pp. 299-335. North-Holland, Amsterdam (1980) · Zbl 1223.20021
[33] Rabin, M.O.: Recursive unsolvability of group theoretic problems. Ann. Math. 2(67), 172-194 (1958) · Zbl 0079.24802 · doi:10.2307/1969933
[34] Rips, E.: Subgroups of small cancellation groups. Bull. Lond. Math. Soc. 14(1), 45-47 (1982) · Zbl 0481.20020 · doi:10.1112/blms/14.1.45
[35] Sela, Z.: Diophantine geometry over groups. VII. The elementary theory of a hyperbolic group. Proc. Lond. Math. Soc. (3) 99(1), 217-273 (2009) · Zbl 1241.20049
[36] Slobodskoĭ, A.M.: Undecidability of the universal theory of finite groups. Algebra i Logika 20(2), 207-230 (1981) (251) · Zbl 0519.03006
[37] Stallings, J.R.: Topology of finite graphs. Invent. Math. 71(3), 551-565 (1983) · Zbl 0521.20013 · doi:10.1007/BF02095993
[38] Wilton, H.: Virtual retractions, conjugacy separability and omnipotence. J. Algebra 323, 323-335 (2010) · Zbl 1223.20021 · doi:10.1016/j.jalgebra.2009.10.009
[39] Wise, D.T.: Subgroup separability of graphs of free groups with cyclic edge groups. Q. J. Math. 51(1), 107-129 (2000) · Zbl 0991.05056 · doi:10.1093/qmathj/50.1.107
[40] Wise, D.T.: The residual finiteness of negatively curved polygons of finite groups. Invent. Math. 149(3), 579-617 (2002) · Zbl 1040.20024 · doi:10.1007/s002220200224
[41] Wise, D.T.: Cubulating small cancellation groups. Geom. Funct. Anal. 14(1), 150-214 (2004) · Zbl 1071.20038 · doi:10.1007/s00039-004-0454-y
[42] Wise, D.T.: Complete square complexes. Comment. Math. Helv. 82(4), 683-724 (2007) · Zbl 1142.20025 · doi:10.4171/CMH/107
[43] Wise, D.T.: The structure of groups with a quasi-convex hierarchy. http://www.math.mcgill.ca/wise/papers.html (2012, preprint) · Zbl 0079.24802
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.