Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Magnus embedding and algorithmic properties of groups $ F/N^{(d)}$


Authors: Funda Gul, Mahmood Sohrabi and Alexander Ushakov
Journal: Trans. Amer. Math. Soc. 369 (2017), 6189-6206
MSC (2010): Primary 20F19, 20F10, 20F65, 03D15
DOI: https://doi.org/10.1090/tran/6880
Published electronically: November 28, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1007/BF02355001
  • [2] Maurice Auslander and R. C. Lyndon, Commutator subgroups of free groups, Amer. J. Math. 77 (1955), 929-931. MR 0075204
  • [3] Christophe Champetier and Vincent Guirardel, Limit groups as limits of free groups, Israel J. Math. 146 (2005), 1-75. MR 2151593, https://doi.org/10.1007/BF02773526
  • [4] L. Frenkel, A. Nikolaev, and A. Ushakov, Knapsack problems in products of groups,
    preprint, arXiv:1408.6509, 2014.
  • [5] C. K. Gupta, On the conjugacy problem for $ F/R^{\prime } $, Proc. Amer. Math. Soc. 85 (1982), no. 2, 149-153. MR 652430, https://doi.org/10.2307/2044269
  • [6] Ilya Kapovich and Alexei Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra 248 (2002), no. 2, 608-668. MR 1882114, https://doi.org/10.1006/jabr.2001.9033
  • [7] Igor Lysenok and Alexander Ushakov, Spherical quadratic equations in free metabelian groups, Proc. Amer. Math. Soc. 144 (2016), no. 4, 1383-1390. MR 3451217, https://doi.org/10.1090/proc/12662
  • [8] Wilhelm Magnus, On a theorem of Marshall Hall, Ann. of Math. (2) 40 (1939), 764-768. MR 0000262
  • [9] Jane Matthews, The conjugacy problem in wreath products and free metabelian groups, Trans. Amer. Math. Soc. 121 (1966), 329-339. MR 0193130
  • [10] 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
  • [11] Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov, Knapsack problems in groups, Math. Comp. 84 (2015), no. 292, 987-1016. MR 3290972, https://doi.org/10.1090/S0025-5718-2014-02880-9
  • [12] 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, https://doi.org/10.1090/s0002-9947-10-04959-7
  • [13] 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
  • [14] 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, https://doi.org/10.1016/0304-3975(95)00031-Q
  • [15] 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
  • [16] V. N. Remeslennikov and V. G. Sokolov, Certain properties of the Magnus imbedding, Algebra i Logika 9 (1970), 566-578 (Russian). MR 0292920
  • [17] V. A. Romankov, Equations in free metabelian groups, Sibirsk. Mat. Zh. 20 (1979), no. 3, 671-673, 694 (Russian). MR 537377
  • [18] John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551-565. MR 695906, https://doi.org/10.1007/BF02095993
  • [19] Alexander Ushakov, Algorithmic theory of free solvable groups: randomized computations, J. Algebra 407 (2014), 178-200. MR 3197157, https://doi.org/10.1016/j.jalgebra.2014.02.014
  • [20] Svetla Vassileva, Polynomial time conjugacy in wreath products and free solvable groups, Groups Complex. Cryptol. 3 (2011), no. 1, 105-120. MR 2806083, https://doi.org/10.1515/GCC.2011.005
  • [21] Svetla Vassileva, The Magnus embedding is a quasi-isometry, Internat. J. Algebra Comput. 22 (2012), no. 8, 1240005, 7. MR 3010819, https://doi.org/10.1142/S021819671240005X

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20F19, 20F10, 20F65, 03D15

Retrieve articles in all journals with MSC (2010): 20F19, 20F10, 20F65, 03D15


Additional Information

Funda Gul
Affiliation: Department of Mathematics, Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: fgul@stevens.edu

Mahmood Sohrabi
Affiliation: Department of Mathematics, Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: msohrab1@stevens.edu

Alexander Ushakov
Affiliation: Department of Mathematics, Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: aushakov@stevens.edu

DOI: https://doi.org/10.1090/tran/6880
Keywords: Magnus embedding, word problem, power problem, conjugacy problem, free solvable groups
Received by editor(s): March 11, 2015
Received by editor(s) in revised form: September 15, 2015
Published electronically: November 28, 2016
Additional Notes: The third author was partially supported by NSA Mathematical Sciences Program grant number H98230-14-1-0128
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society