×

The conjugacy problem and Higman embeddings. (English) Zbl 1055.20023

Mem. Am. Math. Soc. 804, 133 p. (2004).
From the authors’ introduction: In 1961, G. Higman [Proc. R. Soc. Lond., Ser. A 262, 455-475 (1961; Zbl 0104.02101)] published the celebrated theorem that a finitely generated group is recursively presented if and only if it is a subgroup of a finitely presented group. Along with the results of P. S. Novikov [Am. Math. Soc., Transl., II. Ser. 9, 1-122 (1958); translation from Tr. Mat. Inst. Steklova 44, 140 p. (1955; Zbl 0068.01301] and W. W. Boone [Nederl. Akad. Wet., Proc., Ser. A 57, 231-237 (1954; Zbl 0055.00602), ibid. 57, 492-497 (1954; Zbl 0057.01701), ibid. 58, 252-256, 571-577 (1955) and 60, 22-27, 227-232 (1957; Zbl 0067.25706)] this result showed that objects from logic (in that case, recursively enumerable sets) have group theoretic characterizations (see [Yu. I. Manin, The computable and non-computable. Kibernetika, Moskva: “Sovetskoe Radio” (1980; Zbl 0471.03003)] for the philosophy of Higman embeddings).
C. R. J. Clapham [Proc. Lond. Math. Soc., III. Ser. 17, 419-430 (1967; Zbl 0152.00204)] (see also corrections by M. K. Valiev [Lect. Notes Comput. Sci. 32, 432-438 (1975; Zbl 0323.02055)]) was probably the first to investigate properties preserved under Higman embeddings. In particular, he slightly modified the original Higman construction and showed that this embedding preserves solvability (and even the r.e. Turing degree) of the word problem. M. K. Valiev [loc. cit.] sketched a proof of a much stronger result: every finitely generated recursively presented group \(G\) embeds in a finitely presented group \(H\) such that the word problem in \(H\) polynomially reduces to the word problem in \(G\). In particular, if the word problem of a finitely generated group is in P (i.e. can be solved in polynomial time by a deterministic Turing machine) then it can be embedded into a finitely presented group whose word problem is also in P (a correction to Valiev’s paper was published in Mathematical Reviews, MR0412287 (54#413), see also R. C. Lyndon and P. E. Schupp [Combinatorial group theory (1977; Zbl 0368.20023)] and Yu. I. Manin [loc. cit.]). A simplified version of Valiev’s construction (but not a proof of the polynomial reducibility) was later published by S. O. Aanderaa and D. E. Cohen [in Word problems II, Stud. Logic Found. Math. Vol. 95, 17-28 (1980; Zbl 0441.20023)] (see also K. A. Kalorkoti [Proc. Lond. Math. Soc., III. Ser. 44, 312-332 (1982; Zbl 0485.20022)]). In [Ann. Math. (2) 156, No. 2, 467-518 (2002; Zbl 1026.20018)], J.-C. Birget, E. Rips and the authors of this paper obtained a group theoretic characterization of NP (non-deterministic polynomial time): a finitely generated group \(G\) has word problem in NP if and only if \(G\) is embedded into a finitely presented group with polynomial Dehn function.
The conjugacy problem turned out to be much harder to preserve under embeddings. D. J. Collins and C. F. Miller [Proc. Lond. Math. Soc., III. Ser. 34, 535-556 (1977; Zbl 0364.20043)] and A. V. Goryaga and A. S. Kirkinskij [Algebra Logika 14, 393-406 (1975; Zbl 0358.20046); translation in Algebra Logic 14, 240-248 (1976)] proved that even subgroups of index 2 of finitely presented groups do not inherit solvability or unsolvability of the conjugacy problem.
In 1976 D. J. Collins [Kourovka notebook. Unsolved problems in the theory of groups. (1978; Zbl 0401.20001)] posed the following question (Problem 5.22): Does there exist a version of the Higman embedding theorem in which the degree of unsolvability of the conjugacy problem is preserved?
It was quickly realized that the main problem would be in preserving the smallest Turing degree, that is the solvability of conjugacy problem. In 1980 [Word problems II, Stud. Logic Found. Math. Vol. 95, 81-85 (1980; Zbl 0431.20031)], D. J. Collins analyzed existing proofs of Higman’s theorem, and discovered that there are essential difficulties. If a finitely generated group \(C\) is embedded into a finitely presented group \(B\) using any existing at that time constructions then the solvability of conjugacy problem in \(B\) implies certain properties of \(C\) which are much stronger than solvability of conjugacy problem. Collins even wrote the following pessimistic comments: “There seems at present to be no hope to establishing the analogue of Clapham’s theorem.…Furthermore these difficulties seem to be more or less inevitable given the structure of the proof and probably a wholly new strategy will be needed to avoid them. For the present the most one can be hoped for is the isolation of conditions on \(C\) that are necessary and sufficient for the preservation of the solvability of the conjugacy problem in the Higman embedding.”
In this paper, we do find a “new strategy” and prove the following result. Recall [R. J. Thompson, Word problems II, Stud. Logic Found. Math. Vol. 95, 401-441 (1980; Zbl 0431.20030)] that a subgroup \(\mathcal G\) of a group \(\mathcal H\) is called ‘Frattini embedded’ if any two elements of \(\mathcal G\) that are conjugate in \(\mathcal H\) are also conjugate in \(\mathcal G\). Clearly if \(\mathcal G\) is Frattini embedded into \(\mathcal H\) and \(\mathcal H\) has solvable conjugacy problem then \(\mathcal G\) has solvable conjugacy problem (by results D. J. Collins and C. F. Miller and A. V. Goryaga and A. S. Kirkinskij cited above, non-Frattini embedded subgroups do not necessarily inherit solvability of the conjugacy problem).
Theorem 1.1. A finitely generated group has solvable conjugacy problem if and only if it is Frattini embedded into a finitely presented group with solvable conjugacy problem.
Moreover we prove the following stronger result solving the original problem of Collins:
Theorem 1.2. A finitely presented group \(\mathcal G\) with recursively enumerable set of relations has conjugacy problem of r.e. Turing degree \(\alpha\) if and only if \(\mathcal G\) can be Frattini embedded into a finitely presented group \(\mathcal H\) with conjugacy problem of r.e Turing degree \(\alpha\).

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E07 Subgroup theorems; subgroup growth
20F06 Cancellation theory of groups; application of van Kampen diagrams
20F05 Generators, relations, and presentations of groups
PDFBibTeX XMLCite
Full Text: DOI Link