The Diophantine problem in the classical matrix groups
- Authors: Myasnikov A.G.1, Sohrabi M.1
-
Affiliations:
- Stevens Institute of Technology
- Issue: Vol 85, No 6 (2021)
- Pages: 205-244
- Section: Articles
- URL: https://journals.rcsi.science/1607-0046/article/view/133868
- DOI: https://doi.org/10.4213/im9104
- ID: 133868
Cite item
Abstract
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 \geq 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).
About the authors
Aleksei Georgievich Myasnikov
Stevens Institute of Technology
Email: alexeim@math.mcgill.ca
Mahmood Sohrabi
Stevens Institute of Technology
Email: msohrabi@math.carleton.ca
References
- M. Davis, H. Putnam, J. Robinson, “The decision problem for exponential diophantine equations”, Ann. of Math. (2), 74:3 (1961), 425–436
- Ю. В. Матиясевич, “Диофантовость перечислимых множеств”, Докл. АН СССР, 191:2 (1970), 279–282
- 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.
- 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
- 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.
- J. Denef, L. Lipshitz, “Diophantine sets over some rings of algebraic integers”, J. London Math. Soc. (2), 18:3 (1978), 385–391
- A. Garreta, A. Miasnikov, D. Ovchinnikov, The Diophantine problem in finitely generated commutative rings
- O. Kharlampovich, A. Myasnikov, “Equations in algebras”, Internat. J. Algebra Comput., 28:8 (2018), 1517–1533
- O. Kharlampovich, A. Myasnikov, “Undecidability of equations in free Lie algebras”, Trans. Amer. Math. Soc., 371:4 (2019), 2987–2999
- A. Garreta, A. Miasnikov, D. Ovchinnikov, Diophantine problems in rings and algebras: undecidability and reductions to rings of algebraic integers
- A. Tarski, A decision method for elementary algebra and geometry, 2nd ed., Univ. of California Press, Berkeley–Los Angeles, CA, 1951, iii+63 pp.
- Ю. Л. Ершов, “Об элементарных теориях локальных полей”, Алгебра и логика. Семинар, 4:2 (1965), 5–30
- J. Ax, S. Kochen, “Diophantine problems over local fields. I”, Amer. J. Math., 87:3 (1965), 605–630
- J. Ax, S. Kochen, “Diophantine problems over local fields. III. Decidable fields”, Amer. J. Math., 83:3 (1966), 437–456
- А. И. Мальцев, “Конструктивные алгебры. I”, УМН, 16:3(99) (1961), 3–60
- M. O. Rabin, “Computable algebra, general theory and theory of computable fields”, Trans Amer. Math. Soc., 95:2 (1960), 341–360
- В. А. Романьков, “О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах”, Алгебра и логика, 16:4 (1977), 457–471
- M. Duchin, Hao Liang, M. Shapiro, “Equations in nilpotent groups”, Proc. Amer. Math. Soc., 143:11 (2015), 4723–4731
- A. Garreta, A. Miasnikov, D. Ovchinnikov, “Diophantine problems in solvable groups”, Bull. Math. Sci., 10:1 (2020), 2050005, 27 pp.
- A. Garreta, A. Miasnikov, D. Ovchinnikov, “Full rank presentations and nilpotent groups: structure, Diophantine problem, and genericity”, J. Algebra, 556 (2020), 1–34
- E. Rips, Z. Sela, “Canonical representatives and equations in hyperbolic groups”, Invent. Math., 120:3 (1995), 489–512
- F. Dahmani, V. Guirardel, “Foliations for solving equations in groups: free, virtually free, and hyperbolic groups”, J. Topol., 3:2 (2010), 343–404
- V. Diekert, A. Muscholl, “Solvability of equations in graph groups is decidable”, Internat. J. Algebra Comput., 16:6 (2006), 1047–1069
- 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.
- M. Casals-Ruiz, I. Kazachkov, “On systems of equations over free products of groups”, J. Algebra, 333:1 (2011), 368–426
- V. Diekert, M. Lohrey, “Word equations over graph products”, Internat. J. Algebra Comput., 18:3 (2008), 493–533
- 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
- Г. С. Маканин, “Уравнения в свободной группе”, Изв. АН СССР. Сер. матем., 46:6 (1982), 1199–1273
- Г. С. Маканин, “Разрешимость универсальной и позитивной теорий свободной группы”, Изв. АН СССР. Сер. матем., 48:4 (1984), 735–749
- А. А. Разборов, “О системах уравнений в свободной группе”, Изв. АН СССР. Сер. матем., 48:4 (1984), 779–832
- А. А. Разборов, О системах уравнений в свободных группах, Дисс. … канд. физ.-матем. наук, МИАН, М., 1987, 154 с.
- 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
- 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
- A. Je.{z}, “Recompression: a simple and powerful technique for word equations”, J. ACM, 63:1 (2016), 4, 51 pp.
- A. Je.{z}, Word equations in linear space
- 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
- L. Ciobanu, M. Elder, The complexity of solution sets to equations in hyperbolic groups
- А. И. Мальцев, “Об элементарных свойствах линейных групп”, Некоторые проблемы математики и механики, Новосибирск, 1961, 110–132
- 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
- Е. И. Бунина, “Элементарная эквивалентность унитарных линейных групп над полями”, Фундамент. и прикл. матем., 4:4 (1998), 1265–1278
- Е. И. Бунина, “Элементарная эквивалентность унитарных линейных групп над кольцами и телами”, УМН, 53:2(320) (1998), 137–138
- Е. И. Бунина, “Элементарная эквивалентность групп Шевалле”, УМН, 56:1(337) (2001), 157–158
- Е. И. Бунина, “Элементарная эквивалентность групп Шевалле над локальными кольцами”, Матем. сб., 201:3 (2010), 3–20
- Е. И. Бунина, “Изоморфизмы и элементарная эквивалентность групп Шевалле над коммутативными кольцами”, Матем. сб., 210:8 (2019), 3–28
- Е. И. Бунина, А. В. Михалев, А. Г. Пинус, Элементарная и близкие к ней логические эквивалентности классических и универсальных алгебр, МЦНМО, М., 2015, 360 с.
- O. V. Belegradek, “The model theory of unitriangular groups”, Ann. Pure App. Logic, 68:3 (1994), 225–261
- A. Myasnikov, M. Sohrabi, On groups elementarily equivalent to a group of triangular matrices $T_n(R)$
- 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)$, $ngeq 3$
- N. Avni, A. Lubotsky, C. Meiri, “First order rigidity of non-uniform higher rank arithmetic groups”, Invent. Math., 217:1 (2019), 219–240
- А. И. Мальцев, “Об одном соответствии между кольцами и группами”, Матем. сб., 50(92):3 (1960), 257–266
- D. Marker, Model theory. An introduction, Grad. Texts in Math., 217, Springer-Verlag, New York, 2010, viii+342 pp.
- A. Prestel, P. Roquette, Formally $p$-adic fields, Lecture Notes in Math., 1050, Springer-Verlag, Berlin, 1984, v+167 pp.
- A. H. Lachlan, E. W. Madison, “Computable fields and arithmetically definable ordered fields”, Proc. Amer. Math. Soc., 24:4 (1970), 803–807
- E. W. Madison, “A note on computable real fields”, J. Symb. Log., 35:2 (1970), 239–241
- Ю. Л. Ершов, Проблемы разрешимости и конструктивные модели, Математическая Логика и Основания Математики, Наука, М., 1980, 416 с.
- А. Г. Мясников, В. Н. Ремесленников, “Рекурсивные $p$-адические числа и элементарные теории конечно порожденных про-$p$-групп”, Изв. АН СССР. Сер. матем., 51:3 (1987), 613–634
- М. И. Каргаполов, Ю. И. Мерзляков, Основы теории групп, Наука, М., 1972, 240 с.
- D. Carter, G. Keller, “Bounded elementary generation of $SL_n(mathcal{O})$”, Amer. J. Math., 105:3 (1983), 673–687
- 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
- R. K. Dennis, L. N. Vaserstein, “On a question of M. Newman on the number of commutators”, J. Algebra, 118:1 (1988), 150–161
- С. С. Гончаров, Ю. Л. Ершов, Конструктивные модели, Сибирская Школа Алгебры и Логики, Научная книга (НИИ МИОО НГУ), Новосибирск, 1999, xii+360 с.
- Ю. Л. Ершов, “Алгоритмические проблемы в теории полей (положительные аспекты)”, Справочная книга по математической логике, ч. III. Теория рекурсии, Наука, М., 1982, 269–353
- J. Denef, “Hilbert's Tenth Problem for quadratic rings”, Proc. Amer. Math. Soc., 48 (1975), 214–220
- J. Denef, “Diophantine sets over algebraic integer rings. II”, Trans. Amer. Math. Soc., 257:1 (1980), 227–236
- T. Pheidas, “Hilbert's Tenth Problem for a class of rings of algebraic integers”, Proc. Amer. Math. Soc., 104:2 (1988), 611–620
- H. N. Shapiro, A. Shlapentokh, “Diophantine relationships between algebraic number fields”, Comm. Pure Appl. Math., 42:8 (1989), 1113–1122