Geodesic
A polynomial bound on solutions of quadratic equations in free groups
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 148-190.

Voir la notice de l'article provenant de la source Math-Net.Ru

We provide polynomial upper bounds on the size of a shortest solution for quadratic equations in a free group. A similar bound is given for parametric solutions in the description of solution sets of quadratic equations in a free group. 
@article{TM_2011_274_a9,
     author = {Igor G. Lysenok and Alexei G. Myasnikov},
     title = {A polynomial bound on solutions of quadratic equations in free groups},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {148--190},
     publisher = {mathdoc},
     volume = {274},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2011_274_a9/}
}
TY  - JOUR
AU  - Igor G. Lysenok
AU  - Alexei G. Myasnikov
TI  - A polynomial bound on solutions of quadratic equations in free groups
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2011
SP  - 148
EP  - 190
VL  - 274
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2011_274_a9/
LA  - ru
ID  - TM_2011_274_a9
ER  - 
%0 Journal Article
%A Igor G. Lysenok
%A Alexei G. Myasnikov
%T A polynomial bound on solutions of quadratic equations in free groups
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2011
%P 148-190
%V 274
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2011_274_a9/
%G ru
%F TM_2011_274_a9
Igor G. Lysenok; Alexei G. Myasnikov. A polynomial bound on solutions of quadratic equations in free groups. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 148-190. http://geodesic.mathdoc.fr/item/TM_2011_274_a9/

[1] Grigorchuk R.I., Kurchanov P.F., “Nekotorye voprosy teorii grupp, svyazannye s geometriei”, Algebra–7, Itogi nauki i tekhniki. Sovr. probl. matematiki. Fund. napr., 58, VINITI, M., 1990, 191–256

[2] Zeifert G., Trelfall V., Topologiya, RKhD, Moskva; Izhevsk, 2001

[3] Lindon R., Shupp P., Kombinatornaya teoriya grupp, Mir, M., 1980 | MR

[4] Maltsev A.I., “Ob uravnenii $zxyx^{-1}y^{-1}z^{-1}=aba^{-1}b^{-1}$ v svobodnoi gruppe”, Algebra i logika, 1:5 (1962), 45–50 | MR | Zbl

[5] Makanin G.S., “Uravneniya v svobodnoi gruppe”, Izv. AN SSSR. Ser. mat., 46:6 (1982), 1199–1273 | MR | Zbl

[6] Olshanskii A.Yu., “Diagrammy gomomorfizmov grupp poverkhnostei”, Sib. mat. zhurn., 30:6 (1989), 150–171 | MR

[7] Razborov A.A., Ob uravneniyakh v svobodnoi gruppe, Dis. ... kand. fiz.-mat. nauk, MIAN, M., 1987

[8] Bormotov D., Gilman R., Myasnikov A., “Solving one-variable equations in free groups”, J. Group Theory, 12:2 (2009), 317–330 | DOI | MR | Zbl

[9] Baumslag G., Myasnikov A., Remeslennikov V., “Algebraic geometry over groups. I: Algebraic sets and ideal theory”, J. Algebra, 219:1 (1999), 16–79 | DOI | MR | Zbl

[10] Bumagin I., Kharlampovich O., Miasnikov A., “Isomorphism problem for finitely generated fully residually free groups”, J. Pure and Appl. Algebra, 208 (2007), 961–977 | DOI | MR | Zbl

[11] Comerford L.P., Jr., “Quadratic equations over small cancellation groups”, J. Algebra, 69:1 (1981), 175–185 | DOI | MR | Zbl

[12] Comerford L.P., Jr., Edmunds C.C., “Quadratic equations over free groups and free products”, J. Algebra, 68:2 (1981), 276–297 | DOI | MR | Zbl

[13] Comerford L.P., Jr., Edmunds C.C., “Solutions of equations in free groups”, Group theory, Proc. Conf., Singapore, 1987, W. de Gruyter, Berlin, 1989, 347–356 | MR

[14] Culler M., “Using surfaces to solve equations in free groups”, Topology, 20:2 (1981), 133–145 | DOI | MR | Zbl

[15] Dahmani F., Groves D., “The isomorphism problem for toral relatively hyperbolic groups”, Publ. Math. IHES, 107 (2008), 211–290 | DOI | MR | Zbl

[16] Dahmani F., Guirardel V., “The isomorphism problem for all hyperbolic groups”, Geom. and Funct. Anal., 21:2 (2011), 223–300, arXiv: 1002.2590v2 | DOI | MR | Zbl

[17] Diekert V., Robson J.M., “Quadratic word equations”, Jewels are forever, Springer, Berlin, 1999, 314–326 | DOI | MR | Zbl

[18] Grigorchuk R.I., Kurchanov P.F., “On quadratic equations in free groups”, Algebra, Proc. Intern. Conf. Dedicated to the Memory of A.I. Mal'cev, Novosibirsk, 1989, Pt. 1, Contemp. Math., 131, Amer. Math. Soc., Providence, RI, 1992, 159–171 | DOI | MR

[19] Kharlampovich O., Lysënok I.G., Myasnikov A.G., Touikan N.W.M., “The solvability problem for quadratic equations over free groups is NP-complete”, Theory Comput. Syst., 47:1 (2010), 250–258 | DOI | MR | Zbl

[20] Kharlampovich O., Myasnikov A., “Implicit function theorem over free groups”, J. Algebra, 290:1 (2005), 1–203 | DOI | MR | Zbl

[21] Kharlampovich O., Myasnikov A., “Irreducible affine varieties over a free group. I: Irreducibility of quadratic equations and Nullstellensatz”, J. Algebra, 200:2 (1998), 472–516 | DOI | MR | Zbl

[22] Kharlampovich O., Myasnikov A., “Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups”, J. Algebra, 200:2 (1998), 517–570 | DOI | MR | Zbl

[23] Kharlampovich O., Myasnikov A., Equations and algorithmic problems in groups, Publicações Matemáticas do IMPA, IMPA, Rio de Janeiro, 2008 | MR | Zbl

[24] Kharlampovich O., Myasnikov A.G., “Equations and fully residually free groups”, Combinatorial and geometric group theory, Dortmund and Ottawa–Montreal Conf., Trends Math., Birkhäuser, Basel, 2010, 203–242 | MR | Zbl

[25] Kharlampovich O., Myasnikov A., “Elementary theory of free non-abelian groups”, J. Algebra, 302:2 (2006), 451–552 | DOI | MR | Zbl

[26] Lyndon R.C., “The equation $a^2b^2 = c^2$ in free groups”, Mich. Math. J., 6 (1959), 89–95 | DOI | MR | Zbl

[27] Sela Z., “The isomorphism problem for hyperbolic groups. I”, Ann. Math. Ser. 2, 141:2 (1995), 217–283 | DOI | MR | Zbl

[28] Sela Z., “Diophantine geometry over groups. I: Makanin–Razborov diagrams”, Publ. Math. IHES, 93 (2001), 31–105 | DOI | MR | Zbl

[29] Sela Z., “Diophantine geometry over groups. II: Completions, closures and formal solutions”, Isr. J. Math., 134 (2003), 173–254 | DOI | MR | Zbl

[30] Sela Z., “Diophantine geometry over groups. III: Rigid and solid solutions”, Isr. J. Math., 147 (2005), 1–73 | DOI | MR | Zbl

[31] Sela Z., “Diophantine geometry over groups. IV: An iterative procedure for validation of a sentence”, Isr. J. Math., 143 (2004), 1–130 | DOI | MR | Zbl

[32] Sela Z., “Diophantine geometry over groups. V$_1$: Quantifier elimination. I”, Isr. J. Math., 150 (2005), 1–197 | DOI | MR | Zbl

[33] Sela Z., “Diophantine geometry over groups. V$_2$: Quantifier elimination. II”, Geom. and Funct. Anal., 16:3 (2006), 537–706 | MR | Zbl

[34] Sela Z., “Diophantine geometry over groups. VI: The elementary theory of a free group”, Geom. and Funct. Anal., 16:3 (2006), 707–730 | MR | Zbl

[35] Wicks M.J., “A general solution of binary homogeneous equations over free groups”, Pac. J. Math., 41 (1972), 543–561 | DOI | MR | Zbl