|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Неразрешимость проблемы вхождения в подмоноид свободной нильпотентной группы ступени $l\geqslant 2$ достаточно большого ранга
В. А. Романьков Омский филиал Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук
Аннотация:
Дается ответ на вопрос М. Лори и Б. Стейнберга о разрешимости проблемы вхождения в подмоноиды конечно порожденной нильпотентной группы. А именно, строится конечно порожденный подмоноид свободной нильпотентной группы ступени $2$ достаточно большого ранга $r$, проблема вхождения в который алгоритмически неразрешима. Отсюда следует существование подмоноида с аналогичным свойством в любой свободной нильпотентной группе ступени $l \geqslant 2$ ранга $r$. Доказательство основывается на неразрешимости десятой проблемы Гильберта.
Библиография: 28 наименований.
Ключевые слова:
проблема вхождения в подмоноид, нильпотентная группа, десятая проблема Гильберта, интерпретируемость уравнений в группах.
Поступило в редакцию: 28.03.2022 Исправленный вариант: 20.06.2022
Введение Алгоритмические проблемы в группах – классическая тема исследования в алгебре, имеющая топологические истоки и аналоги. В настоящее время эти проблемы привлекают большее внимание, поскольку на их трудноразрешимости в некоторых классах некоммутативных групп основываются схемы алгебраической криптографии, а сами некоммутативные группы служат платформами для реализации схем и алгоритмов некоммутативной алгебраической криптографии. Значительно возрос интерес к сложности алгоритмов, решающих такие задачи, возможности их эффективного использования в практических приложениях. Этим вопросам посвящены монографии [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}
$$
Остается записать особое уравнение
$$
\begin{equation}
\zeta_t = \xi.
\end{equation}
\tag{8}
$$
Для простоты считаем, что $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$ полагаем
$$
\begin{equation}
u_i = [y_2, x_i][y_3, x_i].
\end{equation}
\tag{12}
$$
Для переменной $\zeta_t$, входящей в запись особого уравнения (8), полагаем
$$
\begin{equation}
u_t = [y_2, x_t][y_3,x_t][y_6, y_5].
\end{equation}
\tag{13}
$$
Таким образом, заданы значения элементов $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$, имеющая вид
$$
\begin{equation}
g(\xi ) = A \cdot z_1 \cdot B \cdot y_1\cdot C \cdot z_2 \cdot D \cdot y_2 \cdot E \cdot z_3 \cdot F \cdot z_4 \cdot G\cdot y_3\cdot H \cdot y_4 \cdot I,
\end{equation}
\tag{15}
$$
в которой $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}
w_1=\prod_{i=1}^{3c}[z_3, x_i]^{-\zeta_i}.
\end{equation}
\tag{21}
$$
Также собирательный процесс добавил произведение
$$
\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}$ остается его множитель
$$
\begin{equation}
u_l^{\zeta_l} = ([y_2,x_j][y_3, x_j])^{\zeta_l}.
\end{equation}
\tag{23}
$$
Переходы $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) будет содержать произведение
$$
\begin{equation}
w_2=\prod_{i=3c+1}^{3(c+d)}[z_3, x_i]^{-\zeta_i}.
\end{equation}
\tag{28}
$$
Кроме того, появится произведение
$$
\begin{equation}
g_2=\prod_{i=3c+1}^{3(c+d)}[z_2, x_i]^{- 1},
\end{equation}
\tag{29}
$$
которое соответствует такому же множителю элемента $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 )$. Добавленное произведение имеет вид
$$
\begin{equation}
g_3 = \prod_{i=3(p+q)+1}^t [z_2, x_i]^{-\zeta_i}.
\end{equation}
\tag{30}
$$
Если $\zeta_i\notin T$, $i\ne t$, то от $m_i^{\zeta_i}$ остается множитель
$$
\begin{equation}
u_i^{\zeta_i}=([y_2, x_i][y_3, x_i])^{\zeta_i}.
\end{equation}
\tag{31}
$$
После перевода $(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). Тогда
$$
\begin{equation}
w_3=\prod_{i=3(c+d)+1}^t[z_3, x_i]^{-\zeta_i}
\end{equation}
\tag{34}
$$
есть еще не сокращенный элемент, появившийся в результате заключительного шага собирательного процесса. Учитывая не сокращенные на предыдущих шагах элементы $w_1$ из (21) и $w_2$ из (28), получаем
$$
\begin{equation}
w= w_1w_2w_3 = \prod_{i = 1}^t[z_3, x_i]^{-\zeta_i}.
\end{equation}
\tag{35}
$$
Вторые множители элементов $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$ конечного ранга. Автор искренне признателен рецензентам, благодаря которым он имел возможность существенно улучшить изложение, устранив пробелы и неточности в доказательствах и оформлении статьи.
|
|
|
Список литературы
|
|
|
1. |
A. Myasnikov, V. Shpilrain, A. Ushakov, Group-based cryptography, Adv. Courses Math. CRM Barcelona, Birkhäuser Verlag, Basel, 2008, xvi+183 pp. |
2. |
A. Myasnikov, V. Shpilrain, A. Ushakov, Non-commutative cryptography and complexity of group-theoretic problems, Math. Surveys Monogr., 177, Amer. Math. Soc., Providence, RI, 2011, xiv+385 pp. |
3. |
В. А. Романьков, Алгебраическая криптология, Изд-во Омского гос. ун-та, Омск, 2020, 261 с. |
4. |
С. И. Адян, В. Г. Дурнев, “Алгоритмические проблемы для групп и полугрупп”, УМН, 55:2(332) (2000), 3–94 ; англ. пер.: S. I. Adian, V. G. Durnev, “Decision problems for groups and semigroups”, Russian Math. Surveys, 55:2 (2000), 207–296 |
5. |
Г. А. Носков, В. Н. Ремесленников, В. А. Романьков, “Бесконечные группы”, Итоги науки и техн. Сер. Алгебра. Топол. Геом., 17, ВИНИТИ, М., 1979, 65–157 ; англ. пер.: G. A. Noskov, V. N. Remeslennikov, V. A. Roman'kov, “Infinite groups”, J. Soviet Math., 18:5 (1982), 669–735 |
6. |
В. Н. Ремесленников, В. А. Романьков, “Теоретико-модельные и алгоритмические вопросы теории групп”, Итоги науки и техн. Сер. Алгебра. Топол. Геом., 21, ВИНИТИ, М., 1983, 3–79 ; англ. пер.: V. N. Remeslennikov, V. A. Roman'kov, “Model-theoretic and algorithmic questions in group theory”, J. Soviet Math., 31:3 (1985), 2887–2939 |
7. |
В. А. Романьков, “Об алгоримических проблемах теории групп”, Вестн. Омского ун-та, 2017, № 2, 18–27 |
8. |
Ch. F. Miller, III, “Decision problems in algebraic classes of groups (a survey)”, Word problems: decision problems and the Burnside problem in group theory, Dedicated to H. Neumann (Univ. California, Irvine, CA, 1969), Stud. Logic Found. Math., 71, North-Holland, Amsterdam, 1973, 507–523 |
9. |
А. И. Мальцев, “О гомоморфизмах на конечные группы”, Уч. зап. Ивановского гос. пед. ин-та, 18:5 (1958), 49–60 ; англ. пер.: A. I. Mal'cev, “On homomorphisms onto finite groups”, Amer. Math. Soc. Transl. Ser. 2, 119, Amer. Math. Soc., Providence, RI, 1983, 67–79 |
10. |
F. Bassino, I. Kapovich, M. Lohrey, A. Miasnikov, C. Nicaud, A. Nikolaev, I. Rivin, V. Shpilrain, A. Ushakov, P. Weil, Complexity and randomness in group theory. GAGTA book 1, De Gruyter, Berlin, 2020, xii+374 pp. |
11. |
M. Lohrey, “The rational subset membership problem for groups: a survey”, Groups St. Andrews 2013, London Math. Soc. Lecture Note Ser., 422, Cambridge Univ. Press, Cambridge, 2015, 368–389 |
12. |
V. A. Roman'kov, “On the occurence problem for rational subsets of a group”, Комбинаторные и вычислительные методы в математике, Cб. науч. тр., ОмГУ, Омск, 1999, 235–242 |
13. |
B. А. Романьков, Рациональные подмножества в группах, Изд-во Омского гос. ун-та, Омск, 2014, 176 с. |
14. |
R. H. Gilman, “Formal languages and infinite groups”, Geometric and computational perspectives on infinite groups (Minneapolis, MN, New Brunswick, NJ, 1994), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, Amer. Math. Soc., Providence, RI, 1996, 27–51 |
15. |
V. A. Roman'kov, “Polycyclic, metabelian or soluble of type $(\mathrm{FP})_{\infty}$ groups with Boolean algebra of rational sets and biautomatic soluble groups are virtually abelian”, Glasg. Math. J., 60:1 (2018), 209–218 |
16. |
M. Benois, “Parties rationnelles du groupe libre”, C. R. Acad. Sci. Paris Sér. A, 269 (1969), 1188–1190 |
17. |
S. Eilenberg, M. P. Schützenberger, “Rational sets in commutative monoids”, J. Algebra, 13:2 (1969), 173–191 |
18. |
М. Ю. Недбай, “Проблема вхождения в рациональные подмножества конечно порожденных абелевых групп”, Вестн. Омского ун-та, 1999, № 3, 37–41 |
19. |
Z. Grunschlag, Algorithms in geometric group theory, PhD thesis, Univ. of California, Berkeley, 1999, 127 pp. |
20. |
М. Ю. Недбай, “Проблема вхождения в рациональные подмножества свободного произведения групп”, Вестн. Омского ун-та, 2000, № 2, 17–18 |
21. |
M. Lohrey, B. Steinberg, “Tilings and submonoids of metabelian groups”, Theory Comput. Syst., 48:2 (2011), 411–427 |
22. |
Ю. В. Матиясевич, “Диофантово представление перечислимых предикатов”, Изв. АН СССР. Сер. матем., 35:1 (1971), 3–30 ; англ. пер.: Yu. V. Matijasevič, “Diophantine representation of enumerable predicates”, Math. USSR-Izv., 5:1 (1971), 1–28 |
23. |
Yu. V. Matijasevič, “Some purely mathematical results inspired by mathematical logic”, Logic, foundations of mathematics and computability theory, Proc. 5th internat. congr. logic, methodology and philos. of sci., Part I (Univ. Western Ontario, London, ON, 1975), Univ. Western Ontario Ser. Philos. Sci., 9, Reidel, Dordrecht, 1977, 121–127 |
24. |
Y. Matijasevič, J. Robinson, “Reduction of an arbitrary Diophantine equation to one in 13 unknowns”, Acta Arith., 27 (1975), 521–553 |
25. |
J. P. Jones, “Undecidable Diophantine equations”, Bull. Amer. Math. Soc. (N.S.), 3:2 (1980), 859–862 |
26. |
T. Skolem, Diophantische Gleichungen, Ergeb. Math. Grenzgeb., 5, Springer, Berlin, 1938, 130 pp. |
27. |
В. А. Романьков, “Две проблемы о разрешимых и нильпотентных группах”, Алгебра и логика, 59:6 (2020), 719–733 ; англ. пер.: V. A. Roman'kov, “Two problems for solvable and nilpotent groups”, Algebra and Logic, 59:6 (2021), 483–492 |
28. |
V. A. Roman'kov, “Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two”, Сиб. электрон. матем. изв., 19:1 (2022), 387–403 |
Образец цитирования:
В. А. Романьков, “Неразрешимость проблемы вхождения в подмоноид свободной нильпотентной группы ступени $l\geqslant 2$ достаточно большого ранга”, Изв. РАН. Сер. матем., 87:4 (2023), 166–185; Izv. Math., 87:4 (2023), 798–816
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/im9342https://doi.org/10.4213/im9342 https://www.mathnet.ru/rus/im/v87/i4/p166
|
Статистика просмотров: |
Страница аннотации: | 327 | PDF русской версии: | 7 | PDF английской версии: | 40 | HTML русской версии: | 73 | HTML английской версии: | 120 | Список литературы: | 71 | Первая страница: | 11 |
|