Известия Российской академии наук. Серия математическая
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Изв. РАН. Сер. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Известия Российской академии наук. Серия математическая, 2021, том 85, выпуск 6, страницы 205–244
DOI: https://doi.org/10.4213/im9104
(Mi im9104)
 

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

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

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

Mathematical Department, Stevens Institute of Technology, Hoboken, USA
Список литературы:
Аннотация: В этой работе мы исследуем диофантовы проблемы в классических матричных группах $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$, $\mathrm{T}_n(R)$, $\mathrm{UT}_n(R)$, $n \geqslant 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 наименований.
Ключевые слова: диофантовы проблемы, уравнения, классические матричные группы, разрешимость, неразрешимость.
Поступило в редакцию: 11.09.2020
Исправленный вариант: 21.02.2021
Англоязычная версия:
Izvestiya: Mathematics, 2021, Volume 85, Issue 6, Pages 1220–1256
DOI: https://doi.org/10.1070/IM9104
Реферативные базы данных:
Тип публикации: Статья
УДК: 512.54.0
MSC: 03C60

§ 1. Введение

Напомним, что диофантова проблема, обозначаемая $\mathcal{D}(\mathcal{A})$ (также называемая десятой проблемой Гильберта или обобщенной десятой проблемой Гильберта), в счетной алгебраической структуре $\mathcal{A}$ ставит вопрос о том, существует ли алгоритм, который для данной конечной системы уравнений $S$ над структурой $\mathcal{A}$ определяет, имеет ли система $S$ решения в $\mathcal{A}$ или нет. В частности, если $R$ является конечно порожденным кольцом, диофантова проблема ставит вопрос, существует ли алгоритм, который по данной конечной системе полиномиальных уравнений отвечает, имеет ли она решения в $R$ или нет. Здесь подразумевается, что в кольце $R$ зафиксирована некоторая нумерация элементов, т. е. функция $\nu\colon \mathbb{N} \to R$. В этом случае мы можем пронумеровать все некоммутативные полиномы из $R\langle x_1, x_2, \dots \rangle$ (со счетным количеством переменных $x_1, x_2, \dots$), а также все конечные системы, состоящие из полиномиальных уравнений $p(x_1, \dots,x_n) = 0$, где $p(x_1, \dots,x_n) \in R\langle x_1, x_2, \dots \rangle$. Поэтому такие системы уравнений могут рассматриваться как входные данные для различных алгоритмов. В случае, когда $R$ коммутативно, достаточно рассматривать коммутативные многочлены из $R[x_1,x_2, \dots]$. Исходная версия диофантовой проблемы была сформулирована Гильбертом для кольца целых чисел $\mathbb{Z}$. В 1970 г. Матиясевич, основываясь на работах Дэвиса, Патнема и Робинсон [1], доказал, что диофантова проблема над целыми числами неразрешима [2].

После этого диофантовы проблемы изучались во многих коммутативных кольцах $R$, где неразрешимость диофантовой проблемы над $R$ обычно доказывается сведением $\mathcal{D}(\mathbb{Z})$ к $\mathcal{D}(R)$. По определению диофантова проблема над структурой $\mathcal{A}$ сводима к диофантовой проблеме над $\mathcal{B}$, если существует алгоритм (называемый сводящим или редуцирующим), который по данной системе уравнений $S$ над $\mathcal{A}$ строит систему уравнений $S^*$ над $\mathcal{B}$ такую, что $S$ имеет решение в $\mathcal{A}$ тогда и только тогда, когда $S^*$ имеет решение в $\mathcal{B}$. В таком случае мы пишем $\mathcal{D}(\mathcal{A}) \leqslant \mathcal{D}(\mathcal{B})$. Если сводящий алгоритм работает за полиномиальное время, то редукция называется полиномиальной (или редукцией Карпа). Таким образом, приведенные выше результаты о том, что диофантовы проблемы в $G_n (R)$ и $R$ полиномиально эквивалентны по времени, в точности означают, что $\mathcal {D}(G_n (R))$ и $\mathcal{D}(R)$ сводятся друг к другу за полиномиальное время. В частности, они либо обe разрешимы, либо обe неразрешимы. Уравнениям в коммутативных кольцах посвящено много исследований. Тем не менее, диофантова проблема остается открытой в $\mathbb Q$ и полях $F$, которые являются конечными алгебраическими расширениями $\mathbb Q$. О диофантовой проблеме в кольцах целых алгебраических чисел $\mathcal{O}$ полей $F$ известно гораздо больше. А именно, было показано, что $\mathcal{D} (\mathbb Z)$ сводится к $\mathcal{D}(\mathcal{O})$ для некоторых колец алгебраических чисел $\mathcal{O}$, следовательно, в таких $\mathcal{O}$ диофантова проблема $\mathcal{D}(\mathcal{O}) $ неразрешима. Мы отсылаем читателя к работам [3]–[5] за дополнительной информацией о диофантовой проблеме в различных кольцах и полях теоретико-числового типа. Существуют давние открытые гипотезы (см., например, [6], [4]), которые утверждают, что диофантовы проблемы во всех кольцах $\mathbb{Q}, F $ и $\mathcal{O}$, описанных выше, неразрешимы. Для нашей статьи важен следующий результат. Если коммутативное унитарное кольцо $R$ бесконечно и конечно порождено, то в случае положительной характеристики $\mathcal{D}(R)$ неразрешима, а в случае нулевой характеристики существует кольцо целых алгебраических чисел $\mathcal{O}$ такое, что $\mathcal{D}(\mathcal{O})$ за полиномиальное время сводится к $\mathcal{D}(R)$ (докторская диссертация Кирстен Эйзентрегер (теорема 7.1), которая доступна на ее веб-сайте, см. также [7]).

В классе некоммутативных ассоциативных колец Харлампович и Мясников недавно показали (см. [8]), что диофантова проблема неразрешима в свободных ассоциативных алгебрах над полями и в групповых алгебрах для большого разнообразия групп без кручения, в том числе, для торальных относительно гиперболических групп, частично коммутативных групп (прямоугольных групп Артина), коммутативно транзитивных групп и фундаментальных групп различных графов групп. Для неассоциативных колец ими же доказано, что диофантова проблема неразрешима в свободных алгебрах Ли ранга не меньше трех с коэффициентами в произвольной области целостности [9]. Общий подход к диофантовой проблеме в некоммутативных кольцах (через редукции к коммутативным) был разработан Гарретой, Мясниковым и Овчинниковым в [10].

В другом направлении, идущем из теории моделей, было показано, что теории первого порядка некоторых классических полей разрешимы: Тарский доказал это для комплексных чисел $\mathbb{C} $ и вещественных чисел $ \mathbb {R} $ [11], а Ершов, Ax и Кочен – для $p$-адических чисел $ \mathbb {Q}_p $ и $ \mathbb {Z}_p $ [12]–[14]. Утверждение, что данная конечная система уравнений имеет решение в кольце $ R $, может быть представлено очень конкретной экзистенциальной формулой (положительно-примитивной формулой) с коэффициентами в $ R $, поэтому диофантова проблема является частью теории $ R $ первого порядка, но при этом используются такие коэффициенты, что усложняет всю картину. Фактически, использование констант сильно отличает диофантовы проблемы от классических теоретико-модельных проблем элементарной эквивалентности и разрешимости теорий первого порядка в стандартных языках групп или колец. Мы остановимся на этом подробнее позже, когда будем рассматривать группы матриц над классическими полями.

Подобно диофантовой проблеме в кольцах, если структура $ \mathcal{A} $ счетна или конечна, то мы предполагаем, что она снабжена нумерацией $ \nu\colon \mathbb {N} \to \mathcal{A} $, которая позволяет перечислить все термы на языке $ \mathcal{A} $ с константами в $ \mathcal{A} $, следовательно, все уравнения (которые в данном случае представлены равенствами двух термов), а также все конечные системы уравнений над $ \mathcal{A} $. С другой стороны, если $ \mathcal{A} $ несчетна, то по определению нужно рассматривать только уравнения с константами из некоторого фиксированного счетного (или конечного) подмножества $ C $ в $ \mathcal{A} $. Обозначим эту форму диофантовой проблемы через $\mathcal{D}_C(\mathcal{A}) $. Эта модификация позволяет более точно и единообразно рассматривать диофантовы проблемы над произвольными структурами. Как мы увидим ниже, может случиться так, что диофантова проблема $ \mathcal{D}_C(\mathcal{A}) $ разрешима для одного подмножества $ C \subseteq \mathcal{A} $ и неразрешима для другого, даже в счетных структурах $ \mathcal{A} $. Легко видеть, что для счетного (или конечного) подмножества $ C $ в $ \mathcal{A} $ диофантовы проблемы $ \mathcal{D}_C (\mathcal{A}) $ и $ \mathcal{D}_{\langle C \rangle} (\mathcal{A}) $ сводятся друг к другу, где $ \langle C \rangle $ – это подструктура, порожденная $ C $ в $ \mathcal{A} $ (см. § 3). Кроме того, если $ \mathcal{D}_C(\mathcal{A}) $ разрешима, то структура $ \langle C \rangle $ вычислима (рекурсивна, конструктивна) в смысле Мальцева [15] и Рабина [16]. Однако обратное, вообще говоря, неверно. В § 7 изучается разрешимость диофантовой проблемы для классических несчетных колец $ \mathbb {C}$, $\mathbb {R}$, $\mathbb {Q}_p$, $\mathbb {Z}_p $ относительно различных множеств констант $ C $. Отметим, что $ \mathcal{D}_C (\mathbb{C}) $ разрешимо тогда и только тогда, когда подполе $ \langle C \rangle $ вычислимо, а в $ \mathbb{R} $, $\mathbb{Q}_p $ и $ \mathbb{Z}_p $ разрешимость диофантовой проблемы опять же зависит от подмножества $ C $ и тесно связана с вычислимыми действительными числами и вычислимыми $p$-адическими числами.

Исследования систем уравнений и их разрешимости в группах имеют очень долгую историю. Они восходят к 1912 г., когда Ден начал основополагающие работы по проблемам равенства слов и сопряженности в конечно определенных группах. Напомним, что уравнение в группе $G$ – это выражение типа $ w(x_1, \dots, x_n, g_1, \dots, g_m) = 1 $, где $ w $ – групповое слово от переменных $ x_1, \dots, x_n $ и констант $ g_1, \dots, g_m \in G $. В настоящее время существуют два основных подхода к решению диофантовых проблем в группах. В первом подходе для заданной фиксированной группы $G$ пытаются найти коммутативное кольцо $ A $ с единицей такое, что диофантова проблема в $ A $ алгоритмически сводится к диофантовой проблеме в $G$. В этом случае, если $ \mathcal{D}(A) $ неразрешима, то $ \mathcal{D}(G) $ также неразрешима. Первый принципиальный результат в этом ключе принадлежит Романькову, который показал неразрешимость диофантовой проблемы в любой неабелевой свободной нильпотентной группе $ N $ класса нильпотентности не менее $ 9 $ (он доказал, что $ \mathcal {D}(\mathbb{Z}) \leqslant \mathcal{D}(N) $, даже если рассматривать только одиночные уравнения в группе $ N $) [17]. Недавно Дучин, Лян и Шапиро показали в [18], что $ \mathcal{D}(\mathbb{Z}) \leqslant \mathcal {D}(N) $ для любой неабелевой свободной нильпотентной группы $ N $, следовательно, $ \mathcal {D}(N) $ неразрешима. Далеко идущие обобщения этих результатов были получены Гарретой, Мясниковым и Овчинниковым в [19], где они доказали, что для любой конечно порожденной не почти абелевой нильпотентной группы $G$ существует кольцо целых алгебраических чисел $ \mathcal{O} $ (зависящее от $G$), которое интерпретируется уравнениями в $G$, следовательно, $ \mathcal{D}(\mathcal{O}) $ сводится по Карпу к $ \mathcal{D}(G)$. Кроме того, теми же авторами в [20] было установлено общее достаточное условие для того, чтобы это кольцо $ \mathcal{O} $ было изоморфно $ \mathbb {Z} $, так что в этом случае диофантова проблема в $G$ неразрешима. В частности, оказалось, что случайная нильпотентная группа $G$ (заданная случайным представлением в многообразии $ \mathcal{N}_c $ нильпотентных групп класса не выше $ c $ для любого $ c \geqslant 2 $ ) имеет кольцо $ \mathcal{O}$ изоморфное $\mathbb{Z} $, что влечет неразрешимость диофантовой проблемы в $G$. Эти результаты о нильпотентных группах допускают многочисленные приложения к диофантовым проблемам в ненильпотентных группах $ H $, либо с помощью подходящих диофантовых нильпотентных подгрупп в $ H $, либо с помощью подходящих диофантовых нильпотентных факторов группы $ H $ [19]. Например, этот метод позволяет показать, что диофантова проблема в любой конечно порожденной свободной разрешимой неабелевой группе неразрешима.

Картина кардинально меняется во втором подходе, где пытаются показать, что диофантова проблема в данной группе $G$ разрешима, сводя ее к диофантовой проблеме в неабелевой свободной группе $F$ или свободном моноиде $ M $ (см. статьи Рипса и Селы [21], Дамани и Гирарделя [22], Дикертa и Мушол [23], Казалс–Руис и Казачкова [24], [25] и Дикерта и Лоре [26]). Мы ссылаемся на обзор в [27], где можно найти дальнейшие сведения о достижениях в этой области. Фундаментальные результаты здесь принадлежат Маканину [28], [29] и Разборову [30], [31], которые показали, что диофантовы проблемы $ \mathcal{D}(M) $ и $ \mathcal{D}(F) $ разрешимы и, в случае свободной группы $F$, дополнительно дали описание множеств решений произвольных конечных систем уравнений в терминах диаграмм Маканина–Разборова. Другое описание множеств решений систем в $F$ в терминах систем $\mathrm{NTQ}$ (также называемых $\omega$-резидуальными свободными башнями) было дано в [32]. Системы $\mathrm{NTQ}$ дают эффективный подход к алгебраической геометрии и теории моделей свободных групп. Недавно в серии статей [33]–[37] был разработан совершенно другой метод решения уравнений в свободных группах, свободных моноидах и гиперболических группах.

В своей классической работе [38] Мальцев изучал элементарную эквивалентность матричных групп $ G_n (F) $, где $ G_n \in \{\mathrm{GL}_n, \mathrm{SL}_n, \mathrm{PGL}_n, \mathrm{PSL}_n \} $, $ n \geqslant 3 $, и $F$ – это поле. А именно, он показал, что $ G_n (F) \equiv G_m (L) $ тогда и только тогда, когда $ n = m $ и $ F \equiv L $. Его доказательство было основано на двух основных результатах. Первый утверждает, что для любого целого числа $ k \geqslant 3 $ и любого $ G_n $, описанного выше, существует предложение $ \Phi_ {k, G} $ теории групп, такое, что для любого $ n $ и поля $F$, $ \Phi_ {k, G} $ выполняется в $ G_n(F) $ тогда и только тогда, когда $ k = n $. Согласно второму результату, $F$ и $ G_n(F) $ взаимно интерпретируемы друг в друге. Точнее, группа $ G_n (F) $ абсолютно (т. е. без использования параметров) интерпретируема в $F$, а $F$ интерпретируемо в $ G_n(F) $ равномерно относительно некоторого определимого в языке теории групп подмножества кортежей параметров. Отсюда следует, что теории $ \mathrm{Th}(F) $ и $ \mathrm{Th}(G_n(F)) $ сводятся друг к другу за полиномиальное время, следовательно, $\mathrm{Th} (G_n (F)) $ разрешима тогда и только тогда, когда $ \mathrm{Th}(F) $ разрешима. Позже Бейдар и Михалев предложили другой подход к элементарной эквивалентности классических матричных групп [39], основанный на теореме Кейслера–Шелаха (две структуры элементарно эквивалентны тогда и только тогда, когда их ультрастепени над неглавными ультрафильтрами изоморфны) и описании абстрактных изоморфизмов групп типа $ G_n(F) $. Бунина распространила их результаты на унитарные линейные группы и группы Шевалле [40]–[44]. Мы ссылаемся на недавнюю книгу [45] для исчерпывающего описания этих и некоторых других результатов в этой области. Тут важно отметить, что во всех приведенных выше результатах теории первого порядка включают только стандартные константы языка теории групп (константа 1) и теории колец с единицей (константы $0$ и $1$). Теория моделей группы $\mathrm{UT}_n(R) $, где $ n \geqslant 3 $, а $ R $ – произвольное ассоциативное кольцо с единицей, подробно изучена Белеградком (см. [46]). Здесь он существенно использовал тот факт, что кольцо $ R $ интерпретируется (с параметрами) в группе $ \mathrm{UT}_n(R) $. Авторы данной статьи изучали теорию моделей групп $ \mathrm{SL}_n(\mathcal{O}) $, $ \mathrm{GL}_n(\mathcal{O}) $ и $\mathrm{T}_n(\mathcal{O}) $ для полей и колец целых алгебраических чисел $\mathcal{O}$ в работах [47], [48]. Их метод опять же использует взаимную интерпретируемость (а также би-интерпретируемость) матричной группы и соответствующего кольца. Аналогичным образом Авни, Любоцкий и Мейри изучали элементарную эквивалентность неоднородных арифметических групп высокого ранга [49]. Недавно Сигал и Тент показали, что для групп Шевалле $ G (R) $ ранга не менее $ 2 $ над кольцом $ R $, если $ G (R) $ имеет конечную элементарную ширину, то $ G (R) $ и $ R $ би-интерпретируемы друг в друге. Хотя все приведенные выше теоретико-модельные результаты идейно близки к изучению диофантовых проблем, тем не менее, они не могут напрямую применяться при исследовании уравнений в соответствующих группах. Действительно, чтобы связать диофантовы проблемы в кольце $R$ с диофантовыми проблемами в группах $ G_n (R) $ или $ G (R) $, нужно иметь взаимную интерпретируемость уравнениями, а не произвольными формулами первого порядка. Именно такую интерпретируемость мы и строим в данной статье для $R$ и $G_n(R)$. Напомним, что подмножество (в частности, подгруппа) $\mathrm{H}$ группы $G$ является диофантовым в $G$, если оно определимо в $G$ формулой типа

$$ \begin{equation*} \Phi (x) = \exists \, y_1 \dots \exists \, y_n \bigwedge_ {i = 1}^k w_i(x, y_1, \dots, y_n) = 1, \end{equation*} \notag $$
где $ w_i(x, y_1, \dots, y_n) $ – групповое слово от переменных $ x , y_1, \dots, y_n $. Такие формулы называются диофантовыми (в теории чисел) или положительно-примитивными (в теории моделей). Следуя [19], мы говорим, что структура $ \mathcal A $ e-интерпретируема (или интерпретируема уравнениями, или диофантово интерпретируема) в структуре $ \mathcal B $, если $ \mathcal A $ интерпретируема (см. § 3) в $ \mathcal B $ диофантовыми формулами. Суть этого определения заключается в том, что если $ \mathcal A $ является e-интерпретируемой в $ \mathcal B $, то диофантова проблема в $ \mathcal A $ за полиномиальное время сводится к диофантовой проблеме в $ \mathcal B $. С одной стороны, получить e-интерпретируемость труднее, чем просто интерпретируемость, поскольку в последней можно использовать произвольные формулы первого порядка, а не только диофантовы, но, с другой стороны, для изучения элементарной эквивалентности структур, произвольные константы (параметры из данных структур) не используются, поскольку не входят в сигнатуру, в то время как в диофантовых задачах константы не только разрешены, но и необходимы.

Подгруппа $ G \leqslant \mathrm{GL}_n(R) $ называется большой, если она содержит подгруппу $ \mathrm{E}_n(R) $, порожденную в $ \mathrm{GL}_n(R) $ всеми трансвекциями $ t_{ij} (\alpha) $, $ i \neq j $ и $ \alpha \in R $. В частности, подгруппы $ \mathrm{SL}_n(R) $ (когда $ R $ коммутативно) и $ \mathrm{E}_n(R) $ – большие. Введение больших подгрупп в $ \mathrm{GL}_n(R) $ позволяет унифицировать похожие аргументы, иначе используемые отдельно для каждой из групп $ \mathrm{GL}_n (R) $, $ \mathrm{SL}_n (R) $ и $ \mathrm{E}_n (R) $. Это еще раз подчеркивает тот факт, что наш метод, в отличие от метода, использованного в статье Мальцева [38], основан исключительно на трансвекциях и нильпотентных подгруппах. Ниже через $\mathrm{T}_{ij} $ мы обозначаем однопараметрическую подгруппу $ \{t_{ij} (\alpha) \mid \alpha \in R \} $ группы $ \mathrm{GL}_n (R)$.

В § 4 изучаются диофантовы подгруппы больших подгрупп $G$ в $ \mathrm{GL}_n (R) $, в частности, доказывается следующий ключевой технический результат.

Теорема 4.1. Пусть $G$ – большая подгруппа в $ \mathrm{GL}_n(R) $, $ n \geqslant 3 $. Тогда для любых $ 1 \leqslant k \neq m \leqslant n $ однопараметрическая подгруппа $ \mathrm{T}_{km} $ диофантова в $G$ (определена при помощи констант из множества $ \{t_{ij}(1) \mid 1 \leqslant i \neq j \leqslant n \} $).

Как следствие, нетрудно увидеть, что нильпотентная подгруппа $ \mathrm{UT}_n (R) $ также диофантова в $G$. Аналогичные результаты справедливы для больших подгрупп в $ \mathrm{PGL}_n (R) $ (это образы больших подгрупп в $ \mathrm{GL}_n(R) $ при канонической проекции $\mathrm{GL}_n(R) \to \mathrm{PGL}_n(R)$) при условии, что кольцо $ R $ не имеет делителей нуля (см. п. 4.3). В частности, такие же результаты верны для $ \mathrm{PSL}_n(R) $, но в этом случае предполагается, что кольцо $ R $ также еще и коммутативно.

Аналогичный подход работает и для групп $ \mathrm{T}_n(R) $ и $ \mathrm{UT}_n (R) $, $ n \geqslant 3 $, фактически для любых больших подгрупп в $ \mathrm{T}_n (R) $. Здесь мы называем подгруппу $G$ в $ \mathrm{T}_n (R) $ большой, если она содержит $ \mathrm{UT}_n (R) $. Следующий результат напоминает теорему 4.1, однако, поскольку $ \mathrm{T}_n (R) $ имеет только трансвекции типа $ t_{ij}(\alpha)$, где $ i <j $, то доказательство немного сложнее и результат немного слабее, чем в $ \mathrm{GL}_n (R) $. Хотя этого достаточно для всех наших целей. Ниже через $ R_G $ мы обозначаем множество (фактически, подгруппу) всех скалярных матриц из $\mathrm{GL}_n (R) $, принадлежащих $G$.

Теорема 5.1. Пусть $G$ – большая подгруппа в $\mathrm{T}_n(R)$, $n \geqslant 3$. Тогда верны следующие утверждения:

1) для всех $1\leqslant i, j \leqslant n$ таких, что $j-i \geqslant 2$ подгруппа $\mathrm{T}_{ij}$ диофантова в $G$;

2) для всех $1 \leqslant i < n$ подгруппа $R_G \mathrm{T}_{i,i+1}\mathrm{T}_{1n}$ диофантова в $G$.

Заметим, что в случае $ G = \mathrm{UT}_n (R) $ наши аргументы следуют соображениям, изложенным в [46].

Теперь, используя диофантовость подгрупп $ \mathrm{T}_{ij} $ в теореме 4.1 и подгрупп $ \mathrm{T}_{ij} $ и $ R_G \mathrm{T}_{i, i + 1} \mathrm{T}_{1n} $ в теореме 5.1, а также идеи Мальцева из [50], можно e-интерпретировать кольцо $ R $ в больших подгруппах $G$ в $ \mathrm{GL}_n (R) $ и $ \mathrm{T}_n (R) $, а также в больших подгруппах $ \mathrm{PGL}_n (R) $, при условии, что кольцо $ R $ не имеет делителей нуля (см. теорему 6.1). Мы делаем это в § 6 и резюмируем в следующем следствии.

Следствие 6.4. Кольцо $R$ e-интерпретируемо в $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$ (если $R$ коммутативно), $\mathrm{E}_n(R)$, $\mathrm{T}_n(R)$ и $\mathrm{UT}_n(R)$, где $n \geqslant 3$. Если в $R$ нет делителей нуля, то $R$ также e-интерпретируемо в $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$ (как и раньше, $R$ предполагается коммутативным в этом случае).

Следствие 6.4 показывает, что диофантова проблема в $ R $ полиномиально сводится к диофантовой проблеме для каждой из упомянутых там групп. Чтобы показать обратное (за исключением $ \mathrm{E}_n (R) $), нам понадобится следующий результат (см. § 6), который, как мы полагаем, известен в фольклоре.

Предложение 6.6. Группы $ \mathrm{GL}_n (R) $, $ \mathrm{T}_n (R) $ и $ \mathrm{UT}_n (R) $ e-интерпретируемы в $ R $. Если кольцо $ R $ коммутативно, то группы $ \mathrm{PGL}_n (R) $, $ \mathrm{SL}_n (R) $ и $ \mathrm{PSL}_n (R) $ также e-интерпретируемы в $ R $.

Здесь уместно сделать несколько замечаний по поводу ограничений на кольцо $ R$, которые мы накладываем в результатах выше. Для $ \mathrm{SL}_n (R) $ мы предполагаем, что $ R $ коммутативно только для удобства определения. В принципе, можно расширить полученные результаты на случай некоммутативных колец с делением (тел) $ R $, показав, что и в этом случае $ R $, по-прежнему, e-интерпретируемо в $ \mathrm{SL}_n (R) $, когда $ n \geqslant 3 $. Однако, чтобы показать, что группа $ \mathrm{SL}_n (R) $ является e-интерпретируемой в теле $ R $, нам нужно, чтобы коммутант мультипликативной группы $ R^* $ был диофантовым в $ R^*$. Требование к $ R $ не иметь делителей нуля в случае $ \mathrm{PGL}_n (R) $ и $ \mathrm{PSL}_n (R) $ исходит только из наших аргументов в доказательстве. Мы не знаем, действительно ли это требование необходимо для того, чтобы $ R $ e-интерпретировалось в больших подгруппах $ \mathrm{PGL}_n (R) $.

Комбинируя следствие 6.4 и предложение 6.6, мы получаем основной результат работы – теорему 6.7, которая утверждает, что диофантова проблема во всех классических группах матриц, упомянутых выше, полиномиально по времени эквивалентна диофантовой проблеме в $ R $ (с соответствующими ограничениями на кольцо $ R $).

Наконец, в § 7 мы подробно изучаем диофантовы проблемы в классических группах матриц над полем $ \mathbb{Q} $, полями алгебраических чисел, полями $ \mathbb{C} $, $ \mathbb{R} $ и $ \mathbb{Q} _p $, а также над кольцами $ \mathbb{Z} $, $ \mathbb{Z}_p $ и кольцами целых алгебраических чисел $ \mathcal{O} $. Мы начинаем с диофантовых задач в самих кольцах $ \mathbb{C} $, $ \mathbb{R} $, $ \mathbb{Q}_p $ и $ \mathbb {Z}_p $. Несмотря на то, что теории первого порядка этих колец хорошо изучены, в частности доказана их разрешимость (см., например, [51], [52]), соответствующие диофантовы задачи с различными наборами коэффициентов не были достаточно хорошо исследованы. С этой целью мы описываем (а иногда и доказываем) соответствующие результаты, хотя мы полагаем, что некоторые из них известны в фольклоре.

Обозначение. Через $ G_n (R) $ мы обозначаем любую из классических линейных групп $ \mathrm{GL}_n (R) $, $ \mathrm{SL}_n (R) $, $ \mathrm{T}_n (R) $, $ \mathrm{UT}_n (R) $, $ \mathrm{PGL}_n (R) $, $ \mathrm{PSL}_n (R) $ над кольцом $ R $.

Начнем со следующих двух результатов, которые проясняют ситуацию, когда $ R = \mathbb {Z} $ или $ R $ является алгебраически замкнутым полем.

Теорема 7.1. Пусть $n \geqslant 3$. Тогда диофантова проблема в группах матриц $G_n(\mathbb{Z})$ эквивалентна по Карпу диофантовой проблеме в $\mathbb{Z}$. В частности, диофантова проблема в группах матриц $G_n(\mathbb{Z})$ неразрешима.

Предложение 7.4. Пусть $R$ – алгебраически замкнутое поле. Тогда имеют место следующие утверждения.

1) Если $A$ – вычислимое подполе поля $R$, то теория первого порядка $\mathrm{Th}_A(R)$ поля $R$ с константами из $A$, добавленными в сигнатуру, разрешима. В частности, $\mathcal{D}_A(R)$ разрешима.

2) Пусть $C$ – счетное или конечное подмножество $G_n(R)$ такое, что кольцо $C_R$, порожденное в $R$ всеми элементами, входящими в матрицы из $C$, вычислимо. Тогда диофантова проблема в $G_n(R)$ с константами из $C$ разрешима.

В п. 7.3 рассматриваются диофантовы проблемы в поле $ \mathbb {R} $ вещественных чисел и в классических группах матриц над $ \mathbb {R} $. Пусть $ A $ – счетное (или конечное) подмножество $ \mathbb {R} $. В этом пункте мы сначала обсуждаем, когда диофантова проблема в $\mathbb {R} $ с константами из $ A $ разрешима, а затем применяем эти результаты к диофантовым задачам в классических группах матриц над $ \mathbb {R} $. Заметим сначала, что по лемме 3.3, если $ \mathcal {D}_A (\mathbb {R}) $ разрешима, то подполе $ F(A) $, порожденное $ A $ в $ \mathbb {R} $, вычислимо. Однако обратное, вообще говоря, неверно. Следующий результат проясняет ситуацию.

Предложение 7.5. Пусть $ A $ – конечное или счетное подмножество в $ \mathbb {R} $. Тогда диофантова проблема в $ \mathbb{R} $ с константами из $ A $ разрешима тогда и только тогда, когда упорядоченное подполе $ F(A) $, порожденное $ A $ в $ \mathbb{R} $, вычислимо. Более того, в этом случае разрешима вся теория первого порядка $ \mathrm{Th}_A (\mathbb {R}) $ поля $ \mathbb{R} $ с константами из $A$ в сигнатуре.

Напомним, что вещественное число $ a \in \mathbb {R} $ вычислимо, если его стандартное десятичное разложение $ a = a_0.a_1a_2 \dots $ вычислимо, т. e. целочисленная функция $ n \to a_n $ вычислима. Другими словами, $ a $ вычислимо тогда и только тогда, когда его можно эффективно аппроксимировать рациональными числами с любой точностью. Множество всех вычислимых вещественных чисел $ \mathbb {R}^c $ образует вещественное замкнутое подполе в $ \mathbb{R} $, в частности $ \mathbb {R}^c $ элементарно эквивалентно полю $ \mathbb{ R} $.

В следующем предложении мы собираем некоторые факты о вычислимых упорядоченных подполях $ \mathbb {R} $. Утверждения 1) и 2) были доказаны в [53], 3) доказано в [54] (см. также [55; гл. 6, разд. 3, теорема 4], а 4) известно в фольклоре. Мы благодарны Андрею Морозову за помощь с вычислимыми упорядоченными полями.

Предложение 7.6. Имеют место следующие утверждения.

1) Каждое вычислимое упорядоченное подполе $\mathbb{R}$ содержится в $\mathbb{R}^c$.

2) Упорядоченное подполе $\mathbb{R}^c \leqslant \mathbb{R}$ с порядком, индуцированным с $\mathbb{R}$, невычислимо.

3) Если $F$ – вычислимое упорядоченное поле, то его вещественное замыкание также вычислимо. В частности, если $F$ – вычислимое подполе $\mathbb{R}$, то алгебраическое замыкание $\overline F$ подполя $F$ в $\mathbb{R}$ является вычислимым упорядоченным полем.

4) Если $a_1, \dots,a_m$ – вычислимые вещественные числа, то упорядоченное подполе $\mathbb{Q}(a_1, \dots,a_m) \leqslant \mathbb{R}$ с порядком, индуцированным с $\mathbb{R}$, вычислимо.

Теперь мы можем привести пример, упомянутый выше. А именно, если $ a \in \mathbb {R} $ невычислимое вещественное число, то $ F = \mathbb{Q}(a) $ вычислимое поле, но $ \mathcal {D}_{\{a \}}(\mathbb{R}) $ неразрешима.

Обобщая вышеизложенное, мы получаем следующий результат.

Следствие 7.7. Имеют место утверждения:

диофантова проблема в $ \mathbb {R} $ с коэффициентами в $\mathbb {R}^c $ неразрешима;

диофантова проблема в $ \mathbb {R} $ с коэффициентами в любом конечном подмножестве $ \mathbb {R}^c $ разрешима;

диофантова проблема в $ \mathbb {R} $ с коэффициентами в $ \{a \} $, где $ a $ невычислимо, неразрешима.

Теперь обратимся к диофантовой проблеме в классических группах матриц над $ \mathbb {R}$. Матрица $ A \in \mathrm{GL}_n (\mathbb {R}) $ называется вычислимой, если все элементы в $ A $ являются вычислимыми действительными числами. Следовательно, вычислимые матрицы в $ \mathrm{GL}_n (\mathbb {R}) $ – это в точности матрицы из $\mathrm{GL}_n(\mathbb{R}^c) $.

Теорема 7.8. Пусть $ n \geqslant 3 $ и

$$ \begin{equation*} G_n (\mathbb {R}) \in \{\mathrm{GL}_n (\mathbb {R}), \mathrm{SL}_n (\mathbb {R}), \mathrm{T}_n (\mathbb {R}), \mathrm{UT}_n (\mathbb {R}), \mathrm{PGL}_n ( \mathbb {R}), \mathrm{PSL}_n (\mathbb {R}) \}. \end{equation*} \notag $$
Если $F$ является вычислимым упорядоченным подполем в $ \mathbb {R} $, то теория первого порядка $ \mathrm{Th}_{G_n(F)}(G_n (\mathbb {R})) $ группы матриц $ G_n (\mathbb {R}) $ с константами из $ G_n(F) $ разрешима (здесь $ G_n (F) $ – множество всех матриц из $ G_n (\mathbb {R}) $ с элементами из $F$). В частности, диофантова проблема для уравнений с коэффициентами из $ G_n(F) $ разрешима в $ G_n(\mathbb {R}) $.

Следующий результат существенно дополняет приведенную выше теорему.

Теорема 7.9. Пусть $G$ – большая подгруппа в $ \mathrm{GL}_n (\mathbb {R}) $, где $ n \geqslant 3 $. Если матрица $ A \in \mathrm{SL}_n (\mathbb {R}) $ невычислима, то диофантова проблема в $G$ с коэффициентами из $ \{t_{ij}(1) \mid i, j = 1, \dots, n \} \cup \{A \} $ неразрешима.

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

Теорема 7.10. Имеют место следующие утверждения.

1) Диофантова проблема в вычислимом вещественно замкнутом поле $\mathbb{R}^c$ с коэффициентами в $\mathbb{R}^c$ неразрешима, при этом для каждого конечно порожденного подполя $F$ поля $\mathbb{R}^c$ диофантова проблема в $\mathbb{R}^c$ с коэффициентами в $F$ разрешима.

2) Диофантова проблема в вычислимой группе матриц $G_n(\mathbb{R}^c)$ неразрешима, если $n\geqslant 3$. Однако для каждой конечно порожденной подгруппы $C\leqslant G_n(\mathbb{R}^c)$ диофантова проблема в $G_n(\mathbb{R}^c)$ с коэффициентами в $C$ разрешима.

В п. 7.4 изучаются диофантовы проблемы в кольцах $ \mathbb {Z}_p $ и $ \mathbb {Q}_p $ и в классических матричных группах над ними.

Подобно вычислимым действительным числам, можно определить вычислимые $ p $-адические числа для каждого фиксированного простого числа $ p $. Напомним, что каждое $ p $-адическое число $ a \in \mathbb {Q} _p $ имеет единственное представление в виде $ a = p^m \xi $, где $ m \in \mathbb {Z} $ и $ \xi $ – обратимый элемент в кольце $ \mathbb {Z}_p $. В свою очередь, $ \xi $ однозначно определяется единственной последовательностью натуральных чисел $ \{\xi (i) \}_ {i \in \mathbb {N}} $, где

$$ \begin{equation*} 0 \leqslant \xi (i) <p^{i + 1}, \quad \xi (i + 1) = \xi (i) \ (\operatorname{mod} p^{i + 1}), \qquad i \in \mathbb {N}. \end{equation*} \notag $$
По определению, $p$-адическое число $ a = p^m \xi $ вычислимо, если функция $ i \to \xi (i) $ вычислима. В этом случае последовательность $ \{\xi (i) \}_ {i \in \mathbb {N}} $ дает эффективное $ p $-адическое приближение $ \xi $. Известно (см., например, [56]), что множество $ \mathbb{Q}_p ^c $ всех вычислимых $ p $-адических чисел образует подполе в $ \mathbb {Q}_p $, такое, что $ \mathbb {Q}_p \equiv \mathbb{Q}_p^c $. Отметим также, что кольцо $ \mathbb{Z}_p $ диофантово в $ \mathbb {Q} _p $. Точнее, если $ p \neq 2 $, то $ \mathbb{Z}_p $ выделяется в $ \mathbb {Q}_p $ формулой $ \exists \, y (1 + px^2 = y^2) $, а если $ p = 2 $, то $ \mathbb {Z}_p $ определяется в $ \mathbb {Q}_p $ формулой $ \exists \, y (1 + 2x^3 = y^3) $.

Следующий результат был доказан в [56].

Теорема 7.11. Имеют место следующие утверждения.

1) Теория $ \mathrm{Th} (\mathbb {Z}_p, a_1, \dots, a_n) $ кольца $\mathbb {Z}_p$ с константами $a_1, \dots, a_n$ в сигнатуре разрешима тогда и только тогда, когда каждое из $ a_1, \dots, a_n $ является вычислимым $ p $-адическим числом.

2) Теория $ \mathrm{Th} (\mathbb {Q} _p, a_1, \dots, a_n) $ поля $\mathbb {Q}_p$ с константами $a_1, \dots, a_n$ в сигнатуре разрешима тогда и только тогда, когда каждое из $ a_1, \dots, a_n $ является вычислимым p-адическим числом.

Нам нужна несколько более точная версия приведенных выше результатов в случае, когда теория неразрешима.

Теорема 7.12. Справедливы следующие утверждения.

1) Если целое $p$-адическое число $a$ невычислимо, то уравнения с константами из $\mathbb{Q} \cup \{a\}$ неразрешимы в $\mathbb{Z}_p$.

2) Если $p$-адическое число $a \in \mathbb{Q}_p$ невычислимо, то уравнения с константами из $\mathbb{Q} \cup \{a\}$ неразрешимы в $\mathbb{Q}_p$.

Матрица $ A \in \mathrm{GL}_n (\mathbb {Q}_p) $ называется вычислимой, если все элементы в $ A $ являются вычислимыми $ p $-адическими числами, т. е. $ A \in \mathrm{GL}_n (\mathbb {Q} _p^c) $. Таким образом, вычислимые матрицы в $ \mathrm{GL}_n (\mathbb {Q}_p) $ – это в точности матрицы из $ \mathrm{GL}_n (\mathbb {Q}_p^c) $.

Теорема 7.13. Пусть $n \geqslant 3$. Справедливы следующие утверждения.

1) Пусть

$$ \begin{equation*} G_n(\mathbb{Q}_p) \in \{\mathrm{GL}_n(\mathbb{Q}_p), \mathrm{SL}_n(\mathbb{Q}_p), \mathrm{T}_n(\mathbb{Q})_p,\mathrm{UT}_n(\mathbb{Q}_p), \mathrm{PGL}_n(\mathbb{Q}_p),\mathrm{PSL}_n(\mathbb{Q}_p)\}. \end{equation*} \notag $$
Если $A_1, \dots, A_m$ – вычислимые матрицы из $G_n(\mathbb{Q}_p)$, то теория первого порядка группы $G_n(\mathbb{Q}_p)$ с константами $A_1, \dots, A_m$ разрешима. В частности, диофантова проблема для уравнений с коэффициентами $A_1, \dots, A_m$ разрешима в $G_n(\mathbb{Q}_p)$.

2) Пусть

$$ \begin{equation*} G_n(\mathbb{Z}_p) \in \{\mathrm{GL}_n(\mathbb{Z}_p), \mathrm{SL}_n(\mathbb{Z}_p), \mathrm{T}_n(\mathbb{Z})_p,\mathrm{UT}_n(\mathbb{Z}_p), \mathrm{PGL}_n(\mathbb{Z}_p),\mathrm{PSL}_n(\mathbb{Z}_p)\}. \end{equation*} \notag $$
Если $A_1, \dots, A_m$ – вычислимые матрицы из $G_n(\mathbb{Z}_p)$, то теория первого порядка группы $G_n(\mathbb{Z}_p)$ с константами $A_1, \dots, A_m$ разрешима. В частности, диофантова проблема для уравнений с коэффициентами $A_1, \dots, A_m$ разрешима в $G_n(\mathbb{Z}_p)$.

Теорема 7.14. Если матрица $ A \in \mathrm{SL}_n (\mathbb {Z}_p) $ ($ A \in \mathrm{SL}_n (\mathbb {Q}_p) $) невычислима, то диофантова проблема для уравнений с коэффициентами из $ \{t_ {ij}(1) \mid i, j = 1, \dots, n \} \cup \{A \} $ неразрешима в $\mathrm{SL}_n (\mathbb {Z}_p) $ ($ \mathrm{SL}_n (\mathbb {Q}_p) $).

§ 2. Предварительные результаты

В этом параграфе мы вводим обозначения и напоминаем некоторые технические результаты, которые будут использоваться на протяжении всей статьи.

Пусть $G$ – группа и $x,y$ – элементы из $G$. Тогда через $x^y=y^{-1}xy$ мы обозначаем элемент $x$, сопряженный элементом $y$, и через $[x,y]=x^{-1}y^{-1}xy$ – коммутатор $x$ и $y$. Если $A\subseteq G$ – подмножество элементов из $G$, то $C_G(A)$ – это централизатор $A$ в $G$, т. е. $C_G(A) =\{x \in G \mid \forall \, a \in A\ ([x,a] = 1) \}$. В частности, $Z(G)=\{x\in G\mid \forall \, y\in G\ ([x,y] = 1) \}$ – центр группы $G$. Для подмножеств $X, Y \subseteq G$ через $[X,Y]$ мы обозначаем подгруппу $G$, порожденную всевозможными коммутаторами $[x,y]$, где $x \in X, y \in Y$. В частности, $[G,G]=G'$ – это коммутант (или производная подгруппа) группы $G$. Мы также определяем нижний центральный ряд $G = \gamma_1(G) \geqslant \gamma_2(G) \geqslant \cdots$, группы $G$ по индукции, где $\gamma_{i+1}(G) = [G,\gamma_i(G)]$.

В этой статье мы предполагаем, что $R$ – это произвольное ассоциативное кольцо с единицей (необязательно коммутативное). Мы обозначаем группу единиц $R$ (обратимые элементы $R$ с операцией умножения) как $R^{\times}$ или $R^\ast$, если это требует традиция, и аддитивную группу $R$ – как $R^+$.

Далее мы кратко обсуждаем основные группы, которые рассматриваются в этой статье.

2.1. Общие линейные группы $\mathrm{GL}_n(R)$

Зафиксируем $n\in \mathbb{N}$. Через $\mathrm{GL}_n(R)$ мы обозначаем группу обратимых матриц с коэффициентами в ассоциативном кольце с единицей $R$.

Определим $(n\times n)$-матрицу $e_{ij}$ как матрицу, в которой на позиции $(i,j)$ стоит $1$, и на всех остальных позициях стоит $0$. Если $1 \leqslant i \neq j \leqslant n$, обозначим $t_{ij}(\alpha)=I_n+\alpha e_{ij}$, где $\alpha\in R$ и $I_n$ – это единичная матрица размера $n\times n$. Матрицы $t_{i,j}(\alpha)$ называются трансвекциями. Мы также иногда обозначаем $t_{i,j}=t_{i,j}(1)$ и $\mathcal{T}_n = \{t_{ij} \mid 1 \leqslant i \neq j \leqslant n\}$.

Трансвекции $t_{ij}(\alpha)$, $t_{kl}(\beta)$, где $\alpha, \beta \in R$, удовлетворяют хорошо известным соотношениям Стейнберга:

1) $t_{ij}(\alpha)t_{ij}(\beta)=t_{ij}(\alpha+\beta)$;

2) $[t_{ik}(\alpha),t_{kl}(\beta)] = t_{il}(\alpha\beta)$ для $i\neq l$;

3) $[t_{ik}(\alpha),t_{jl}(\beta)] =1$ для $i \neq l, j \neq k$.

Заметим, что из 2) следует равенство $[t_{ij}(\alpha),t_{ki}(\beta)] = t_{kj}(-\alpha\beta)$ для $j\neq k$.

Обозначим $n\times n$ диагональную матрицу с элементами $\alpha_i\in R^{\times}$ на позиции $(i,i)$ как $\operatorname{diag}(\alpha_1, \dots ,\alpha_n)$. Тогда $\operatorname{diag}(\alpha_1, \dots,\alpha_n) \in \mathrm{GL}_n(R)$ и все такие элементы образуют подгруппу $D_n(R)$ в $\mathrm{GL}_n(R)$. Заметим, что для всех $\alpha_1, \dots, \alpha_n \in R^{\times}$, $\beta \in R$ выполняются

$$ \begin{equation} \operatorname{diag}(\alpha_1, \dots,\alpha_n)^{-1}t_{ij}(\beta)\operatorname{diag}(\alpha_1, \dots,\alpha_n) = t_{ij}(\alpha_i^{-1} \beta \alpha_j). \end{equation} \tag{1} $$
В частности,
$$ \begin{equation} [t_{ij}(\beta),\operatorname{diag}(\alpha_1, \dots,\alpha_n)] = t_{ij}(\alpha_i^{-1} \beta \alpha_j -\beta). \end{equation} \tag{2} $$

Обозначим скалярную матрицу $\operatorname{diag}(\alpha, \dots ,\alpha) = \alpha I_n$, где $\alpha\in R^{\times}$, как $d(\alpha)$. Все такие матрицы образуют подгруппу $R^\times I_n \leqslant D_n(R)$ изоморфную $R^\times$. Определим подгруппу $\mathrm{Z}_n(R)$ в $R^\times I_n$, состоящую из всех скалярных матриц $d(\alpha)$, где $\alpha$ – центральный элемент $R^{\times}$. Из (2) следует, что $\mathrm{Z}_n(R)$ образует центр в группах $R^\times I_n$ и $\mathrm{GL}_n(R)$.

Теперь для $\alpha \in R^\times$ рассмотрим матрицы

$$ \begin{equation*} d_i(\alpha)\stackrel{\mathrm{def}}{=} \operatorname{diag}(1,\dots, \underbrace{\alpha}_{i}, \dots, 1). \end{equation*} \notag $$

Хорошо известно (см., например, [57]), что если $R$ – это поле, то существуют натуральные числа $r$, $s$, которые зависят только от $n$, такие, что каждый элемент $g \in \mathrm{GL}_n(R)$ может быть записан как произведение

$$ \begin{equation} g= x_1 \cdots x_r d_n(\beta)y_1 \cdots y_s, \end{equation} \tag{3} $$
где $x_i$, $y_j$ – это трансвекции и $\beta \in R^\times$.

2.2. Специальные линейные и элементарные группы $\mathrm{SL}_n(R)$ и $\mathrm{E}_n(R)$

Подгруппа $\mathrm{E}_n(R)$ группы $\mathrm{GL}_n(R)$, порожденная всеми трансвекциями, называется элементарной линейной группой, $\mathrm{E}_n(R) = \langle t_{ij}(\alpha) \mid \alpha \in R,\, 1\leqslant i\neq j\leqslant n\rangle $.

Определение 2.1. Мы говорим, что подгруппа $G \leqslant \mathrm{GL}_n(R)$ большая, если $G$ содержит $\mathrm{E}_n(R)$.

В этой работе мы всегда предполагаем, если не оговорено противное, что размер матриц $n\geqslant 3$.

Если кольцо $R$ коммутативно, то, как обычно, мы определяем группу $\mathrm{SL}_n(R)$ как множество всех матриц с определителем $1$. Это определение может быть обобщенно на случай некоммутативных колец с делением (с помощью определителя Дьедонне), но мы не рассматриваем такие группы в этой статье. Всякий раз, когда мы работаем с группами $\mathrm{SL}_n(R)$, мы предполагаем, что $R$ коммутативно. Очевидно, что $\mathrm{SL}_n(R)$ содержит $\mathrm{E}_n(R)$, в частности, по определению, $\mathrm{SL}_n(R)$ – большая подгруппа в $\mathrm{GL}_n(R)$. Если $R$ – евклидово кольцо, то $\mathrm{SL}_n(R)=\mathrm{E}_n(R)$, но в общем случае это не всегда так. Для полей $R$ мы также имеем

$$ \begin{equation*} [\mathrm{GL}_n(R),\mathrm{GL}_n(R)] = \mathrm{SL}_n(R). \end{equation*} \notag $$
Тогда из (3) следует, что
$$ \begin{equation*} \mathrm{GL}_n(R) \simeq \mathrm{SL}_n(R) \rtimes d_n(R^\times) \simeq \mathrm{GL}_n(R)' \rtimes R^\times; \end{equation*} \notag $$
здесь $d_n(R^\times) = \{d_n(\alpha) \mid \alpha \in R^\times\}$. Заметим также, что в этом случае
$$ \begin{equation*} [\mathrm{SL}_n(R),\mathrm{SL}_n(R)] = \mathrm{SL}_n(R). \end{equation*} \notag $$

Следуя [58], мы говорим, что $\mathrm{SL}_n(R)$ ограниченно элементарно порождена, если существует натуральное $w$ такое, что каждый элемент в $\mathrm{SL}_n(R)$ может быть записан как произведение не более $w$ трансвекций. Упорядочим все пары $(i,j)$, где $ i,j = 1, \dots,n$, каким-нибудь фиксированным способом и запишем в виде последовательности $\sigma$, например, $\sigma = (1,1), \dots, (n,n)$. Повторим эту последовательность (в том же порядке) $w$ раз и обозначим полученную последовательность через $\sigma^* = \sigma$, $\sigma$, $\dots$, $\sigma = (i_1,j_1), \dots,(i_m,j_m)$, где $m=wn^2$. Тогда каждый элемент $g \in \mathrm{SL}_n(R)$ может быть записан как произведение

$$ \begin{equation*} g = t_{i_1j_1}(\alpha_1) \cdots t_{i_mj_m}(\alpha_m) \end{equation*} \notag $$
для некоторых $\alpha_1, \dots,\alpha_m \in R$ с фиксированным порядком трансвекций (заметим, что мы позволяем $\alpha_i=0$ для некоторых $i$).

Для $ 1 \leqslant i \neq j \leqslant n$, обозначим однопараметрическую подгруппу $\{t_{ij}(\alpha) \mid \alpha \in R\}$ как $\mathrm{T}_{ij}$. Тогда ограниченное элементарное порождение $\mathrm{SL}_n(R)$ эквивалентно существованию последовательности пар $(i_1,j_1), \dots, (i_m,j_m)$, где $1\leqslant i_k \neq j_k \leqslant n$ такой, что

$$ \begin{equation*} \mathrm{SL}_n(R) = \mathrm{T}_{i_1j_1} \cdots \mathrm{T}_{i_mj_m}. \end{equation*} \notag $$
Если $R$ является полем, то ограниченная элементарная порожденность $\mathrm{SL}_n(R)$ следует из формулы (3). Используя гораздо более сложный аргумент, можно показать, что $\mathrm{SL}_n(\mathcal{O})$ ограниченно элементарно порождена в случае колец целых алгебраических чисел $\mathcal{O}$, см. [58]. Однако это не выполняется для произвольных областей целостности. Действительно, в [59], [60] показано, что если $F$ – поле бесконечной степени трансцендентности над своим простым подполем (например, $F=\mathbb{C}$), то для каждого натурального $c$ существует матрица $g\in \mathrm{SL}_n(F[x])$, которая не может быть представлена как произведение $c$ коммутаторов.

2.3. Унитреугольные группы $\mathrm{UT}_n(R)$

Верхнетреугольные трансвекции $t_{ij}(\alpha)$, где $1\leqslant i<j\leqslant n$, $\alpha\in R$, порождают подгруппу $\mathrm{UT}_n(R)$ всех унитреугольных матриц в $\mathrm{GL}_n(R)$.

Для $m= 1, \dots, n$ через $\mathrm{UT}^m(n,R)$ обозначим подгруппу в $\mathrm{UT}_n(R)$, состоящую из всех матриц с $m-1$ нулевыми диагоналями над главной диагональю. Тогда

$$ \begin{equation} \mathrm{UT}_n(R) = \mathrm{UT}_n^1(R) > \mathrm{UT}_n^2(R) > \dots > \mathrm{UT}_n^n(R) = 1. \end{equation} \tag{4} $$
Более того, если мы положим $\mathrm{UT}_n^m=1$ для $m>n$, то для всех $r, s \in \mathbb{N}$,
$$ \begin{equation*} [\mathrm{UT}_n^r(R),\mathrm{UT}_n^s(R)] = \mathrm{UT}_n^{r+s}(R). \end{equation*} \notag $$
Из этого следует, что (4) – это нижний центральный ряд группы $\mathrm{UT}_n(R)$, т. е. $\gamma_m(\mathrm{UT}_n(R)) = \mathrm{UT}_n^m(R)$. Простые вычисления показывают, что каждая матрица $g \in \mathrm{UT}_n^m(R)$ может быть единственным образом записана в виде следующего произведения:
$$ \begin{equation*} g = t_{n-m,n}(\alpha_{n-m}) t_{n-m-1,n-1}(\alpha_{n-m-1}) \cdots t_{1,1+m}(\alpha_1)h, \end{equation*} \notag $$
где $\alpha_i \in R$ и $h \in \mathrm{UT}_n^{m+1}(R)$. Поэтому,
$$ \begin{equation} \mathrm{UT}_n^m(R) = \mathrm{T}_{n-m,n} \mathrm{T}_{n-m-1,n-1} \cdots \mathrm{T}_{1,1+m}\mathrm{UT}_n^{m+1}(R). \end{equation} \tag{5} $$
Это показывает, что $\mathrm{UT}_n(R)$ раскладывается в конечное произведение одно-параметрических подгрупп $\mathrm{T}_{ij}$.

2.4. Треугольные группы $\mathrm{T}_n(R)$

Напомним, что группа треугольных матриц $\mathrm{T}_n(R)$ состоит из всех верхнетреугольных матриц $x = (x_{ij})$ над $R$ с обратимыми элементами на диагонали, т. е. $x_{ij} = 0$ для $i>j$, $x_{ij} \in R$ для $i <j$ и $x_{ii} \in R^\times$ для $1\leqslant i \leqslant n$. Очевидно, что $\mathrm{UT}_n(R) \leqslant \mathrm{T}_n(R)$.

Заметим, что каждая матрица $x \in \mathrm{T}_n(R)$ может быть записана как произведение $x= d_x u_x$, где $d_x = \operatorname{diag}(x_{11}, \dots,x_{nn})$, и $u_x \in \mathrm{UT}_n(R)$. Здесь $u_x = (y_{ij})$ состоит из элементов $y_{ij} = x_{ii}^{-1}x_{ij}$ для $i<j$. Следовательно, $\mathrm{T}_n(R) = D_n(R) \mathrm{UT}_n(R)$ и $D_n(R) \cap \mathrm{UT}_n(R) = 1$. Более того, $\mathrm{UT}_n(R)$ – это нормальная подгруппа в $\mathrm{T}_n(R)$ (это следует из (1)), т. е.

$$ \begin{equation*} \mathrm{T}_n(R) \simeq \mathrm{UT}_n(R) \rtimes D_n(R). \end{equation*} \notag $$

Определение 2.2. Мы говорим, что $G \leqslant \mathrm{T}_n(R)$ является большой подгруппой в $\mathrm{T}_n(R)$, если $G$ содержит $\mathrm{UT}_n(R)$.

Заметим, что $\mathrm{UT}_n(R)$ является большой подгруппой в $\mathrm{T}_n(R)$, но не в $\mathrm{GL}_n(R)$.

2.5. Проективные группы $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$

Проективная линейная группа $\mathrm{PGL}_n(R)$ и проективная специальная линейная группа $\mathrm{PSL}_n(R)$ определяются как факторгруппы $\mathrm{PGL}_n(R) = \mathrm{GL}_n(R)/Z(\mathrm{GL}_n(R))$ и $\mathrm{PSL}_n(R) = \mathrm{SL}_n(R)/Z(\mathrm{SL}_n(R))$ соответственно групп $\mathrm{GL}_n(R)$ и $\mathrm{SL}_n(R)$ по их центрам. Напомним, что $Z(\mathrm{GL}_n(R))=\mathrm{Z}_n(R)$ состоит из всех скалярных матриц $d(\alpha)$, где $\alpha$ – центральный элемент в $R^\times$. Аналогично, $Z(\mathrm{SL}_n(R)) = \mathrm{Z}_n(R) \cap \mathrm{SL}_n(R)$.

Определение 2.3. Мы называем подгруппу $G$ в $\mathrm{PGL}_n(R)$ большой, если она содержит $\phi(\mathrm{E}_n(R))$, где $\phi\colon \mathrm{GL}_n(R)\to \mathrm{PGL}_n(R)$ – естественный гомоморфизм.

§ 3. Диофантова проблема

3.1. Уравнения, константы и вычислимые структуры

Напомним, что под диофантовой проблемой $\mathcal{D}(\mathcal{A})$ в алгебраической структуре $\mathcal{A}$ мы понимаем вопрос о том, имеет ли решение в $\mathcal{A}$ данная система уравнений с константами из $\mathcal{A}$. Проблема $\mathcal{D}(\mathcal{A})$ разрешима, если существует алгоритм, который по данной конечной системе уравнений $S$ с константами из $\mathcal{A}$ устанавливает, имеет ли $S$ решение в $\mathcal{A}$. Мы предполагаем, что структура $\mathcal{A}$ счетная и, более того, снабжена фиксированной нумерацией $\mathcal{A} = \{a_1,a_2, \dots \}$, заданной сюръективной (но необязательно инъективной) функцией $\nu\colon \mathbb{N} \to \mathcal{A}$. Функция $\nu$ может использоваться для нумерации всех конечных систем уравнений с коэффициентами в $\mathcal{A}$ со счетным числом переменных $x_1, x_2, \dots$, а затем для их подачи на вход алгоритма, решающего диофантову проблему $\mathcal{D}(\mathcal{A})$. Заметим, что разрешимость $\mathcal{D}(\mathcal{A})$ зависит от выбора нумерации $\nu\colon \mathbb{N} \to \mathcal{A}$, т. е. при некоторых $\nu$ проблема $\mathcal{D}(\mathcal{A})$ разрешима, а при некоторых – нет. Например, для каждой нетривиальной конечной или счетной группы существует бесконечное счетное представление (через порождающие и соотношения) с неразрешимой проблемой равенства, что влечет неразрешимость диофантовой проблемы в этой группе относительно нумераций, использующих такое представление. Однако обычно исследуются только “естественные” нумерации $\nu$, т. е. те, что происходят от конечных описаний элементов структуры $\mathcal{A}$, отражающих природу этой структуры. К примеру, если $\mathcal{A}$ – конечно порожденная группа, то можно описать элементы $\mathcal{A}$ конечными словами в фиксированном конечном множестве порождающих и использовать эффективную нумерацию слов; тогда как если $\mathcal{A}$ является, скажем, группой матриц $\mathrm{GL}_n(R)$ над кольцом $R$, то элементы $\mathrm{GL}_n(R)$ могут быть описаны кортежами по $n^2$ элементов из $R$ так, что нумерация $R$ может быть использована, чтобы нумеровать элементы $\mathrm{GL}_n(R)$. Здесь и всюду далее под эффективной нумерацией слов (или многочленов, или любых других формул некоторой конечной сигнатуры) мы понимаем такую нумерацию $\mu\colon n \to w_n$ слов в данном конечном или счетном алфавите, что для любого числа $n \in \mathbb{N}$ можно вычислить слово $w_n$, и для любого слова $w$ в данном алфавите можно вычислить номер $n$ такой, что $w = w_n$. Если $\mathcal{A}$ – конечно порожденное ассоциативное кольцо $R$ с единицей, то мы можем представить элементы $\mathcal{A}$ в виде некоммутативных многочленов с целыми коэффициентами от конечного числа переменных (иначе говоря, в виде элементов свободного ассоциативного кольца с единицей конечно ранга), затем эффективно нумеровать эти многочлены. Аналогично, для коммутативного кольца $R$ можно использовать обычные коммутативные многочлены. Есть два способа сделать формулировку диофантовой проблемы более точной: либо в явном виде зафиксировать нумерацию $\nu$ структуры $\mathcal{A}$ в диофантовой проблеме (обозначим ее через $\mathcal{D}_\nu(\mathcal{A})$), либо ввести определение, что $\mathcal{D}(\mathcal{A})$ разрешима, если существует нумерация $\nu$ структуры $\mathcal{A}$ такая, что $\mathcal{D}_\nu(\mathcal{A})$ разрешима. Для изучения того, какие нумерации “разумны” в контексте диофантовых проблем, нам необходимо уделить внимание теории вычислимых алгебр, или вычислимой теории моделей, которые ведут начало от основополагающих трудов Рабина [16] и Мальцева [15] (за деталями отсылаем к книге [55] и более современной обзорной работе [61]).

Напомним, что структура $\mathcal{A}$ с конечной сигнатурой вычислима по отношению к нумерации $\nu\colon \mathbb{N} \to \mathcal{A}$, если все операции и предикаты (включая равенство) на $\mathcal{A}$ вычислимы относительно нумерации $\nu$. В частности, группа $\mathrm{G}$ вычислима по отношению к $\nu$, если существуют две вычислимые функции $f(x,y)$ и $h(x,y)$ такие, что для любых $i, j \in \mathbb{N}$ имеет место следующее: $\nu(i)\cdot\nu(j) = \nu(f(i,j))$ и $\nu(i) = \nu(j) \Longleftrightarrow h(i,j) = 1$. Аналогично, счетное кольцо $R$ вычислимо по отношению к $\nu\colon \mathbb{N} \to R$, если в дополнение к предшествующим условиям существует вычислимая функция $g(x,y)$ такая, что $\nu(i) + \nu(j) = \nu(g(i,j))$.

Следующее наблюдение показывает связь между разрешимостью диофантовых проблем и вычислимостью структур.

Лемма 3.1. Пусть $\mathcal{A}$ – счетная структура, заданная с нумерацией $\nu$: $\mathbb{N} \to \mathcal{A}$. Если диофантова проблема $\mathcal{D}_\nu(\mathcal{A})$ разрешима, то структура $\mathcal{A}$ вычислима по отношению к $\nu$.

Доказательство. Приведем набросок доказательства в случае групп. Поскольку общий случай аналогичен, мы оставляем его читателю. Пусть $A = \{a_1, a_2, \dots\}$, где $a_i = \nu(i)$, $i \in \mathbb{N}$. В предположении, что $\mathcal{D}_\nu(A)$ разрешима, нам требуется показать, что $A$ вычислима, т. е. что вычислимы следующие множества:
$$ \begin{equation*} \{(i,j) \mid a_i = a_j,\, i,j \in \mathbb{N}\},\qquad \{(i,j,k) \mid a_i\cdot a_j = a_k,\, i,j,k \in \mathbb{N}\}. \end{equation*} \notag $$
Эти множества задаются уравнениями в $A$, тем самым они вычислимы. Лемма доказана.

Лемма 3.1 показывает, что касательно диофантовой проблемы интересны лишь те нумерации структуры $\mathcal{A}$, при которых $\mathcal{A}$ вычислима. Такие нумерации называются конструктивизациями структуры $\mathcal{A}$. Вопрос о том, обладает ли данная счетная структура $\mathcal{A}$ конструктивизацией, является одним из основных в вычислимой теории моделей, что обуславливает множество результатов в этом направлении (см. [55], [61], [62]), которые могут здесь применяться.

Пусть $\mu$ и $\nu$ – две нумерации $\mathcal{A}$. Будем говорить, что $\mu$ сводится к $\nu$ (и обозначим $\mu \preceq \nu$), если существует вычислимая функция $f(x)$ такая, что $\mu = \nu \circ f$. Назовем $\mu$ и $\nu$ эквивалентными (и обозначим $\mu \sim \nu$), если $\nu \preceq \nu$ и $\nu \preceq \mu$.

Лемма 3.2 (см. [55]). Пусть $\mathcal{A}$ – конечно порожденная структура, обладающая по крайней мере одной конструктивизацией. Тогда все конструктивизации $\mathcal{A}$ эквивалентны между собой.

Следовательно, конечно порожденная структура $\mathcal{A}$ обладает конструктивизацией, если и только если проблема равенства в $\mathcal{A}$ по отношению к некоторому (а тогда любому) конечному порождающему множеству разрешима. В этом случае любая другая конструктивизация эквивалентна происходящей от произвольного конечного набора порождающих, как описано выше. По этой причине обычно мы не упоминаем в явном виде нумерацию для конечно порожденных структур.

Если $\mathcal{A}$ несчетно, то, как мы упоминали во введении, приходится рассматривать только те уравнения, в которых константы принадлежат фиксированному счетному (или конечному) подмножеству $C$ структуры $\mathcal{A}$, которое снабжено нумерацией $\nu\colon \mathbb{N} \to C$. Этот вид диофантовой проблемы обозначается $\mathcal{D}_C(\mathcal{A})$. Далее будет удобно вместо множества $C$ рассматривать подструктуру $\langle C \rangle$, порожденную подмножеством $C$ в $\mathcal{A}$. В этом случае необходимо рассматривать нумерации $\langle C \rangle$, которые “совместимы” с данной нумерацией $C$.

Для этого напомним следующее понятие из вычислимой теории моделей (см. [55]). Пусть $S$ – множество с нумерацией $\nu$, а $\phi\colon S \to S^*$ – вложение. Скажем, что нумерация $\nu^*\colon \mathbb{N} \to S^*$ продолжает нумерацию $\nu$, если существует вычислимая функция $f\colon \mathbb{N} \to \mathbb{N}$ такая, что $\phi\circ \nu = \nu^*\circ f$. Легко построить нумерацию $\langle C \rangle$, которая продолжает данную нумерацию порождающего множества $C$ (см. [55; гл. 6, разд. 1, теорема 1]).

Далее, если не указано обратное, для подмножества $C$ структуры $\mathcal{A}$ мы будем всегда рассматривать нумерации $\nu^*$ подструктуры $\langle C \rangle$, продолжающие данную нумерацию $C$. Более того, мы всегда будем предполагать, что для данного $n \in \mathbb{N}$ мы можем вычислить терм $t$ в сигнатуре структуры $\mathcal{A}$ с константами из $C$, который представляет элемент $\nu^*(n)$ в структуре $\langle C \rangle$. И наоборот, для любого такого терма $t$ мы можем вычислить число $n \in \mathbb{N}$ такое, что $\nu^*(n) = t$. Назовем такие нумерации $\nu^*$ эффективными. Чтобы построить эффективную нумерацию $\langle C \rangle$ в случае, когда $\mathcal{A}$ является группой, надо лишь эффективно пронумеровать все слова в алфавите $C^{\pm 1}$; в случае, когда $\mathcal{A}$ является коммутативным кольцом с единицей, надо пронумеровать все многочлены из $\mathbb{Z}[C]$.

Нам пригодится следующая лемма.

Лемма 3.3. Пусть $\mathcal{A}$ – структура, $C$ – конечное или счетное подмножество $\mathcal{A}$, снабженное нумерацией $\nu$, а $\langle C \rangle$ – подструктура, порожденная $C$ в $\mathcal{A}$, с эффективной нумерацией, продолжающей $\nu$. Тогда имеет место следующее.

1) Диофантовы проблемы $\mathcal{D}_C(\mathcal{A})$ и $\mathcal{D}_{\langle C \rangle}(\mathcal{A})$ эквивалентны (сводятся друг к другу).

2) Если $\mathcal{D}_C(\mathcal{A})$ разрешима, то $\langle C \rangle$ вычислима по отношению к любой нумерации $\langle C \rangle$, продолжающей нумерацию $\nu$ порождающего множества $C$.

Доказательство. Чтобы доказать утверждение 1) мы должны показать, что $\mathcal{D}_C(\mathcal{A})$ и $\mathcal{D}_{\langle C \rangle}(\mathcal{A})$ сводятся друг к другу. Так как $\nu^*$ – эффективная нумерация, продолжающая нумерацию $\nu$, мы можем для каждого $n \in \mathbb{N}$ вычислить терм $t$, который выражает элемент $\nu^*(n)$ через порождающие из $C$. Следовательно, для данной конечной системы уравнений $S(X)$ с коэффициентами в $\langle C \rangle$, мы можем “переписать” каждый коэффициент $a$ в $S(X)$ в виде терма $t_a$, который выражает $a$ через порождающие из $C$, и соответственно скорректировать систему $S(X)$. Полученная таким образом система $S^*$ содержит коэффициенты только из $C$ и имеет в точности то же множество решений в $\mathcal{A}$, что и система $S$. Это сводит $\mathcal{D}_{\langle C \rangle}(\mathcal{A})$ к $\mathcal{D}_C(\mathcal{A})$. Обратно, чтобы свести $\mathcal{D}_C(\mathcal{A})$ к $\mathcal{D}_{\langle C \rangle}(\mathcal{A})$, мы можем проделать следующее. Прежде всего заметим, что так как $\nu^*$ продолжает $\nu$, есть вычислимая функция $f\colon \mathbb{N} \to \mathbb{N}$ такая, что для каждого $n \in \mathbb{N}$ значение $f(n)$ представляет собой “номер” элемента $\nu(n)$ в нумерации $\nu^*$. Это позволяет алгоритмически переписать систему $T$ с коэффициентами в $C$ в виде эквивалентной системы $T^*$ с коэффициентами в $\langle C \rangle$. Это сводит $\mathcal{D}_C(\mathcal{A})$ к $\mathcal{D}_{\langle C \rangle}(\mathcal{A})$.

Мы опускаем не вызывающее затруднений доказательство утверждения 2).

Лемма доказана.

Далее мы всегда полагаем, без ограничения общности, что коэффициенты в диофантовой проблеме принадлежат счетной подструктуре $\langle C\rangle$, а не множеству $C$.

3.2. Диофантовы множества и е-интерпретируемость

Чтобы доказать, что $\mathcal{D}(\mathcal{A})$ сводится к $\mathcal{D}(\mathcal{M})$ для некоторых структур $\mathcal{A}$ и $\mathcal{M}$, достаточно показать, что $\mathcal{A}$ интерпретируема при помощи уравнений (или е-интерпретируема) в $\mathcal{M}$.

Понятие е-интерпретируемости было введено в [19], [20], [10]. Напомним соответствующие определения и приведем основные факты, которые будут использованы ниже.

Далее мы используем некурсивное полужирное начертание для обозначения кортежей элементов, т. е. $\mathbf{a}=(a_1, \dots, a_n)$. Более того, мы всегда предполагаем, что уравнения могут содержать константы из алгебраической структуры, в которой они рассматриваются.

Определение 3.4. Подмножество $D \subset M^m$ называется диофантовым, или определимым системами уравнений в $\mathcal{M}$, или е-определимым в $\mathcal{M}$, если существует конечная система уравнений $\Sigma_{D}(x_1,\dots,x_m, y_1, \dots, y_k)$ в сигнатуре структуры $\mathcal{M}$ такая, что для любого кортежа $\mathbf{a}\in M^m$ имеет место $\mathbf{a} \in D$, если и только если система $\Sigma_{D}(\mathbf{a}, \mathbf{y})$ с переменными $\mathbf {y}$ имеет решение в $\mathcal{M}$. В таком случае говорим, что $\Sigma_D$ е-определяет $D$ в $\mathcal{M}$.

Замечание 3.5. Отметим, что, в тех же обозначениях, если подмножество $D \subset M^m$ е-определимо, то оно определимо в $\mathcal{M}$ формулой $\exists \, \mathbf{y} \Sigma_{D}(\mathbf{x}, \mathbf{y})$. Такие формулы называются позитивно-примитивными, или пп-формулами. Таким образом, е-определимые подмножества иногда называются пп-определимыми. С другой стороны, в теории чисел такие множества обычно называются диофантовыми. Наконец, в терминах алгебраической геометрии их можно описать как проекции алгебраических множеств.

Определение 3.6. Алгебраическая структура $\mathcal{A}= (A; f, \dots, r, \dots, c, \dots)$ называется е-интерпретируемой в другой алгебраической структуре $\mathcal{M}$, если существует $n\in \mathbb{N}$, подмножество $D \subseteq \mathcal{M}^n$ и сюръективное отображение (оно называется интерпретирующим отображением) $\phi\colon D \twoheadrightarrow \mathcal{A}$ такое, что:

1) $D$ е-определимо в $\mathcal{M}$;

2) для каждой функции $f=f(y_1, \dots, y_k)$ в сигнатуре структуры $\mathcal{A}$ прообраз относительно $\phi$ графика $f$, т. е. множество

$$ \begin{equation*} \{(\overline{x}_1, \dots, \overline{x}_k, \overline{x}_{k+1})\in D^{k+1} \mid \phi(\overline{x}_{k+1}) = f(\phi(\overline{x}_1), \dots, \phi(\overline{x}_k))\}, \end{equation*} \notag $$
где для каждого $1\leqslant i \leqslant k+1$, $\overline{x}_i=(x_{i1}, \dots, x_{in})$, является е-определимым в $\mathcal{M}$;

3) для каждого отношения $r$ в сигнатуре структуры $\mathcal{A}$, а также для отношения равенства $=$ в $\mathcal{A}$, прообраз относительно $\phi$ графика $r$ является е-определимым в $\mathcal{M}$.

Предположим, что $\mathcal{A}$ е-интерпретируема в $\mathcal{M}$ в соответствии с определением 3.6 выше. Эта интерпретация полностью задается отображением $\phi$ и набором $\Gamma$, состоящим из диофантовых формул, которые определяют множество $D$ из п. 1), функции $f$ из п. 2) и отношения $r$ из п. 3). Через $P_\Gamma \subseteq \mathcal{M}$ обозначим конечное множество констант (параметров), которые встречаются в формулах набора $\Gamma$. Понятие e-интерпретируемости является частным случаем классического понятия интерпретируемости формулами первого порядка, когда вместо произвольных формул первого порядка для интерпретирования используются конечные системы уравнений. Отметим, что в теории чисел существуют понятия диофантового определения и диофантового порождения, введенные Шлапентох [5] непосредственно для изучения десятой проблемы Гильберта в числовых полях и играющие роль, аналогичную роли е-интерпретируемости.

Следующая лемма описывает фундаментальное свойство е-интерпретируемости. Интуитивно, она утверждает, что если $\mathcal{A}$ е-интерпретируема в $\mathcal{M}$ при помощи формул $\Gamma$ и интерпретирующего отображения $\phi\colon D \twoheadrightarrow \mathcal{A}$, то любая система уравнений в $\mathcal{A}$ может быть алгоритмически “закодирована” эквивалентной системой в $\mathcal{M}$. Для формулировки потребуются следующие обозначения. Пусть $C$ – конечное или счетное подмножество $\mathcal{A}$, снабженное нумерацией $\nu\colon \mathbb{N} \to C$. Для каждого $c_i = \nu(i) \in C$ зафиксируем произвольный кортеж $d_i \in \phi^{-1}(c_i)$. Через $D_C$ обозначим множество всех элементов в $\mathcal{M}$, которые встречаются в качестве компонент кортежей $d_i$ из $\phi^{-1}(C)$. Через $C_\Gamma$ обозначим множество $D_C \cup P_\Gamma $. Будем говорить, что нумерация $\nu^*\colon \mathbb{N} \to C_\Gamma$ совместима с нумерацией $\nu$ (по отношению к множеству представителей $\{d_i \mid i \in \mathbb{N}\}$), если существует алгоритм, который по каждому $i \in \mathbb{N}$ вычисляет номера относительно $\nu^*$ компонент кортежа $d_i$. Например, можно сначала пронумеровать все элементы в $P_\Gamma$, а затем для $ i = 1,2,\dots$ пронумеровать в естественном порядке все компоненты $d_1,d_2, \dots$ .

Лемма 3.7 (см. [19]). Пусть $\mathcal{A}$ е-интерпретируема в $\mathcal{M}$ при помощи набора формул $\Gamma$ и интерпретирующего отображения $\phi\colon D \twoheadrightarrow \mathcal{A}$ (в обозначениях определения 3.6). Пусть $C$ – конечное или счетное подмножество $\mathcal{A}$, снабженное нумерацией $\nu$. Тогда есть работающий за полиномиальное время алгоритм, который по каждой конечной системе уравнений $S(\mathbf{x})$ в $\mathcal{A}$ с коэффициентами в $C$ строит конечную систему уравнений $S^*(\mathbf{y}, \mathbf{z})$ в $\mathcal{M}$ с коэффициентами в множестве $C_\Gamma$ (заданном через совместимую нумерацию $\nu^*\colon \mathbb{N} \to C_\Gamma $) такую, что если $(\mathbf{b}, \mathbf{c})$ является решением $S^*(\mathbf{y}, \mathbf{z})$ в $\mathcal{M}$, то $\mathbf{b}\in D$ и $\phi(\mathbf{b})$ является решением $S(\mathbf{x})$ в $\mathcal{A}$. Более того, любое решение $\mathbf{a}$ системы $S(\mathbf{x})$ в $\mathcal{A}$ возникает таким образом, т. е. $\mathbf{a} = \phi(\mathbf{b})$ для некоторого решения $(\mathbf{b}, \mathbf{c})$ системы $S^*(\mathbf{y}, \mathbf{z})$ в $\mathcal{M}$.

Теперь приведем два ключевых следствия леммы 3.7.

Следствие 3.8. Пусть $\mathcal{A}$ е-интерпретируема в $\mathcal{M}$ при помощи набора формул $\Gamma$ и интерпретирующего отображения $\phi\colon D \twoheadrightarrow \mathcal{A}$ (в обозначениях определения 3.6). Пусть $C$ – конечное или счетное подмножество $\mathcal{A}$, снабженное нумерацией $\nu$. Тогда диофантова проблема в $\mathcal{A}$ с коэффициентами в $C$ сводится за полиномиальное время (сводится по Карпу) к диофантовой проблеме в $\mathcal{M}$ с коэффициентами в $C_\Gamma$ по отношению к любой совместимой с $\nu$ нумерации $\nu^*$. Следовательно, если $\mathcal{D}_C(\mathcal{A})$ неразрешима, то и $\mathcal{D}_{C_\Gamma}(\mathcal{M})$ (относительно нумерации $\nu^*$) неразрешима.

Следствие 3.9. e-Интерпретируемость является транзитивным отношением, т. е. если $\mathcal{A}_1$ е-интерпретируема в $\mathcal{A}_2$, а $\mathcal{A}_2$ е-интерпретируема в $\mathcal{A}_3$, то $\mathcal{A}_1$ е-интерпретируема в $\mathcal{A}_3$.

§ 4. Диофантова структура больших подгрупп в $\mathrm{GL}_n(R)$ и $\mathrm{PGL}_n(R)$

В этом параграфе мы покажем, что многие важные подгруппы классических матричных групп над $R$ являются диофантовыми. Всюду далее мы используем обозначения из § 2.

4.1. Диофантовость однопараметрических подгрупп $\mathrm{T}_{ij}$ в больших подгруппах $\mathrm{GL}_n(R)$

Мы начинаем со следующего ключевого результата.

Теорема 4.1. Пусть $G$ – большая подгруппа в $ \mathrm{GL}_n(R) $, $ n \geqslant 3 $. Тогда для любых $ 1 \leqslant k \neq m \leqslant n $ однопараметрическая подгруппа $ \mathrm{T}_{km} $ диофантова в $G$ (определена при помощи констант из множества $ \{t_{ij}(1) \mid 1 \leqslant i \neq j \leqslant n \} $).

Доказательство. Пусть $x=(x_{st})\in G$ и предположим, что $xt_{ij}=t_{ij}x$. Без потери общности будем считать, что $i<j$, тогда
$$ \begin{equation*} \begin{aligned} \, &\begin{pmatrix} x_{11}&x_{12}& \cdots & x_{1i}& \cdots & x_{1j} & \cdots & x_{1n} \\ x_{21}&x_{22}& \cdots & x_{2i}& \cdots & x_{2j} & \cdots & x_{2n}\\ \vdots &\vdots &\ddots &\vdots &\vdots &\vdots & \vdots&\vdots \\ x_{i1}+x_{j1}&x_{i2}+x_{j2}& \cdots & x_{ii}+x_{ji} &\cdots & x_{ij}+x_{jj} & \cdots & x_{in}+x_{jn} \\ \vdots &\vdots &\vdots &\vdots &\ddots &\vdots & \vdots &\vdots\\ x_{j1}&x_{j2}& \cdots & x_{ji}&\cdots & x_{jj} & \cdots & x_{jn}\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots & \ddots &\vdots \\ x_{n1} &x_{n2}& \cdots & x_{ni} &\cdots & x_{nj} & \cdots & x_{nn} \end{pmatrix}=t_{ij}x \\ &\qquad=xt_{ij} = \begin{pmatrix} x_{11}& x_{12}& \cdots & x_{1i}& \cdots & x_{1i}+ x_{1j} & \cdots & x_{1n}\\ x_{21} & x_{22}& \cdots & x_{2i} & \cdots & x_{2i}+x_{2j} & \cdots & x_{2n}\\ \vdots &\vdots &\ddots &\vdots &\vdots &\vdots & \vdots &\vdots\\ x_{i1}& x_{i2}& \cdots & x_{ii} &\cdots & x_{ii}+x_{ij} & \cdots & x_{in} \\ \vdots &\vdots &\vdots &\vdots &\ddots &\vdots & \vdots &\vdots\\ x_{j1}& x_{j2}& \cdots & x_{ji}&\cdots & x_{ji}+x_{jj} & \cdots & x_{jn}\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots & \ddots&\vdots\\ x_{n1} & x_{n2}& \cdots & x_{ni} &\cdots & x_{ni} +x_{nj} & \cdots & x_{nn} \end{pmatrix}. \end{aligned} \end{equation*} \notag $$

Сравнивая строку с номером $i$ и столбец с номером $j$ двух матриц, мы видим, что каждый недиагональный элемент $i$-го столбца и $j$-й строки матрицы $x$ должен быть нулем и $x_{ii}=x_{jj}$, так что,

$$ \begin{equation} x\in C_G(t_{ij})\quad \Longleftrightarrow \quad \begin{cases} x_{ii}=x_{jj}, & \\ x_{st}=0, &\text{ если } s\neq t, \text{ и } s=j \text{ или } t=i. \end{cases} \end{equation} \tag{6} $$
Следовательно, для фиксированного $k\neq m$, каждый $t_{ij}$, где $i\neq m$ и $j\neq k$, принадлежит $C_G(t_{km})$.

Положим $S_{km} = \{t_{ij}\,|\, i\neq m,\, j\neq k\}$. Рассмотрим следующий централизатор в группе $G$:

$$ \begin{equation} C_G(S_{km}) = \bigcap_{1\leqslant i\neq m,\, j\neq k\leqslant n}C_G(t_{ij}). \end{equation} \tag{7} $$

Предположим теперь, что $x\in C_G(S_{km})$, и рассмотрим $x_{ij}$, где $i\neq j$ и $(i,j)\neq (k,m)$. Если $i\neq k$ и $j\neq m$, то $t_{ji}\in S_{km}$ и $x_{ij}=0$ согласно (6). Пусть $i=k$, но $j\neq m$. Тогда $t_{jm}\in S_{km}$. Снова, согласно (6), имеем $x_{ij}=0$. Оставшийся случай рассматривается также, как и уже разобранный выше. Поэтому,

$$ \begin{equation*} x\in C_G(S_{km})\quad \Rightarrow\quad \begin{cases} x_{ij}=0, &\text{ если } i\neq j \text{ и } (i,j)\neq (k,m), \\ x_{ii}=x_{jj} &\text{ для всех } 1\leqslant i,j \leqslant n. \end{cases} \end{equation*} \notag $$

Отметим, что если $x \in C_G(S_{km})$ и $x_{11} = \alpha, x_{km} = \beta$, то $x = d(\alpha)t_{km}(\alpha^{-1}\beta)$, так что матрица $d(\alpha)$ принадлежит $G$. Следовательно, $C_G(S_{km}) = R_G \mathrm{T}_{km}$, где $R_G = R^\times_n \cap G$ есть подгруппа всех скалярных матриц над $R^\times$, принадлежащих $G$.

Отметим, что любая скалярная матрица в $G$ перестановочна с любой трансвекцией вида $t_{ij}, i \neq j$. Таким образом,

$$ \begin{equation*} \mathrm{T}_{km}=[C_G(S_{kj}),t_{jm}] \end{equation*} \notag $$
для любых $j \neq k,m$. Значит, подгруппа $C_G(S_{kj})$ диофантова как централизатор конечного множества трансвекций, следовательно, множество $\mathrm{T}_{km}$ также является диофантовым. Теорема доказана.

Следствие 4.2. Пусть $G = \mathrm{GL}_n(R)$, $n \geqslant 3$. Тогда для любых $1\leqslant k \neq m\,{\leqslant}\, n$ подгруппа $\mathrm{T}_{km}$ диофантова в $G$ (с константами $t_{ij}, 1\leqslant i \neq j \leqslant n$).

Следствие 4.3. Пусть $R$ – коммутативное кольцо и $G = \mathrm{SL}_n(R)$, $n \geqslant 3$. Тогда для любых $1\leqslant k \neq m \leqslant n$ подгруппа $\mathrm{T}_{km}$ диофантова в $G$ (с константами $t_{ij}, 1\leqslant i \neq j \leqslant n$).

4.2. Диофантовость $\mathrm{UT}_n(R)$ и $\mathrm{T}_n(R)$ в больших подгруппах $\mathrm{GL}_n(R)$

Этот пункт мы начнем с доказательства небольшой леммы, которая не раз пригодится далее в статье.

Лемма 4.4. Пусть $A_1, \dots,A_k$ – диофантовы подмножества в группе $H$. Тогда их произведение $A = A_1 \cdots A_k$ диофантово в $H$.

Доказательство. Достаточно заметить, что $x \in H$ принадлежит $A$ тогда и только тогда, когда следующая формула выполнена в группе $H$:
$$ \begin{equation*} \exists \, y_1 \dots \exists \, y_k(a = y_1 \cdots y_k) \wedge \biggl(\bigwedge_{i = 1}^k(y_i \in A_i)\biggr). \end{equation*} \notag $$
Так как множества $A_i$ диофантовы в $H$, то формула выше описывает диофантово подмножество в $H$. Лемма доказана.

Предложение 4.5. Пусть $G$ – большая подгруппа в $\mathrm{GL}_n(R)$, $n \geqslant 3$. Тогда для любого $1\leqslant m\leqslant n-1$ подгруппа $\mathrm{UT}_n^m(R)$ является диофантовой в $G$. В частности, $\mathrm{UT}_n(R)$ диофантова в $G$.

Доказательство. Зафиксируем $1\leqslant m \leqslant n-1$ и пусть $\mathrm{UT}^n_n(R)=\{1\}$. По (5) получаем, что
$$ \begin{equation*} \mathrm{UT}_n^m(R) = \mathrm{T}_{n-m,n} \mathrm{T}_{n-m-1,n-1} \cdots \mathrm{T}_{1,1+m}\mathrm{UT}_n^{m+1}(R). \end{equation*} \notag $$
Положим
$$ \begin{equation*} P_m = \mathrm{T}_{n-m,n} \mathrm{T}_{n-m-1,n-1} \cdots \mathrm{T}_{1,1+m}. \end{equation*} \notag $$
Тогда
$$ \begin{equation} \mathrm{UT}_n^m(R) = P_m P_{m+1} \cdots P_{n-1}. \end{equation} \tag{8} $$

Из (8) следует, что каждая подгруппа $\mathrm{UT}_n^m(R)$ является некоторым конечным произведением однопараметрических подгрупп $\mathrm{T}_{ij}$. По лемме 4.1, каждая подгруппа $\mathrm{T}_{ij}$ является диофантовой в $G$. Таким образом, доказываемое предложение следует из леммы 4.4. Предложение доказано.

Лемма 4.6. Пусть $G$ – большая подгруппа в $\mathrm{GL}_n(R)$, $n \geqslant 3$. Тогда множество $R_G$ всех скалярных матриц из $G$ является диофантовым в $G$.

Доказательство. Заметим, что $R_G$ есть в точности централизатор множества всех трансвекций $\{t_{ij} \mid 1\leqslant i \neq j \leqslant n\}$. Следовательно, $R_G$ диофантово в $G$. Лемма доказана.

Предложение 4.7. Пусть $G$ – большая подгруппа $\mathrm{GL}_n(R)$, $n \geqslant 3$. Тогда если $R^+$ не содержит элементов порядка $2$, то верны следующие утверждения:

1) $G\cap D_n(R)$ диофантово в $G$;

2) $G\cap \mathrm{T}_n(R)$ диофантово в $G$.

Доказательство. Для доказательства п. 1) для любого $1\leqslant k \neq m \leqslant n$ положим $d_{km} = d_k(-1)d_m(-1)$, т. е. $d_{km}= \operatorname{diag}(\beta_1, \dots, \beta_n)$, где $\beta_k = -1$, $\beta_m\,{=}\,{-}1$ и $\beta_i=1$, если $i\neq k,m$. Заметим, что для $x = (x_{ij}) \in \mathrm{GL}_n(R)$
$$ \begin{equation*} \begin{aligned} \, &xd_{km} = d_{km}x \\ &\qquad\Longleftrightarrow\quad \bigwedge_{i \neq m,k}[(-x_{im} = x_{im}) \wedge(-x_{m i} = x_{m i}) \wedge (-x_{i k}=x_{ik}) \wedge(-x_{k i}=x_{ki})]. \end{aligned} \end{equation*} \notag $$

Так как $R^+$ не содержит элементов порядка 2 и $k$ пробегает все возможные значения, то из правой части эквивалентности выше имеем $x_{m i} = x_{im} = 0$ для всех $i \neq m$.

Значит, система уравнений

$$ \begin{equation*} \bigwedge_{1 \leqslant i\neq j \leqslant n} xd_{ij} = d_{ij}x \end{equation*} \notag $$
определяет $D_n(R)$ в $G$.

Для доказательства п. 2) отметим сначала, что группа $\mathrm{UT}_n(R)$ нормальна в $\mathrm{T}_n(R)$. Поэтому $G\cap \mathrm{T}_n(R) = (G\cap D_n(R)) \mathrm{UT}_n(R)$ есть произведение двух диофантовых подгрупп из $G$ выше (по предыдущему пункту и предложению 4.5). Поэтому по лемме 4.4 $\mathrm{T}_n(R)$ диофантово в $G$. Предложение доказано.

4.3. Диофантовы подгруппы в $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$

Пусть $\phi\colon\mathrm{GL}_n(R){\kern1pt}{\to} \mathrm{PGL}_n(R)$ – канонический эпиморфизм. Образ подгруппы $H$ из $\mathrm{GL}_n(R)$ под действием $\phi$ обозначим через $H^\phi$. Напомним, что подгруппа $G$ из $\mathrm{PGL}_n(R)$ является большой, если она содержит $\phi(\mathrm{E}_n(R))$, т. е. $G = H^\phi$ для некоторой большой подгруппы $H$ из $\mathrm{GL}_n(R)$.

Отметим, что для $1\leqslant i\neq j\leqslant n$, $\ker(\phi)\cap \mathrm{T}_{ij}=\{I_n\}$ и $\mathrm{T}_{ij}^\phi\cong \mathrm{T}_{ij}$.

Предложение 4.8. Пусть $G$ является большой подгруппой в $\mathrm{PGL}_n(R)$, где $n \geqslant 3$ и $R$ не содержит делителей нуля. Тогда для любого $1\leqslant i\neq j \leqslant n$, подгруппа $\mathrm{T}_{ij}^\phi$ диофантова в $G$.

Доказательство. Пусть $H{\kern1pt}{=}{\kern1pt}\phi^{-1}(G)$, тогда $H$ большая подгруппа в $\mathrm{GL}_n(R)$. Рассмотрим множество $S_{km} = \{t_{ij}\mid i\neq m,\, j\neq k\}$ в $H$, введенное в доказательстве теоремы 4.1, и пусть $S_{km}^\phi= \{t^\phi_{ij}\mid i\neq m,\, j\neq k\}$.

Заметим, что для $y\in G$ и $x\in H$, для которых $\phi(x)=y$, $yt^\phi_{ij}=t_{ij}^\phi y$ тогда и только тогда, когда существует $z\in R_H$ такой, что $t_{ij} x=xt_{ij}z$ для $x=(x_{st})\,{\in}\, H$. Без потери общности можем предположить, что $i<j$. Тогда

$$ \begin{equation*} \begin{aligned} \, &\begin{pmatrix} x_{11}&x_{12}& \cdots & x_{1i}& \cdots & x_{1j} & \cdots & x_{1n} \\ x_{21}&x_{22}& \cdots & x_{2i}& \cdots & x_{2j} & \cdots & x_{2n}\\ \vdots &\vdots &\ddots &\vdots &\vdots &\vdots & \vdots&\vdots \\ x_{i1}+x_{j1}&x_{i2}+x_{j2}& \cdots & x_{ii}+x_{ji} &\cdots & x_{ij}+x_{jj} & \cdots & x_{in}+x_{jn} \\ \vdots &\vdots &\vdots &\vdots &\ddots &\vdots & \vdots &\vdots\\ x_{j1}&x_{j2}& \cdots & x_{ji}&\cdots & x_{jj} & \cdots & x_{jn}\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots & \ddots &\vdots \\ x_{n1} &x_{n2}& \cdots & x_{ni} &\cdots & x_{nj} & \cdots & x_{nn} \end{pmatrix}=t_{ij}x \\ &\qquad=xt_{ij} z=\begin{pmatrix}\alpha x_{11}&\alpha x_{12}& \cdots & \alpha x_{1i}& \cdots & \alpha(x_{1i}+ x_{1j}) & \cdots & \alpha x_{1n}\\ \alpha x_{21} &\alpha x_{22}& \cdots & \alpha x_{2i} & \cdots & \alpha(x_{2i}+x_{2j}) & \cdots & \alpha x_{2n}\\ \vdots &\vdots &\ddots &\vdots &\vdots &\vdots & \vdots &\vdots\\ \alpha x_{i1}&\alpha x_{i2}& \cdots & \alpha x_{ii} &\cdots & \alpha(x_{ii}+x_{ij}) & \cdots & \alpha x_{in} \\ \vdots &\vdots &\vdots &\vdots &\ddots &\vdots & \vdots &\vdots\\ \alpha x_{j1}&\alpha x_{j2}& \cdots & \alpha x_{ji}&\cdots & \alpha(x_{ji}+x_{jj}) & \cdots & \alpha x_{jn}\\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots & \ddots&\vdots\\ \alpha x_{n1} &\alpha x_{n2}& \cdots & \alpha x_{ni} &\cdots & \alpha (x_{ni} +x_{nj}) & \cdots & \alpha x_{nn} \end{pmatrix}, \end{aligned} \end{equation*} \notag $$
где $z=\alpha I$, $\alpha \in R$. Рассмотрим столбец с номером $i$ обеих матриц и сравним недиагональные $(s,i)$-элементы, $s \neq i$. Имеем $x_{si}=\alpha x_{si}$. Значит, либо $x_{si}=0$, либо $\alpha=1$, так как $R$ не содержит делителей нуля. Предположим $\alpha \neq 1$. Тогда $x_{si}=0$ для всех $s \neq i$. Сравнивая диагональные элементы $i$-х столбцов, имеем $x_{ii}+x_{ji} = \alpha x_{ii}$. Так как $x_{ji} = 0$, то $x_{ii} = \alpha x_{ii}$ и, значит, $x_{ii} = 0$. Поэтому весь столбец с номером $i$ в матрице $x$ состоит из нулей, что противоречит тому, что $x \in \mathrm{GL}_n(R)$ есть обратимая матрица. Следовательно, $\alpha = 1$. Из этого вытекает, что равенство $t_{ij}x = xt_{ij} z$ выше превращается в $t_{ij}x = xt_{ij}$.

Следуя теореме 4.1, получаем равенство

$$ \begin{equation*} [C_G(S^\phi_{kj}),t_{jm}^\phi] = [\mathrm{T}_{kj}R_H,t_{jm}]^\phi = \mathrm{T}_{km}^\phi, \end{equation*} \notag $$
а значит, $T^\phi_{km}$ диофантово в $G$. Предложение доказано.

Следствие 4.9. Если $G$ – большая подгруппа в $\mathrm{PGL}_n(R)$ и кольцо $R$ не содержит делителей нуля, то $\mathrm{UT}^\phi_n(R)$ диофантова подгруппа в $G$.

Доказательство следует из леммы 4.4 и предложения 4.8.

Следствие 4.10. Пусть $G=\mathrm{PGL}_n(R)$ или $G=\mathrm{PSL}_n(R)$ (в этом случае мы полагаем, что кольцо $R$ коммутативно). Если $R$ не содержит делителей нуля и $R^+$ не имеет элементов порядка $2$, то истинны следующие утверждения:

1) $G\cap D^\phi_n(R)$ диофантово в $G$;

2) $G\cap \mathrm{T}_n^{\phi}(R)$ диофантово в $G$.

Доказательство. По аналогии с доказательством предложения 4.7, пусть $d_{ij}=d_id_j$. Заметим, что $d_{ij}^\phi\neq 1$. Пусть $G_1=C_G(\{d^\phi_{ij}\mid 1\leqslant i\neq j\leqslant n\})$, и $H_1=C_H(\{d_{ij}\mid 1\leqslant i\neq j\leqslant n\})= H\cap D_n(R)$. Пусть $y\in G_1$ и $\phi(x)=y$, $x\in H$. Тогда если $yd_{km}^\phi=d_{km}^\phi y$, то существует $z=\alpha I\in R_H$ такой, что
$$ \begin{equation*} \bigwedge_{i \neq k,m}[(-x_{im} = \alpha x_{im}) \wedge(-x_{m i} = \alpha x_{m i}) \wedge (-x_{i k}=\alpha x_{ik}) \wedge(-x_{k i}=\alpha x_{ki})], \end{equation*} \notag $$
а также $-x_{kk}=-\alpha x_{kk}$ и $-x_{mm}=-\alpha x_{mm}$. Таким образом, получаем, что $(1-\alpha)x_{kk}=0$. Так как $R$ не содержит делителей нуля, то либо $\alpha=1$, либо $x_{kk}=0$.

Введем множество позитивных экзистенциальных предложений, чтобы исключить последний случай. Без потери общности мы можем предположить, что $k=1$. Напомним, что $T^\phi_{ij}$ диофантово в $G$. Итак, рассмотрим позитивные экзистенциальные предложения

$$ \begin{equation*} \exists \, \overline{u} \biggl(\bigwedge_{1\leqslant i\neq j \leqslant n} \bigl((yd_{ij}^\phi=d_{ij}^\phi y ) \wedge (y t^\phi_{ij}y^{-1}=u_{ij})\wedge (u_{ij}\in T^\phi_{ij})\bigr)\biggr). \end{equation*} \notag $$

Это значит, что $x$ удовлетворяет $xt_{1m}=t_{1m}(\beta_m)x z_m$ для некоторых $\beta_m\in R$ и $z_m=\alpha_m I \in R_H$. Отметим, что $\beta_m \neq 0$.

Докажем от противного, что $x_{11}\neq 0$. Предположим $x_{11}=0$ и для каждого $m\neq 1$ применим соответствующее уравнение к $x$. Прямыми матричными вычислениями и сравнением $(1,1)$-элементов получившихся матриц с двух сторон уравнения, мы получаем $0=\beta_m\alpha_m x_{m 1}$ и для всех $m$, $x_{m 1}=0$. Таким образом, первый столбец в $x$ полностью состоит из нулей, а значит, матрица $x$ необратима, что не так. Поэтому $\alpha=1$ и доказательство в этом случае такое же, как и в предложении 4.7. Следствие доказано.

§ 5. Диофантова структура больших подгрупп $\mathrm{T}_n(R)$

Следующий результат перекликается с теоремой 4.1 о диофантовости однопараметрических подгрупп $\mathrm{T}_{ij}$ в больших подгруппах из $\mathrm{GL}_n(R)$. Однако, так как $\mathrm{T}_n(R)$ содержит только трансвекции типа $t_{ij}(\alpha)$, $i<j$, то обоснование следующей теоремы несколько сложнее, а результат несколько слабее, чем в случае с $\mathrm{GL}_n(R)$.

Теорема 5.1. Пусть $G$ – большая подгруппа в $\mathrm{T}_n(R)$, $n \geqslant 3$. Тогда верны следующие утверждения:

1) для всех $1\leqslant i, j \leqslant n$ таких, что $j-i \geqslant 2$ подгруппа $\mathrm{T}_{ij}$ диофантова в $G$;

2) для всех $1 \leqslant i < n$ подгруппа $R_G \mathrm{T}_{i,i+1}\mathrm{T}_{1n}$ диофантова в $G$.

Доказательство. Положим $x=(x_{ij})\in G$,
$$ \begin{equation*} x\in C_G(t_{km})\quad \Longleftrightarrow\quad \begin{cases} x_{kk}=x_{mm}, & \\ x_{ij}=0, &\text{ если } i\neq j, \text{ либо } j=k, \text{ либо } i=m. \end{cases} \end{equation*} \notag $$

Из этого следует, что для $1\leqslant k < m \leqslant n$ централизатор множества

$$ \begin{equation*} S_{km} = \{t_{km}, t_{1i}, t_{jn} \mid i \neq 1, k;\, j\neq m,n\} \end{equation*} \notag $$
в $G$ состоит из матриц $x = (x_{ij})$, где $x_{ij} = 0$, если $i <j$, $(i,j) \notin \{(k,m), (1,m), (k,n),(1,n)\}$ и $x_{11} = \dots = x_{nn}$. Обозначим этот централизатор (а значит, диофантово в $G$ множество) через $C_{km}$.

Для удобства вычислений представим элемент $x = (x_{ij}) \in C_{km}$ как следующее произведение, зависящее от $k,m$ и $n$. Итак, если $1 < k < m < n$, то

$$ \begin{equation*} x = d(\sigma) t_{1m}(\sigma^{-1}\alpha)t_{km}(\sigma^{-1}\beta)t_{kn}(\sigma^{-1} \gamma)t_{1n}(\sigma^{-1}\delta), \end{equation*} \notag $$
где $x_{11} = \sigma$, $x_{1m} = \alpha$, $x_{km} = \beta$, $x_{kn} = \gamma$ и $x_{1n} = \delta$. Если $1=k < m < n$, тогда в обозначениях выше
$$ \begin{equation*} x = d(\sigma) t_{1m}(\sigma^{-1}\alpha)t_{1n}(\sigma^{-1}\delta). \end{equation*} \notag $$
Если $1 < k < m = n$, то
$$ \begin{equation*} x = d(\sigma) t_{kn}(\sigma^{-1} \gamma)t_{1n}(\sigma^{-1}\delta), \end{equation*} \notag $$
и в случае $1=k$, $m=n$,
$$ \begin{equation*} x = d(\sigma) t_{1n}(\sigma^{-1}\delta). \end{equation*} \notag $$

Скалярная матрица $d(\sigma)$ выше принадлежит $G$, так как $G$ содержит $x$ и $\mathrm{UT}_{n}(R)$. Также заметим, что $C_{km}$ содержит $R_G$ – подгруппу всех скалярных матриц из $G$, так как $[R_G,t_{ij}] = 1$ для любой трансвекции $t_{ij}$. Таким образом, имеем

$$ \begin{equation*} C_{km} =R_G\mathrm{T}_{1m}\mathrm{T}_{km}\mathrm{T}_{kn}\mathrm{T}_{1n}. \end{equation*} \notag $$
В частности, для любых $j>1$ и любых $i<n$
$$ \begin{equation} C_{1j} = R_G\mathrm{T}_{1j}\mathrm{T}_{1n}, \qquad C_{in} = R_G\mathrm{T}_{in}\mathrm{T}_{1n}. \end{equation} \tag{9} $$

Далее для $j>2$ имеем

$$ \begin{equation*} \mathrm{T}_{1j} = [C_{1,j-1},t_{j-1,j}], \end{equation*} \notag $$
а значит, $\mathrm{T}_{1j}$ диофантово в $G$, так как множество $C_{1,j-1}$ является диофантовым. Аналогично, для $i<n-1$ имеем
$$ \begin{equation*} \mathrm{T}_{i,n} = [t_{i,i+1},C_{i+1,n}], \end{equation*} \notag $$
и это значит, что $\mathrm{T}_{i,n}$ тоже диофантово в $G$.

Предположим теперь, что $1<i<j<n$, $j-i\geqslant 2$. Заметим, что множество $[C_{i,j-1},t_{j-1,j}]$ состоит из матриц вида $x = (x_{st}) \in G$ таких, что $x_{st} = 0$ для всех $s<t$, где $(s,t) \notin \{(1,j), (i,j)\}$. Очевидно, это множество диофантово. Аналогично, множество $[t_{i,i+1},C_{i+1,j}]$ является диофантовым и состоит из матриц $x = (x_{st}) \in G$ таких, что $x_{st} = 0$, где $s<t$ и $(s,t) \notin \{(i,j),(i,n)\}$. Поэтому множество

$$ \begin{equation*} \mathrm{T}_{ij} = [C_{i,j-1},t_{j-1,j}] \cap [t_{i,i+1},C_{i+1,j}], \end{equation*} \notag $$
является диофантовым как пересечение двух диофантовых множеств. Пункт 1) теоремы доказан.

Для доказательства п. 2) заметим сначала, что (9) влечет $R_G\mathrm{T}_{12}\mathrm{T}_{1n} = C_{12}$ и $R_G\mathrm{T}_{n-1,n}\mathrm{T}_{1n} = C_{n-1,n}$, поэтому эти множества диофантовы в $G$.

Зафиксируем $1<i<n-1$. Пусть $x = (x_{st}) \in C_{i,i+1}$. Тогда $[x,t_{i+1,i+2}] = t_{1,i+2}(\alpha)t_{i,i+2}(\beta)$, где $\sigma^{-1}x_{1,i+1} = \alpha$ и $\sigma^{-1}x_{i,i+1} = \beta$, где $\sigma=x_{11}$. Следовательно, $x_{1,i+1} = 0$ тогда и только тогда, когда

$$ \begin{equation*} [x,t_{i+1,i+2}] = t_{i,i+2}(\beta) \in \mathrm{T}_{i,i+2}. \end{equation*} \notag $$
Это условие диофантово, так как множество $\mathrm{T}_{i,i+2}$ диофантово по первому пункту теоремы. Аналогично, для таких матриц $x$ имеем $x_{in} = 0$ тогда и только тогда, когда $[t_{i-1,i},x] \in \mathrm{T}_{i-1,i+1}$. Это условие также диофантово в $G$. Пересечение этих двух условий является диофантовым условием, и оно описывает подгруппу $R_G\mathrm{T}_{i,i+1}\mathrm{T}_{1n}$ в $G$. Пункт 2) теоремы доказан.

Теорема доказана.

Следствие 5.2. Пусть $G = \mathrm{T}_n(R)$, $n \geqslant 3$. Верны следующие утверждения:

1) для всех $1\leqslant i, j \leqslant n$, для которых $j-i \geqslant 2$, подгруппа $\mathrm{T}_{ij}$ диофантова в $G$;

2) для всех $1 \leqslant i < n$ подгруппа $R_G \mathrm{T}_{i,i+1}\mathrm{T}_{1n}$ диофантова в $G$.

Следствие 5.3. Пусть $G = \mathrm{UT}_n(R)$, $n \geqslant 3$. Верны следующие утверждения:

1) для всех $1\leqslant i, j \leqslant n$, для которых $j-i \geqslant 2$, подгруппа $\mathrm{T}_{ij}$ диофантова в $G$;

2) для всех $1 \leqslant i < n$ подгруппа $\mathrm{T}_{i,i+1}\mathrm{T}_{1n}$ диофантова в $G$.

Предложение 5.4. Пусть $G$ – большая подгруппа в $\mathrm{T}_n(R)$, $n \geqslant 3$. Тогда

1) подгруппа $R_G$ е-интерпретируема в $G$;

2) подгруппа $R_G \mathrm{UT}_n(R)$ диофантова в $G$.

Доказательство. Для доказательства п. 1) заметим, что
$$ \begin{equation*} R_G \mathrm{T}_{1n} = R_G\mathrm{T}_{12}\mathrm{T}_{1n} \cap R_G\mathrm{T}_{23}\mathrm{T}_{1n} \end{equation*} \notag $$
является диофантовым как пересечение диофантовых подгрупп $G$ (по теореме 5.1). Подгруппа $\mathrm{T}_{1n}$ также диофантова в $G$. Следовательно, факторгруппа $R_G \mathrm{T}_{1n}/\mathrm{T}_{1n} \simeq R_G$ е-интерпретируема в $G$.

Обоснование п. 2) аналогично доказательству предложения 4.5.

Действительно, по (8)

$$ \begin{equation*} \mathrm{UT}(n,R) = P_1 \cdots P_{n-1}, \end{equation*} \notag $$
где
$$ \begin{equation*} P_m = \mathrm{T}_{n-m,n} \mathrm{T}_{n-m-1,n-1} \cdots \mathrm{T}_{1,1+m}. \end{equation*} \notag $$

По теореме 5.1 и лемме 4.4 все произведения $P_2, \dots,P_{n-1}$ диофантовы в $G$. Рассмотрим произведение

$$ \begin{equation*} P_1' = (R_G\mathrm{T}_{n-1,n}\mathrm{T}_{1n}) (R_G\mathrm{T}_{n-2,n-1}\mathrm{T}_{1n}) \cdots (R_G\mathrm{T}_{1,2}\mathrm{T}_{1n}) = R_GP_1\mathrm{T}_{1n}. \end{equation*} \notag $$
По теореме 5.1 и лемме 4.4 $P_1'$ диофантово в $G$. Следовательно,
$$ \begin{equation*} R_GU\mathrm{T}_n(R) = P_1'P_2 \cdots P_{n-1} \end{equation*} \notag $$
также диофантово в $G$. Предложение доказано.

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

Теорема 6.1. Пусть $G$ – большая подгруппа в $\mathrm{GL}_n(R)$, $\mathrm{PGL}_n(R)$ (мы предполагаем, что в этом случае кольцо $R$ не имеет делителей нуля) или $\mathrm{T}_n(R)$, где $n \geqslant 3$. Тогда кольцо $R$ является e-интерпретируемым в $G$.

Доказательство. Рассмотрим все три случая один за другим.

Случай 1. $G$ – это большая подгруппа в $\mathrm{GL}_n(R)$. Из теоремы 4.1 следует, что подгруппы $\mathrm{T}_{12}$, $\mathrm{T}_{2n}$ и $\mathrm{T}_{1n}$ диофантовы в $G$.

Мы e-интерпретируем $R$ на $\mathrm{T}_{1n}$, определяя структуру кольца $\langle \mathrm{T}_{1n}; \oplus, \otimes \rangle$ на этом множестве следующим способом. Для $x, y \in \mathrm{T}_{1n}$ положим

$$ \begin{equation} x \oplus y = x\cdot y. \end{equation} \tag{10} $$

Заметим, что если $x = t_{1n}(\alpha), y = t_{1n}(\beta)$, то $x\cdot y = t_{1n}(\alpha + \beta)$, что согласуется со сложением в $R$.

Чтобы определить операцию $x\otimes y$ для матриц $x, y \in \mathrm{T}_{1n}$, введем некоторые обозначения. Пусть $x_1, y_1 \in G$ – такие матрицы, что

$$ \begin{equation} x_1 \in \mathrm{T}_{12}\quad \text{и}\quad [x_1,t_{2n}] = x, \qquad y_1 \in \mathrm{T}_{2n}\quad \text{и}\quad [t_{12},y_1] = y. \end{equation} \tag{11} $$
Заметим, что такие $x_1, y_1$ всегда существуют и единственны, так как если $x = t_{1n}(\alpha), y = t_{1n}(\beta)$, то $x_1 = t_{12}(\alpha), y_1 = t_{2n}(\beta)$. Теперь определим
$$ \begin{equation*} x\otimes y = [x_1,y_1]. \end{equation*} \notag $$
Легко увидеть, что тогда
$$ \begin{equation} [x_1,y_1] = [t_{12}(\alpha),t_{2n}(\beta)] = t_{1n}(\alpha\beta), \end{equation} \tag{12} $$
т. е. $\otimes$ согласуется с умножением в $R$. Для завершения доказательства нам необходимы два утверждения.

Утверждение 6.2. Отображение $\alpha \to t_{1n}(\alpha)$ определяет изоморфизм колец $R \to \langle \mathrm{T}_{1n}; \oplus, \otimes \rangle$.

Это немедленно следует из конструкции.

Утверждение 6.3. Кольцо $\langle \mathrm{T}_{1n}; \oplus, \otimes \rangle$ e-интерпретируемо в $G$.

Для доказательства этого утверждения, заметим сначала, что, как было упомянуто выше, $\mathrm{T}_{1n}$ диофантова в $G$. Сложение $\oplus$, определенное в (10), очевидно, диофантово в $G$. Поскольку подгруппы $\mathrm{T}_{12}$ и $\mathrm{T}_{2n}$ диофантовы в $G$, условия (11) тоже диофантовы в $G$, как и условие (12). Это показывает, что умножение $\otimes$ тоже диофантово в $G$. Это завершает доказательство случая 1).

Случай 2. $G$ – это большая подгруппа в $\mathrm{PGL}_n(R)$. Доказательство аналогично случаю 1), но вместо теоремы 4.1 мы используем предложение 4.8.

Случай 3. $G$ – это большая подгруппа в $\mathrm{T}_n(R)$. Мы используем идеи случая 1) с некоторыми изменениями. Вместо подгруппы $\mathrm{T}_{12}$ мы используем подгруппу $\mathrm{T}_{12}' = R_G\mathrm{T}_{12}\mathrm{T}_{1n}$, если $n>3$, которая диофантова в $G$. Если $n=3$, мы также используем $\mathrm{T}_{23}'=R_G\mathrm{T}_{23}\mathrm{T}_{13}$ вместо $\mathrm{T}_{2n}=\mathrm{T}_{23}$. В обоих ситуациях мы можем придерживаться аргумента из случая 1). Единственное различие состоит в том, что $x_1 \in \mathrm{T}_{12}'$ и $y_1\in \mathrm{T}_{23}'$ не единственны, если $n=3$. Это не влияет на доказательство, так как для любых таких $x_1$ и $y_1$ коммутатор $[x_1,y_1]$ не изменяется.

Это завершает доказательство теоремы.

Следствие 6.4. Кольцо $R$ e-интерпретируемо в $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$ (если $R$ коммутативно), $\mathrm{E}_n(R)$, $\mathrm{T}_n(R)$ и $\mathrm{UT}_n(R)$, где $n \geqslant 3$. Если, кроме того, в $R$ нет делителей нуля, то $R$ также e-интерпретируемо в $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$ (как и раньше, $R$ предполагается коммутативным в этом случае).

Замечание 6.5. Если $n\geqslant 3$, то кольцо $R$ e-интерпретируемо в группах $\mathrm{GL}_n(R)$, $\mathrm{PGL}_n(R)$, $\mathrm{E}_n(R)$ на всех однопараметричных подгруппах $\mathrm{T}_{ij}$. Это также выполняется в $\mathrm{T}_n(R)$ и $\mathrm{UT}_n(R)$, если $j-i\geqslant 2$. Более того, если $R$ коммутативно, то это верно в $\mathrm{SL}_n(R)$ и $\mathrm{PSL}_n(R)$.

Далее мы доказываем результат, обратный теореме 6.1 (за исключением случая $\mathrm{E}_n(R)$). Этот результат, несомненно, известен специалистам, но поскольку мы не смогли найти подходящую ссылку, то мы приводим доказательство.

Предложение 6.6. Группы $\mathrm{GL}_n(R)$, $\mathrm{T}_n(R)$ и $\mathrm{UT}_n(R)$ e-интерпретируемы в $R$. Если $R$ коммутативно, то группы $\mathrm{PGL}_n(R)$, $\mathrm{SL}_n(R)$ и $\mathrm{PSL}_n(R)$ также e-интерпретируемы в $R$.

Доказательство. Пусть $x = (x_{ij})$ есть $(n\times n)$-матрица над кольцом $R$. Отождествим $x = (x_{ij})$ с $n^2$-набором $\overline x$ из $R^{n^2}$, где
$$ \begin{equation*} \overline x = (x_{11}, \dots,x_{1n}, x_{21}, \dots, x_{n1}, \dots, x_{nn}). \end{equation*} \notag $$
Матричное умножение $\odot$ на наборах $\overline x$ и $\overline y$ из $R^{n^2}$ определяем следующим образом:
$$ \begin{equation*} \overline x \odot \overline y = \overline z\quad \Longleftrightarrow\quad \bigwedge_{i,j = 1}^n z_{ij} = P_{ij}(\overline x,\overline y), \end{equation*} \notag $$
где $P_{ij}(\overline x, \overline y)$ – целый многочлен $\Sigma_{s= 1}^n x_{is}y_{sj}$. Следовательно, операция $\odot$ диофантова.

Теперь для доказательства e-интерпретируемости $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$, $\mathrm{T}_n(R)$ и $\mathrm{UT}_n(R)$ в $R$ достаточно определить соответствующие подмножества в $R^{n^2}$ с помощью диофантовых формул. Мы делаем это отдельно для каждого случая.

Случай $\mathrm{GL}_n(R)$. Матрица $x = (x_{ij})$ лежит в $\mathrm{GL}_n(R)$ тогда и только тогда, когда она обратима, т. е. существует матрица $y = (y_{ij})$ такая, что $xy = I_n$. На языке наборов $\overline x$ и $\overline y$ мы можем записать это условие как

$$ \begin{equation*} \exists \, \overline y (\overline x \odot \overline y) = \overline I_n. \end{equation*} \notag $$
Это условие диофантово, а значит $\mathrm{GL}_n(R)$ e-интерпретируема в $R$.

Случай $\mathrm{SL}_n(R)$. В этом случае, $R$ является коммутативным. Напомним, что детерминант $(n\times n)$-матрицы $(x_{ij})$ с элементами в коммутативном кольце $R$ может быть записан как фиксированный многочлен $\operatorname{Det}_n(\overline x)$ с переменными $\overline x$. Значит, матрица $x= (x_{ij})$ лежит в $\mathrm{SL}_n(R)$ тогда и только тогда, когда $\operatorname{Det}_n(\overline x)\,{=}\,1$. Это – диофантово определение $\mathrm{SL}_n(R)$ в $R$.

Случай $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$. Заметим, что если $R$ коммутативно, то подгруппы всех скалярных матриц в $\mathrm{GL}_n(R)$ и $\mathrm{SL}_n(R)$ диофантовы, так как они являются централизаторами всех трансвекций $t_{ij}$. Тогда факторгруппы $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$ e-интерпретируемы в группах $\mathrm{GL}_n(R)$ и $\mathrm{SL}_n(R)$ соответственно. Тогда е-интерпретируемость $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$ в $R$ следует из транзитивности e-интерпретаций.

Случай $\mathrm{T}_n(R)$. По определению $x= (x_{ij}) \in \mathrm{T}_n(R)$ тогда и только тогда, когда $x_{ij} =0$ для всех $i<j$ и существует $y$ в $R$ такой, что $x_{11} \cdots x_{nn} y = 1$. Оба эти условия диофантовы, а значит $\mathrm{T}_n(R)$ e-интерпретируема в $R$.

Случай $\mathrm{UT}_n(R)$ аналогичен предыдущему случаю.

Это завершает доказательство предложения.

Мы теперь можем доказать основной результат статьи, но для этого необходимы некоторые обозначения.

Как отмечалось ранее, для матричной группы $G_n(R)$ мы рассматриваем диофантовы проблемы типа $\mathcal{D}_C(G_n(R))$, где $C$ – счетное или конечное подмножество $G_n(R)$, снабженное нумерацией $\nu\colon \mathbb{N} \to C$. Пусть $C_R \subseteq R$ означает множество всех элементов $R$, которые встречаются в матрицах из $C$. Отметим, что в случае $\mathrm{PGL}_n(R)$ или $\mathrm{PSL}_n(R)$ мы полагаем, что элементы из $C$ (которые представляют собой смежные классы по центру $\mathrm{GL}_n(R)$ или $\mathrm{SL}_n(R)$) заданы некими фиксированными представителями, т. е. матрицами над $R$. Нумерация $\nu$ индуцирует нумерацию $\nu^*\colon \mathbb{N} \to C_R$ следующим образом. Пронумеруем матрицы из $C$ с помощью $\nu$, затем для каждой матрицы $\nu(n)$ пронумеруем ее элементы в неком фиксированном порядке и совместим все это в нумерацию $\nu^*$. В дальнейшем, если дана нумерация $\nu\colon \mathbb{N} \to C$, то мы всегда предполагаем, что нумерация множества $C_R$ – это нумерация $\nu^*$, построенная выше.

Подобным образом, если $B \subseteq R$ – счетное или конечное подмножество $R$, снабженное нумерацией $\mu\colon \mathbb{N} \to B$, то через $B_G$ мы обозначаем подмножество $\{t_{1n}(\mu(i) \mid i \in \mathbb{N}\} $ однопараметрической подгруппы $\mathrm{T}_{1n}$ группы $G_n(R)$. Таким образом, $B_G$ – это в точности подмножество констант из интерпретации $R$ на $\mathrm{T}_{1n}$, соответствующее множеству констант $B$ в $R$. Продолжим нумерацию $\mu$ до нумерации $\mu^*\colon \mathbb{N} \to B_G$, полагая $\mu^*(i) = t_{1n}(\mu(i))$. В дальнейшем, если дана нумерация $\mu\colon \mathbb{N} \to B$, то мы всегда предполагаем, что нумерация множества $B_G$ – это нумерация $\mu^*$, построенная выше. Теперь мы готовы для формулировки основного результата.

Теорема 6.7. Пусть $n \geqslant 3$. Тогда диофантова проблема в каждой из групп $\mathrm{GL}_n(R)$, $\mathrm{SL}_n(R)$ (в этом сучае $R$ коммутативно), $\mathrm{T}_n(R)$ и $\mathrm{UT}_n(R)$, а также в $\mathrm{PGL}_n(R)$ и $\mathrm{PSL}_n(R)$ (в этом случае мы также предполагаем, что в $R$ нет делителей нуля) эквивалентна по Карпу диофантовой проблеме в $R$. Более точно, справедливы следующие утверждения:

1) если $C$ – счетное или конечное подмножество $G_n(R)$ (с нумерацией $\nu$), то $\mathcal{D}_C(G_n(R))$ сводится к $\mathcal{D}_{C_R}(R)$ (относительно нумерации $\nu^*$);

2) если $B$ – счетное или конечное подмножество $R$ (с нумерацией $\mu$), то $\mathcal{D}_B(R)$ сводится к $\mathcal{D}_{B_G}(G_n(R))$ (относительно нумерации $\mu^*$).

Доказательство. Теорема вытекает из следствия 6.4, предложения 6.6 и свойств e-интерпретаций, отмеченных в следствии 3.8.

Нам не удалось доказать, что $\mathrm{E}_n(R)$ e-интерпретируема в $R$ для всех ассоциативных колец $R$. Однако следующее утверждение выполняется.

Теорема 6.8. Если $\mathrm{E}_n(R)$ ограничено элементарно порождена, то $\mathrm{E}_n(R)$ e-интерпретируема в $R$. В этом случае диофантова проблема в $\mathrm{E}_n(R)$ эквивалентна по Карпу диофантовой проблеме в $R$ при условии, что $n\geqslant 3$.

Для произвольных ассоциативных колец $R$ следующий результат вытекает из следствия 6.4.

Предложение 6.9. Если диофантова проблема неразрешима над кольцом $R$, то она также неразрешима над группой $\mathrm{E}_n(R)$ для всех $n \geqslant 3$.

§ 7. Диофантова проблема в группах матриц над классическими кольцами и полями

В этом параграфе мы рассматриваем диофантову проблему в группах матриц над классическими кольцами и полями.

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

7.1. $R$ является кольцом целых алгебраических чисел или числовым полем

Под числовым полем $F$ мы понимаем конечное алгебраическое расширение $\mathbb{Q}$. Кольцо целых $\mathcal{O}$ числового поля $F$ – это подкольцо $F$, состоящее из всех корней приведенных многочленов с целыми коэффициентами.

В соответствии с классическим результатом Ю. В. Матиясевича [2], диофантова проблема в $\mathbb{Z}$ неразрешима. Вместе с теоремой 6.7 это дает следующее утверждение.

Теорема 7.1. Пусть $n \geqslant 3$. Тогда диофантова проблема в группах матриц $G_n(\mathbb{Z})$ эквивалентна по Карпу диофантовой проблеме в $\mathbb{Z}$. В частности, диофантова проблема в группах матриц $G_n(\mathbb{Z})$ неразрешима.

Напомним одну из наиболее значительных гипотез в теории чисел.

Гипотеза 7.2. Диофантова проблема в $\mathbb{Q}$, а также в любом числовом поле $F$, а также в любом кольце целых $\mathcal{O}$ является неразрешимой.

Для $\mathbb{Q}$ и его любого конечного расширения $F$ вышеприведенная гипотеза открыта. Однако для колец целых $\mathcal{O}_F$ полей $F$, в некоторых случаях установлена неразрешимость диофантовой проблемы. А именно, известно, что $\mathbb{Z}$ диофантово в $\mathcal{O}_F$, если $[F : \mathbb{Q}] = 2$, или $F$ является вполне вещественным [63], [64], или $[F : \mathbb{Q}] > 3$ и $F$ имеет в точности два невещественных вложения в поле комплексных чисел [65], или $F$ является абелевым числовым полем [66]. За дальнейшими деталями мы отсылаем к обзорным публикациям [4], [3] и монографии [5].

Если гипотеза 7.2 верна, то верна и следующая гипотеза.

Гипотеза 7.3. Пусть $n \geqslant 3$ и $R \in \{\mathbb{Q}, F, \mathcal{O}\}$, где $F$ – числовое поле, и $\mathcal{O}$ – кольцо целых. Тогда диофантова проблема в группах матриц $G_n(R)$ неразрешима.

7.2. $R$ является алгебраически замкнутым полем

Следующий результат наверняка известен в фольклоре. Поскольку нам не удалось найти подходящую ссылку, мы приводим набросок доказательства.

Предложение 7.4. Пусть $R$ – алгебраически замкнутое поле. Тогда имеют место следующие утверждения.

1) Если $A$ – вычислимое подполе поля $R$, то теория первого порядка $\mathrm{Th}_A(R)$ поля $R$ с константами из $A$, добавленными в сигнатуру, разрешима. В частности, $\mathcal{D}_A(R)$ разрешима.

2) Пусть $C$ – счетное или конечное подмножество $G_n(R)$ такое, что кольцо $C_R$, порожденное в $R$ всеми элементами, входящими в матрицы из $C$, вычислимо. Тогда диофантова проблема в $G_n(R)$ с константами из $C$ разрешима.

Доказательство. Рассмотрим нумерацию $\nu\colon \mathbb{N} \to A$, которая дает вычислимость $A$. Пусть $\overline A$ обозначает алгебраическое замыкание $A$ в $R$, т. е. наименьшее алгебраически замкнутое подполе $R$, содержащее $A$. Нумерация $\nu$ продолжается до нумерации $\mu\colon \mathbb{N} \to \overline A$, что дает вычислимость $\overline A$, см. [62]. Так как теория первого порядка алгебраически замкнутых полей данной характеристики допускает элиминацию кванторов, вся теория $\mathrm{Th}_A(\overline A)$ сводится к утверждениям об $\overline A$, не содержащим кванторов. Последние разрешимы, поскольку $\overline A$ вычислимо. Более того, $\overline A$ является элементарной подмоделью $R$, так что $\mathrm{Th}_A(\overline A) = \mathrm{Th}_A(R)$. Отсюда получаем, что $\mathrm{Th}_A(R)$ разрешима, что и требовалось.

Утверждение 2) следует из следует из теоремы 6.7 и 1).

Предложение доказано.

Теперь мы обращаемся к случаю классических полей с разрешимой теорией первого порядка, таким как $\mathbb{C}$, $\mathbb{R}$ и $\mathbb{Q}_p$ для произвольного простого $p$. Мы уделяем особое внимание кольцу $p$-адических целых чисел $\mathbb{Z}_p$, благодаря его отношению к про-$p$ пополнениям групп.

7.3. $R$ является полем вещественных чисел

Пусть $R = \mathbb{R}$ – поле вещественных чисел, и $A$ – его счетное (или конечное) подмножество. В этом разделе мы рассматриваем, когда диофантова проблема в $\mathbb{R}$ с константами из $A$ (которую мы обозначаем $D_A(\mathbb{R})$) разрешима, а затем применяем эти результаты к случаю диофантовых проблем в классических группах матриц над $\mathbb{R}$.

Прежде всего заметим, что по лемме 3.3 если $D_A(\mathbb{R})$ разрешима, то подполе $F(A)$, порожденное $A$ в $\mathbb{R}$, вычислимо. Обратное однако неверно. Например, как мы отмечаем ниже, если $a \in \mathbb{R}$ не является вычислимым действительным числом, то $F = \mathbb{Q}(a)$ – вычислимое поле, но $\mathcal{D}_{\{a\}}(\mathbb{R})$ неразрешима. Следующее предложение проясняет ситуацию.

Предложение 7.5. Пусть $ A $ – конечное или счетное подмножество в $ \mathbb {R} $. Тогда диофантова проблема в $ \mathbb{R} $ с константами из $ A $ разрешима тогда и только тогда, когда упорядоченное подполе $ F(A) $, порожденное $ A $ в $ \mathbb{R} $, вычислимо. Более того, в этом случае разрешима вся теория первого порядка $ \mathrm{Th}_A (\mathbb {R}) $ поля $ \mathbb{R} $ с константами из $A$ в сигнатуре.

Доказательство. Предположим, что $A$ – конечное или счетноe подмножество $\mathbb{R}$ с разрешимой $\mathcal{D}_A(\mathbb{R})$. По лемме 3.3 подполе $F(A)$, порожденное $A$ в $\mathbb{R}$, вычислимо. Тем самым, достаточно показать вычислимость порядка $\leqslant $, индуцированного на $F(A)$ c $\mathbb{R}$. Заметим, что $a\leqslant b$ в $\mathbb{R}$, если и только если уравнение $b-a = y^2$ имеет решение по $y$. Отсюда, если $\mathcal{D}_A(\mathbb{R})$ разрешима, то $\leqslant$ вычислим на $F(A)$.

Теперь докажем обратное. Предположим, что $F(A)$ – вычислимое упорядоченное поле. Уравнение $E(x_1,\dots,x_n, a_1, \dots,a_m) = 0$ в переменных $x_1,\dots,x_n$ с коэффициентами $a_1, \dots,a_m \in A$ имеет решение в $\mathbb{R}$, если и только если формула $\Phi(a_1, \dots,a_m) = \exists \, x_1 \dots \exists \, x_n (E(x_1,\dots,x_n, a_1, \dots,a_m) = 0)$ верна в $\mathbb{R}$. Поскольку $\mathbb{R}$ в сигнатуре упорядоченного кольца допускает элиминацию кванторов, формула $\Phi(y_1, \dots,y_m)$ со свободными переменными $y_1, \dots,y_m$ эквивалентна в $\mathbb{R}$ формуле $\Psi(y_1, \dots,y_m)$, не содержащей кванторов. Таким образом, $\Phi(a_1, \dots,a_m)$ выполняется в $\mathbb{R}$, если и только если в $\mathbb{R}$ выполняется $\Psi(a_1, \dots,a_m)$. Последнее алгоритмически разрешимо, поскольку упорядоченное подполе $F(A)$ вычислимо.

Наконец, докажем последнее утверждение. Пусть $\Phi(a_1, \dots,a_n)$ – предложение с коэффициентами из $F(A)$. Учитывая элиминацию кванторов в вещественно замкнутых полях, мы можем считать, что $\Phi(a_1, \dots,a_n)$ не содержит кванторов. Но в таком случае, поскольку поле $F(A)$ вычислимо, мы можем алгоритмически установить, выполняется ли это предложение в $\mathbb{R}$. Тем самым, $\mathrm{Th}_A(\mathbb{R})$ разрешима. Предложение доказано.

Вспомним, что вещественное число $a \in \mathbb{R}$ вычислимо, если его десятичное разложение $a = a_0.a_1a_2 \dots$ вычислимо, т. е. целочисленная функция $n \to a_n$ вычислима. Другими словами, число $a$ вычислимо, если и только если оно эффективно аппроксимируется рациональными числами с любой точностью. Множество всех вычислимых вещественных чисел $\mathbb{R}^c$ образует вещественно замкнутое подполе поля $\mathbb{R}$, в частности, $\mathbb{R}^c$ элементарно эквивалентно $\mathbb{R}$.

Следующее предложение собирает несколько фактов о вычислимых упорядоченных подполях $\mathbb{R}$. Пункты 1) и 2) доказаны в [53], 3) доказан в [54] (см. также [55; гл. 6, разд. 3, теорема 4]) и 4) известен в фольклоре.

Предложение 7.6. Имеют место следующие утверждения.

1) Каждое вычислимое упорядоченное подполе $\mathbb{R}$ содержится в $\mathbb{R}^c$.

2) Упорядоченное подполе $\mathbb{R}^c \leqslant \mathbb{R}$ с порядком, индуцированным с $\mathbb{R}$, невычислимо.

3) Если $F$ – вычислимое упорядоченное поле, то его вещественное замыкание также вычислимо. В частности, если $F$ – вычислимое подполе $\mathbb{R}$, то алгебраическое замыкание $\overline F$ подполя $F$ в $\mathbb{R}$ является вычислимым упорядоченным полем.

4) Если $a_1, \dots,a_m$ – вычислимые вещественные числа, то упорядоченное подполе $\mathbb{Q}(a_1, \dots,a_m) \leqslant \mathbb{R}$ с порядком, индуцированным с $\mathbb{R}$, вычислимо.

Доказательство. 1) и 2) доказаны в [53]. Теорема 4 в [55; гл. 3, разд. 6] утверждает, что если $F_0$ является алгебраическим расширением вычислимого поля $F$, то конструктивизация поля $F$ продолжается до конструктивизации поля $F_0$, если и только если вычислимо перечислимо множество многочленов $f \in F[x]$, имеющих корень в $F_0$. В нашем случае всякий многочлен $f \in F[x]$, имеющий корень в $\mathbb{R}$, также имеет корень в $F$. Достаточно показать вычислимую перечислимость множества многочленов $f \in F[x]$, имеющих корень в $\mathbb{R}$. Для каждого $n \in \mathbb{N}$ рассмотрим многочлен $h(x,z_0, \dots, z_n) = z_nx^n + z_{n-1}x^{n-1} + \dots + z_0$ и формулу $\Phi_n(z_0, \dots,z_n) = \exists \, x h(x,\overline z) = 0$. По построению для любых $a_0, \dots, a_n \in \mathbb{R}$ формула $\Phi_n(a_0, \dots,a_n)$ выполняется в $\mathbb{R}$, если и только если многочлен $a_nx^n + \dots + a_0$ имеет корень в $\mathbb{R}$. Поскольку $\mathbb{R}$ допускает элиминацию кванторов (с $\leqslant$ в сигнатуре), для каждого $n$ можно найти не содержащую кванторов формулу $\Phi_n'(z_0, \dots,z_n)$ такую, что $\Phi_n'(a_0, \dots,a_n)$ выполняется в $\mathbb{R}$, если и только если многочлен $a_nx^n + \dots + a_0$ имеет корень в $\mathbb{R}$. Теперь, если $a_0, \dots, a_n$ принадлежат $F$, поскольку $F$ вычислимо, мы можем алгоритмически проверить выполняется ли в $\mathbb{R}$ формула $\Phi_n'(a_0, \dots,a_n)$. Таким образом, чтобы организовать вычислимое перечисление всех имеющих корень в $\mathbb{R}$ многочленов $f \in F[x]$, мы можем перечислять все многочлены $f_1, f_2, \dots, $ в $F[x]$ и по очереди проверять, имеет ли $f_i$ корень в $\mathbb{R}$. Тем самым, п. 3) доказан.

Чтобы доказать 4), рассмотрим конечное расширение $\mathbb{Q}(t_1, \dots, t_m, \alpha_1, \dots,\alpha_k)$ поля $\mathbb{Q}$. Мы можем считать, что $L = \mathbb{Q}(t_1, \dots, t_m)$ – чисто трансцендентное расширение, а $F = L(\alpha_1, \dots,\alpha_k)$ – алгебраическое. Легко видеть, что поле $L$ вычислимо (см., например, [55], [62]). Покажем сначала, что ограничение порядка $\leqslant $ с $\mathbb{R}$ на $L$ вычислимо в $L$. Рассмотрим $L$ как поле рациональных функций от $t_1, \dots, t_n$ с коэффициентами в $\mathbb{Q}$ и заметим, что достаточно показать, что для любого многочлена $f(\overline x) = f(x_1, \dots,x_m)$ с рациональными коэффициентами можно алгоритмически проверить, какое неравенство имеет место: $f(\overline t) >0$ или $f(\overline t) <0$ (здесь $f(\overline t) = f(t_1, \dots,t_m)$). Отметим, что $f(\overline t) \neq 0$. Элементы $t_1, \dots,t_m$ вычислимы, так что для каждого $s = 1, \dots,m$ существуют вычислимые последовательности рациональных чисел $\{a_i^{(s)}\}_{i \in \mathbb{N}}$ и $\{b_i^{(s)}\}_{i \in \mathbb{N}}$ такие, что $\{a_i^{(s)}\}_{i \in \mathbb{N}}$ возрастает и сходится к $t_s$, а $\{b_i^{(s)}\}_{i \in \mathbb{N}}$ убывает и сходится к $t_s$. Так как $f(\overline t) \neq 0$, в некоторой малой окрестности точки $\overline t \in \mathbb{R}^m$ многочлен $f(x_1, \dots,x_m)$ либо строго положителен, либо строго отрицателен. Для $i \in \mathbb{N}$ рассмотрим формулу

$$ \begin{equation*} \Phi_i = \exists \, y_1 \dots \exists \, y_m \biggl(\bigwedge_{j=1}^m (a_i^{(j)} \leqslant y_j \leqslant b_i^{(j)}) \wedge (f(y_1, \dots,y_m) = 0)\biggr). \end{equation*} \notag $$
Так как теория $\mathrm{Th}(\mathbb{R})$ разрешима, мы можем алгоритмически решить для каждого $i \in \mathbb{N}$, выполняется ли $\Phi_i$ в $\mathbb{R}$. Поскольку $f(\overline x)$ не имеет нулей в некоторой малой окрестности точки $\overline t$, формула $\Phi_i$ не выполняется в $\mathbb{R}$ для некоего $i$, которое мы можем найти. Из этого следует, что многочлен $f(\overline x)$ либо положителен, либо отрицателен на окрестности
$$ \begin{equation*} U_i = \prod_{j=1}^m[a_i^{(j)},b_i^{(j)}]. \end{equation*} \notag $$
Отсюда, вычислив значение $f(a_i^{(1)}, \dots, a_i^{(m)})$, мы можем установить, выполнено ли неравенство $f(\overline t) >0$ или $f(\overline t) <0$, что и требовалось.

Теперь рассмотрим алгебраическое расширение $F =L(\alpha_1, \dots,\alpha_k)$. Мы ограничимся случаем $k = 1$. Рассуждения в общем случае аналогичны. Пусть $f = a_nx^n + \dots +a_0$ – минимальный многочлен элемента $\alpha = \alpha_1$ над $L$, где $a_i = {P_i(\overline t)}/{Q_i(\overline t)}$ являются рациональными функциями от $t_1, \dots,t_m$ с рациональными коэффициентами. Легко видеть, что поле $F$ вычислимо, так что надо лишь проверить, что порядок $\leqslant$ вычислим в $F$. Рассмотрим произвольный элемент $b \in F$. Мы можем считать, что $b\neq 0$ и что его можно (алгоритмически) представить в виде нетривиальной линейной комбинации

$$ \begin{equation*} b = \frac{P_0(\overline t)}{Q_0(\overline t)}\cdot 1 + \dots + \frac{P_{n-1}(\overline t)}{Q_{n-1}(\overline t)}\alpha^{n-1} \end{equation*} \notag $$
базисных элементов $1, \dots,\alpha^{n-1}$ поля $F$ над $L$. Чтобы установить, имеет место неравенство $b>0$ или $b<0$, рассмотрим рациональную функцию
$$ \begin{equation*} h(\overline x,y) = \frac{P_0(\overline x)}{Q_0(\overline x)}\cdot 1 + \dots + \frac{P_{n-1}(\overline x)}{Q_{n-1}(\overline x)}y^{n-1}. \end{equation*} \notag $$
Заметим, что $h(\overline t,\alpha) \neq 0$. Тем самым, в малой окрестности точки $(\overline t,\alpha)$ функция $h(\overline x,y) $ либо строго положительна, либо строго отрицательна. Вещественные числа $t_1, \dots,t_m, \alpha$ вычислимы, так что, повторяя предыдущие рассуждения, мы можем показать, что можно установить, имеет ли место неравенство $b>0$ или $b <0$. Таким образом, п. 4) доказан. Предложение доказано.

Следующий результат подытоживает вышеизложенное.

Следствие 7.7. Справедливы утверждения:

– диофантова проблема в $\mathbb{R}$ с коэффициентами в $\mathbb{R}^c$ неразрешима;

– диофантова проблема в $\mathbb{R}$ с коэффициентами в любом конечном подмножестве $\mathbb{R}^c$ разрешима;

– диофантова проблема в $\mathbb{R}$ с коэффициентами в $\{a\}$, где $a$ невычислимо, неразрешима.

Обратимся теперь к диофантовой проблеме в классических группах матриц над $\mathbb{R}$.

Назовем матрицу $A \in \mathrm{GL}_n(\mathbb{R})$ вычислимой, если все элементы $A$ – вычислимые вещественные числа. Таким образом, в $\mathrm{SL}_n(\mathbb{R})$ вычислимыми являются в точности матрицы из $\mathrm{SL}_n(\mathbb{R}^c)$.

Теорема 7.8. Пусть $ n \geqslant 3 $ и

$$ \begin{equation*} G_n (\mathbb {R}) \in \{\mathrm{GL}_n (\mathbb {R}), \mathrm{SL}_n (\mathbb {R}), \mathrm{T}_n (\mathbb {R}), \mathrm{UT}_n (\mathbb {R}), \mathrm{PGL}_n ( \mathbb {R}), \mathrm{PSL}_n (\mathbb {R}) \}. \end{equation*} \notag $$
Если $F$ является вычислимым упорядоченным подполем в $ \mathbb {R} $, то теория первого порядка $ \mathrm{Th}_{G_n(F)}(G_n (\mathbb {R})) $ группы матриц $ G_n (\mathbb {R}) $ с константами из $ G_n(F) $ разрешима (здесь $ G_n (F) $ – множество всех матриц из $ G_n (\mathbb {R}) $ с элементами из $F$). В частности, диофантова проблема для уравнений с коэффициентами из $ G_n(F) $ разрешима в $ G_n(\mathbb {R}) $.

Доказательство. По предложению 7.5 теория $\mathrm{Th}_{ F}(\mathbb{R})$ разрешима. Поскольку группа $G_n(\mathbb{R})$ интерпретируема в поле $\mathbb{R}$ без использования параметров (теорема 6.6), теория первого порядка группы $G_n(\mathbb{R})$ с константами из $G_n(F)$ разрешима, что и требовалось. Теорема доказана.

Следующий результат дополняет приведенную выше теорему.

Теорема 7.9. Пусть $G$ – большая подгруппа в $ \mathrm{GL}_n (\mathbb {R}) $, где $ n \geqslant 3 $. Если матрица $ A \in \mathrm{SL}_n (\mathbb {R}) $ невычислима, то диофантова проблема в $G$ с коэффициентами из $ \{t_{ij}(1) \mid i, j = 1, \dots, n \} \cup \{A \} $ неразрешима.

Доказательство. Рассмотрим предполагаемые теоремой $G$ и $A \in \mathrm{SL}_n(\mathbb{R})$ и предположим, что существует алгоритм, устанавливающий, имеет ли решение в $G$ данная система уравнений с коэффициентами в $\{t_{ij}\} \cup \{A\}$. Покажем, что в этом случае матрица $A$ вычислима. Группа $\mathrm{SL}_n(\mathbb{R})$ порождена трансвекциями. Рассмотрим произвольное разложение матрицы $A$ в произведение трансвекций:
$$ \begin{equation} A = t_{i_1j_1}(\alpha_1) \cdots t_{i_mj_m}(\alpha_m). \end{equation} \tag{13} $$
Рассмотрим множество $S$ всех разложений $A = t_{i_1j_1}(\beta_1) \cdots t_{i_mj_m}(\beta_m)$ с фиксированной последовательностью пар индексов $(i_1,j_1)$, $\dots$, $(i_m,j_m)$ и фиксированными знаками вещественных чисел $\beta_k$, т. е. $\operatorname{sign}(\beta_k) = \operatorname{sign}(\alpha_k)$, $k = 1, \dots,m$. Чтобы упростить обозначения, положим $x_k(\beta) = t_{i_kj_k}(\beta)$. Теперь покажем, что существует некоторое разложение
$$ \begin{equation*} A = x_1(\beta_1) \cdots x_m(\beta_m), \end{equation*} \notag $$
где все числа $\beta_1, \dots,\beta_m$ вычислимы. Для каждого $n \in \mathbb{N}$ определим рациональные числа $r_{1,n}, \dots , r_{m,n}$ индукцией по $n$. Пусть $r_{k,0}$ означает целую часть вещественного числа $|\alpha_k|$, где $\alpha_k$, $k = 1, \dots,m$, – как в уравнении (13). Предположим, что $r_{k,n-1}$, $k = 1, \dots,m$, уже определены. Пусть $(y_{1,n},\dots,y_{m,n})$ – наименьший в левом лексикографическом порядке кортеж целых чисел такой, что:

1) $0\leqslant y_{k,n}\leqslant 9$, $k = 1, \dots,m$;

2) существуют $\gamma_{1,n}, \dots, \gamma_{m,n}\in\mathbb{R}$ такие, что $A = x_1(\gamma_{1,n}) \cdots x_m(\gamma_{m,n})$;

3) $\operatorname{sign}(\gamma_{k,n}) = \operatorname{sign}(\alpha_k)$, $k = 1, \dots,m$;

4) $ 0 \leqslant |\gamma_{k,n}| - (r_{k,n-1} + y_{k,n}/10^n) < 1/10^n$, $k= 1, \dots,m$.

Заметим, что такой кортеж $(y_{1,n}, \dots,y_{m,n})$ существует. Положим $r_{k,n} = r_{k,n-1} + y_{k,n}/10^n$. Имеем, что для каждого $k$ последовательность $\{r_{k,n}\}_{n \in \mathbb{N}}$ является последовательностью Коши, а значит, сходится к некоторому вещественному числу $\beta_k$. Поскольку $0 \leqslant |\gamma_{k,n}| - r_{k,n} < 1/10^n$, последовательность $\{|\gamma_{k,n}|\}_{n \in \mathbb{N}}$ также сходится к $\beta_k$, $k = 1, \dots,m$. Таким образом, $\{\gamma_{k,n}\}_{n \in \mathbb{N}}$ сходится к $\varepsilon_k \beta_k$, где $\varepsilon_k = \operatorname{sign}(\alpha_k)$, $k = 1, \dots,m$.

Так как $A = x_1(\gamma_{1,n}) \cdots x_m(\gamma_{m,n})$, существуют многочлены $P_{ij}$ с целыми коэффициентами такие, что для любого $n \in \mathbb{N}$ элемент $a_{ij}$ матрицы $A$ равен $P_{ij}(\gamma_{1,n}, \dots, \gamma_{m,n})$. Это следует из того, что для каждых $i$, $j$

$$ \begin{equation*} a_{ij} = \lim_{n \to \infty} P_{ij}(\gamma_{1,n}, \dots, \gamma_{m,n}) = P_{ij}(\varepsilon_1\beta_1, \dots, \varepsilon_m\beta_m). \end{equation*} \notag $$
Отсюда имеем, что каждый элемент $a_{ij}$ вычислим при условии, что вещественные числа $\beta_1, \dots,\beta_m$ вычислимы. Чтобы доказать, что вещественное число $\beta_k$ вычислимо, достаточно показать, что числовая последовательность $\{y_{k,n}\}_{n \in \mathbb{N}}$ вычислима. Сначала докажем, что каждое из условий 1)–4) может быть задано в группе $G$ при помощи диофантовых формул. Действительно, условие 2) диофантово потому, что однопараметрические подгруппы $\mathrm{T}_{ij}$ определимы диофантовыми формулами с константами из $\{t_{ij}\}$ для каждых $i,j$. Заметим, что поле $\mathbb{R}$ е-интерпретируемо в $G$ по теореме 6.1 и замечанию 6.5 на каждой однопараметрической подгруппе $\mathrm{T}_{ij}$. Предикат $x\leqslant y$ в $\mathbb{R}$ диофантов, так как он равносилен условию $\exists \, z (y-x = z^2)$. Тем самым, условия 1), 3), 4) могут быть заданы диофантовыми формулами. По предположению существует алгоритм, устанавливающий, имеет ли решение в $G$ данная конечная система уравнений с коэффициентами в $\{t_{ij}\} \cup \{A\}$. Это показывает, что для $n = 1, 2, \dots $ можно вычислить $y_{1,n}, \dots, y_{m,n}$. Тогда действительные числа $\beta_1, \dots,\beta_m$, а также сама матрица $A$ вычислимы. Это завершает доказательство теоремы.

Теорема 7.10. Имеют место следующие утверждения.

1) Диофантова проблема в вычислимом вещественно замкнутом поле $\mathbb{R}^c$ с коэффициентами в $\mathbb{R}^c$ неразрешима, так что для каждого конечно порожденного подполя $F$ поля $\mathbb{R}^c$ диофантова проблема в $\mathbb{R}^c$ с коэффициентами в $F$ разрешима.

2) Диофантова проблема в вычислимой группе матриц $G_n(\mathbb{R}^c)$ неразрешима, если $n\geqslant 3$. Однако для каждой конечно порожденной подгруппы $C\leqslant G_n(\mathbb{R}^c)$ диофантова проблема в $G_n(\mathbb{R}^c)$ с коэффициентами в $C$ разрешима.

Доказательство. По предложению 7.6 упорядоченное поле $\mathbb{R}^c$ невычислимо. Тогда по предложению 7.5 диофантова проблема в $\mathbb{R}^c$ с коэффициентами в $\mathbb{R}^c$ неразрешима. Если $F$ – конечно порожденное подполе $\mathbb{R}^c$, то по предложению 7.6 оно является вычислимым упорядоченным полем. Отсюда имеем, что по предложению 7.5 диофантова проблема в $\mathbb{R}^c$ с коэффициентами в $\mathbb{R}^c$ разрешима. Это доказывает утверждение 1).

Утверждение 2) следует из 1), теоремы 7.8 и основной теоремы 6.7.

Теорема доказана.

7.4. Кольца $p$-адических чисел $\mathbb{Z}_p$ и $\mathbb{Q}_p$

Аналогично можно определить вычислимые $p$-адические числа для каждого фиксированного простого числа $p$. Напомним, что каждое $p$-адическое число $a \in \mathbb{Q}_p$ единственным образом представляется в виде $a = p^m\xi$, где $m \in \mathbb{Z}$, а $\xi$ – обратимый элемент кольца $\mathbb{Z}_p$. В свою очередь, обратимый элемент $\xi$ определен единственной последовательностью натуральных чисел $\{\xi(i)\}_{i \in \mathbb{N}}$, где

$$ \begin{equation*} 0\leqslant \xi(i) < p^{i+1}, \quad \xi(i+1) = \xi(i)\ (\operatorname{mod} p^{i+1}), \qquad i \in \mathbb{N}. \end{equation*} \notag $$
$p$-Адическое число $a = p^m\xi$ вычислимо, если последовательность $i \to \xi(i)$ вычислима. В таком случае последовательность $\{\xi(i)\}_{i \in \mathbb{N}}$ задает эффективную $p$-адическую аппроксимацию $\xi$. Известно (см., например, [56]), что множество $\mathbb{Q}_p^c$ всех вычислимых $p$-адических чисел образует подполе поля $\mathbb{Q}_p$ такое, что $\mathbb{Q}_p \equiv \mathbb{Q}_p^c$. Отметим также, что кольцо $\mathbb{Z}_p$ диофантово в $\mathbb{Q}_p$. Более точно, если $p \neq 2$, то $\mathbb{Z}_p$ задается в $\mathbb{Q}_p$ формулой $\exists \, y (1+px^2 = y^2)$; если же $p= 2$, то $\mathbb{Z}_p$ задается формулой $\exists \, y(1+2x^3 = y^3)$ (см. [55]).

Теорема 7.11 (см. [56]). Имеют место следующие утверждения.

1) Теория $ \mathrm{Th} (\mathbb {Z}_p, a_1, \dots, a_n) $ кольца $\mathbb {Z}_p$ с константами $a_1, \dots, a_n$ в сигнатуре разрешима тогда и только тогда, когда каждое из $a_1, \dots, a_n $ является вычислимым $ p $-адическим числом.

2) Теория $ \mathrm{Th} (\mathbb {Q} _p, a_1, \dots, a_n) $ поля $\mathbb {Q}_p$ с константами $a_1, \dots, a_n$ в сигнатуре разрешима тогда и только тогда, когда каждое из $a_1, \dots, a_n $ является вычислимым $p$-адическим числом.

При рассмотрении случая неразрешимой теории нам потребуется более точная версия предшествующей теоремы.

Теорема 7.12. Справедливы следующие утверждения.

1) Если целое $p$-адическое число $a$ невычислимо, то уравнения с константами из $\mathbb{Q} \cup \{a\}$ неразрешимы в $\mathbb{Z}_p$.

2) Если $p$-адическое число $a \in \mathbb{Q}_p$ невычислимо, то уравнения с константами из $\mathbb{Q} \cup \{a\}$ неразрешимы в $\mathbb{Q}_p$.

Доказательство. Для доказательства 1) заметим, что если уравнения с константами из $\mathbb{Q} \cup \{a\}$ разрешимы в $\mathbb{Z}_p$, то можно легко построить эффективную аппроксимацию $a$. Следовательно, в этом случае $a$ – вычислимо, и мы получаем противоречие.

Чтобы доказать утверждение 2), представим $a \in \mathbb{Q}_p$ в виде $a = p^m\xi$, где $m \in \mathbb{Z}$, а $\xi$ – обратимый элемент кольца $\mathbb{Z}_p$. Заметим, что $\mathbb{Z}_p$ диофантово в $\mathbb{Q}_p$, поэтому этот случай доказывается тем же рассуждением, что и выше, с очевидными изменениями. Теорема доказана.

Назовем матрицу $A \in \mathrm{GL}_n(\mathbb{Q}_p)$ вычислимой, если все элементы матрицы $A$ являются вычислимыми $p$-адическими числами, т. е. $A \in \mathrm{GL}_n(\mathbb{Q}_p^c)$. Тогда все вычислимые матрицы в $\mathrm{SL}_n(\mathbb{Q}_p)$ – в точности все матрицы из $\mathrm{SL}_n(\mathbb{Q}_p^c)$.

Теорема 7.13. Пусть $n \geqslant 3$. Справедливы следующие утверждения.

1) Пусть

$$ \begin{equation*} G_n(\mathbb{Q}_p) \in \{\mathrm{GL}_n(\mathbb{Q}_p), \mathrm{SL}_n(\mathbb{Q}_p), \mathrm{T}_n(\mathbb{Q})_p,\mathrm{UT}_n(\mathbb{Q}_p), \mathrm{PGL}_n(\mathbb{Q}_p),\mathrm{PSL}_n(\mathbb{Q}_p)\}. \end{equation*} \notag $$
Если $A_1, \dots, A_m$ – вычислимые матрицы из $G_n(\mathbb{Q}_p)$, то теория первого порядка группы $G_n(\mathbb{Q}_p)$ с константами $A_1, \dots, A_m$ разрешима. В частности, диофантова проблема для уравнений с коэффициентами $A_1, \dots, A_m$ разрешима в $G_n(\mathbb{Q}_p)$.

2) Пусть

$$ \begin{equation*} G_n(\mathbb{Z}_p) \in \{\mathrm{GL}_n(\mathbb{Z}_p), \mathrm{SL}_n(\mathbb{Z}_p), \mathrm{T}_n(\mathbb{Z})_p,\mathrm{UT}_n(\mathbb{Z}_p), \mathrm{PGL}_n(\mathbb{Z}_p),\mathrm{PSL}_n(\mathbb{Z}_p)\}. \end{equation*} \notag $$
Если $A_1, \dots, A_m$ – вычислимые матрицы из $G_n(\mathbb{Z}_p)$, то теория первого порядка группы $G_n(\mathbb{Z}_p)$ с константами $A_1, \dots, A_m$ разрешима. В частности, диофантова проблема для уравнений с коэффициентами $A_1, \dots, A_m$ разрешима в $G_n(\mathbb{Z}_p)$.

Доказательство следует из теоремы 7.11 и предложения 6.6.

Теорема 7.14. Если матрица $ A \in \mathrm{SL}_n (\mathbb {Z}_p) $ ($ A \in \mathrm{SL}_n (\mathbb {Q}_p) $) невычислима, то диофантова проблема для уравнений с коэффициентами из $ \{t_ {ij}(1) \mid i, j = 1, \dots, n \} \cup \{A \} $ неразрешима в $\mathrm{SL}_n (\mathbb {Z}_p) $ ($ \mathrm{SL}_n (\mathbb {Q}_p) $).

Доказательство следует из теоремы 7.12 аналогично теореме 7.9.

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

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

Образец цитирования: А. Г. Мясников, М. Сохраби, “Диофантовы проблемы в классических матричных группах”, Изв. РАН. Сер. матем., 85:6 (2021), 205–244; Izv. Math., 85:6 (2021), 1220–1256
Цитирование в формате AMSBIB
\RBibitem{MyaSoh21}
\by А.~Г.~Мясников, М.~Сохраби
\paper Диофантовы проблемы в~классических матричных группах
\jour Изв. РАН. Сер. матем.
\yr 2021
\vol 85
\issue 6
\pages 205--244
\mathnet{http://mi.mathnet.ru/im9104}
\crossref{https://doi.org/10.4213/im9104}
\zmath{https://zbmath.org/?q=an:1487.20011}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2021IzMat..85.1220M}
\transl
\jour Izv. Math.
\yr 2021
\vol 85
\issue 6
\pages 1220--1256
\crossref{https://doi.org/10.1070/IM9104}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000745285800001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85124245374}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/im9104
  • https://doi.org/10.4213/im9104
  • https://www.mathnet.ru/rus/im/v85/i6/p205
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Статистика просмотров:
    Страница аннотации:321
    PDF русской версии:44
    PDF английской версии:42
    HTML русской версии:134
    Список литературы:45
    Первая страница:16
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024