The Diophantine problem in some metabelian groups

Kharlampovich, Olga; López, Laura; Myasnikov, Alexei

doi:10.1090/mcom/3533

The Diophantine problem in some metabelian groups
HTML articles powered by AMS MathViewer

by Olga Kharlampovich, Laura López and Alexei Myasnikov;

Math. Comp. 89 (2020), 2507-2519

DOI: https://doi.org/10.1090/mcom/3533

Published electronically: April 16, 2020

HTML | PDF | Request permission

Abstract:

In this paper we show that the Diophantine problem in solvable Baumslag–Solitar groups $BS(1,k)$ and in wreath products $A \wr \mathbb {Z}$, where $A$ is a finitely generated abelian group and $\mathbb {Z}$ is an infinite cyclic group, is decidable, i.e., there is an algorithm that, given a finite system of equations with constants in such a group, decides whether or not the system has a solution in the group.

References

J. Denef and L. Lipshitz, Diophantine sets over some rings of algebraic integers, J. London Math. Soc. (2) 18 (1978), no. 3, 385–391. MR 518221, DOI 10.1112/jlms/s2-18.3.385
Volker Diekert and Markus Lohrey, Existential and positive theories of equations in graph products, Theory Comput. Syst. 37 (2004), no. 1, 133–156. Symposium on Theoretical Aspects of Computer Science (Antibes-Juan les Pins, 2002). MR 2038406, DOI 10.1007/s00224-003-1110-x
Volker Diekert and Anca Muscholl, Solvability of equations in graph groups is decidable, Internat. J. Algebra Comput. 16 (2006), no. 6, 1047–1069. MR 2286422, DOI 10.1142/S0218196706003372
Moon Duchin, Hao Liang, and Michael Shapiro, Equations in nilpotent groups, Proc. Amer. Math. Soc. 143 (2015), no. 11, 4723–4731. MR 3391031, DOI 10.1090/proc/12630
Ju. L. Eršov, Elementary group theories, Dokl. Akad. Nauk SSSR 203 (1972), 1240–1243 (Russian). MR 297840
Albert Garreta, Alexei Miasnikov, and Denis Ovchinnikov, Random nilpotent groups, polycyclic presentations, and Diophantine problems, Groups Complex. Cryptol. 9 (2017), no. 2, 99–115. MR 3717096, DOI 10.1515/gcc-2017-0007
O. Greco, Unique non-unique factorization, Master’s thesis, 2010, University of Stockholm.
M. I. Kargapolov, V. N. Remeslennikov, N. S. Romanovskiĭ, V. A. Roman′kov, and V. A. Čurkin, Algorithmic questions for $\sigma$-powered groups, Algebra i Logika 8 (1969), 643–659. MR 283060
Markus Lohrey and Géraud Sénizergues, Theories of HNN-extensions and amalgamated products, Automata, languages and programming. Part II, Lecture Notes in Comput. Sci., vol. 4052, Springer, Berlin, 2006, pp. 504–515. MR 2307261, DOI 10.1007/11787006_{4}3
Roger C. Lyndon, Equations in free groups, Trans. Amer. Math. Soc. 96 (1960), 445–457. MR 151503, DOI 10.1090/S0002-9947-1960-0151503-8
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 153726
G. S. Makanin, The problem of the solvability of equations in a free semigroup, Mat. Sb. (N.S.) 103(145) (1977), no. 2, 147–236, 319 (Russian). MR 470107
G. S. Makanin, Equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6, 1199–1273, 1344 (Russian). MR 682490
G. A. Noskov, The elementary theory of a finitely generated almost solvable group, Izv. Akad. Nauk SSSR Ser. Mat. 47 (1983), no. 3, 498–517 (Russian). MR 703594
Thanases Pheidas and Karim Zahidi, Undecidability of existential theories of rings and fields: a survey, Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999) Contemp. Math., vol. 270, Amer. Math. Soc., Providence, RI, 2000, pp. 49–105. MR 1802009, DOI 10.1090/conm/270/04369
V. A. Roman′kov, Unsolvability of the problem of endomorphic reducibility in free nilpotent groups and in free rings, Algebra and Logic 16 (1977), no. 4, 310–320.
V. A. Roman′kov. Equations in free metabelian groups, Siberian Mathematical Journal, 20 (1979), no.3, 469–471.
N. S. Romanovskiĭ, On the elementary theory of an almost polycyclic group, Mathematics of the USSR-Sbornik, 39 (1981), no. 1, 125–132.
A. L. Semënov, 1984 Math. Logical theories of one-place functions on the set of natural numbers. USSR Izv. 22, 587–618.
W. Szmielew, Elementary properties of Abelian groups, Fund. Math. 41 (1955), 203–271. MR 72131, DOI 10.4064/fm-41-2-203-271