The conjugacy problem for groups, and Higman embeddings

Authors:
A. Yu. Ol'shanskii and M. V. Sapir

Journal:
Electron. Res. Announc. Amer. Math. Soc. **9** (2003), 40-50

MSC (2000):
Primary 20F10; Secondary 03D40, 20M05

DOI:
https://doi.org/10.1090/S1079-6762-03-00110-0

Published electronically:
June 24, 2003

MathSciNet review:
1988871

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For every finitely generated recursively presented group we construct a finitely presented group containing such that is (Frattini) embedded into and the group has solvable conjugacy problem if and only if has solvable conjugacy problem. Moreover, and have the same r.e. Turing degrees of the conjugacy problem. This solves a problem by D. Collins.

**[BORS]**J. C. Birget, A. Yu. Ol'shanskii, E. Rips, M. V. Sapir.

Isoperimetric functions of groups and computational complexity of the word problem. Annals of Mathematics, 156, 2 (2002), 467-518.**[Cla]**C. R. J. Clapham,*An embedding theorem for finitely generated groups*, Proc. London Math. Soc. (3)**17**(1967), 419–430. MR**0222147**, https://doi.org/10.1112/plms/s3-17.3.419**[Col]**Donald J. Collins,*Conjugacy and the Higman embedding theorem*, Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), Stud. Logic Foundations Math., vol. 95, North-Holland, Amsterdam-New York, 1980, pp. 81–85. MR**579940****[CM]**Donald J. Collins and Charles F. Miller III,*The conjugacy problem and subgroups of finite index*, Proc. London Math. Soc. (3)**34**(1977), no. 3, 535–556. MR**0435227**, https://doi.org/10.1112/plms/s3-34.3.535**[GK]**A. V. Gorjaga and A. S. Kirkinskiĭ,*The decidability of the conjugacy problem cannot be transferred to finite extensions of groups*, Algebra i Logika**14**(1975), no. 4, 393–406 (Russian). MR**0414718****[Hi]**G. Higman,*Subgroups of finitely presented groups*, Proc. Roy. Soc. Ser. A**262**(1961), 455–475. MR**0130286****[KT]***Kourovka Notebook*. Unsolved Problems in Group Theory. 5th edition, Novosibirsk, 1976.**[Mak]**G. S. Makanin,*Equations in a free group*, Izv. Akad. Nauk SSSR Ser. Mat.**46**(1982), no. 6, 1199–1273, 1344 (Russian). MR**682490****[Ma]**Ju. I. Manin,*\cyr Vychislimoe i nevychislimoe*, “Sovet. Radio”, Moscow, 1980 (Russian). \cyr Kibernetika. [Cybernetics]. MR**611681****[Mil]**Charles F. Miller III,*On group-theoretic decision problems and their classification*, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. Annals of Mathematics Studies, No. 68. MR**0310044****[Ol2]**A. Yu. Ol′shanskiĭ,*On the distortion of subgroups of finitely presented groups*, Mat. Sb.**188**(1997), no. 11, 51–98 (Russian, with Russian summary); English transl., Sb. Math.**188**(1997), no. 11, 1617–1664. MR**1601512**, https://doi.org/10.1070/SM1997v188n11ABEH000276**[OlSa01]**Alexander Yu. Ol′shanskii and Mark V. Sapir,*Length and area functions on groups and quasi-isometric Higman embeddings*, Internat. J. Algebra Comput.**11**(2001), no. 2, 137–170. MR**1829048**, https://doi.org/10.1142/S0218196701000401**[OlSa02]**A. Yu. Olshanskii, M. V. Sapir. The Conjugacy Problem and Higman Embeddings. Preprint arXiv:math.GR/0212227.**[Rot]**Joseph J. Rotman,*An introduction to the theory of groups*, 3rd ed., Allyn and Bacon, Inc., Boston, MA, 1984. MR**745804****[SBR]**M. V. Sapir, J. C. Birget, E. Rips.

Isoperimetric and isodiametric functions of groups, Annals of Mathematics, 157, 2 (2002), 345-466.**[Va]**M. K. Valiev,*On polynomial reducibility of the word problem under embedding of recursively presented groups in finitely presented groups*, Mathematical foundations of computer science 1975 (Fourth Sympos., Mariánské Lázně, 1975) Springer, Berlin, 1975, pp. 432–438. Lecture Notes in Comput. Sci., Vol. 32. MR**0412287**

Retrieve articles in *Electronic Research Announcements of the American Mathematical Society*
with MSC (2000):
20F10,
03D40,
20M05

Retrieve articles in all journals with MSC (2000): 20F10, 03D40, 20M05

Additional Information

**A. Yu. Ol'shanskii**

Affiliation:
Mathematics Department, Vanderbilt University, Nashville, Tennessee 37240, and Mechanics-Mathematics Department, Chair of Higher Algebra, Moscow State University, Moscow, Russia

Email:
alexander.olshanskiy@vanderbilt.edu \quad olshan@shabol.math.msu.su

**M. V. Sapir**

Affiliation:
Mathematics Department, Vanderbilt University, Nashville, Tennessee 37240

Email:
msapir@math.vanderbilt.edu

DOI:
https://doi.org/10.1090/S1079-6762-03-00110-0

Received by editor(s):
March 2, 2003

Published electronically:
June 24, 2003

Additional Notes:
Both authors were supported in part by the NSF grant DMS 0072307. In addition, the research of the first author was supported in part by the Russian Fund for Basic Research 02-01-00170 and by the INTAS grant 99-1224; the research of the second author was supported in part by the NSF grant DMS 9978802 and the US-Israeli BSF grant 1999298.

Communicated by:
Efim Zelmanov

Article copyright:
© Copyright 2003
American Mathematical Society