×

Diophantine problems in solvable groups. (English) Zbl 1511.20118

Summary: We study the Diophantine problem (decidability of finite systems of equations) in different classes of finitely generated solvable groups (nilpotent, polycyclic, metabelian, free solvable, etc.), which satisfy some natural “non-commutativity” conditions. For each group \(G\) in one of these classes, we prove that there exists a ring of algebraic integers \(O\) that is interpretable in \(G\) by finite systems of equations \((e\)-interpretable), and hence that the Diophantine problem in \(O\) is polynomial time reducible to the Diophantine problem in \(G\). One of the major open conjectures in number theory states that the Diophantine problem in any such \(O\) is undecidable. If true this would imply that the Diophantine problem in any such \(G\) is also undecidable. Furthermore, we show that for many particular groups \(G\) as above, the ring \(O\) is isomorphic to the ring of integers \(\mathbb{Z}\), so the Diophantine problem in \(G\) is, indeed, undecidable. This holds, in particular, for free nilpotent or free solvable non-abelian groups, as well as for non-abelian generalized Heisenberg groups and uni-triangular groups \(UT(n,\mathbb{Z}),n\geq 3\). Then, we apply these results to non-solvable groups that contain non-virtually abelian maximal finitely generated nilpotent subgroups. For instance, we show that the Diophantine problem is undecidable in the groups \(\mathrm{GL}(3,\mathbb{Z}),SL(3,\mathbb{Z}),T(3,\mathbb{Z})\).

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F70 Algebraic geometry over groups; equations over groups
03B25 Decidability of theories and sets of sentences
11U05 Decidability (number-theoretic aspects)
20F18 Nilpotent groups
20F16 Solvable groups, supersolvable groups
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Auslander, L., Discrete solvable matrix groups, Proc. Amer. Math. Soc.11 (1960) 687-688. · Zbl 0097.01303
[2] Burke, E. K., The undecidability of the unification problem for nilpotent groups of class \(\geq 5\), J. London Math. Soc.s2-48(1) (1993) 52-58. · Zbl 0806.20029
[3] Casals-Ruiz, M. and Kazachkov, I., On Systems of Equations Over Free Partially Commutative Groups, (American Mathematical Society, 2011). · Zbl 1278.20057
[4] Casals-Ruiz, M. and Kazachkov, I., On systems of equations over free products of groups, J. Algebra333(1) (2011) 368-426. · Zbl 1239.20048
[5] Chapuis, O., On the theories of free solvable groups, J. Pure Appl. Algebra131(1) (1998) 13-24. · Zbl 0927.20015
[6] Ciobanu Radomirovic, L., Volker Diekert, V. and Elder, M., Solution sets for equations over free groups are edt0l languages, Int. J. Algebra Comput.26(5) (2016) 843-886. · Zbl 1401.68156
[7] Dahmani, F. and Guirardel, V., Foliations for solving equations in groups: Free, virtually free, and hyperbolic groups, J. Topology3(2) (2016) 343-404. · Zbl 1217.20021
[8] Davis, M., Putnam, H. and Robinson, J., The decision problem for exponential Diophantine equations, Annal. Math.74(3) (1961) 425-436. · Zbl 0111.01003
[9] Denef, J., Hilbert’s tenth problem for quadratic rings, Proc. Amer. Math. Soc.48 (1975) 214-220. · Zbl 0324.02032
[10] Denef, J. and Lipshitz, L.. Diophantine sets over some rings of algebraic integers, J. London Math. Soc.s2-18(3) (1978) 385-391. · Zbl 0399.10049
[11] Diekert, V., Jeż, A. and Plandowski, W., Finding all solutions of equations in free groups and monoids with involution, in Computer Science - Theory and Applications eds. Hirsch, E. A., Kuznetsov, S. O., Pin, J.-É. and Vereshchagin, N. K. (Springer International Publishing, Cham, 2014), pp. 1-15. · Zbl 1382.68348
[12] Diekert, V. and Lohrey, M., Word equations over graph products, Int. J. Algebra Comput.18(3) (2008) 493-533. · Zbl 1186.20041
[13] Diekert, V. and Muscholl, A., Solvability of equations in graph groups is decidable, Int. J. Algebra Comput.16(6) (2006) 1047-1069. · Zbl 1112.03009
[14] Duchin, M., Liang, H. and Shapiro, M., Equations in nilpotent groups, Proc. Amer. Math. Soc.143(11) (2015) 4723-4731. · Zbl 1330.20047
[15] Durnev, V. G., Unsolvability of the problem of endomorphic reducibility for sets of elements of a free nilpotent group of rank 2, in Problems in Group Theory and Homological Algebra (Russian), (Yaroslavl State University, Yaroslavl’, 1988), pp. 88-93. · Zbl 0668.20030
[16] Ershov, Y., Elementary group theories, Dokl. Akad. Nauk SSSR203 (1972) 1240-1243. · Zbl 0264.02047
[17] N. Garcia-Fritz and H. Pasten, Towards Hilbert’s Tenth Problem for rings of integers through Iwasawa theory and Heegner points, preprint (2019), arXiv:1909.01434. · Zbl 1469.11168
[18] A. Garreta, A. Miasnikov and D. Ovchinnikov, Diophantine problems in rings and algebras: Undecidability and reductions to rings of algebraic integers, preprint (2018), arXiv:1805.02573v1.
[19] A. Garreta, A. G. Miasnikov and D. Ovchinnikov, Properties of random nilpotent groups, preprint (2016), arXiv:1612.01242v2. · Zbl 1378.20049
[20] K. M. George, Verbal properties of certain groups, PhD thesis, University of Cambridge (1976).
[21] Hall, P., Finite-by-nilpotent groups, Proc. Camb. Phil. Soc.52(4) (1956) 611-616. · Zbl 0072.25801
[22] Hodges, W., Model Theory, , Vol. 42 (Cambridge University Press, Cambridge, 1993). · Zbl 0789.03031
[23] Jeż, A., Recompression: A simple and powerful technique for word equations, J. ACM63(1) (2016) 4:1-4:51. · Zbl 1403.68374
[24] Kargapolov, M. I. and Merzljakov, J. I., Fundamentals of the Theory of Groups, Vol. 62 (Springer-Verlag, New York-Berlin, 1979), Translated from the second Russian edition by Robert G. Burns. · Zbl 0549.20001
[25] Kharlampovich, O., A finitely presented solvable group with unsolvable word problem, Math. USSR-Izvestiya19(1) (1982) 151-169. · Zbl 0494.20021
[26] Kharlampovich, O. and Miasnikov, A. G., Model theory and algebraic geometry in groups, non-standard actions and algorithmic problems, Proc. of the Int. Congress of Mathematicians, v. 2, Invited Lectures, 2014, Seoul, , pp. 223-244. · Zbl 1373.20057
[27] Kharlampovich, O. and Miasnikov, A. G., Undecidability of equations in free Lie algebras, Trans. Amer. Math. Soc.08 (2017) 2987-2999. · Zbl 1486.17008
[28] Kharlampovich, O. and Miasnikov, A. G., Tarski-type problems for free associative algebras, J. Algebra500 (2018) 589-643, special issue dedicated to Efim Zelmanov. · Zbl 1403.03055
[29] Kharlampovich, O. and Miasnikov, A. G., Undecidability of the first order theories of free noncommutative Lie algebras, J. Symbolic Logic83(3) (2018) 1204-1216. · Zbl 1502.03008
[30] Kharlampovich, O. and Miasnikov, A. G., What does a group algebra of a free group “know” about the group?Annal. Pure Appl. Logic169(6) (2018) 523-547. · Zbl 1442.16027
[31] Kharlampovich, O. and Myasnikov, A., Irreducible affine varieties over a free group: Ii. systems in triangular quasi-quadratic form and description of residually free groups. J. Algebra200(2) (1998) 517-570. · Zbl 0904.20017
[32] Kharlampovich, O. and Myasnikov, A., Equations in algebras, Int. J. Algebra Comput.28(8) (2018) 1517-1533. · Zbl 1403.16002
[33] O. Kharlampovich, L. Lopez and A. Miasnikov, Diophantine problem in some metabelian groups, preprint (2019), arXiv:1903.10068.
[34] Lennox, J. C. and Robinson, D. J. S., The Theory of Infinite Soluble Groups, (Clarendon Press, 2004). · Zbl 1059.20001
[35] Lysenok, I., Miasnikov, A. G. and Ushakov, A., Quadratic equations in the grigorchuk group, Groups Geometry Dynamics10 (2013) 4. · Zbl 1341.20037
[36] I. Lysenok and A. Ushakov, Orientable quadratic equations in free metabelian groups, preprint (2018), arXiv:1804.06018. · Zbl 1339.20037
[37] Makanin, G. S., Equations in a free group, Math. USSR-Izvestiya21(3) (1983) 483. · Zbl 0527.20018
[38] Malcev, A. Ĩ., On a correspondence between rings and groups, Amer. Math. Soc. Transl.45(2) (1960) 221-231. · Zbl 0148.24601
[39] Mal’cev, A. I., On free soluble groups, Soviet Math. Dokl.1 (1960) 65-68. · Zbl 0097.24802
[40] Marker, D., Model Theory: An Introduction, (SpringerNew York, 2002). · Zbl 1003.03034
[41] Matijasevič, Y. V., The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR191 (1970) 279-282.
[42] Mazur, B. and Rubin, K., Ranks of twists of elliptic curves and Hilbert’s Tenth Problem, Inventiones Math.181(3) (2010) 541-575. · Zbl 1227.11075
[43] Merzljakov, J. I., Algebraic linear groups as full groups of automorphisms and the closure of their verbal subgroups, Algebra i Logika Sem.6(1) (1967) 83-94. · Zbl 0244.20053
[44] Miasnikov, A. G., Definable invariants of bilinear mappings, Siberian Math. J.31(1) (1990) 89-99. · Zbl 0763.03020
[45] Miasnikov, A. G., Oger, F. and Sohrabi, S., Elementary equivalence of rings with finitely generated additive groups, Annal. Pure Appl. Logic169(6) (2018) 514-522. · Zbl 1505.03083
[46] Miasnikov, A. G. and Sohrabi, M., Groups elementarily equivalent to a free nilpotent group of finite rank, Annal. Pure Appl. Logic162(11) (2011) 916-933. · Zbl 1223.03022
[47] A. G. Miasnikov and M. Sohrabi, Elementary coordinatization of finitely generated nilpotent groups, preprint (2013), arXiv:1311.1391v3.
[48] Neumann, H., Varieties of Groups, (Springer-Verlag New York, Inc., New York, 1967). · Zbl 0251.20001
[49] Noskov, G. A., The elementary theory of a finitely generated almost solvable group, Izv. Akad. Nauk SSSR Ser. Mat.47(3) (1983) 498-517. · Zbl 0521.20019
[50] Pheidas, T. and Zahidi, K., Undecidability of existential theories of rings and fields: A survey, Contemporary Math.270 (2000) 49-106. · Zbl 0981.03013
[51] B. Poonen, Hilbert’s Tenth Problem over rings of number-theoretic interest (2003), http://math.mit.edu/ poonen/papers/aws2003.pdf.
[52] Razborov, A. A., On systems of equations in a free group, Math. USSR-Izvestiya25(1) (1985) 115. · Zbl 0579.20019
[53] Rips, E. and Sela, Z., Canonical representatives and equations in hyperbolic groups, Inventiones Math.120(1) (1995) 489-512. · Zbl 0845.57002
[54] Roman’kov, V. A., Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings, Algebra and Logic, 16(4) (1977) 310-320. · Zbl 0411.20021
[55] Roman’kov, V. A., Equations in free metabelian groups, Siberian Math. J.20(3) (1979) 469-471. · Zbl 0427.20025
[56] Roman’kov, V. A., Universal theory of nilpotent groups, Mat. Zametki25(4) (1979) 487-495. · Zbl 0419.20031
[57] Roman’kov, V. A., The width of verbal subgroups of solvable groups, Algebra i Logika21(1) (1982) 60-72. · Zbl 0504.20020
[58] Roman’kov, V. A., Equations over groups, Groups Complexity Cryptol.4 (2012) 191-239. · Zbl 1304.20058
[59] Romanovskij, N. S., On the elementary theory of an almost polycyclic group, Math. USSR, Sb.39 (1981) 125-132. · Zbl 0462.20029
[60] Segal, D., Polycyclic Groups, , Vol. 82 (Cambridge University Press, Cambridge, 1983). · Zbl 0516.20001
[61] Segal, D., Words: Notes on Verbal Width in Groups, , Vol. 361 (Cambridge University Press, Cambridge, 2009). · Zbl 1198.20001
[62] Shapiro, H. N. and Shlapentokh, A., Diophantine relationships between algebraic number fields, Commun. Pure Appl. Math.42(8) (1989) 1113-1122. · Zbl 0698.12022
[63] Shlapentokh, A., Hilbert’s Tenth Problem: Diophantine Classes and Extensions to Global Fields, (Cambridge University Press, 2007). · Zbl 1196.11166
[64] P. W. Stroud, Topic in the theory of verbal subgroups, PhD thesis, University of Cambridge (1966).
[65] Truss, J. K., Equation-solving in free nilpotent groups class 2 and 3, Bull. London Math. Soc.27(1) (1995) 39-45. · Zbl 0819.20035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.