| Известия Российской академии наук. Серия математическая |
|
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях) Неразрешимость проблемы вхождения в подмоноид свободной нильпотентной группы ступени В. А. Романьков Омский филиал Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук
Англоязычная версия:
Izvestiya: Mathematics, 2023, Volume 87, Issue 4, Pages DOI: https://doi.org/10.4213/im9342e 
Реферативные базы данных:
     ВведениеАлгоритмические проблемы в группах – классическая тема исследования в алгебре, имеющая топологические истоки и аналоги. В настоящее время эти проблемы привлекают большее внимание, поскольку на их трудноразрешимости в некоторых классах некоммутативных групп основываются схемы алгебраической криптографии, а сами некоммутативные группы служат платформами для реализации схем и алгоритмов некоммутативной алгебраической криптографии. Значительно возрос интерес к сложности алгоритмов, решающих такие задачи, возможности их эффективного использования в практических приложениях. Этим вопросам посвящены монографии [1]–[3]. Наряду с классическими проблемами равенства, сопряженности и вхождения М. Дена и проблемой изоморфизма Г. Титце, сформулированными в начале прошлого века, в последние десятилетия активно изучаются их естественные обобщения, а также другие алгоритмические проблемы (см. обзорные статьи [4]–[8]). В настоящей работе рассматривается проблема вхождения в конечно порожденный подмоноид – важнейший фрагмент более общей проблемы вхождения в рациональное подмножество группы. Частным случаем этой проблемы является проблема вхождения в конечно порожденную подгруппу. Речь идет о свободных нильпотентных группах конечного ранга, поэтому важно отметить, что согласно классическому результату А. И. Мальцева [9] проблема вхождения в подгруппу конечно порожденной нильпотентной группы алгоритмически разрешима. Проблему вхождения в подмоноид некоммутативной группы в настоящее время рассматривают как перенесение классической проблемы целочисленного линейного программирования, где фигурирует проблема вхождения в подмоноид свободной абелевой группы, на некоммутативную платформу. Возникло и развивается новое направление исследований – некоммутативная дискретная оптимизация (см. [10; гл. 5]). При этом особое внимание уделяется классу конечно порожденных нильпотентных групп, как наиболее близкому к классу абелевых групп. Основным результатом статьи является доказательство алгоритмической неразрешимости проблемы вхождения в фиксированный конечно порожденный подмоноид свободной нильпотентной группы ступени $2$ достаточно большого ранга и обобщение этого результата на свободные нильпотентные группы произвольной ступени $l\geqslant 3$. Исследованиями проблемы вхождения в рациональные подмножества групп занимались многие авторы. М. Лори в обзорной статье [11], представляющей результаты по этому направлению, сформулировал проблему о существовании конечно порожденной нильпотентной группы с неразрешимой проблемой вхождения в подмоноиды (проблема 24). Этот вопрос затрагивался также в докладах Б. Стейнберга на различных научных семинарах. В работе [12] (см. также монографию [13]) автором доказано, что проблема вхождения в рациональные подмножества алгоритмически неразрешима в свободной нильпотентной группе любой ступени $l \geqslant 2$ достаточно большого ранга $r$. В доказательстве использовалась интерпретация диофантовых уравнений в данной группе. Однако вопрос о разрешимости проблемы вхождения в конечно порожденные подмоноиды такой группы остался открытым. Фигурировавшие в доказательстве рациональные подмножества были далеки от подмоноидов. Напомним некоторые определения. Класс рациональных подмножеств группы $G$ есть наименьший класс, содержащий все конечные подмножества группы, замкнутый относительно операций объединения, умножения и операции Клини порождения подмножеством $K$ подмоноида $K^*$ группы $G$. Понятие рационального подмножества группы является естественным обобщением классического понятия регулярного подмножества свободного моноида. Заметим, что произвольная подгруппа $H$ группы $G$ рациональна тогда и только тогда, когда она конечно порождена (см., например, [13], [14]). Имеет место аналог теоремы Клини о задании регулярных подмножеств свободного моноида конечными автоматами: подмножество $R$ группы $G$ является рациональным тогда и только тогда, когда $R$ является выпускным множеством конечного автомата над $G$ (детальные сведения относительно определений и основных свойств рациональных подмножеств в группах см. в монографии [13] или статье [14]). Структура статьи следующая. В § 1 приводится ряд определений и вспомогательных результатов о проблеме вхождения в рациональные подмножества группы. В § 2 приводится основной результат работы – строится конечно порожденный подмоноид свободной нильпотентной группы ступени $2$ достаточно большого ранга, проблема вхождения в который алгоритмически неразрешима. В качестве следствия этот результат распространяется на свободные нильпотентные группы ступени $l \geqslant 3$. В статье используются стандартные обозначения свободной абелевой группы $A_r$ ранга $r$ и свободной нильпотентной группы $N_{r,l}$ ранга $r$ ступени нильпотентности $l$. Через $[x, y] = x^{-1}y^{-1}xy$ обозначается коммутатор элементов $x$, $y$ некоторой группы $G$, а через $G'$ – ее коммутант. Как обычно, $\mathbb{Z}$ обозначает множество целых, а $\mathbb{N}$ – множество натуральных чисел. Для $k \in \mathbb{N}$ через $\mathbb{N}_k$ обозначается множество первых $k$ натуральных чисел. § 1. Проблема вхождения в рациональные подмножества группыОбозначим через $\operatorname{Rat}(G)$ семейство рациональных подмножеств группы $G$. По определению $\operatorname{Rat}(G)$ является наименьшим семейством подмножеств группы $G$, содержащим все конечные подмножества и замкнутым относительно операций $\bullet$ объединения: $R_1, R_2 \in \operatorname{Rat}(G)\ \Rightarrow\ R_1 \cup R_2 \in \operatorname{Rat}(G)$; $\bullet$ умножения: $R_1, R_2 \in \operatorname{Rat}(G)\ \Rightarrow\ R_1 \cdot R_2 = \{r_1r_2 \colon r_1\in R_1,\, r_2\in R_2\}\in \operatorname{Rat}(G)$; $\bullet$ порождения подмоноида: $R\in \operatorname{Rat}(G)\ \Rightarrow\ R^* = \bigcup_{i=1}^{\infty} R^i \cup \{1\} \in \operatorname{Rat}(G)$. Примерами рациональных подмножеств являются конечно порожденные (и только конечно порожденные) подгруппы и конечно порожденные подмоноиды. В общем случае семейство $\operatorname{Rat}(G)$ не замкнуто относительно операций пересечения и дополнения. Результаты по характеризации конечно порожденных групп $G$, в которых $\operatorname{Rat}(G)$ является булевой алгеброй, т. е. замкнутым относительно операций пересечения и дополнения семейством, приведены в [13] и [15]. Представим некоторые известные результаты по проблеме вхождения в рациональные подмножества группы. Положительные результаты: $\bullet$ М. Бенуа [16]. Проблема вхождения в рациональные подмножества разрешима в свободных группах. $\bullet$ С. Эйленберг, М. П. Шютценберже [17] (независимое доказательство в [18]). Проблема вхождения в рациональные подмножества разрешима в абелевых группах. $\bullet$ З. Грюншлаг [19]. Разрешимость проблемы вхождения в рациональные подмножества сохраняется при конечных расширениях групп. $\bullet$ М. Ю. Недбай [20]. Разрешимость проблемы вхождения в рациональные подмножества сохраняется при свободных произведениях групп. Отрицательные результаты: $\bullet$ В. А. Романьков [12]. Для любого $l \geqslant 2$ и достаточно большого $r$ в свободной нильпотентной группе $N_{r,l}$ неразрешима проблема вхождения в рациональные подмножества. $\bullet$ М. Лори, Б. Стейнберг [21]. Свободная метабелева группа $M_r$ ранга $r \geqslant 2$ содержит конечно порожденный подмоноид с неразрешимой проблемой вхождения. Доказательства в [12] основываются на неразрешимости десятой проблемы Гильберта, а в [21] – на неразрешимости проблемы существования комбинаторного замощения (относительно других многочисленных результатов по проблеме вхождения в рациональные подмножества групп см. обзор [11]). Заметим, что проблема вхождения в конечно порожденный подмоноид свободной абелевой группы $A_r \simeq \mathbb{Z}^r$ имеет отношение к следующей задаче целочисленного линейного программирования: для данной целочисленной матрицы $A$ размера $m\times r$ и вектора $b \in \mathbb{Z}^r$ определить, существует ли решение $x \in \mathbb{N}^m$ уравнения $xA = b$. На теоретико-групповом языке это проблема вхождения в подмоноид группы $A_r$, порожденный строками матрицы $A$. Известно, что эта версия проблемы целочисленного линейного программирования принадлежит классу NP-полных проблем. Проблему вхождения в конечно порожденные подмоноиды произвольных групп в настоящее время рассматривают как естественное обобщение проблемы целочисленного линейного программирования. Обзор соответствующих результатов можно найти в книге [10]. § 2. Пример конечно порожденного подмоноида свободной нильпотентной группы ступени два достаточно большого ранга, для которого неразрешима проблема вхожденияПусть $\zeta_1, \dots, \zeta_t$ – произвольный набор коммутирующих переменных. Многочлен $D(\zeta_1, \dots, \zeta_t)$ с целыми коэффициентами от этих переменных называется диофантовым. В настоящей работе произвольное диофантово уравнение будем записывать в виде
$$
\begin{equation}
D(\zeta_1, \dots, \zeta_t) = \xi,\qquad \xi \in \mathbb{Z},
\end{equation}
\tag{1}
$$
где многочлен из левой части имеет нулевой свободный член. Напомним, что десятая проблема Гильберта – это вопрос о существовании алгоритма, который по данному диофантову уравнению определяет, имеет ли оно целочисленное решение. Ю. В. Матиясевич (см. [22]–[24]) доказал, что такого алгоритма не существует. Более того, он установил, что существует такой диофантов многочлен $D_0(\zeta_1, \dots, \zeta_{t_0})$ с нулевым свободным членом, что для класса диофантовых уравнений вида
$$
\begin{equation}
D_0(\zeta_1,\dots, \zeta_{t_0}) = \xi,\qquad \xi \in \mathbb{Z},
\end{equation}
\tag{2}
$$
не существует алгоритма, определяющего разрешимость уравнений этого класса в целых числах. Так как при $\xi = 0$ уравнение очевидно разрешимо, то данный класс уравнений алгоритмически неразрешим при дополнительном ограничении $\xi \ne 0$. Впоследствии было установлено, что десятая проблема Гильберта алгоритмически неразрешима уже для диофантовых уравнений от тринадцати неизвестных (см. [24]) и затем – для девяти неизвестных (см. [25]). 2.1. Системы СколемаВ монографии [26] Т. Сколем показал, что любое диофантово уравнение $D(\zeta_1, \dots, \zeta_t) = \xi$ эквивалентно системе уравнений от большего числа переменных трех видов: $\zeta' \zeta'' - \zeta''' =0$, $\zeta' + \zeta'' - \zeta'''=0$ и $\zeta' - \zeta'' = 0$, а также одному уравнению вида $\zeta' - \xi =0$, $\xi \in \mathbb{Z}$, где каждая переменная $\zeta'$, $\zeta''$, $\zeta'''$ либо встречается в записи исходного многочлена $D(\zeta_1, \dots, \zeta_t)$, либо вводится дополнительно. Такую систему называют системой Сколема. В дальнейшем уравнения системы Сколема записываем также в виде $\zeta'\zeta'' = \zeta'''$, $\zeta' + \zeta'' = \zeta'''$, $\zeta' = \zeta''$ и $\zeta' = \xi$ соответственно. 2.1.1. Алгоритм получения системы СколемаПокажем, как записать систему Сколема по уравнению вида (2). Считаем, что либо все коэффициенты многочлена $D_0(\zeta_1, \dots, \zeta_{t_0})$ положительны, либо среди них встречаются коэффициенты разных знаков. Если первоначально все эти коэффициенты отрицательны, то переходим к уравнению, полученному умножением обеих частей на $-1$. Возьмем один из нелинейных мономов левой части рассматриваемого уравнения. Пусть $\zeta'\zeta''$ – произведение двух его множителей. Введем новую переменную $\zeta'''$ и запишем в систему новое уравнение $\zeta'\zeta''= \zeta'''$, одновременно заменив в рассматриваемом мономе (а также в других мономах) произведение $\zeta'\zeta''$ на $\zeta'''$. Степень монома уменьшится на единицу. Если он стал линейным, переходим к следующему моному. Если нет, то продолжаем действовать аналогично с данным мономом до тех пор, пока он не станет линейным. Затем переходим к следующему моному и т.д. В результате левая часть уравнения будет представлена как алгебраическая сумма переменных. Далее вводим новые переменные, заменяя в этой сумме $\zeta' + \zeta''$ на $\zeta'''$ (аналогично $- \zeta' - \zeta''$ заменяем на $- \zeta'''$), дописывая в систему уравнение $\zeta' + \zeta'' = \zeta'''$. Продолжаем этот процесс. Если все коэффициенты в алгебраической сумме равны $1$, то последним будет уравнение вида $\zeta = \xi$, которое также включим в систему. Если присутствовали слагаемые разных знаков, то преобразовав все слагаемые левой части, мы приходим к уравнению вида $\zeta' - \zeta'' = \xi$. Заменяем $\zeta' - \zeta''$ на $\zeta'''$, дописывая уравнение $\zeta' = \zeta'' + \zeta'''$. Включаем в систему оставшееся после всех замен уравнение $\zeta''' = \xi $. В результате получим систему Сколема. 2.1.2. Положительные диофантовы уравнения и системы СколемаДиофантово уравнение, которое считается разрешимым, если у него существует решение в целых положительных числах, назовем положительным. Аналогично система Сколема, для которой разрешимость означает существование решения в целых положительных числах, называется положительной. Лемма 1. Разрешимость произвольного диофантова уравнения (1) равносильна разрешимости некоторого положительного диофантова уравнения от $2t$ переменных, эффективно строящегося по данному уравнению. Доказательство. Запишем каждую переменную $\zeta_i$ в виде разности новых переменных $\zeta_i' - \zeta_i''$. Подставив указанные разности вместо переменных уравнения (1), получим диофантово уравнение
$$
\begin{equation}
D_1(\zeta_1', \zeta_1'', \dots, \zeta_t', \zeta_t'') = 0.
\end{equation}
\tag{3}
$$
Очевидно, что разрешимость уравнения (1) в целых числах влечет разрешимость уравнения (3) в целых положительных числах и наоборот. Лемма доказана. Лемма 2. Разрешимость произвольного диофантова уравнения вида (1), у которого $\xi \ne 0$ (в частности, уравнения (2)), равносильна существованию решения у некоторой положительной системы Сколема $S = S_{\xi}$, эффективно строящейся по данному уравнению. Доказательство. Прежде всего, следуя лемме 1, построим по уравнению (1) равносильное положительное диофантово уравнение
$$
\begin{equation}
D'(\zeta_1', \zeta_1'', \dots, \zeta_{t}', \zeta_{t}'') = \xi.
\end{equation}
\tag{4}
$$
Здесь $\zeta_i = \zeta_i' - \zeta_i''$, $i = 1, \dots, t$. Затем запишем для полученного уравнения (4) равносильную ему систему Сколема, как это объяснено выше в подпункте 2.1.1. При этом замены видов $\zeta'\zeta''$ на $\zeta'''$ и $\zeta' + \zeta''$ на $\zeta'''$ приводят к положительным вводимым переменным $\zeta'''$. Один раз может потребоваться замена переменных для уравнения вида $\zeta'-\zeta'' = \xi$. Если $\xi > 0$, то вводим новую переменную $\zeta'''$, заменяя данное уравнение на два: $\zeta' = \zeta'' + \zeta'''$ и $\zeta''' = \xi$, которые записываем в систему. Если $\xi < 0$, то вводим новую переменную $\zeta'''$, заменяя данное уравнение на $\zeta'' = \zeta' + \zeta'''$ и $\zeta''' = - \xi$, которые дописываем в систему. Очевидно, что разрешимость уравнения (4) (а значит, и уравнения (1)) равносильна существованию у полученной системы Сколема $S_{\xi}$ решения в положительных целых числах, и наоборот. Лемма доказана. Рассмотрим полученную положительную систему Сколема $S_{\xi}$. Для дальнейшего нам понадобится перенумерация переменных, введение новых переменных и упорядочение уравнений системы $S_{\xi}$. Для простоты обозначение $S_{\xi}$ в данном процессе не изменяется. Допустим, что в $S_{\xi}$ имеется $c$ уравнений вида $\zeta_i\zeta_j=\zeta_l$. Вводя, если нужно, новые переменные $\zeta_i'$ и производя соответствующие замены вида $\zeta_i$ на $\zeta_i'$, добьемся того, что каждая переменная будет входить в записи этих уравнений в точности один раз. В систему $S_{\xi}$ добавятся уравнения вида $\zeta_i'=\zeta_i$. Далее перенумеруем переменные таким образом, что все $c$ уравнений указанного вида приобретут вид
$$
\begin{equation}
\zeta_{1}\zeta_{2}= \zeta_{3},\quad \dots, \quad \zeta_{3(c-1)+1} \zeta_{3(c-1)+2}= \zeta_{3c}.
\end{equation}
\tag{5}
$$
Пусть система $S_{\xi}$ содержит $d$ уравнений вида $\zeta_i+\zeta_j = \zeta_l$. Аналогично только что рассмотренному случаю, добьемся того, что среди переменных рассматриваемого множества уравнений не будет переменных предыдущей подсистемы, а каждая переменная в их записи будет входить в эти уравнения в точности один раз. Перенумеруем переменные данной подсистемы таким образом, что все $d$ уравнений указанного вида будут включать только переменные $\zeta_{3c+1}, \dots, \zeta_{3(c+d)}$, а сама подсистема приобретет вид
$$
\begin{equation}
\zeta_{3c+1} + \zeta_{3c+2} = \zeta_{3(c+1)},\quad \dots,\quad \zeta_{3(c+d-1) +1} + \zeta_{3(c+d-1) +2} = \zeta_{3(c+d)}.
\end{equation}
\tag{6}
$$
Далее запишем третью подсистему, состоящую из уравнений, связанных с равенством переменных, кроме особого уравнения, содержащего параметр $\xi$:
$$
\begin{equation}
\zeta_i = \zeta_j,\qquad (i, j) \in I \subseteq \mathbb{N} \times \mathbb{N}.
\end{equation}
\tag{7}
$$
Остается записать особое уравнение Для простоты считаем, что $t$ – наибольший индекс переменных и $t > 3(c+d)$. Данное свойство обеспечивается введением дополнительной переменной, если это необходимо.Равенства (7) задают на множестве всех переменных $\{\zeta_1, \dots, \zeta_t\}$ классы эквивалентности, получающиеся замыканием записанных отношений равенства по рефлексивности и транзитивности. Выберем в каждом таком классе $[\zeta_i] = \{\zeta_i, \zeta_{i_1}, \dots, \zeta_{i_{s(i)}}\}$ по одному представителю $\zeta_i$. Пусть $T$ – множество всех выбранных представителей. Считаем, что его элементы не встречаются в уравнениях подсистем (5) и (6). Также не включаем в $T$ переменную $\zeta_t$ из уравнения (8). Эти условия легко выполнить, вводя, если нужно, новые переменные. Считаем, что они обеспечены в описываемом процессе. Таким образом, $\zeta_1, \dots, \zeta_t$ – все переменные системы $S_{\xi}$. 2.2. Основной результатТеорема. Существует конечно порожденный подмоноид $M$ свободной нильпотентной группы $N_r = N_{r,2}$ достаточно большого ранга $r$, проблема вхождения в который алгоритмически неразрешима. 2.2.1. Общий план доказательстваВ лемме 2 доказано, что по диофантову уравнению вида (2) с параметром $\xi \ne 0$ можно эффективно построить положительную систему Сколема $S_{\xi}$ от большего числа переменных, разрешимость которой в положительных целых числах равносильна разрешимости выбранного уравнения в целых числах. Выбирается группа $N_r$ (определяется ее ранг $r$). Определяется конечное множество порождающих элементов подмоноида $M$ группы $N_r$. Подмоноид $M$ не зависит от $\xi$. Также определяется элемент $g(\xi)\in N_r$, зависящий от $\xi$. Дальнейшие рассуждения выглядят следующим образом. Предположим, что проблема вхождения элементов вида $g(\xi )$ в подмоноид $M$ алгоритмически разрешима. Будет установлено следующее: если соответствующий алгоритм показал, что элемент $g(\xi )$ принадлежит подмоноиду $M$, то система $S_{\xi}$ разрешима в целых положительных числах, а значит, и соответствующее уравнение (2), отвечающее параметру $\xi $, имеет решение в целых числах. Далее будет доказано: если уравнение вида (2) с параметром $\xi$ имеет решение, а значит, система $S_{\xi}$ разрешима в целых положительных числах, то элемент $g(\xi )$ принадлежит подмоноиду $M$. Отсюда вытекает, что разрешимость проблемы вхождения в $M$ позволяет определять разрешимость уравнений вида (2) в целых числах. Так как последняя задача алгоритмически неразрешима, то неразрешима и проблема вхождения в $M$. 2.2.2. Построение подмоноида $M$ и элементов вида $g(\xi )$Базисы групп $N_r$ и $N_r'$. Базис группы $N_r$ представим в виде объединения трех попарно непересекающихся множеств:
$$
\begin{equation*}
X = \{x_1, \dots, x_t\},\qquad Y = \{y_1, \dots, y_6\},\qquad Z = \{z_1, \dots,z_4\}.
\end{equation*}
\notag
$$
Значит, $r = t + 10$. Образы этих элементов составляют базис свободной абелевой факторгруппы $N_r/N_r'$. Базисом коммутанта $N_r'$ как свободной абелевой группы будет множество всех возможных коммутаторов от базисных элементов группы $N_r$ вида
$$
\begin{equation*}
\begin{gathered} \, [x_j, x_i]\quad (j > i),\qquad [y_q, y_p]\quad (q > p),\qquad [z_v, z_s]\quad (v > s), \\ [y_q, x_i],\qquad [z_v, x_i],\qquad [z_v, y_c], \end{gathered}
\end{equation*}
\notag
$$
где $i, j = 1, \dots, t$; $p, q = 1, \dots, 6$; $s, v = 1,\dots, 4$. Ранг коммутанта $N_r'$ как свободной абелевой группы равен $\binom{t+10}2$. Порождающие элементы подмоноида $M$ и перенос рассуждений в группу $N$. Лемма 3. Пусть $G$ – группа, $M$ – ее подмоноид. Предположим, что $M$ содержит нормальную подгруппу $K$ группы $G$. Тогда элемент $g\in G$ принадлежит $M$ тогда и только тогда, когда его образ $\overline{g}$ принадлежит образу $\overline{M}$ подмоноида $M$ в факторгруппе $\overline{G} = G/K$. Доказательство. Очевидно, что если $g\in M$, то $\overline{g}\in \overline{M}$. Пусть $\overline{g} = \overline{m}$ – образ некоторого элемента $m \in M$. Тогда $g = mh$ для некоторого $h\in K$. Так как $K\leqslant M$, то $h\in M$, следовательно, $g\in M$. Лемма доказана. В качестве порождающих подмоноида $M$ выберем элементы $y_i, z_i$, $i = 1, \dots, 4$, и $m_i = x_iu_i$, $m_i^{-} = x_i^{-1}$, где $u_i\in N_r'$ для $i = 1, \dots, t$ (элементы $u_i$ будут определены в следующем пункте), а также элементы подмножества $W\subseteq N_r'$. Подмножество $W$ содержит все возможные элементы вида $[x_j, x_i]^{\pm 1}$, $j > i$, за исключением случаев, когда $j > i$ – индексы переменных левой части уравнения из множества (5), т. е. когда пара $(j, i)$ принадлежит множеству $\{(2, 1),\, \dots,\, (3(c-1)+2,\, 3(c-1)+1)\}$. Также в $W$ включаются все элементы вида $[z_4, x_l]^{\pm 1}$, кроме случаев, когда $l$ – соответствующий индекс переменной правой части уравнения из (6), т. е. когда $l$ принадлежит множеству $\{3(c+1),\, \dots,\, 3(c+d)\}$. Элементы из $W$ порождают подмоноид $K$, являющийся нормальной подгруппой группы $N_r$. Определим группу $N = N_r/K$. Перенесем рассуждения в группу $N$, в которой по лемме 3 проблема вхождения в образ подмоноида $M$ равносильна исходной проблеме вхождения в $M$. Для простоты сохраняем для $N$ обозначения образов рассматриваемых подмоноида и элементов группы $N_r$. Все коммутаторы, включенные в $W$, в группе $N$ равны $1$. Заметим, что в $N$ перестановочны элементы $m_i$, $m_i^{-}$ с элементами $m_j$, $m_j^{-}$ во всех случаях, кроме тех, когда $(j, i)\in \{(2,1),\, (5,4),\, \dots,\, (3(c-1)+ 2, 3(c-1)+1)\}$. Также элемент $z_4$ перестановочен со всеми элементами $m_l$, $m_l^{-}$, кроме случаев, когда $l \in \{3(c+1),\, \dots,\, 3(c+d)\}$. Факторгруппа $N/N'$ изоморфна факторгруппе $N_r/N_r'$, т. е. является свободной абелевой группой ранга $r$, базис которой индуцирован базисом $X\cup Y \cup Z$ группы $N_r$. Так как все коммутаторы вида $[x_j, x_i], [z_4, x_l]$, включенные в $W$, принадлежат базису коммутанта $N_r'$, образы остальных элементов этого базиса составят базис коммутанта $N'$ как свободной абелевой группы. Таким образом, базис коммутанта $N'$ есть множество
$$
\begin{equation*}
\begin{aligned} \, &\{[x_j, x_{j-1}]\ (j = 2, 5, \dots, 3(c-1)+2),\ [y_q, y_p]\ (q > p), \\ &\qquad [z_v, z_s]\ (s, v = 1, \dots, 4,\, v > s),\ [y_q, x_i]\ (i=1, \dots, t), \\ &\qquad [z_v, x_i]\ (v= 1, 2, 3,\, i=1, \dots, t),\ [z_v, y_p]\ (v = 1, \dots, 4), \\ &\qquad [z_4, x_l]\ (l=3(c+1), \dots, 3(c+d))\}, \end{aligned}
\end{equation*}
\notag
$$
где $p, q = 1, \dots, 6$. Определение элементов $u_i\in N'$, входящих в запись порождающих $m_i$, $i = 1, \dots, t$. Элементы $u_i$ также, как элементы $m_i=x_iu_i$, взаимно однозначно соответствуют переменным $\zeta_i$, $i = 1, \dots, t$. Определим элементы $u_i$, $u_j$ и $u_l $, соответствующие уравнениям вида $\zeta_i\zeta_j = \zeta_l$ из (5). Полагаем
$$
\begin{equation}
\begin{alignedat}{2} u_i &= [y_2, x_i][y_3, x_i][y_4, x_i], &\qquad i &= 1, 4, \dots, 3(c-1) + 1, \\ u_j &= [y_1, x_j][y_2,x_j][y_3, x_j][z_2, x_j], &\qquad j &= 2, 5, \dots, 3(c-1) +2, \\ u_l &= [y_2, x_l][y_3, x_l][x_{l-1}, x_{l-2}]^{-1}, &\qquad l &= 3, 6, \dots, 3c. \end{alignedat}
\end{equation}
\tag{9}
$$
Таким образом, заданы значения элементов $u_1, \dots, u_{3c}$, а следовательно, и значения элементов $m_1, \dots, m_{3c}$. Определим элементы $u_i$, $u_j$ и $u_l$, соответствующие уравнениям вида $\zeta_i + \zeta_j = \zeta_l$ из (6). Полагаем
$$
\begin{equation}
\begin{alignedat}{2} u_i &= [y_2, x_i][y_3, x_i][z_4, x_{i+2}], &\qquad i &= 3c+1, 3(c +1) +1, \dots, 3(c + d - 1) +1, \\ u_j &= [y_2, x_j][y_3, x_j][z_4, x_{j+1}], &\qquad j &= 3c+2, 3(c +1) +2, \dots, 3(c + d - 1) +2, \\ u_l &= [y_2, x_l][y_3, x_l], &\qquad l &= 3(c+1), 3(c+2), \dots, 3(c+d). \end{alignedat}
\end{equation}
\tag{10}
$$
Таким образом, заданы значения элементов $u_{3c+1}, \dots, u_{3(c+d)}$, а следовательно, и значения элементов $m_{3c+1}, \dots, m_{3(c+d)}$. Если переменная $\zeta_i$ входит в $T$ (в частности $i > 3(c+d)$), полагаем
$$
\begin{equation}
u_i = [y_2, x_i][y_3, x_i][z_3, x_i][z_3, x_{i_1}] \cdots [z_3, x_{i_{s(i)}}].
\end{equation}
\tag{11}
$$
Индексы соответствуют классу эквивалентности $[\zeta_i]=\{\zeta_i, \zeta_{i_1}, \dots, \zeta_{i_{s(i)}}\}$. Для остальных (не входящих в $T$) переменных $\zeta_i$, $i > 3(c+d)$, за исключением $\zeta_t$ полагаем Для переменной $\zeta_t$, входящей в запись особого уравнения (8), полагаем Таким образом, заданы значения элементов $u_i$ для $i = 3(c+d) +1, \dots, t$, а следовательно, и значения элементов $m_{3(c+d)+1}, \dots, m_{t}$.Итак, определены все порождающие элементы подмоноида $M$. Элементы $g(\xi )$, проверяемые на принадлежность подмоноиду $M$. Полагаем
$$
\begin{equation}
g(\xi ) = z_1y_1z_2y_2z_3z_4y_3y_4\cdot \prod_{j\in J}[z_1,x_j]^{-1}\cdot \prod_{i\in J'}[z_2, x_i]^{-1}\cdot [y_6, y_5]^{\xi},
\end{equation}
\tag{14}
$$
где $J = \{2, 5, \dots, 3(c - 1)+2\}$, $J' = \mathbb{N}_t \setminus J$. 2.2.3. Возможные записи элементов $g(\xi )$ через произведение порождающих элементов подмоноида $M$ и их связь с решением системы $S_{\xi}$В начале докажем вспомогательное утверждение. Лемма 4. Пусть $N_s=N_{s,2}$ – свободная нильпотентная группа ступени два с базисом $v_1, \dots, v_s$. Тогда любые два различных произведения базисных элементов, каждый из которых входит в запись в точности один раз, задают различные элементы группы $N_s$. Доказательство. Для $s=2$ утверждение очевидно, так как $v_2v_1 = v_1v_2[v_2, v_1]$, $[v_2, v_1] \ne 1$. Предположим, что $s\geqslant 3$ и имеются два представления указанного вида одного элемента группы $N_s$: $v_{i_1}\cdots v_{i_s} = v_{j_1}\cdots v_{j_s}$. Выберем $i_l\ne i_1, i_s$ и перейдем к факторгруппе $N_s$ по нормальному замыканию элемента $x_{i_l}$, изоморфной группе $N_{s-1}=N_{s-1,2}$. По индукции заключаем, что либо $i_1=j_1$, если $j_1\ne i_l$, либо $i_s=j_s$ в противном случае. Оба случая рассматриваются аналогично. Пусть для определенности $i_s = j_s$. Умножаем обе части рассматриваемого равенства справа на $v_{i_s}^{-1}$ и применяем индукцию по рангу. Лемма доказана. Заметим, что в общем случае полугруппа, порожденная базисными элементами группы $N_s$, не является свободной. Например, $v_1v_2^2v_1 = v_2v_1^2v_2$. Продолжим доказательство теоремы. Лемма 5. Предположим, что элемент $g(\xi )$ принадлежит $M$. Тогда для него существует запись через порождающие подмоноида $M$, имеющая вид в которой $A, \dots, I$ есть произведения порождающих подмоноида $M$ вида $m_i$, $m_i^{-}$, $i = 1, \dots, t$. Доказательство. Из представления (14) следует, что порождающие $y_i$, $z_i$, $i = 1, \dots, 4$, должны входить в запись правой части равенства (15) в точности по одному разу обязательно в том же порядке, в каком они расположены друг относительно друга в представлении (14). Для того чтобы это установить, профакторизуем группу $N$ по нормальному замыканию элементов $y_5, y_6, x_1, \dots, x_t$. Получим свободную нильпотентную группу $N_8=N_{8,2}$ с базисом, состоящим из образов элементов $y_i$, $z_i$, $i = 1, \dots, 4$.
Чтобы показать вхождение по одному разу, рассмотрим естественный гомоморфизм группы $N$ в свободную абелеву группу $N_8/N_8'$. Образ произвольного элемента $h\in N$ имеет канонический вид $\overline{h}=\prod_{i=1}^4\overline{y}_i^{\,\alpha_i}\overline{z}_i^{\,\beta_i}$ в индуцированном базисе $\{\overline{y}_i, \overline{z}_i,\, i = 1, \dots, 4\}$, где $\alpha_i$, $\beta_i$ – суммарные степени в $h$ элементов $y_i$ и $z_i$ соответственно. Так как для элемента $g(\xi )$ его образ в $N_8/N_8'$ совпадает с образом произведения $z_1y_1z_2y_2z_3z_4y_3y_4$, для которого все $\alpha_i$, $\beta_i$ равны $1$, то это должно быть выполнено для любого его выражения в $N$. Так как в записи (15) могут присутствовать только положительные степени порождающих подмоноида $M$, то каждый из элементов $y_i$, $z_i$, $i = 1, \dots, 4$, должен входить в запись правой части равенства (15) в точности один раз. Чтобы получить утверждение о порядке вхождения базисных элементов $y_i$, $z_i$, $i = 1, \dots, 4$, в правую часть равенства (15), достаточно перейти к образам элемента $g(\xi )$ и правой части его записи (15) в группе $N_8$ и воспользоваться леммой 4. Лемма доказана. Так как образ элемента $g(\xi)$ в свободной абелевой факторгруппе $N/N'$ не зависит от элементов вида $x_i^{\pm 1}$, в записи правой части равенства (15) суммарная степень вхождения любого элемента $m_i$ должна совпадать с суммарной степенью вхождения элемента $m_i^{-}$. Считаем эту суммарную степень параметром $\zeta_i$. Далее для определения расположения элементов вида $m_i$, $m_i^{-}$ в правой части равенства (15) анализируется собирательный процесс, заключающийся в последовательном переводе для каждого $i$ всех элементов вида $m_i$, $m_i^{-}$ справа налево до крайнего левого их вхождения. Будут использоваться формулы $vm_i = m_iv[v, x_i]$, $vm_i^{-} = m_i^{-}v[v, x_i^{-1}] = m_i^{-}v[v, x_i]^{-1}$. Элементы $m_i$, $m_i^{-}$ перестановочны между собой, после их полного сбора происходит сокращение всех элементов вида $x_i^{\pm 1}$. Расположение в записи элементов из $N'$ не имеет значения, так как $N'$ – центральная подгруппа. Заметим, что $\zeta_i > 0$ для любого $i=1, \dots, t$. Действительно, если элементы $m_j$, $m_j^{-}$, $j \in J$, не входят в правую часть равенства (15), то в ее записи в ходе собирательного процесса не может появиться ненулевая степень элемента $[z_1, x_j]$. Если же не входят элементы $m_i$, $m_i^{-}$, $i\in J'$, то в записи не может появиться ненулевая степень элемента $[z_2, x_i]$. В то же время элемент $g(\xi )$ содержит в записи (14) элементы $[z_1, x_j]^{-1}$, $j \in J$, и элементы $[z_2, x_i]^{-1}$, $i \in J'$, что противоречит предположению. Пусть $v$ – один из порождающих $z_2$, $y_i$, $i = 1, \dots, 4$, группы $N$. Тогда коммутатор $[v, x_i]$ не входит в $W$ и поэтому является элементом базиса группы $N'$. При этом предположении справедлива следующая лемма. Лемма 6. 1. Пусть элемент $u_i$ (значит, и $m_i$) содержит в своей записи коммутатор $[v, x_i]$ (см. (9)–(13)). Тогда все вхождения элементов $m_i^{-}$ должны быть справа от $v$, а вхождения $m_i$ – слева. 2. Пусть элемент $u_i$ (значит, и $m_i$) не содержит в своей записи элемента $[v, x_i]$ для $v \in \{y_1, \dots, y_4, z_2\}$ (см. (9)–(13)) и при этом в записи (14) элемента $g(\xi)$ нет степеней этого коммутатора. Тогда суммарные степени элементов $m_i$ и $m_i^{-}$ справа (значит, и слева) от $v$ должны совпадать. Доказательство. 1. Непосредственно проверяется, что в записи (14) элемента $g(\xi )$ и в записях элементов $u_j$ (и $m_j$), $j \ne i$, нет степеней коммутатора $[v, x_i]$, о котором идет речь. Тогда суммарная степень $m_i^{\zeta_i}$ содержит множитель $[v, x_i]^{\zeta_i}$. Для выполнения равенства (15) необходимо, чтобы этот множитель сократился за счет элементов добавляемых в результате собирательного процесса относительно элементов $m_i$, $m_i^{-}$. Переход $m_i$ через $v$ добавляет положительную степень $[v, x_i]$, а переход $m_i^{-}$ – отрицательную $[v, x_i]^{-1}$. Чтобы получить в собирательном процессе максимально возможную по абсолютной величине степень элемента $[v, x_i]^{-\zeta_i}$, все вхождения $m_i^{-}$ должны быть справа от $v$. При этом все вхождения $m_i$ должны быть слева от $v$, иначе собирательный процесс добавит положительную степень $[v, x_i]$, и сокращения не произойдет. Полное сокращение при указанном расположении очевидно.
2. Появляющиеся в результате собирательного процесса степени коммутатора $[v, x_i]$ должны сократиться между собой. Если справа от $v$ суммарная степень $m_i$ равна $\xi_1$, а суммарная степень $m_i^{-}$ – $\xi_2$, то собирательный процесс добавит в запись правой части равенства элемент $[v, x_i]^{\xi_1 - \xi_2}$. Значит, $\xi_1 = \xi_2$. Лемма доказана. Следствие 1. 1. Пусть $i = 1, 4, \dots, 3(c-1)+1$. Тогда все вхождения $m_i$ принадлежат $CD$, а все вхождения $m_i^{-}$ – $I$. 2. Пусть $i = 2, 5, \dots, 3(c-1)+2$. Тогда все вхождения $m_i$ принадлежат $AB$, а все вхождения $m_i^{-}$ – $H$. 3. Пусть $i = 3, 6, \dots, 3c$ или $i = 3c+1, \dots, t$. Тогда все вхождения $m_i$ принадлежат $CD$, а все вхождения $m_i^{-}$ – $H$. Доказательство. 1. В данном случае п. 1 леммы 6 применим для $v= y_2, y_3, y_4$, откуда следует, что все вхождения $m_i$ принадлежат $ABCD$ (слева относительно $y_2$), а все вхождения $m_i^{-}$ – $I$ (справа относительно $y_4$). При этом происходит сокращение степени $[v, x_i]^{\zeta_i}$. Пункт 2 применим для $v=y_1$. Из него следует уточнение расположения $m_i$: все вхождения принадлежат $CD$.
2. Пункт 1 леммы 6 применим для $v= y_1, y_2, y_3, z_2$, откуда следует, что все вхождения $m_i$ принадлежат $AB$ (слева относительно $y_1$), а все вхождения $m_i^{-}$ – $HI$ (справа относительно $y_3$). При этом происходит сокращение степени $[v, x_i]^{\zeta_i}$. Пункт 2 применим для $v=y_4$. Из него следует уточнение расположения $m_i^{-}$: все вхождения принадлежат $H$. 3. Пункт 1 леммы 6 применим для $v= y_2, y_3$, откуда следует, что все вхождения $m_i$ принадлежат $ABCD$ (слева относительно $y_2$), а все вхождения $m_i^{-}$ – $HI$ (справа относительно $y_3$). При этом происходит сокращение степени $[v, x_i]^{\zeta_i}$. Пункт 2 применим для $v=y_1, y_4$. Из него следует уточнение расположения $m_i$: все вхождения принадлежат – $CD$, и $m_i^{-}$: все вхождения принадлежат $H$. Следствие установлено. Сопоставленные порождающим $m_i$ подмоноида $M$ положительные целые параметры $\zeta_i$ в случае вхождения элемента $g(\xi )$ в $M$ являются решением системы $S_{\xi}$. Далее рассматриваются значения элементов $z_i$, $i = 1, \dots, 4$, для уточнения расположений элементов вида $m_i$, $m_i^{-}$ в правой части равенства (15). Рассмотрим роль порождающего $z_1$. Для каждого $j\in J$ элемент $g(\xi )$ содержит в записи (14) элемент $[z_1, x_j]^{-1}$. Элементы $[z_1, x_j]^{\pm 1}$ не входят в канонические записи порождающих подмоноида $M$. Они могут появиться только в результате собирательного процесса элементов $m_j$, $m_j^{-}$. Это возможно, если в точности один элемент $m_j$ находится слева от $z_1$, т. е. входит в $A$, а остальные элементы $m_j$ должны входить в $B$. Рассмотрим роль порождающего $z_2$. Для каждого $i \in J'$ все элементы $m_i$ по лемме 6 входят в $CD$. Элемент $g(\xi )$ содержит в записи (14) элемент $[z_2, x_i]^{-1}$. Элементы $[z_2, x_i]^{\pm 1}$ не входят в канонические записи порождающих подмоноида $M$. Они могут появиться только в результате собирательного процесса элементов $m_i$, $m_i^{-}$, причем в точности один элемент $m_i$ должен быть слева от $z_2$. Значит, он должен входить в $C$, а остальные должны входить в $D$. Перейдем к порождающим $z_3$ (обеспечивает выполнение равенств (7)) и $z_4$ (обеспечивает выполнение равенств (6)). В лемме 6 установлено, что все элементы $m_i^{-}$ входят в $HI$, а все элементы вида $m_i$ – в $ADCD$. Это означает, что в собирательном процессе все элементы $m_i^{-}$ переходят через $z_3$ и $z_4$. Рассмотрим множество $T$ представителей классов эквивалентности $[\zeta_i]$, соответствующих уравнениям вида $\zeta_i = \zeta_j$ из (7). Пусть $i$ – индекс одного из таких представителей. По формуле (11) элемент $u_i$ содержит в своей записи произведение $[z_3, x_i][z_3, x_{i_1}] \cdots [z_3, x_{i_{s(i)}}]$, соответствующее классу эквивалентности $[\zeta_i]=\{\zeta_i, \zeta_{i_1}, \dots, \zeta_{i_{s(i)}}\}$. После собирательного процесса, примененного в равенстве (15) к элементам $m_i$ и $m_i^{-}$, и сокращения элементов $x_i^{\pm 1}$ остается множитель $c_i = [z_3, x_i]^{\zeta_i}[z_3, x_{i_1}]^{\zeta_i} \cdots [z_3, x_{i_{s(i)}}]^{\zeta_i}$. Элементов вида $[z_3, x_k]^{\pm 1}$ нет в записи элемента $g(\xi)$, их также нет в записях, порождающих $m_j$ при $j \ne i$. Множители $[z_3, x_k]^{-\zeta_k}$, $k = i, i_1, \dots, i_{s(i)}$, появляются в собирательном процессе при переходе элементов $m_k^{-}$ через $z_3$. Их произведение сокращается с $c_i$, что необходимо для выполнения равенства (15), только тогда, когда выполняются равенства $\zeta_i = \zeta_{i_1} = \dots = \zeta_{i_{s(i)}}$. Это заключение справедливо для всех классов эквивалентности. Значит, справедливость равенства (15) влечет выполнение равенств подсистемы (7). Рассмотрим в системе $S_{\xi}$ все уравнения вида $\zeta_i + \zeta_j = \zeta_l$ из (6). После собирательного процесса и сокращения в записи (15) элементов $x_i^{\pm 1}$, $x_j^{\pm 1}$ и $x_l^{\pm 1}$ должно произойти сокращение степеней коммутатора $[z_4, x_l]$. От элементов $m_i^{\zeta_i}$, $m_j^{\zeta_j}$ останется множитель $[z_4, x_l]^{\zeta_i + \zeta_j}$, так как $u_i$ содержит множитель $[z_4, x_l]$, а $u_j$ – множитель $[z_4, x_l]$ (см. (10)). Так как $[z_4, x_i], [z_4, x_j]\in W$, собирательный процесс при переходе $m_i^{-}$ и $m_j^{-}$ через $z_4$ не дает неединичных коммутаторов. Элемент $m_l^{-}$, наоборот, не содержит множителей степени элемента $[z_4, x_l]$, но добавляет в запись при переходе через $z_4$ элемент $[z_4, x_l]^{-\zeta_l}$. Полное сокращение степеней коммутатора $[z_4, x_l]$, необходимое для выполнения равенства (15), происходит только в том случае, когда $\zeta_i+\zeta_j = \zeta_l$. Значит, справедливость равенства (15) влечет выполнение равенств подсистемы (6). Рассмотрим в системе $S_{\xi}$ все уравнения вида $\zeta_i \zeta_j = \zeta_l$ из (5). По лемме 6 все элементы $m_j$ принадлежат $AB$, а все элементы $m_j^{-}$ – $H$. Элементы $m_i$ принадлежат $CD$, $m_i^{-}$ – $I$. Собирательный процесс для $m_j$, $m_j^{-}$ даст при переходе элементов $m_j^{-}$ через элементы $m_i$ множитель $[m_j^{\zeta_j}, m_i^{\zeta_i}] = [x_j, x_i]^{\zeta_i\zeta_j}$. Элемент $m_l^{\zeta_l}$ содержит множитель $[x_j, x_i]^{\zeta_l}$ (см. формулы (9)), который должен сократиться при завершении собирательного процесса. Это возможно только в случае, когда $\zeta_i\zeta_j = \zeta_l$. Значит, справедливость равенства (15) влечет выполнение равенств подсистемы (5). Рассмотрим единственное уравнение (8) системы $S_{\xi}$, включающее в себя $\xi$ и соответствующий его переменной $\zeta_t$ элемент $x_t$. После проведения собирательного процесса для элементов $m_t, m_t^{-1}$ и исключения из канонической записи правой части равенства (15) элементов $x_t^{\pm 1}$ в правой части останется множитель $[y_6, y_5]^{\zeta_t}$, равный элементу левой части $[y_6, y_5]^{\xi}$, что означает выполнение равенства (8). Итоговое расположение порождающих $m_i$, $m_i^{-}$ в правой части равенства (15). Итак, по рассматриваемой положительной системе Сколема $S_{\xi}$ определяется запись вида (15) с указанным выше расположением порождающих вида $m_i$, $m_i^{-}$, $i = 1, \dots, t$, а именно,
$$
\begin{equation}
\begin{aligned} \, &g(\xi ) = \underbrace{m_2m_5 \cdots m_{3(c-1)+2}}_{A} \cdot z_1 \cdot \underbrace{m_2^{\zeta_2 - 1}m_5^{\zeta_5-1} \cdots m_{3(c-1)+2}^{\zeta_{3(c-1)+2}-1}}_B \cdot y_1 \nonumber \\ &\ \times \underbrace{m_1m_3\cdots m_{3(c-1)+1}m_{3c} \cdot \prod_{i=3c+1}^tm_i}_C \cdot z_2 \nonumber \\ &\ \times \underbrace{m_1^{\zeta_1-1}m_3^{\zeta_3-1}\cdots m_{3(c-1)+1}^{\zeta_{3(c-1}-1}m_{3c}^{\zeta_{3c}-1} \cdot \prod_{i=3c+1}^tm_i^{\zeta_i-1}}_D \cdot y_2z_3z_4y_3 \nonumber \\ &\ \times\underbrace{(m_2^{-})^{\zeta_2}(m_3^{-})^{\zeta_3}(m_5^{-})^{\zeta_5}(m_6^{-})^{\zeta_6}\cdots (m_{3(c-1)+2}^{-})^{\zeta_{3(c-1)+2}}(m_{3c}^{-})^{\zeta_{3c}} \cdot \prod_{i=3c+1}^t(m_i^{-})^{\zeta_i}}_H \cdot y_4 \nonumber \\ &\ \times \underbrace{(m_1^{-})^{\zeta_1}(m_4^{-})^{\zeta_4}\cdots (m_{3(c-1)+1}^{-})^{\zeta_{3(c-1)+1}}}_I. \end{aligned}
\end{equation}
\tag{16}
$$
Совокупность значений $\zeta_1, \dots, \zeta_t$ есть решение рассматриваемой системы $S_{\xi}$, из которого получается решение диофантова уравнения (2). 2.2.4. Доказательство принадлежности элемента $g(\xi )$ подмоноиду $M$ в случае разрешимости системы $S_{\xi}$Будем использовать введенные выше соглашения и обозначения. Пусть $\zeta_1, \dots, \zeta_t$ – набор положительных целых чисел, являющийся решением положительной системы Сколема $S_{\xi}$. Следовательно, имеют место равенства (5)–(8). Возьмем в группе $N$ элементы $m_i=x_iu_i$, $m_i^{-}=x_i^{-1}$ в суммарных степенях $\zeta_i$ для $i = 1, \dots, t$. Элементы $u_i$, $i = 1, \dots, t$, определяются формулами (9)–(13). Для доказательства принадлежности элемента $g(\xi)$ подмоноиду $M$ группы $N$ достаточно установить справедливость равенства (16). Рассмотрим собирательный процесс, заключающийся в последовательном переводе в зафиксированном выражении (16) элементов вида $m_i^{-}$ до вхождений $m_i$ и полного сокращения множителей $x_i^{\pm 1}$ для $i =1, \dots, t$. Для вхождения элемента $g(\xi)$ в $M$ достаточно установить, что после завершения собирательного процесса в правой части выражения (16) останется представление этого элемента по формуле (14). Так как порядок вхождения элементов $y_i$, $z_i$, $i = 1, \dots, 4$, в ходе собирательного процесса не меняется, обращаем внимание только на появление и сокращение степеней базисных элементов из $N'$. Собирательный процесс начнем с порождающих $m_i$, $m_i^{-}$ для $i = 1, \dots, 3c$, соответствующих переменным подсистемы (5) системы $S_{\xi}$. Переведем элементы $m_j^{-}$ для $j \in J = \{ 2, 5, \dots, 3(c-1)+2\}$ из $H$ в $AB$. После сокращения всех вхождений $x_j^{\pm 1}$ от $m_j^{\zeta_j}$ остается его множитель
$$
\begin{equation}
u_j^{\zeta_j} = ([y_1, x_j][y_2,x_j][y_3, x_j][z_2, x_j])^{\zeta_j}.
\end{equation}
\tag{17}
$$
В собирательном процессе элементы $m_j^{-}$ должны переходить через $y_1, y_2, y_3, z_1, \dots, z_4$. В $A$ через $z_1$ переводится только один $m_j^{-}$. Это добавляет в запись (16) элемент $[z_1, x_j]^{-1}$, который есть в записи (14) элемента $g(\xi)$. Переход через $z_4$ не добавляет в запись элементов, так как $[z_4, x_j] \in W$ и поэтому тривиален в $N$. Можно считать, что через порождающие $y_1$, $y_2$, $y_3$, $z_2$, $z_3$ переводится целиком степень $(m_j^{-})^{\zeta_j}$. При этом в записи возникает дополнительное произведение $([y_1, x_j][y_2, x_j] [y_3, x_j][z_2, x_j])^{-\zeta_j}\cdot [z_3, x_j]^{-\zeta_j}$, первый множитель которого сокращается с элементом (17). Остается несокращенным множитель $[z_3, x_j]^{-\zeta_j}$. В данном процессе $(m_j^{-})^{\zeta_j}$ при прохождении $CD$ также переходит через суммарную степень $m_{j-1}^{\zeta_{j-1}}$. В правую часть выражения (16) добавляется элемент
$$
\begin{equation}
[x_{j-1}^{\zeta_{j-1}}, x_j^{-\zeta_j}]=[x_j, x_{j-1}]^{\zeta_{j-1}\zeta_j}.
\end{equation}
\tag{18}
$$
Продолжим собирательный процесс переводом элементов $m_l^{-}$ для $l\,{=}\, 3, 6, \dots, 3c$, из $H$ в $CD$. После сокращения всех вхождений $x_l^{\pm 1}$, от $m_l^{\zeta_l}$ остается его множитель
$$
\begin{equation}
u_l^{\zeta_l} = ([y_2,x_l][y_3, x_l])^{\zeta_l}\cdot [x_{l-1}, x_{l-2}]^{-\zeta_l}.
\end{equation}
\tag{19}
$$
Элемент $[x_{l-1}, x_{l-2}]^{-\zeta_l}$ в его записи сокращается с элементом (18), так как показатели степеней (при этом $j = l-1$) удовлетворяют уравнению $\zeta_{l-1}\zeta_{l-2}=\zeta_l$ подсистемы (5). Так как в $C$ находится в точности один из элементов $m_l$, через $z_2$ переводится только один $m_l^{-}$. Этот переход добавляет элемент $[z_2, x_l]^{-1}$, который есть в записи (14) элемента $g(\xi )$. Переход через $z_4$ не добавляет в запись элемента, так как $[z_4, x_l] \in W$ и поэтому тривиален в $N$. Остается рассмотреть переход элемента $(m_l^{-})^{\zeta_l}$ через $y_2$, $y_3$, $z_3$. В записи возникает дополнительное произведение $([y_2, x_l] [y_3, x_l])^{-\zeta_l}\cdot [z_3, x_l]^{-\zeta_l}$, первый множитель которого сокращается с первым множителем элемента (19). Остается в записи $[z_3, x_l]^{-\zeta_l}$. Переведем элементы $m_i^{-}$ для $i = 1, 4, \dots, 3(c-1) + 1$ из $I$ в $CD$. После сокращения всех вхождений $x_i^{\pm 1}$, от $m_i^{\zeta_i}$ остается его множитель
$$
\begin{equation}
u_i^{\zeta_i} = ([y_2,x_i][y_3, x_i][y_4, x_i])^{\zeta_i}.
\end{equation}
\tag{20}
$$
В $C$ содержится в точности один элемент $m_i$, поэтому через $z_2$ переводится только один $m_i^{-}$. Это дает элемент $[z_2, x_i]^{-1}$, который есть в записи (14) элемента $g(\xi )$. Переход через $z_4$ не добавляет в запись элементов, так как $[z_4, x_i] \in W$ и поэтому тривиален в $N$. Переходы $(m_i^{-})^{\zeta_i}$ через $y_2$, $y_3$, $y_4$, $z_3$ добавляют в правую часть выражения (16) произведение $([y_2,x_i][y_3, x_i][y_4, x_i])^{-\zeta_i}$, которое сокращается с элементом (20), и элемент $[z_3, x_i]^{-\zeta_i}$. К этому моменту собирательный процесс проведен для всех элементов $m_i$, $m_i^{-}$ при $i = 1, \dots, 3c$. Осталось в записи правой части выражения (16) произведение Также собирательный процесс добавил произведение
$$
\begin{equation}
g_1=\prod_{j\in J}[z_1, x_j]^{-1}[z_2, x_{j-1}]^{-1}[z_2, x_{j+1}]^{-1},
\end{equation}
\tag{22}
$$
которое соответствует такому же множителю элемента $g(\xi )$ в (14). Продолжим собирательный процесс для элементов $m_i, m_i^{-}$ для $i = 3(c-1)+1, \dots, 3(c+d)$, соответствующих переменным подсистемы (6) системы $S_{\xi}$. Переведем элементы $m_l^{-}$ для $l=3(c+1), \dots, 3(c+d)$ из $H$ в $CD$. В $C$ через $z_2$ переводится только один $m_l^{-}$. Это дает элемент $[z_2, x_l]^{-1}$, который есть в записи $g(\xi )$. После сокращения всех вхождений $x_l^{\pm 1}$, от $m_l^{\zeta_l}$ остается его множитель Переходы $m_l^{-}$ через $y_2, y_3, z_3, z_4$ добавляют произведение
$$
\begin{equation}
([y_2,x_l][y_3, x_i])^{-\zeta_l}\cdot [z_3, x_l]^{-\zeta_l}\cdot [z_4, x_l]^{-\zeta_l},
\end{equation}
\tag{24}
$$
первый множитель которого сокращается с элементом (23). Переведем элементы $m_i^{-}$ для $i = 3c+ 1, \dots, 3(c+d-1)+1$ из $H$ в $CD$. После сокращения всех вхождений $x_i^{\pm 1}$, от $m_i^{\zeta_i}$ остается его множитель
$$
\begin{equation}
u_i^{\zeta_i} = ([y_2,x_i][y_3, x_i])^{\zeta_i}\cdot [z_4, x_{i+2}]^{\zeta_i}.
\end{equation}
\tag{25}
$$
В $C$ через $z_2$ переводится только один $m_i^{-}$. Это дает элемент $[z_2, x_i]^{-1}$, который есть в записи (14) элемента $g(\xi)$. Переход через $z_4$ не добавляет в запись элемента, так как $[z_4, x_i] \in W$ и поэтому тривиален в $N$. Переходы $m_i^{-}$ через $y_2$, $y_3$, $z_3$ добавляют произведение $([y_2,x_i][y_3, x_i])^{-\zeta_i}$, которое сокращается с первым множителем элемента (25), и элемент $[z_3, x_i]^{-\zeta_i}$. Аналогично рассматриваются переходы элементов $m_j^{-}$ для $j = 3c+ 2, \dots, 3(c+d-1)+2$ из $H$ в $CD$. От $m_j^{\zeta_j}$ остается множитель
$$
\begin{equation}
u_j^{\zeta_j} = ([y_2,x_j][y_3, x_j])^{\zeta_j}\cdot [z_4, x_{j+1}]^{\zeta_j}.
\end{equation}
\tag{26}
$$
В $C$ через $z_2$ переводится только один $m_j^{-}$. Это дает элемент $[z_2, x_j]^{-1}$, который есть в записи (14) элемента $g(\xi)$. Переход через $z_4$ не добавляет в запись элемента, так как $[z_4, x_j] \in W$ и поэтому тривиален в $N$. Переходы $m_j^{-}$ через $y_2$, $y_3$, $z_3$ добавляют произведение $([y_2,x_j][y_3, x_j])^{-\zeta_j}$, которое сокращается с первым множителем элемента (25), и элемент $[z_3, x_j]^{-\zeta_j}$. По окончании собирательного процесса элементов $m_i$, $m_i^{-}$ при $i = 3(c-1)+1, \dots, 3(c+d)$ правая часть равенства (16) будет содержать произведение
$$
\begin{equation}
\prod_{l=3(c+1),\, \dots,\, 3(c+d)}[z_4, x_l]^{-(\zeta_{l-2} +\zeta_{l-1}-\zeta_l)}
\end{equation}
\tag{27}
$$
(см. правые множители в формулах (24)–(26), учитывая, что в них $i=l-2$, $j=l-1$). Это произведение равно $1$, так как все показатели степеней его множителей равны $0$, поскольку соответствующие им значения удовлетворяют уравнениям вида $\zeta_{l-2} + \zeta_{l-1} =\zeta_l$ подсистемы (6) системы $S_{\xi}$. Также правая часть выражения (16) будет содержать произведение Кроме того, появится произведение которое соответствует такому же множителю элемента $g(\xi )$ в записи (14). Перейдем к заключительному шагу собирательного процесса для элементов $m_i$, $m_i^{-}$ для $i = 3(c+d)+1, \dots, t$, соответствующих переменным подсистемы (7) и уравнения (8) системы $S_{\xi}$. Каждый $m_i^{-}$ переходит из $H$ в $CD$, причем только один из них переходит в $C$, добавляя $[z_2, x_i]^{-\zeta_i}$ в запись правой части равенства (16). Эти добавленные элементы входят в запись (14) элемента $g(\xi )$. Добавленное произведение имеет вид Если $\zeta_i\notin T$, $i\ne t$, то от $m_i^{\zeta_i}$ остается множитель После перевода $(m_i^{-})^{\zeta_i}$ в запись добавляется произведение $([y_2, x_i][y_3, x_i])^{-\zeta_i}\cdot [z_3, x_i]^{-\zeta_i}$, первый множитель которого сокращается с элементом (31).Для $i=t$ имеем
$$
\begin{equation}
u_t^{\zeta_t} = ([y_2, x_t][y_3, x_t])^{\zeta_t}\cdot [y_6, y_5]^{\zeta_t}.
\end{equation}
\tag{32}
$$
Второй множитель совпадает с множителем $[y_6, y_5]^{\xi}$ в записи (14) элемента $g(\xi )$, поскольку $\zeta_t = \xi$ в соответствии с уравнением (8). После перевода элемента $m_t^{-}$ из $H$ в $CD$ в запись добавляется произведение $([y_2, x_t][y_3, x_t])^{-\zeta_t}\cdot [z_3, x_t]^{-\zeta_t}$, первый множитель которого сокращается с первым множителем элемента (32). Если $\zeta_i \in T$, то от $m_i^{\zeta_i}$ остается множитель
$$
\begin{equation}
u_i^{\zeta_i}=([y_2, x_i][y_3, x_i])^{\zeta_i}\cdot ([z_3, x_i][z_3, x_{i_1}] \cdots [z_3, x_{i_{s(i)}}])^{\zeta_i}.
\end{equation}
\tag{33}
$$
Так как рассматриваемые переменные удовлетворяют подсистеме (7) системы $S_{\xi}$, выполнены равенства $\zeta_i = \zeta_{i_1} = \dots = \zeta_{i_{s(i)}}$. Тогда второй множитель правой части формулы (33) равен $[z_3,x_i]^{\zeta_i}[z_3, x_{i_1}]^{\zeta_{i_1}} \cdots [z_3, x_{i_{s(i)}}]^{\zeta_{i_{s(i)}}}$. После перевода $(m_i^{-})^{\zeta_i}$ в запись добавляется произведение $([y_2, x_i][y_3, x_i])^{-\zeta_i}\cdot [z_3, x_i]^{-\zeta_i}$, первый множитель которого сокращается с первым множителем элемента (33). Тогда есть еще не сокращенный элемент, появившийся в результате заключительного шага собирательного процесса. Учитывая не сокращенные на предыдущих шагах элементы $w_1$ из (21) и $w_2$ из (28), получаемВторые множители элементов $u_i^{\zeta_i}$ из (33) дадут произведение
$$
\begin{equation}
\prod_{\{i\colon \zeta_i\in T\}}^t[z_3, x_i]^{\zeta_i},
\end{equation}
\tag{36}
$$
которое сократится с элементом $w$ из (34). Произведение элементов $g_i$, $i = 1,2,3$, определенных в (22), (29) и (30), умноженное на элемент $z_1y_1z_2y_2z_3z_4y_3y_4$, дает выражение (14) элемента $g(\xi)$. Итак установлено, что правая часть равенства (16) после завершения собирательного процесса совпадет с правой частью представления (14) элемента $g(\xi)$. Теорема доказана. Следствие 2. Для любого $l\geqslant 3$ в свободной нильпотентной группе $N_{r,l}$ достаточно большого ранга $r$ существует конечно порожденный подмоноид $\widetilde{M}$, проблема вхождения в который алгоритмически неразрешима. Доказательство. Рассмотрим стандартный гомоморфизм $\rho \colon N_{r,l} \to N_{r}$. Обозначим через $\widetilde{M}$ полный прообраз подмоноида $M$. Так как подгруппа $\operatorname{ker}(\rho) = \gamma_3(N_{r,l})$ (третий член нижнего центрального ряда группы $N_{r,l}$) конечно порождена, $\widetilde{M}$ – конечно порожденный подмоноид. По лемме 3 проблема вхождения в подмоноид $\widetilde{M}$ в группе $N_{r,l}$ равносильна проблеме вхождения в подмоноид $M$ в группе $N_r$. Значит, эта проблема алгоритмически неразрешима. Следствие установлено. Краткое сообщение о полученных результатах (без доказательств) опубликовано в [27]. В [28] представлены достаточные условия разрешимости проблемы вхождения в конечно порожденный подмоноид свободной нильпотентной группы класса $2$ конечного ранга. Автор искренне признателен рецензентам, благодаря которым он имел возможность существенно улучшить изложение, устранив пробелы и неточности в доказательствах и оформлении статьи. 
Цитирование в формате AMSBIB
\RBibitem{Rom23} |
|
||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|