Remote Access Electronic Research Announcements

Electronic Research Announcements

ISSN 1079-6762



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
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 ${\mathcal G}$ we construct a finitely presented group ${\mathcal H}$containing ${\mathcal G}$ such that ${\mathcal G}$ is (Frattini) embedded into ${\mathcal H}$ and the group ${\mathcal H}$ has solvable conjugacy problem if and only if ${\mathcal G}$ has solvable conjugacy problem. Moreover, ${\mathcal G}$ and ${\mathcal H}$ have the same r.e. Turing degrees of the conjugacy problem. This solves a problem by D. Collins.

References [Enhancements On Off] (What's this?)

  • [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
  • [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
  • [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, Vychislimoe i nevychislimoe, “Sovet. Radio”, Moscow, 1980 (Russian). 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, 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, 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

Similar Articles

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: \quad

M. V. Sapir
Affiliation: Mathematics Department, Vanderbilt University, Nashville, Tennessee 37240

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