## Quadratic equations in hyperbolic groups are NP-complete

HTML articles powered by AMS MathViewer

- by Olga Kharlampovich, Atefeh Mohajeri, Alexander Taam and Alina Vdovina PDF
- Trans. Amer. Math. Soc.
**369**(2017), 6207-6238 Request permission

## Abstract:

We prove that in a torsion-free hyperbolic group $\Gamma$, the length of the value of each variable in a minimal solution of a quadratic equation $Q=1$ is bounded by $N|Q|^3$ for an orientable equation, and by $N|Q|^{4}$ for a non-orientable equation, where $|Q|$ is the length of the equation and the constant $N$ can be computed. We show that the problem, whether a quadratic equation in $\Gamma$ has a solution, is in NP, and that there is a PSpace algorithm for solving arbitrary equations in $\Gamma$. If additionally $\Gamma$ is non-cyclic, then this problem (of deciding existence of a solution) is NP-complete. We also give a slightly larger bound for minimal solutions of quadratic equations in a toral relatively hyperbolic group.## References

- Ian Agol, Joel Hass, and William Thurston,
*The computational complexity of knot genus and spanning area*, Trans. Amer. Math. Soc.**358**(2006), no. 9, 3821–3850. MR**2219001**, DOI 10.1090/S0002-9947-05-03919-X - G. N. Arzhantseva,
*On quasiconvex subgroups of word hyperbolic groups*, Geom. Dedicata**87**(2001), no. 1-3, 191–208. MR**1866849**, DOI 10.1023/A:1012040207144 - Martin R. Bridson and André Haefliger,
*Metric spaces of non-positive curvature*, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999. MR**1744486**, DOI 10.1007/978-3-662-12494-9 - Vladimir V. Chaynikov,
*Properties of hyperbolic groups: Free normal subgroups, quasiconvex subgroups and actions of maximal growth*, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–Vanderbilt University. MR**3121970** - Leo P. Comerford Jr. and Charles C. Edmunds,
*Quadratic equations over free groups and free products*, J. Algebra**68**(1981), no. 2, 276–297. MR**608536**, DOI 10.1016/0021-8693(81)90265-9 - Leo P. Comerford Jr. and Charles C. Edmunds,
*Products of commutators and products of squares in a free group*, Internat. J. Algebra Comput.**4**(1994), no. 3, 469–480. MR**1297152**, DOI 10.1142/S0218196794000105 - Marc Culler,
*Using surfaces to solve equations in free groups*, Topology**20**(1981), no. 2, 133–145. MR**605653**, DOI 10.1016/0040-9383(81)90033-1 - François Dahmani,
*Existential questions in (relatively) hyperbolic groups*, Israel J. Math.**173**(2009), 91–124. MR**2570661**, DOI 10.1007/s11856-009-0084-z - F. Dahmani, V. Guirardel, and D. Osin,
*Hyperbolically embedded subgroups and rotating families in groups acting on hyperbolic spaces*, to appear in Mem. Amer. Math. Soc., e-print arXiv:1111.7048 [math.GR] (2011). - David B. A. Epstein and Derek F. Holt,
*Computation in word-hyperbolic groups*, Internat. J. Algebra Comput.**11**(2001), no. 4, 467–487. MR**1850213**, DOI 10.1142/S0218196701000619 - Michael R. Garey and David S. Johnson,
*Computers and intractability*, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR**519066** - R. I. Grigorchuk and P. F. Kurchanov,
*On quadratic equations in free groups*, Proceedings of the International Conference on Algebra, Part 1 (Novosibirsk, 1989) Contemp. Math., vol. 131, Amer. Math. Soc., Providence, RI, 1992, pp. 159–171. MR**1175769**, DOI 10.1007/bf01058681 - R. I. Grigorchuk and I. G. Lysionok,
*A description of solutions of quadratic equations in hyperbolic groups*, Internat. J. Algebra Comput.**2**(1992), no. 3, 237–274. MR**1189234**, DOI 10.1142/S0218196792000153 - Claudio Gutiérrez,
*Satisfiability of equations in free groups is in PSPACE*, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 21–27. MR**2114513**, DOI 10.1145/335305.335308 - O. Kharlampovich, I. G. Lysënok, A. G. Myasnikov, and N. W. M. Touikan,
*The solvability problem for quadratic equations over free groups is NP-complete*, Theory Comput. Syst.**47**(2010), no. 1, 250–258. MR**2643918**, DOI 10.1007/s00224-008-9153-7 - Olga Kharlampovich and Alexei Myasnikov,
*Implicit function theorem over free groups*, J. Algebra**290**(2005), no. 1, 1–203. MR**2154989**, DOI 10.1016/j.jalgebra.2005.04.001 - Olga Kharlampovich and Alina Vdovina,
*Linear estimates for solutions of quadratic equations in free groups*, Internat. J. Algebra Comput.**22**(2012), no. 1, 1250004, 16. MR**2900857**, DOI 10.1142/S0218196711006704 - M. Kufleitner,
*Wortgleichungen in hyperbolischen gruppen*, Ph.D. thesis, Universität Stuttgart, Holzgartenstr. 16, 70174 Stuttgart, 2001. - I. G. Lysenok and A. G. Myasnikov,
*A polynomial bound for solutions of quadratic equations in free groups*, Tr. Mat. Inst. Steklova**274**(2011), no. Algoritmicheskie Voprosy Algebry i Logiki, 148–190 (Russian, with Russian summary); English transl., Proc. Steklov Inst. Math.**274**(2011), no. 1, 136–173. MR**2962940**, DOI 10.1134/S0081543811060101 - G. S. Makanin,
*Equations in a free group*, Izv. Akad. Nauk SSSR Ser. Mat.**46**(1982), no. 6, 1199–1273, 1344 (Russian). MR**682490** - A. I. Mal′cev,
*On the equation $zxyx^{-1}y^{-1}z^{-1}= aba^{-1}b^{-1}$ in a free group*, Algebra i Logika Sem.**1**(1962), no. 5, 45–50 (Russian). MR**0153726** - A. Yu. Ol′shanskiĭ,
*Diagrams of homomorphisms of surface groups*, Sibirsk. Mat. Zh.**30**(1989), no. 6, 150–171 (Russian); English transl., Siberian Math. J.**30**(1989), no. 6, 961–979 (1990). MR**1043443**, DOI 10.1007/BF00970919 - A. Yu. Ol′shanskiĭ,
*On residualing homomorphisms and $G$-subgroups of hyperbolic groups*, Internat. J. Algebra Comput.**3**(1993), no. 4, 365–409. MR**1250244**, DOI 10.1142/S0218196793000251 - E. Rips and Z. Sela,
*Canonical representatives and equations in hyperbolic groups*, Invent. Math.**120**(1995), no. 3, 489–512. MR**1334482**, DOI 10.1007/BF01241140 - Alina A. Vdovina,
*Constructing of orientable Wicks forms and estimation of their number*, Comm. Algebra**23**(1995), no. 9, 3205–3222. MR**1335298**, DOI 10.1080/00927879508825398 - A. Vdovina,
*On the number of nonorientable Wicks forms in a free group*, Proc. Roy. Soc. Edinburgh Sect. A**126**(1996), no. 1, 113–116. MR**1378835**, DOI 10.1017/S0308210500030626 - Alina Vdovina,
*Products of commutators in free products*, Internat. J. Algebra Comput.**7**(1997), no. 4, 471–485. MR**1459623**, DOI 10.1142/S0218196797000216

## Additional Information

**Olga Kharlampovich**- Affiliation: Department of Mathematics and Statistics, Hunter College, CUNY, 695 Park Avenue, New York, New York 10065
- MR Author ID: 191704
- Email: okharlampovich@gmail.com
**Atefeh Mohajeri**- Affiliation: Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street W., Montreal H3A 0B9, Canada
- MR Author ID: 885924
- Email: at.mohajeri@gmail.com
**Alexander Taam**- Affiliation: Department of Mathematics, Graduate Center, CUNY, 365 Fifth Avenue, New York, New York 10016
- Address at time of publication: Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken, New Jersey 07030
- Email: alex.taam@gmail.com
**Alina Vdovina**- Affiliation: School of Mathematics and Statistics, Newcastle University, Newcastle upon Tyne, NE1 7RU, United Kingdom
- Email: Alina.Vdovina@newcastle.ac.uk
- Received by editor(s): July 9, 2014
- Received by editor(s) in revised form: May 11, 2015, and September 16, 2015
- Published electronically: February 13, 2017
- © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**369**(2017), 6207-6238 - MSC (2010): Primary 20F10, 20F65, 20F67; Secondary 03D15
- DOI: https://doi.org/10.1090/tran/6829
- MathSciNet review: 3660218