Диофантовы проблемы в классических матричных группах

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

В этой работе мы исследуем диофантовы проблемы в классических матричных группах $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$, $\mathrm{T}_n(R)$, $\mathrm{UT}_n(R)$, $n \geq 3$, над ассоциативным кольцом с единицей $R$. Мы показываем что если $G_n(R)$ – это одна из выше перечисленных групп, то диофантова проблема в $G_n(R)$ полиномиально по времени эквивалентна (эквивалентна по Карпу) диофантовой проблеме над $R$. В случае, когда $G_n(R)=\mathrm{SL}_n(R)$, мы предполагаем, что кольцо $R$ коммутативно. Аналогичные результаты верны для $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$ в случае если в $R$ нет делителей нуля (для $\mathrm{PGL}_n(R)$, кольцо $R$ необязательно коммутативно).Библиография: 66 наименований.

Об авторах

Алексей Георгиевич Мясников

Stevens Institute of Technology

Email: alexeim@math.mcgill.ca

Махмуд Сохраби

Stevens Institute of Technology

Email: msohrabi@math.carleton.ca

Список литературы

  1. M. Davis, H. Putnam, J. Robinson, “The decision problem for exponential diophantine equations”, Ann. of Math. (2), 74:3 (1961), 425–436
  2. Ю. В. Матиясевич, “Диофантовость перечислимых множеств”, Докл. АН СССР, 191:2 (1970), 279–282
  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.
  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
  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.
  6. J. Denef, L. Lipshitz, “Diophantine sets over some rings of algebraic integers”, J. London Math. Soc. (2), 18:3 (1978), 385–391
  7. A. Garreta, A. Miasnikov, D. Ovchinnikov, The Diophantine problem in finitely generated commutative rings
  8. O. Kharlampovich, A. Myasnikov, “Equations in algebras”, Internat. J. Algebra Comput., 28:8 (2018), 1517–1533
  9. O. Kharlampovich, A. Myasnikov, “Undecidability of equations in free Lie algebras”, Trans. Amer. Math. Soc., 371:4 (2019), 2987–2999
  10. A. Garreta, A. Miasnikov, D. Ovchinnikov, Diophantine problems in rings and algebras: undecidability and reductions to rings of algebraic integers
  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.
  12. Ю. Л. Ершов, “Об элементарных теориях локальных полей”, Алгебра и логика. Семинар, 4:2 (1965), 5–30
  13. J. Ax, S. Kochen, “Diophantine problems over local fields. I”, Amer. J. Math., 87:3 (1965), 605–630
  14. J. Ax, S. Kochen, “Diophantine problems over local fields. III. Decidable fields”, Amer. J. Math., 83:3 (1966), 437–456
  15. А. И. Мальцев, “Конструктивные алгебры. I”, УМН, 16:3(99) (1961), 3–60
  16. M. O. Rabin, “Computable algebra, general theory and theory of computable fields”, Trans Amer. Math. Soc., 95:2 (1960), 341–360
  17. В. А. Романьков, “О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах”, Алгебра и логика, 16:4 (1977), 457–471
  18. M. Duchin, Hao Liang, M. Shapiro, “Equations in nilpotent groups”, Proc. Amer. Math. Soc., 143:11 (2015), 4723–4731
  19. A. Garreta, A. Miasnikov, D. Ovchinnikov, “Diophantine problems in solvable groups”, Bull. Math. Sci., 10:1 (2020), 2050005, 27 pp.
  20. A. Garreta, A. Miasnikov, D. Ovchinnikov, “Full rank presentations and nilpotent groups: structure, Diophantine problem, and genericity”, J. Algebra, 556 (2020), 1–34
  21. E. Rips, Z. Sela, “Canonical representatives and equations in hyperbolic groups”, Invent. Math., 120:3 (1995), 489–512
  22. F. Dahmani, V. Guirardel, “Foliations for solving equations in groups: free, virtually free, and hyperbolic groups”, J. Topol., 3:2 (2010), 343–404
  23. V. Diekert, A. Muscholl, “Solvability of equations in graph groups is decidable”, Internat. J. Algebra Comput., 16:6 (2006), 1047–1069
  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.
  25. M. Casals-Ruiz, I. Kazachkov, “On systems of equations over free products of groups”, J. Algebra, 333:1 (2011), 368–426
  26. V. Diekert, M. Lohrey, “Word equations over graph products”, Internat. J. Algebra Comput., 18:3 (2008), 493–533
  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
  28. Г. С. Маканин, “Уравнения в свободной группе”, Изв. АН СССР. Сер. матем., 46:6 (1982), 1199–1273
  29. Г. С. Маканин, “Разрешимость универсальной и позитивной теорий свободной группы”, Изв. АН СССР. Сер. матем., 48:4 (1984), 735–749
  30. А. А. Разборов, “О системах уравнений в свободной группе”, Изв. АН СССР. Сер. матем., 48:4 (1984), 779–832
  31. А. А. Разборов, О системах уравнений в свободных группах, Дисс. … канд. физ.-матем. наук, МИАН, М., 1987, 154 с.
  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
  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
  34. A. Je.{z}, “Recompression: a simple and powerful technique for word equations”, J. ACM, 63:1 (2016), 4, 51 pp.
  35. A. Je.{z}, Word equations in linear space
  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
  37. L. Ciobanu, M. Elder, The complexity of solution sets to equations in hyperbolic groups
  38. А. И. Мальцев, “Об элементарных свойствах линейных групп”, Некоторые проблемы математики и механики, Новосибирск, 1961, 110–132
  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
  40. Е. И. Бунина, “Элементарная эквивалентность унитарных линейных групп над полями”, Фундамент. и прикл. матем., 4:4 (1998), 1265–1278
  41. Е. И. Бунина, “Элементарная эквивалентность унитарных линейных групп над кольцами и телами”, УМН, 53:2(320) (1998), 137–138
  42. Е. И. Бунина, “Элементарная эквивалентность групп Шевалле”, УМН, 56:1(337) (2001), 157–158
  43. Е. И. Бунина, “Элементарная эквивалентность групп Шевалле над локальными кольцами”, Матем. сб., 201:3 (2010), 3–20
  44. Е. И. Бунина, “Изоморфизмы и элементарная эквивалентность групп Шевалле над коммутативными кольцами”, Матем. сб., 210:8 (2019), 3–28
  45. Е. И. Бунина, А. В. Михалев, А. Г. Пинус, Элементарная и близкие к ней логические эквивалентности классических и универсальных алгебр, МЦНМО, М., 2015, 360 с.
  46. O. V. Belegradek, “The model theory of unitriangular groups”, Ann. Pure App. Logic, 68:3 (1994), 225–261
  47. A. Myasnikov, M. Sohrabi, On groups elementarily equivalent to a group of triangular matrices $T_n(R)$
  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)$, $ngeq 3$
  49. N. Avni, A. Lubotsky, C. Meiri, “First order rigidity of non-uniform higher rank arithmetic groups”, Invent. Math., 217:1 (2019), 219–240
  50. А. И. Мальцев, “Об одном соответствии между кольцами и группами”, Матем. сб., 50(92):3 (1960), 257–266
  51. D. Marker, Model theory. An introduction, Grad. Texts in Math., 217, Springer-Verlag, New York, 2010, viii+342 pp.
  52. A. Prestel, P. Roquette, Formally $p$-adic fields, Lecture Notes in Math., 1050, Springer-Verlag, Berlin, 1984, v+167 pp.
  53. A. H. Lachlan, E. W. Madison, “Computable fields and arithmetically definable ordered fields”, Proc. Amer. Math. Soc., 24:4 (1970), 803–807
  54. E. W. Madison, “A note on computable real fields”, J. Symb. Log., 35:2 (1970), 239–241
  55. Ю. Л. Ершов, Проблемы разрешимости и конструктивные модели, Математическая Логика и Основания Математики, Наука, М., 1980, 416 с.
  56. А. Г. Мясников, В. Н. Ремесленников, “Рекурсивные $p$-адические числа и элементарные теории конечно порожденных про-$p$-групп”, Изв. АН СССР. Сер. матем., 51:3 (1987), 613–634
  57. М. И. Каргаполов, Ю. И. Мерзляков, Основы теории групп, Наука, М., 1972, 240 с.
  58. D. Carter, G. Keller, “Bounded elementary generation of $SL_n(mathcal{O})$”, Amer. J. Math., 105:3 (1983), 673–687
  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
  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
  61. С. С. Гончаров, Ю. Л. Ершов, Конструктивные модели, Сибирская Школа Алгебры и Логики, Научная книга (НИИ МИОО НГУ), Новосибирск, 1999, xii+360 с.
  62. Ю. Л. Ершов, “Алгоритмические проблемы в теории полей (положительные аспекты)”, Справочная книга по математической логике, ч. III. Теория рекурсии, Наука, М., 1982, 269–353
  63. J. Denef, “Hilbert's Tenth Problem for quadratic rings”, Proc. Amer. Math. Soc., 48 (1975), 214–220
  64. J. Denef, “Diophantine sets over algebraic integer rings. II”, Trans. Amer. Math. Soc., 257:1 (1980), 227–236
  65. T. Pheidas, “Hilbert's Tenth Problem for a class of rings of algebraic integers”, Proc. Amer. Math. Soc., 104:2 (1988), 611–620
  66. H. N. Shapiro, A. Shlapentokh, “Diophantine relationships between algebraic number fields”, Comm. Pure Appl. Math., 42:8 (1989), 1113–1122

© Мясников А.Г., Сохраби М., 2021

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах