Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
Published electronically: April 14, 2010
MathSciNet review: 2645045
Full-text PDF

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?)


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: http://dx.doi.org/10.1090/S0002-9947-10-04959-7
PII: S 0002-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.