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), 4050
MSC (2000):
Primary 20F10; Secondary 03D40, 20M05
Published electronically:
June 24, 2003
MathSciNet review:
1988871
Fulltext 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), 467518.
 [Cla]
C.
R. J. Clapham, An embedding theorem for finitely generated
groups, Proc. London Math. Soc. (3) 17 (1967),
419–430. MR 0222147
(36 #5199)
 [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, NorthHolland, AmsterdamNew York,
1980, pp. 81–85. MR 579940
(81m:20051)
 [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
(55 #8187)
 [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
(54 #2813)
 [Hi]
G.
Higman, Subgroups of finitely presented groups, Proc. Roy.
Soc. Ser. A 262 (1961), 455–475. MR 0130286
(24 #A152)
 [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 (84m:20040)
 [Ma]
Ju.
I. Manin, Vychislimoe i nevychislimoe, “Sovet.
Radio”, Moscow, 1980 (Russian). Kibernetika. [Cybernetics]. MR 611681
(82i:03002)
 [Mil]
Charles
F. Miller III, On grouptheoretic 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 (46 #9147)
 [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
(99a:20038), http://dx.doi.org/10.1070/SM1997v188n11ABEH000276
 [OlSa01]
Alexander
Yu. Ol′shanskii and Mark
V. Sapir, Length and area functions on groups and quasiisometric
Higman embeddings, Internat. J. Algebra Comput. 11
(2001), no. 2, 137–170. MR 1829048
(2002b:20058), http://dx.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
(85f:20001)
 [SBR]
M. V. Sapir, J. C. Birget, E. Rips.
Isoperimetric and isodiametric functions of groups, Annals of Mathematics, 157, 2 (2002), 345466.
 [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 (54 #413)
 [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), 467518.
 [Cla]
 C. R. J. Clapham.
An embedding theorem for finitely generated groups, Proc. London. Math. Soc. (3), 17 (1967), 419430. MR 36:5199
 [Col]
 Donald J. Collins.
Conjugacy and the Higman embedding theorem. Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), pp. 8185, Stud. Logic Foundations Math., 95, NorthHolland, AmsterdamNew York, 1980. MR 81m:20051
 [CM]
 D. J. Collins, C. F. Miller III.
The conjugacy problem and subgroups of finite index. Proc. London Math. Soc. (3) 34 (1977), no. 3, 535556. MR 55:8187
 [GK]
 A. V. Gorjaga, A. S. Kirkinski. The decidability of the conjugacy problem cannot be transferred to finite extensions of groups. Algebra i Logika 14 (1975), no. 4, 393406. (Russian) MR 54:2813
 [Hi]
 G. Higman. Subgroups of finitely presented groups. Proc. Roy. Soc. Ser. A, 262 (1961), 455475. MR 24:A152
 [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, 11991273, 1344; English transl., Math. USSRIzv. 21 (1983), 546582. MR 84m:20040
 [Ma]
 Yu. I. Manin. The computable and the noncomputable, ``Sovetskoe Radio", Moscow, 1980 MR 82i:03002
 [Mil]
 Charles F. Miller III.
On grouptheoretic decision problems and their classification. Annals of Mathematics Studies, No. 68. Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. MR 46:9147
 [Ol2]
 A. Yu. Ol'shanskii.
On distortion of subgroups in finitely presented groups. Mat. Sb. 188 (1997), no. 11, 5198; English transl., Sb. Math. 188 (1997), no. 11, 16171664. MR 99a:20038
 [OlSa01]
 A. Yu. Ol'shanskii, M. V. Sapir. Length and area functions on groups and quasiisometric Higman embeddings. Internat. J. Algebra Comput. 11 (2001), no. 2, 137170. MR 2002b:20058
 [OlSa02]
 A. Yu. Olshanskii, M. V. Sapir. The Conjugacy Problem and Higman Embeddings. Preprint arXiv:math.GR/0212227.
 [Rot]
 J. Rotman.
An Introduction to the Theory of Groups. Allyn & Bacon, third edition, 1984. MR 85f:20001
 [SBR]
 M. V. Sapir, J. C. Birget, E. Rips.
Isoperimetric and isodiametric functions of groups, Annals of Mathematics, 157, 2 (2002), 345466.
 [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ázne, 1975), pp. 432438. Lecture Notes in Comput. Sci., Vol. 32, Springer, Berlin, 1975. MR 54:413
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 MechanicsMathematics 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:
http://dx.doi.org/10.1090/S1079676203001100
PII:
S 10796762(03)001100
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 020100170 and by the INTAS grant 991224; the research of the second author was supported in part by the NSF grant DMS 9978802 and the USIsraeli BSF grant 1999298.
Communicated by:
Efim Zelmanov
Article copyright:
© Copyright 2003
American Mathematical Society
