×

Finding non-trivial elements and splittings in groups. (English) Zbl 1244.20034

The article deals with the recursive (un)solvability of various problems for finitely presented groups, that is the (non-)existence of algorithms performing specific constructions. The motivating question is that of the existence of a partial algorithm which, on input of a finite presentation of a non-trivial group \(G\), outputs a word in the generators non-trivial in \(G\).
A weak form of the motivating question is negatively answered in Theorem 4.2: \(k>0\) being fixed, there is no such algorithm yielding a word of length \(\leq k\). Similarly, it is proved in Theorem 5.5 that there is no algorithm which, on input of a finite presentation of a group which is the free product of two non-trivial finitely presentable subgroups, outputs finite presentations for the factors; and in Theorem 6.6 that there is no algorithm which, on input of finite presentations of two non-trivial groups \(G\) and \(H\), outputs a partial map from the generators of \(G\) to \(H\) which extends to a group embedding.
The key step to all results is a recursion-theoretic elaboration on a construction for the Adian-Rabin Theorem by C. McA. Gordon, [Lond. Math. Soc. Lect. Note Ser. 204, 105-110 (1995; Zbl 0843.20027)].

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F05 Generators, relations, and presentations of groups
03D80 Applications of computability and recursion theory
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations

Citations:

Zbl 0843.20027
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adian, S. I., Finitely presented groups and algorithms, Dokl. Akad. Nauk SSSR, 117, 9-12 (1957)
[2] Boone, W. W., The word problem, Ann. of Math., 70, 207-265 (1959) · Zbl 0102.00902
[3] Boone, W. W.; Haken, W.; Poenaru, V., On Recursively Unsolvable Problems in Topology and Their Classification, Contributions to Mathematical Logic (1968), North-Holland Publishing: North-Holland Publishing Amsterdam · Zbl 0246.57015
[4] Boone, W. W.; Rogers, H., On a problem of J.H.C. Whitehead and a problem of Alonzo Church, Math. Scand., 19, 185-192 (1966) · Zbl 0166.26503
[5] Gordon, C., Some embedding theorems and undecidability questions for groups, (Combinatorial and Geometric Group Theory. Combinatorial and Geometric Group Theory, Edinburgh, 1993. Combinatorial and Geometric Group Theory. Combinatorial and Geometric Group Theory, Edinburgh, 1993, London Math. Soc. Lecture Note Ser., vol. 204 (1995), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 105-110 · Zbl 0843.20027
[6] Hatcher, A., Algebraic Topology (2002), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 1044.55001
[7] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory (2004), Dover
[8] Markov, A. A., The insolubility of the problem of homeomorphy, Dokl. Akad. Nauk SSSR, 121, 218-220 (1958), (in Russian) · Zbl 0092.00702
[9] (Mazurov, V. D.; Khukhro, E. I., The Kourovka Notebook (2006), Russian Acad. Sci. Siber. Div., Inst. Math.: Russian Acad. Sci. Siber. Div., Inst. Math. Novosibirsk) · Zbl 1084.20001
[10] Miller, C. F., Decision problems for groups-survey and reflections, (Algorithms and Classification in Combinatorial Group Theory. Algorithms and Classification in Combinatorial Group Theory, Berkeley, CA, 1989. Algorithms and Classification in Combinatorial Group Theory. Algorithms and Classification in Combinatorial Group Theory, Berkeley, CA, 1989, Math. Sci. Res. Inst. Publ., vol. 23 (1992), Springer: Springer New York), 1-59 · Zbl 0752.20014
[11] Post, E. L., Recursive unsolvability of a problem of Thue, J. Symbolic Logic, 12, 1-11 (1947) · Zbl 1263.03030
[12] Rabin, M. O., Recursive unsolvability of group theoretic problems, Ann. of Math., 67, 172-194 (1958) · Zbl 0079.24802
[13] Rogers, H., Theory of Recursive Functions and Effective Computability (1987), MIT Press · Zbl 0183.01401
[14] Rotman, J., An Introduction to the Theory of Groups (1995), Springer: Springer New York · Zbl 0810.20001
[15] Scott, P.; Wall, T., Topological methods in group theory, (Homological Group Theory, Proc. Sympos.. Homological Group Theory, Proc. Sympos., Durham, 1977. Homological Group Theory, Proc. Sympos.. Homological Group Theory, Proc. Sympos., Durham, 1977, London Math. Soc. Lecture Note Ser., vol. 36 (1979), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, New York), 137-203
[16] Seifert, H.; Threlfall, W., A Textbook of Topology (1980), Academic Press Inc.: Academic Press Inc. London, (translated from the 1934 German original Lehrbuch der Topologie) · Zbl 0469.55001
[17] Stallings, J. R., Group theory and three-dimensional manifolds, (Yale Math., vol. 4 (1971), Yale University Press: Yale University Press New Haven) · Zbl 0717.20026
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.