Spherical quadratic equations in free metabelian groups

Lysenok, Igor; Ushakov, Alexander

doi:10.1090/proc/12662

Spherical quadratic equations in free metabelian groups
HTML articles powered by AMS MathViewer

by Igor Lysenok and Alexander Ushakov PDF

Proc. Amer. Math. Soc. 144 (2016), 1383-1390 Request permission

Abstract:

We prove that the Diophantine problem for spherical quadratic equations in free metabelian groups is solvable and, moreover, $\mathbf {NP}$-complete.

References

Gilbert Baumslag and Kurt Mahler, Equations in free metabelian groups, Michigan Math. J. 12 (1965), 417–420. MR 181665
Erik D. Demaine and Martin L. Demaine, Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity, Graphs Combin. 23 (2007), no. suppl. 1, 195–208. MR 2320628, DOI 10.1007/s00373-007-0713-4
Carl Droms, Jacques Lewin, and Herman Servatius, The length of elements in free solvable groups, Proc. Amer. Math. Soc. 119 (1993), no. 1, 27–33. MR 1160298, DOI 10.1090/S0002-9939-1993-1160298-8
Roger C. Lyndon, Equations in free metabelian groups, Proc. Amer. Math. Soc. 17 (1966), 728–730. MR 195929, DOI 10.1090/S0002-9939-1966-0195929-6
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
Wilhelm Magnus, On a theorem of Marshall Hall, Ann. of Math. (2) 40 (1939), 764–768. MR 262, DOI 10.2307/1968892
Jane Matthews, The conjugacy problem in wreath products and free metabelian groups, Trans. Amer. Math. Soc. 121 (1966), 329–339. MR 193130, DOI 10.1090/S0002-9947-1966-0193130-8
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, DOI 10.1090/s0002-9947-10-04959-7
V. N. Remeslennikov and N. S. Romanovskiĭ, Irreducible algebraic sets in a metabelian group, Algebra Logika 44 (2005), no. 5, 601–621, 638 (Russian, with Russian summary); English transl., Algebra Logic 44 (2005), no. 5, 336–347. MR 2195022, DOI 10.1007/s10469-005-0032-x
V. A. Roman′kov, Equations in free metabelian groups, Sibirsk. Mat. Zh. 20 (1979), no. 3, 671–673, 694 (Russian). MR 537377
Vitaliĭ Roman’kov, Equations over groups, Groups Complex. Cryptol. 4 (2012), no. 2, 191–239. MR 3043434, DOI 10.1515/gcc-2012-0015
N. S. Romanovskiĭ, Algebraic sets in a metabelian group, Algebra Logika 46 (2007), no. 4, 503–513, 529 (Russian, with Russian summary); English transl., Algebra Logic 46 (2007), no. 4, 274–280. MR 2363556, DOI 10.1007/s10469-007-0026-y
Alexander Ushakov, Algorithmic theory of free solvable groups: randomized computations, J. Algebra 407 (2014), 178–200. MR 3197157, DOI 10.1016/j.jalgebra.2014.02.014
Svetla Vassileva, Polynomial time conjugacy in wreath products and free solvable groups, Groups Complex. Cryptol. 3 (2011), no. 1, 105–120. MR 2806083, DOI 10.1515/GCC.2011.005
A. M. Vershik and S. V. Dobrynin, Geometrical approach to the free solvable groups, Internat. J. Algebra Comput. 15 (2005), no. 5-6, 1243–1260. MR 2197831, DOI 10.1142/S0218196705002657