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)

 
 

 

The word and geodesic problems in free solvable groups


Authors: A. Myasnikov, V. Roman'kov, A. Ushakov and A. Vershik
Journal: Trans. Amer. Math. Soc. 362 (2010), 4655-4682
MSC (2000): Primary 20F16; Secondary 68W30
DOI: https://doi.org/10.1090/S0002-9947-10-04959-7
Published electronically: April 14, 2010
MathSciNet review: 2645045
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the computational complexity of the Word Problem (WP) in free solvable groups $ S_{r,d}$, where $ r \geq 2$ is the rank and $ d \geq 2$ is the solvability class of the group. It is known that the Magnus embedding of $ S_{r,d}$ into matrices provides a polynomial time decision algorithm for WP in a fixed group $ S_{r,d}$. Unfortunately, the degree of the polynomial grows together with $ d$, so the uniform algorithm is not polynomial in $ d$. In this paper we show that WP has time complexity $ O(r n \log_2 n)$ in $ S_{r,2}$, and $ O(n^3 r d)$ in $ S_{r,d}$ for $ d \geq 3$. However, it turns out, that a seemingly close problem of computing the geodesic length of elements in $ S_{r,2}$ is $ NP$-complete. We prove also that one can compute Fox derivatives of elements from $ S_{r,d}$ in time $ O(n^3 r d)$; in particular, one can use efficiently the Magnus embedding in computations with free solvable groups. Our approach is based on such classical tools as the Magnus embedding and Fox calculus, as well as on relatively new geometric ideas; in particular, we establish a direct link between Fox derivatives and geometric flows on Cayley graphs.


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

  • 1. J. Almeida, Semidirect products of pseudovarieties from the universal algebraist's point of view, J. Pure Appl. Algebra 60 (1989), pp. 113-128. MR 1020712 (91a:20068)
  • 2. J. Almeida and P. Weil, Free profinite semigroups over semidirect products, Izvestiya VUZ Matematika 39 (1995), pp. 3-31. MR 1391317 (97e:20078)
  • 3. K. Auinger and B. Steinberg, The geometry of profinite graphs with applications to free groups and finite monoids., Trans. Amer. Math. Soc. 356 (2004), pp. 805-851. MR 2022720 (2005a:20040)
  • 4. -, A constructive version of the Ribes-Zalesskii product theorem, Math. Z. 250 (2005), pp. 287-297. MR 2178787 (2006h:20029)
  • 5. -, Constructing divisions into power groups, Theoret. Comput. Sci. 341 (2005), pp. 1-21. MR 2159641 (2007b:68127)
  • 6. J. Birman, Braids, Links and Mapping Class Groups, Annals of Math. Studies. Princeton University Press, 1974. MR 0375281 (51:11477)
  • 7. B. Bollobas, Graph Theory: An Introductory Course, Graduate Texts in Mathematics. Springer, 1990. MR 536131 (80j:05053)
  • 8. G. Chartrand and O. Oellermann, Applied and Algorithmic Graph Theory. McGraw-Hill, New York, 1993. MR 1211413
  • 9. D. F. Cowan, A class of varieties of inverse semigroups, J. Algebra 141 (1991), pp. 115-142. MR 1118319 (92f:20063)
  • 10. R. Crowell and R. Fox, Introduction to Knot Theory, Graduate Texts in Mathematics. Springer, 1984. MR 0445489 (56:3829)
  • 11. CRyptography And Groups (CRAG) C++ Library, Available at http://www.acc.stevens. edu/downloads.php.
  • 12. R. Diestel, Graph Theory, Graduate Texts in Mathematics 173. Springer, 2005. MR 2159259 (2006e:05001)
  • 13. C. Droms, J. Lewin, and H. Servatius, The length of elements in free solvable groups, Proc. Amer. Math. Soc. 119 (1993), pp. 27-33. MR 1160298 (93k:20051)
  • 14. A. Dyubina, Instability of the virtual solvability and the property of being virtually torsion-free for quasi-isometric groups, Int. Math. Res. Notices 21 (2000), pp. 1097-1101. MR 1800990 (2001j:20060)
  • 15. M. Elder, A polynomial-time algorithm to compute geodesic length in BS(1,p), in preparation.
  • 16. D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston, Word processing in groups. Jones and Bartlett Publishers, 1992. MR 1161694 (93i:20036)
  • 17. A. Erschler, On drift and entropy growth for random walks on groups, Ann. of Prob. 31 (2003), pp. 1193-1204. MR 1988468 (2004c:60018)
  • 18. A. Eskin, D. Fisher, and K. Whyte, Quasi-isometries and Rigidity of Solvable Groups, Pure Appl. Math. Quart. 3 (2007), pp. 927-947. MR 2402598
  • 19. B. Farb and L. Mosher, A rigidity theorem for the solvable Baumslag-Solitar groups. With an appendix by Daryl Cooper, Invent. Math. 131 (1998), pp. 419-451. MR 1608595 (99b:57003)
  • 20. -, Quasi-isometric rigidity for the solvable Baumslag-Solitar groups. II, Invent. Math. 137 (1999), pp. 613-649. MR 1709862 (2001g:20053)
  • 21. R. H. Fox, Free differential calculus I, Ann. of Math. (2) 57 (1953), pp. 547-560. MR 0053938 (14:843d)
  • 22. -, Free differential calculus II, Ann. of Math. (2) 59 (1954), pp. 196-210. MR 0062125 (15:931e)
  • 23. -, Free differential calculus III, Ann. of Math. (2) 64 (1956), pp. 407-419. MR 0095876 (20:2374)
  • 24. -, Free differential calculus IV, Ann. of Math. (2) 71 (1960), pp. 408-422. MR 0111781 (22:2642)
  • 25. M. Garey and D. Johnson, The Rectilinear Steiner Tree Problem is NP-complete, SIAM J. Comput. 32 (1977), pp. 826-834. MR 0443426 (56:1796)
  • 26. M. Gromov, Groups of polynomial growth and expanding maps, Publ. Math. IHES 53 (1981), pp. 53-73. MR 623534 (83b:53041)
  • 27. -, Infinite groups as geometric objects. Proceedings of the International Congress of Mathematicians, 1, pp. 385-395, 1983. MR 804694 (87c:57033)
  • 28. K. W. Gruenberg, Residual properties of infinite soluble groups, Proc. London Math. Soc. 7 (1957), pp. 29-62. MR 0087652 (19:386a)
  • 29. N. Gupta, Free group rings, Contemporary Mathematics 66. American Mathematical Society, 1987. MR 895359 (88j:20030)
  • 30. M. Hanan, On Steiner's problem with rectilinear distance, SIAM J. Appl. Math. 14 (1966), pp. 255-265. MR 0224500 (37:99)
  • 31. A. Hatcher, Algebraic Topology. Cambridge University Press, Cambridge, 2002. MR 1867354 (2002k:55001)
  • 32. V. Kaimanovich and A. M. Vershik, Random walks on discrete groups: Boundary and entropy., Ann. Probab. 11 (1983), pp. 457-490. MR 704539 (85d:60024)
  • 33. M. I. Kargapolov and V. N. Remeslennikov, The conjugacy problem for free solvable groups, Algebra i Logika Sem. 5 (1966), pp. 15-25. Russian. MR 0206080 (34:5905)
  • 34. R. M. Karp, Reducibility Among Combinatorial Problems. Complexity of Computer Computations, Computer Applications in the Earth Sciences, pp. 85-103. Springer, 1972. MR 0378476 (51:14644)
  • 35. O. Kharlampovich, A finitely presented solvable group with unsolvable word problem, Izvest. Ak. Nauk, Ser. Mat. 45 (1981), pp. 852-873. MR 631441 (82m:20036)
  • 36. O. Kharlampovich and M. Sapir, Algorithmic problems in varieties, Int. J. Algebr. Comput. 5 (1995), pp. 379-602. MR 1361261 (96m:20045)
  • 37. W. Magnus, On a theorem of Marshall Hall, Ann. of Math. 40 (1939), pp. 764-768. MR 0000262 (1:44b)
  • 38. S. W. Margolis and J. C. Meakin, $ E$-unitary inverse monoids and the Cayley graph of a group presentation, J. Pure Appl. Algebra 58 (1989), pp. 45-76. MR 996174 (90f:20096)
  • 39. S. W. Margolis, J. C. Meakin, and J. B. Stephen, Free objects in certain varieties of inverse semigroups, Canadian J. Math. 42 (1990), pp. 1084-1097. MR 1099459 (92j:20057)
  • 40. J. Matthews, The conjugacy problem in wreath products and free metabelian groups, Trans. Amer. Math. Soc. 121 (1966), pp. 329-339. English transl., Soviet Math. Dokl. 8 (1967), 555-557. MR 0193130 (33:1351)
  • 41. J. Milnor, Growth of finitely generated solvable groups, J. Differ. Geom. 2 (1968), pp. 447-449. MR 0244899 (39:6212)
  • 42. L. Mosher, M. Sageev, and K. Whyte, Quasi-actions on trees. I. Bounded valence, Ann. of Math. (2) 158 (2003), pp. 115-164. MR 1998479 (2004h:20055)
  • 43. W. D. Munn, Free inverse semigroups, Proc. London Math. Soc. 29 (1974), pp. 385-404. MR 0360881 (50:13328)
  • 44. H. Newmann, Varieties of groups. Springer, 1967. MR 0215899 (35:6734)
  • 45. W. Parry, Growth Series of Some Wreath Products, Trans. Amer. Math. Soc. 331 (1992), pp. 751-759. MR 1062874 (92h:20061)
  • 46. V. N. Remeslennikov, Certain properties of the Magnus embedding, Algebra i Logika 8 (1969), pp. 72-76.
  • 47. V. N. Remeslennikov and N. S. Romanovskii, Algorithmic problems for solvable groups. Word Problems II: The Oxford book, pp. 337-346. North-Holland, 1980. MR 579951 (81h:20044)
  • 48. V. N. Remeslennikov and V. G. Sokolov, Certain properties of the Magnus embedding, Algebra i Logika 9 (1970), pp. 566-578. MR 0292920 (45:2001)
  • 49. J. Rhodes and B. Steinberg, Profinite semigroups, varieties, expansions and the structure of relatively free profinite semigroups, Internat. J. Algebra Comput. 11 (2001), pp. 627-672. MR 1880372 (2002j:20114)
  • 50. A. L. Shmel$ '$kin, Wreath products and group varities, Izvestiya AN SSSR, seriya matematika, 29 (1965), pp. 149-176.
  • 51. I. M. Singer and J. A. Thorpe, Lectures Notes on Elementary Topology and Geometry, Undergraduate Texts in Mathematics. Springer-Verlag, 1967. MR 0213982 (35:4834)
  • 52. A. M. Vershik, Geometry and dynamics on the free solvable groups, preprint. Erwin Schroedinger Institute, Vienna, 1999, pp. 1-16.
  • 53. -, Dynamic theory of growth in groups: Entropy, boundaries, examples, Uspekhi Mat. Nauk 55 (2000), pp. 59-128. MR 1786730 (2001m:37019)
  • 54. A. M. Vershik and S. Dobrynin, Geometrical approach to the free solvable groups, Internat. J. Algebra Comput. 15 (2005), 1243-1260. MR 2197831 (2006m:20049)
  • 55. B. A. F. Wehrfritz, Two examples of soluble groups that are not conjugacy separable, J. London Math. Soc. 2 (1973), pp. 312-316. MR 0338176 (49:2942)
  • 56. -, Another example of a soluble group that is not conjugacy separable, J. London Math. Soc. 14 (1976), pp. 380-382. MR 0422429 (54:10418)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20F16, 68W30

Retrieve articles in all journals with MSC (2000): 20F16, 68W30


Additional Information

A. Myasnikov
Affiliation: Department of Mathematics and Statistics, McGill University, Montreal, Canada H3A 2K6
Email: amiasnikov@gmail.com

V. Roman'kov
Affiliation: Department of Mathematics, Omsk State University, Omsk, Russia 644077
Email: romankov@math.omsu.omskreg.ru

A. Ushakov
Affiliation: Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken, New Jersey 07030
Email: aushakov@stevens.edu

A. Vershik
Affiliation: Petersburg Department of Steklov Institute of Mathematics, St. Petersburg, Russia 191023
Email: vershik@pdmi.ras.ru

DOI: https://doi.org/10.1090/S0002-9947-10-04959-7
Keywords: Free solvable groups, word problem, geodesic problem, Fox derivatives, Steiner tree problem, theoretical computer science
Received by editor(s): July 11, 2008
Published electronically: April 14, 2010
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society