The Diophantine problem in the classical matrix groups

A. G. Myasnikov ; M. Sohrabi

Izvestiya. Mathematics , Tome 85 (2021) no. 6, pp. 1220-1256.

Résumé

In this paper we study the Diophantine problem in the classical matrix groups $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$, $\mathrm{T}_n(R)$ and $\mathrm{UT}_n(R)$, $n\geqslant 3$, over an associative ring $R$ with identity. We show that if $G_n(R)$ is one of these groups, then the Diophantine problem in $G_n(R)$ is polynomial-time equivalent (more precisely, Karp equivalent) to the Diophantine problem in $R$. When $G_n(R)=\mathrm{SL}_n(R)$ we assume that $R$ is commutative. Similar results hold for $\mathrm{PGL}_n(R)$ and $\mathrm{PSL}_n(R)$ provided $R$ has no zero divisors (for $\mathrm{PGL}_n(R)$ the ring $R$ is not assumed to be commutative).

Détail

Keywords: Diophantine problems, classical matrix groups, decidability, undecidability.
Mots-clés : equations

Bibliographie

[1] M. Davis, H. Putnam, J. Robinson, “The decision problem for exponential diophantine equations”, Ann. of Math. (2), 74:3 (1961), 425–436 | DOI | MR | Zbl

[2] Yu. V. Matiyasevich, “Enumerable sets are diophantine”, Soviet Math. Dokl., 11 (1970), 354–358 | MR | Zbl

[3] B. Poonen, Hilbert's tenth problem over rings of number-theoretic interest, Notes for Arizona winter school on “Number theory and logic”, 2003, 19 pp. http://math.mit.edu/~poonen/papers/aws2003.pdf

[4] T. Pheidas, K. 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., 270, Amer. Math. Soc., Providence, RI, 2000, 49–105 | DOI | MR | Zbl

[5] A. Shlapentokh, Hilbert's tenth problem. Diophantine classes and extensions to global fields, New Math. Monogr., 7, Cambridge Univ. Press, Cambridge, 2007, xiv+320 pp. | DOI | MR | Zbl

[6] J. Denef, L. Lipshitz, “Diophantine sets over some rings of algebraic integers”, J. London Math. Soc. (2), 18:3 (1978), 385–391 | DOI | MR | Zbl

[7] A. Garreta, A. Miasnikov, D. Ovchinnikov, The Diophantine problem in finitely generated commutative rings, arXiv: 2012.09787

[8] O. Kharlampovich, A. Myasnikov, “Equations in algebras”, Internat. J. Algebra Comput., 28:8 (2018), 1517–1533 | DOI | MR | Zbl

[9] O. Kharlampovich, A. Myasnikov, “Undecidability of equations in free Lie algebras”, Trans. Amer. Math. Soc., 371:4 (2019), 2987–2999 | DOI | MR | Zbl

[10] A. Garreta, A. Miasnikov, D. Ovchinnikov, Diophantine problems in rings and algebras: undecidability and reductions to rings of algebraic integers, arXiv: 1805.02573

[11] A. Tarski, A decision method for elementary algebra and geometry, 2nd ed., Univ. of California Press, Berkeley–Los Angeles, CA, 1951, iii+63 pp. | MR | Zbl

[12] Yu. L. Ershov, “Ob elementarnykh teoriyakh lokalnykh polei”, Algebra i logika. Seminar, 4:2 (1965), 5–30 | MR | Zbl

[13] J. Ax, S. Kochen, “Diophantine problems over local fields. I”, Amer. J. Math., 87:3 (1965), 605–630 ; II. A complete set of axioms for $p$-adic number theory, 631–648 | DOI | MR | Zbl | DOI | MR

[14] J. Ax, S. Kochen, “Diophantine problems over local fields. III. Decidable fields”, Amer. J. Math., 83:3 (1966), 437–456 | DOI | MR | Zbl

[15] A. I. Mal'tsev, “Constructive algebras. I”, Russian Math. Surveys, 16:3 (1961), 77–129 | DOI | MR | Zbl

[16] M. O. Rabin, “Computable algebra, general theory and theory of computable fields”, Trans Amer. Math. Soc., 95:2 (1960), 341–360 | DOI | MR | Zbl

[17] V. A. Roman'kov, “Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings”, Algebra and Logic, 16:4 (1977), 310–320 | DOI | MR | Zbl

[18] M. Duchin, Hao Liang, M. Shapiro, “Equations in nilpotent groups”, Proc. Amer. Math. Soc., 143:11 (2015), 4723–4731 | DOI | MR | Zbl

[19] A. Garreta, A. Miasnikov, D. Ovchinnikov, “Diophantine problems in solvable groups”, Bull. Math. Sci., 10:1 (2020), 2050005, 27 pp. | DOI | MR | Zbl

[20] A. Garreta, A. Miasnikov, D. Ovchinnikov, “Full rank presentations and nilpotent groups: structure, Diophantine problem, and genericity”, J. Algebra, 556 (2020), 1–34 | DOI | MR | Zbl

[21] E. Rips, Z. Sela, “Canonical representatives and equations in hyperbolic groups”, Invent. Math., 120:3 (1995), 489–512 | DOI | MR | Zbl

[22] F. Dahmani, V. Guirardel, “Foliations for solving equations in groups: free, virtually free, and hyperbolic groups”, J. Topol., 3:2 (2010), 343–404 | DOI | MR | Zbl

[23] V. Diekert, A. Muscholl, “Solvability of equations in graph groups is decidable”, Internat. J. Algebra Comput., 16:6 (2006), 1047–1069 | DOI | MR | Zbl

[24] M. Casals-Ruiz, I. Kazachkov, On systems of equations over free partially commutative groups, Mem. Amer. Math. Soc., 212, no. 999, Amer. Math. Soc., Providence, RI, 2011, viii+153 pp. | DOI | MR | Zbl

[25] M. Casals-Ruiz, I. Kazachkov, “On systems of equations over free products of groups”, J. Algebra, 333:1 (2011), 368–426 | DOI | MR | Zbl

[26] V. Diekert, M. Lohrey, “Word equations over graph products”, Internat. J. Algebra Comput., 18:3 (2008), 493–533 | DOI | MR | Zbl

[27] O. Kharlampovich, A. Myasnikov, “Model theory and algebraic geometry in groups, non-standard actions and algorithmic problems”, Proceedings of the international congress of mathematicians–Seoul 2014, Invited lectures, v. 2, Kyung Moon Sa, Seoul, 2014, 223–245 | MR | Zbl

[28] G. S. Makanin, “Equations in a free group”, Math. USSR-Izv., 21:3 (1983), 483–546 | DOI | MR | Zbl

[29] G. S. Makanin, “Decidability of the universal and positive theories of a free group”, Math. USSR-Izv., 25:1 (1985), 75–88 | DOI | MR | Zbl

[30] A. A. Razborov, “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162 | DOI | MR | Zbl

[31] A. A. Razborov, O sistemakh uravnenii v svobodnykh gruppakh, Diss. ... kand. fiz.-matem. nauk, MIAN, M., 1987, 154 pp. http://people.cs.uchicago.edu/~razborov/files/phd.pdf

[32] O. Kharlampovich, A. Myasnikov, “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

[33] V. Diekert, A. Je.{z}, W. Plandowski, “Finding all solutions of equations in free groups and monoids with involution”, Inform. and Comput., 251 (2016), 263–286 | DOI | MR | Zbl

[34] A. Je.{z}, “Recompression: a simple and powerful technique for word equations”, J. ACM, 63:1 (2016), 4, 51 pp. | DOI | MR | Zbl

[35] A. Je.{z}, Word equations in linear space, arXiv: 1702.00736

[36] L. Ciobanu, V. Diekert, M. Elder, “Solution sets for equations over free groups are EDT0L languages”, Internat. J. Algebra Comput., 26:5 (2016), 843–886 | DOI | MR | Zbl

[37] L. Ciobanu, M. Elder, The complexity of solution sets to equations in hyperbolic groups, arXiv: 2001.09591

[38] A. I. Maltsev, “Ob elementarnykh svoistvakh lineinykh grupp”, Nekotorye problemy matematiki i mekhaniki, Novosibirsk, 1961, 110–132 | MR | Zbl

[39] C. I. Beidar, A. V. Michalev, “On Malcev's theorem on elementary equivalence of linear groups”, Proceedings of the international conference on algebra, Part 1 (Novosibirsk, 1989), Contemp. Math., 131, Part 1, Amer. Math. Soc., Providence, RI, 1992, 29–35 | DOI | MR | Zbl

[40] E. I. Bunina, “Elementarnaya ekvivalentnost unitarnykh lineinykh grupp nad polyami”, Fundament. i prikl. matem., 4:4 (1998), 1265–1278 | MR | Zbl

[41] E. I. Bunina, “Elementary equivalence of unitary linear groups over rings and skew fields”, Russian Math. Surveys, 53:2 (1998), 374–376 | DOI | DOI | MR | Zbl

[42] E. I. Bunina, “Elementary equivalence of Chevalley groups”, Russian Math. Surveys, 56:1 (2001), 152–153 | DOI | DOI | MR | Zbl

[43] E. I. Bunina, “Elementary equivalence of Chevalley groups over local rings”, Sb. Math., 201:3 (2010), 321–337 | DOI | DOI | MR | Zbl

[44] E. I. Bunina, “Isomorphisms and elementary equivalence of Chevalley groups over commutative rings”, Sb. Math., 210:8 (2019), 1067–1091 | DOI | DOI | MR | Zbl

[45] E. I. Bunina, A. V. Mikhalev, A. G. Pinus, Elementarnaya i blizkie k nei logicheskie ekvivalentnosti klassicheskikh i universalnykh algebr, MTsNMO, M., 2015, 360 pp.

[46] O. V. Belegradek, “The model theory of unitriangular groups”, Ann. Pure App. Logic, 68:3 (1994), 225–261 | DOI | MR | Zbl

[47] A. Myasnikov, M. Sohrabi, On groups elementarily equivalent to a group of triangular matrices $T_n(R)$, arXiv: 1609.09802

[48] A. G. Myasnikov, M. Sohrabi, Bi-interpretability with $\mathbb{Z}$ and models of the complete elementary theories of $\operatorname{SL}(n,O)$, $\mathrm T(n,O)$ and $\operatorname{GL}(n,O)$, $n\geq 3$, arXiv: 2004.03585

[49] N. Avni, A. Lubotsky, C. Meiri, “First order rigidity of non-uniform higher rank arithmetic groups”, Invent. Math., 217:1 (2019), 219–240 | DOI | MR | Zbl

[50] A. I. Mal'cev, “On a correspondence between rings and groups”, Amer. Math. Soc. Transl. Ser. 2, 45, Amer. Math. Soc., Providence, R.I., 1965, 221–231 | DOI | MR | Zbl

[51] D. Marker, Model theory. An introduction, Grad. Texts in Math., 217, Springer-Verlag, New York, 2010, viii+342 pp. | DOI | MR | Zbl

[52] A. Prestel, P. Roquette, Formally $p$-adic fields, Lecture Notes in Math., 1050, Springer-Verlag, Berlin, 1984, v+167 pp. | DOI | MR | Zbl

[53] A. H. Lachlan, E. W. Madison, “Computable fields and arithmetically definable ordered fields”, Proc. Amer. Math. Soc., 24:4 (1970), 803–807 | DOI | MR | Zbl

[54] E. W. Madison, “A note on computable real fields”, J. Symb. Log., 35:2 (1970), 239–241 | DOI | MR | Zbl

[55] Yu. L. Ershov, Problemy razreshimosti i konstruktivnye modeli, Matematicheskaya Logika i Osnovaniya Matematiki, Nauka, M., 1980, 416 pp. | MR | Zbl

[56] A. G. Myasnikov, V. N. Remeslennikov, “Recursive $p$-adic numbers and elementary theories of finitely generated pro-$p$-groups”, Math. USSR-Izv., 30:3 (1988), 577–597 | DOI | MR | Zbl

[57] M. I. Kargapolov, J. I. Merzljakov, Fundamentals of the theory of groups, Grad. Texts in Math., 62, Springer-Verlag, New York–Berlin, 1979, xvii+203 pp. | MR | MR | Zbl | Zbl

[58] D. Carter, G. Keller, “Bounded elementary generation of $SL_n(\mathcal{O})$”, Amer. J. Math., 105:3 (1983), 673–687 | DOI | MR | Zbl

[59] W. van der Kallen, “$\operatorname{SL}_3(\mathbb{C}[X])$ does not have bounded word length”, Algebraic $K$-theory, Part I (Oberwolfach, 1980), Lecture Notes in Math., 966, Springer, Berlin–New York, 1982, 357–361 | MR | Zbl

[60] R. K. Dennis, L. N. Vaserstein, “On a question of M. Newman on the number of commutators”, J. Algebra, 118:1 (1988), 150–161 | DOI | MR | Zbl

[61] Yu. L. Ershov, S. S. Goncharov, Constructive models, Siberian School Algebra Logic, Consultants Bureau, New York, 2000, xii+293 pp. | MR | Zbl | Zbl

[62] Yu. L. Ershov, “Algoritmicheskie problemy v teorii polei (polozhitelnye aspekty)”, Spravochnaya kniga po matematicheskoi logike, ch. III. Teoriya rekursii, Nauka, M., 1982, 269–353 | MR

[63] J. Denef, “Hilbert's Tenth Problem for quadratic rings”, Proc. Amer. Math. Soc., 48 (1975), 214–220 | DOI | MR | Zbl

[64] J. Denef, “Diophantine sets over algebraic integer rings. II”, Trans. Amer. Math. Soc., 257:1 (1980), 227–236 | DOI | MR | Zbl

[65] T. Pheidas, “Hilbert's Tenth Problem for a class of rings of algebraic integers”, Proc. Amer. Math. Soc., 104:2 (1988), 611–620 | DOI | MR | Zbl

[66] H. N. Shapiro, A. Shlapentokh, “Diophantine relationships between algebraic number fields”, Comm. Pure Appl. Math., 42:8 (1989), 1113–1122 | DOI | MR | Zbl