| Известия Российской академии наук. Серия математическая |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Диофантовы проблемы в классических матричных группах А. Г. Мясников, М. Сохраби Mathematical Department, Stevens Institute of Technology, Hoboken, USA
Англоязычная версия:
Izvestiya: Mathematics, 2021, Volume 85, Issue 6, Pages DOI: https://doi.org/10.1070/IM9104 
Реферативные базы данных:
   § 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)$ может быть записан как произведение где $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)$ может быть записан как произведение для некоторых $\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$ вычислима, т. е. что вычислимы следующие множества: Эти множества задаются уравнениями в $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$. Таким образом, для любых $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$: Так как множества $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
$$
Положим Тогда
Из (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)$
Так как $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, получаем равенство а значит, $T^\phi_{km}$ диофантово в $G$. Предложение доказано.Следствие 4.9. Если $G$ – большая подгруппа в $\mathrm{PGL}_n(R)$ и кольцо $R$ не содержит делителей нуля, то $\mathrm{UT}^\phi_n(R)$ диофантова подгруппа в $G$. Следствие 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$ такой, что а также $-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$,
Из этого следует, что для $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$,
Скалярная матрица $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$ имеем а значит, $\mathrm{T}_{1j}$ диофантово в $G$, так как множество $C_{1,j-1}$ является диофантовым. Аналогично, для $i<n-1$ имеем и это значит, что $\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*}
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$. Следовательно, также диофантово в $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}$ положим Заметим, что если $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$ – такие матрицы, что Заметим, что такие $x_1, y_1$ всегда существуют и единственны, так как если $x = t_{1n}(\alpha), y = t_{1n}(\beta)$, то $x_1 = t_{12}(\alpha), y_1 = t_{2n}(\beta)$. Теперь определим Легко увидеть, что тогда т. е. $\otimes$ согласуется с умножением в $R$. Для завершения доказательства нам необходимы два утверждения.Утверждение 6.2. Отображение $\alpha \to t_{1n}(\alpha)$ определяет изоморфизм колец $R \to \langle \mathrm{T}_{1n}; \oplus, \otimes \rangle$. Это немедленно следует из конструкции. Для доказательства этого утверждения, заметим сначала, что, как было упомянуто выше, $\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}$, где Матричное умножение $\odot$ на наборах $\overline x$ и $\overline y$ из $R^{n^2}$ определяем следующим образом: где $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)$ либо положителен, либо отрицателен на окрестности Отсюда, вычислив значение $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$ и что его можно (алгоритмически) представить в виде нетривиальной линейной комбинации базисных элементов $1, \dots,\alpha^{n-1}$ поля $F$ над $L$. Чтобы установить, имеет место неравенство $b>0$ или $b<0$, рассмотрим рациональную функцию Заметим, что $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 $ и Если $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)$. Теперь покажем, что существует некоторое разложение где все числа $\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) Пусть Если $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) $).
Цитирование в формате AMSBIB
\RBibitem{MyaSoh21} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|