Magnus embedding and algorithmic properties of groups 𝐹/𝑁^{(𝑑)}

Gul, Funda; Sohrabi, Mahmood; Ushakov, Alexander

doi:10.1090/tran/6880

Magnus embedding and algorithmic properties of groups $F/N^{(d)}$
HTML articles powered by AMS MathViewer

by Funda Gul, Mahmood Sohrabi and Alexander Ushakov PDF

Trans. Amer. Math. Soc. 369 (2017), 6189-6206 Request permission

Abstract:

In this paper we further study properties of Magnus embedding, give a precise reducibility diagram for Dehn problems in groups of the form $F/N^{(d)}$, and provide a detailed answer to Problem 12.98 in The Kourovka notebook. We also show that most of the reductions are polynomial time reductions and can be used in practical computation.

References

M. I. Anokhin, On the word problem and the conjugacy problem for groups of the form $F/V(R)$, Mat. Zametki 61 (1997), no. 1, 3–9 (Russian, with Russian summary); English transl., Math. Notes 61 (1997), no. 1-2, 3–8. MR 1620057, DOI 10.1007/BF02355001
Maurice Auslander and R. C. Lyndon, Commutator subgroups of free groups, Amer. J. Math. 77 (1955), 929–931. MR 75204, DOI 10.2307/2372606
Christophe Champetier and Vincent Guirardel, Limit groups as limits of free groups, Israel J. Math. 146 (2005), 1–75. MR 2151593, DOI 10.1007/BF02773526
L. Frenkel, A. Nikolaev, and A. Ushakov, Knapsack problems in products of groups, preprint, arXiv:1408.6509, 2014.
C. K. Gupta, On the conjugacy problem for $F/R^{\prime }$, Proc. Amer. Math. Soc. 85 (1982), no. 2, 149–153. MR 652430, DOI 10.1090/S0002-9939-1982-0652430-X
Ilya Kapovich and Alexei Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra 248 (2002), no. 2, 608–668. MR 1882114, DOI 10.1006/jabr.2001.9033
Igor Lysenok and Alexander Ushakov, Spherical quadratic equations in free metabelian groups, Proc. Amer. Math. Soc. 144 (2016), no. 4, 1383–1390. MR 3451217, DOI 10.1090/proc/12662
Wilhelm Magnus, On a theorem of Marshall Hall, Ann. of Math. (2) 40 (1939), 764–768. MR 262, DOI 10.2307/1968892
Jane Matthews, The conjugacy problem in wreath products and free metabelian groups, Trans. Amer. Math. Soc. 121 (1966), 329–339. MR 193130, DOI 10.1090/S0002-9947-1966-0193130-8
V. D. Mazurov and E. I. Khukhro (eds.), Unsolved problems in group theory. The Kourovka notebook, Thirteenth augmented edition, Russian Academy of Sciences Siberian Division, Institute of Mathematics, Novosibirsk, 1995. MR 1392713
Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov, Knapsack problems in groups, Math. Comp. 84 (2015), no. 292, 987–1016. MR 3290972, DOI 10.1090/S0025-5718-2014-02880-9
A. Myasnikov, V. Roman’kov, A. Ushakov, and A. Vershik, The word and geodesic problems in free solvable groups, Trans. Amer. Math. Soc. 362 (2010), no. 9, 4655–4682. MR 2645045, DOI 10.1090/s0002-9947-10-04959-7
Charles F. Miller III, On group-theoretic decision problems and their classification, Annals of Mathematics Studies, No. 68, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. MR 0310044
Ashish V. Naik, Kenneth W. Regan, and D. Sivakumar, On quasilinear-time complexity theory, Theoret. Comput. Sci. 148 (1995), no. 2, 325–349. STACS ’94 (Caen, 1994). MR 1355592, DOI 10.1016/0304-3975(95)00031-Q
A. Yu. Olshanskii and M. V. Sapir, Length functions on subgroups in finitely presented groups, Groups—Korea ’98 (Pusan), de Gruyter, Berlin, 2000, pp. 297–304. MR 1751101
V. N. Remeslennikov and V. G. Sokolov, Certain properties of the Magnus imbedding, Algebra i Logika 9 (1970), 566–578 (Russian). MR 0292920
V. A. Roman′kov, Equations in free metabelian groups, Sibirsk. Mat. Zh. 20 (1979), no. 3, 671–673, 694 (Russian). MR 537377
John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
Alexander Ushakov, Algorithmic theory of free solvable groups: randomized computations, J. Algebra 407 (2014), 178–200. MR 3197157, DOI 10.1016/j.jalgebra.2014.02.014
Svetla Vassileva, Polynomial time conjugacy in wreath products and free solvable groups, Groups Complex. Cryptol. 3 (2011), no. 1, 105–120. MR 2806083, DOI 10.1515/GCC.2011.005
Svetla Vassileva, The Magnus embedding is a quasi-isometry, Internat. J. Algebra Comput. 22 (2012), no. 8, 1240005, 7. MR 3010819, DOI 10.1142/S021819671240005X