The Diophantine problem in some metabelian groups
HTML articles powered by AMS MathViewer
- by Olga Kharlampovich, Laura López and Alexei Myasnikov HTML | PDF
- Math. Comp. 89 (2020), 2507-2519 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 0297840
- 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 0283060
- 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 0153726
- 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 0470107
- 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
Additional Information
- Olga Kharlampovich
- Affiliation: Department of Mathematics and Statistics, Hunter College and Graduate Center of City University of New York, Room 919/944 East, 695 Park Avenue, New York, New York 10065
- MR Author ID: 191704
- Laura López
- Affiliation: The Graduate Center, City University of New York, 365 Fifth Avenue, New York, New York 10016
- Alexei Myasnikov
- Affiliation: Department of Mathematical Sciences, Stevens Institute of Technology, One Castle Point Terrace, Hoboken, New Jersey 07030
- MR Author ID: 670299
- Received by editor(s): July 28, 2019
- Received by editor(s) in revised form: October 31, 2019, and January 11, 2020
- Published electronically: April 16, 2020
- Additional Notes: The first author gratefully acknowledges support over the years by grant 422503 from the Simons Foundation.
- © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 2507-2519
- MSC (2010): Primary 20F16, 20F70
- DOI: https://doi.org/10.1090/mcom/3533
- MathSciNet review: 4109575