Аннотация:
Представлен алгоритм, определяющий максимальный ранг свободной нильпотентной метабелевой или соответственно нильпотентной группы, изоморфно вложимой в данную частично коммутативную нильпотентную группу той же ступени нильпотентности. Показано, как осуществляются эти вложения.
Библиография: 12 названий.
Среди классов групп, определение которых связано со структурой простых графов, выделяется класс (свободных) частично коммутативных групп. Они также называются прямоугольными группами Артина и графовыми группами. Эти группы имеют приложения как в математике, так и в компьютерных науках. В них разрешимы проблемы равенства и сопряженности. Каждая частично коммутативная группа действует свободно и кокомпактно на конечномерном CAT(0) кубическом комплексе. Имеется также много других свойств топологического и алгебраического характера, составляющих богатую теорию частично коммутативных групп, см. по этому поводу обзорные статьи [1], [2].
Приведем определения. Пусть $\Gamma=\langle X; E\rangle $ обозначает ненаправленный граф без кратных ребер и петель с множеством вершин $X=\{x_1, \dots, x_n\}$ и множеством ребер $E\subseteq X\times X$. Частично коммутативная группа $F(\Gamma )$ определяется следующим представлением через порождающие элементы и определяющие соотношения:
К теории параллельных вычислений частично коммутативные группы имеют следующее отношение. Пусть $X$ – множество операций. Слово в алфавите $X$ кодирует очередность выполнения операций в некотором процессе. Некоторые пары операций перестановочны (коммутируют), другие – нет. Следовательно, $\Gamma$ является графом коммутирования для рассматриваемого процесса. Коммутирующие операции можно выполнять параллельно. Первоначально были введены в обращение частично коммутативные моноиды, определение которых фактически совпадает с (1.1). Группы появились вместе с необходимостью рассматривать обратимые операции. Методы теории групп стали применяться в теории графов и наоборот, методы теории графов проникли в теорию групп в связи с исследованием упомянутых процессов вычислений.
По мере развития теории стали рассматриваться частично коммутативные группы многообразий. Пусть $\mathfrak{W}$ – многообразие групп. Частично коммутативная группа многообразия $\mathfrak{W}$ относительно графа $\Gamma=\langle X; E\rangle$ определяется заданием через порождающие элементы и определяющие соотношения в многообразии $\mathfrak{W}$, как
Наибольшее внимание уделяется многообразиям $\mathfrak{N}_k$, $k\in \mathbb{N}$, всех нильпотентных групп ступени не больше чем $k$ и многообразию всех метабелевых групп $\mathfrak{A}^2$. Также привлекают внимание многообразия $\mathfrak{A}^l$, $l\in \mathbb{N}$, всех разрешимых групп ступени не больше чем $l$ и многообразия $\mathfrak{N}_k\cap \mathfrak{A}^l$, в частности, многообразия нильпотентных метабелевых групп $\mathfrak{N}_k\cap \mathfrak{A}^2$. Первоначально Дромс в [3] использовал группы вида $F(\Gamma; \mathfrak{N}_2)$ для доказательства того, что изоморфизм групп $F(\Gamma )$ и $F(\Delta )$, где графы имеют общее множество вершин, влечет изоморфизм графов $\Gamma $ и $\Delta$. А именно, вначале он установил это утверждение для групп $F(\Gamma; \mathfrak{N}_2)$ и $F(\Delta; \mathfrak{N}_2)$, а затем перенес на исходные группы – их естественные накрывающие. Впоследствии частично коммутативные группы многообразий стали изучаться как самостоятельный объект. Относительно нормальных форм элементов частично коммутативных нильпотентных метабелевых и нильпотентных групп см. соответственно работы Тимошенко [4], [5]. Эти работы имеют существенное значение для данной статьи, так как в них построены мальцевские базы указанных групп, используемые в доказательствах получаемых результатов.
Мотивацией данной работы служит возможность перенесения некоторых свойств свободных групп рассматриваемых многообразий на другие группы этих многообразий. Например, таким способом могут переноситься свойства из работ [6] и [7] об алгоритмической (не)разрешимости уравнений и проблемы эндоморфной сводимости. В некоторых случаях для выполнения свойства требуется достаточно большой ранг свободной группы. Например, неразрешимость проблемы вхождения в подмоноид свободной нильпотентной группы ступени $k\geqslant 2$ установлена в [8] для свободной группы достаточно большого ранга. Именно при обсуждении возможности перенесения этого свойства был высказан соответствующий вопрос А. Ю. Ольшанского, на которой дается ответ в данной работе.
Далее в работе всюду $\Gamma $ обозначает ненаправленный граф без петель и кратных ребер с множеством вершин $X=\{x_1, \dots, x_n\}$, упорядоченных в соответствии с индексами, и множеством ребер $E \subseteq X \times X$. Коммутатор двух элементов группы понимается как $[g, f]= g^{-1}f^{-1}gf$. Простые коммутаторы определяются индуктивно как $[g_1, g_2, \dots, g_{i+1}]=[[g_1, g_2, \dots, g_{i}], g_{i+1}]$. Через $G'$ обозначается коммутант группы $G$. Нижний центральный ряд $G=\gamma_1(G) \geqslant \gamma_2(G) \geqslant \dots \geqslant \gamma_i(G) \dots $ группы $G$ определяется индуктивно формулой $\gamma_{i+1}=[\gamma_i(G), G]$.
2. Предварительные результаты
В [9] Мальцев доказал, что множество элементов $\{g_{\xi},\,\xi \in \Xi \}$ порождает в свободной нильпотентной группе $N_{r,k}$ ранга $r$ ступени $k$ свободную нильпотентную подгруппу той же ступени $k$, для которой оно является множеством свободных порождающих тогда и только тогда, когда образы этих элементов линейно независимы в абелизации (факторе по коммутанту) $N_{r,k}/N_{r,k}'$. В [10] Баумслаг доказал аналогичное утверждение для произвольной свободной разрешимой группы $S_{r,l}$ ранга $r$ ступени $l$, в частности, для свободной метабелевой группы $M_r$ ранга $r$. Из этих результатов следует справедливость аналогичного утверждения для свободных нильпотентных разрешимых групп $N(\mathfrak{A}^l)_{r,k}$, в частности, свободных нильпотентных метабелевых групп $N(\mathfrak{A}^2)_{r,k}$ ранга $r$ ступени $k$.
Мальцевские базы. Пусть $G$ – конечно порожденная нильпотентная группа без кручения. Тогда в ней существует центральный нормальный ряд с бесконечными циклическими факторами
Возьмем элементы $a_i\in G_i$ такие, что $G_{i}=$ gp($a_i, G_{i+1}$), $i=1, \dots, s$. Следующее определение содержится, например, в [11].
Определение 1. Упорядоченный набор элементов $\overline{a}=(a_1, \dots, a_s)$ называется мальцевской базой группы $G$, соответствующей ряду (2.1). Произвольный элемент $g\in G$ однозначно представляется в виде
где множители расположены в указанном порядке. Показатели степеней $\alpha_i$ называются мальцевскими координатами элемента $g$ относительно базы $\overline{a}$.
Известно (см., например, [11] или [12]), что факторы верхнего центрального ряда нильпотентной группы без кручения также не имеют кручения. В этом случае центральный ряд с бесконечными циклическими факторами можно выбрать как уплотнение верхнего центрального ряда, взяв в качестве мальцевской базы прообразы базисных элементов факторов как свободных абелевых групп конечного ранга.
Обычно в качестве мальцевской базы относительно свободной нильпотентной группы без кручения выбираются простые и сложные коммутаторы от порождающих элементов, называемые базисными коммутаторами. Например, базисные коммутаторы Холла [12] группы $N_{r,k}$ с базой $Y=\{y_1, \dots, y_r\}$ определяются и упорядочиваются следующим образом.
Упорядоченный набор базисных коммутаторов является мальцевской базой группы $N_{r,k}$.
Для группы $N(\mathfrak{A}^2)_{r,k}$ рассматриваются только простые базисные коммутаторы $[y_{i_1}, y_{i_2}, \dots, y_{i_s}]$, $y_{i_2}\leqslant y_{i_3} \leqslant \dots \leqslant y_{i_s}$, $y_{i_1}> y_{i_2}$, до веса $k$ включительно, также составляющие мальцевскую базу.
Предположим, что в конечно порожденной нильпотентной группе без кручения $G$ факторы нижнего центрального ряда также не имеют кручения, следовательно, являются свободными абелевыми группами конечного ранга. Зафиксировав в каждом факторе базу свободной абелевой группы, мы собираем мальцевскую базу группы $G$ как объединение прообразов элементов этих баз. В качестве прообразов берем произведения коммутаторов соответствующего веса. Таким образом, элементы мальцевской базы разбиваются на непересекающиеся подмножества в соответствии с их весами. Такие мальцевские базы будем называть соответствующими уплотнению нижнего центрального ряда. В частности, такими являются базы составленные из базисных коммутаторов групп вида $N_{r,k}$ и $N(\mathfrak{A}^2_{r,k})$ описанные выше.
Известно, что частично коммутативные группы многообразий $\mathfrak{N}_k\cap \mathfrak{A}^2$ и $\mathfrak{N}_k$ не имеют кручения. Более того, факторы нижних центральных рядов этих групп также не имеют кручения (см. [4], [5] соответственно).
В работе [4] дано описание мальцевской базы группы $F(\Gamma, \mathfrak{N}_k\cap \mathfrak{A}^2)$, соответствующей уплотнению ее нижнего центрального ряда. В работе [5] получено описание мальцевской базы произвольной частично коммутативной нильпотентной группы $F(\Gamma, \mathfrak{N}_k)$, также являющейся уплотнением нижнего центрального ряда. Описание этих баз конструктивное, для любого элемента $g$, записанного через порождающие элементы группы, эффективно находится запись вида (2.2), Ввиду сложности и громоздкости данное описание и процесс записи элемента в соответствующей нормальной форме (2.2) здесь не приводятся.
3. Вспомогательные результаты
Лемма 1. Пусть $G$ – конечно порожденная нильпотентная группа без кручения, порожденная элементами $y_1, \dots, y_r$, $\overline{a}=(a_1, \dots, a_s)$ – ее мальцевская база. Пусть $H$ – нильпотентная группа с выделенным набором элементов $g_1, \dots, g_r$ такая, что отображение $ y_i \mapsto g_i$, $i=1, \dots, r$, определяет гомоморфизм $\phi$ группы $G$ в группу $H$. Тогда $\phi $ является вложением в том и только том случае, если набор элементов $\phi (\overline{a})=(\phi (a_1), \dots, \phi (a_s))$ составляет мальцевскую базу образа $\phi (G)$.
Доказательство. Если $\phi (\overline{a})$ мальцевская база для $\phi (G)$, то образ $\phi (g)$ любого элемента $g\in G$ однозначно записывается в виде
что соответствует записи элемента $g$ в форме (2.2). Значит, $\phi$ – вложение. Если данной однозначности нет, то $\operatorname{ker}(\phi) \neq 1$ и $\phi$ не вложение.
Следствие 1. Пусть $\mathfrak{N}$ – одно из многообразий $\mathfrak{N}_k$ или $\mathfrak{N}_k\cap \mathfrak{A}^2$, $G$ – свободная группа в этом многообразии ранга $r$ с базой $\overline{y}=\{y_1, \dots, y_r\}$ (т.е. группа $N_{r,k}$ или $N(\mathfrak{A}^2)_{r,k}$), $\overline{a}=(a_1, \dots, a_s)$ – мальцевская база этой группы. Пусть $H$ – группа из рассматриваемого многообразия $\mathfrak{N}$ и $\overline{g}=\{g_1, \dots, g_r\}$ – набор ее порождающих элементов. Тогда $G$ изоморфна группе $H$ относительно гомоморфизма $\phi$, определяемого отображением $ y_i\mapsto g_i$, $i=1, \dots, r$, в том и только том случае, если $\phi (\overline{a})=(\phi (a_1), \dots, \phi (a_s))$ составляет мальцевскую базу образа $\phi (G)$.
Доказательство. Утверждение прямо следует из леммы 1. Нужно только заметить, что условие гомоморфности $\phi$ в данном случае выполняется автоматически как следствие свободы группы $G$.
4. Основные результаты
Теорема 1. Пусть $\Gamma=\langle X; E\rangle$ – граф и $F=F(\Gamma; \mathfrak{N})$ – частично коммутативная группа для одного из многообразий вида $\mathfrak{N}_k\cap \mathfrak{A}^2$ или $\mathfrak{N}_k$, $k \geqslant 2$. Пусть $\overline{g}=\{g_1, \dots, g_r\}$ – конечное множество порождающих элементов ее подгруппы $G$. Тогда существует алгоритм, который определяет, является ли $G$ свободной группой данного многообразия $\mathfrak{N}$ с базой $\overline{g}$.
Доказательство. Согласно двум приведенным в разделе 2 результатам Тимошенко можно считать, что мальцевская база группы $F$ состоит из совокупности элементов, разбитых на подмножества, соответствующие базам свободных абелевых факторов нижнего центрального ряда группы $F$. Пусть $\overline{a}_i=(a_{i_1}, \dots, a_{i_{s(i)}})$, $i=1, \dots, k-1$, – часть мальцевской базы, соответствующая фактору $\gamma_i(F)/\gamma_{i+1}(F)$. Для того, чтобы выполнялись условия следствия 1, обеспечивающие свободу подгруппы $G$ с базой $\overline{g}$, необходимо и достаточно, чтобы для любого $i$ множество образов базисных коммутаторов от $\overline{g}$ веса $i$ были в этом факторе линейно независимыми. Данное условие сводится к стандартной проверке на линейную независимость набора элементов свободной абелевой группы. В данном случае – группы $\gamma_i(F)/\gamma_{i+1}(F)$, порождающие которой известны. Предварительно образы рассматриваемых базисных коммутаторов в факторе $\gamma_i(F)/\gamma_{i+1}(F)$ переписываются через образы базы $\overline{a}_i $. Такая переписка также стандартна.
Теорема 2. Пусть $\mathfrak{N}$ – одно из многообразий вида $\mathfrak{N}_k$ или $\mathfrak{N}_k\cap \mathfrak{A}^2$. Пусть $F=F(\Gamma; \mathfrak{N})$ – частично коммутативная группа для $\mathfrak{N}$. Тогда существует алгоритм, определяющий возможность вложения любой свободной группы $G$ многообразия $\mathfrak{N}$ в группу $F$.
Доказательство. Допустим, нужно определить возможность вложения свободной группы $G$ ранга $r$ с базой $\overline{y}=\{y_1, \dots, y_r\}$ в группу $F$. Как замечено в разделе 2, набор $\overline{g}=\{g_1, \dots, g_r\}$, $g_i=\phi (y_i)$, $i=1, \dots, r$, порождающих образа такого вложения $\phi$ должен быть линейно независимым по модулю коммутанта $F'$. Значит, при $r\geqslant n+1$ такое вложение невозможно. Итак считаем, что $r \leqslant n$.
Рассмотрим набор элементов $\overline{g}=\{g_1, \dots, g_r\}$ группы $F$, записанных в виде $g_i=\prod_{j=1}^nx_j^{\alpha_{i,j}}u_i$, $u_i\in G'$, с неопределенными показателями степеней из алгебры многочленов $ \Lambda= \mathbb{Z}[\alpha_{1,1}, \dots,\alpha_{r,n}]$, которые могут принимать целые значения, и произвольными $u_i$. Мальцевская база $\overline{a}=(a_1, \dots, a_s)$ группы $F$, которую мы считаем приуроченной к нижнему центральному ряду, позволяет однозначно представить любой элемент $g\in F$ в виде (2.2) с показателями степеней из $\Lambda$, не зависящими от $u_i$, $i=1, \dots, r$.
Выберем подбазу $\overline{a}_i$, соответствующую фактору $\gamma_i(F)/\gamma_{i+1}(F)$, для каждого $i=1, \dots, k$. Представим каждый базисный коммутатор веса $i$ от $\overline{g}$ в виде линейной комбинации элементов $\overline{a}_i$ с коэффициентами (показателями степеней) из $\Lambda$ по модулю $\gamma_{i+1}(F)$. Такое представление единственно. Показатели степеней при этом (коэффициенты представления) не зависят от элементов $u_i$, $i=1, \dots, r$. Из коэффициентов представлений составим матрицу $M_i$. Заметим, что в ней количество строк не больше чем столбцов.
Вычислим все максимальные миноры матрицы $M_i$. Если хотя бы один из них не равен $0$, данные векторы линейно независимы. Если для любого $i$ существует так полученный ненулевой минор $m_i$, то существует специализация $\Lambda \to \mathbb{Z}$, для которой образы этих миноров также ненулевые. Значит, по следствию 1 подгруппа $\operatorname{gp}(g_1, \dots, g_r)$ изоморфна свободной группе многообразия $\mathfrak{N}$ с базой $\overline{g}$, а группа $G$ вложима в $F$.
Если хотя бы для одного $i$ все максимальные миноры нулевые, то любой максимальный минор для этого $i$, полученный гомоморфизмом специализации $\Lambda \to \mathbb{Z}$ будет нулевым, следовательно, полученные специализацией векторы линейно зависимы над $\mathbb{Z}$. По следствию 1 группа $G$ не вложима в $F$.
Теорема доказана.
Пример 1. Пусть $\Gamma$ – граф с множеством вершин $X=\{x_1, x_2, x_3, x_4\}$ и множеством ребер $E=\{\{x_1, x_2\}, \{x_2, x_3\}, \{x_3,x_4\}\}$, $F=F(\Gamma; \mathfrak{N}_2)$ – частично коммутативная нильпотентная группа ступени $2$. Мальцевскую базу в ней составляют элементы $x_1, x_2, x_3, x_4, [x_3, x_1], [x_4, x_1], [x_4, x_2]$ (это было замечено еще в работе [3]). В группе $N_{4,2}$ имеется $6$ базисных коммутаторов веса $2$, поэтому она не вложима в $F$. В группе $N_{3,2}$ множество базисных коммутаторов веса $2$ состоит из $3$ элементов. Используем алгоритм теоремы 2 для нахождения образа ее базы в $F$. Вычисляем матрицы $M_1$ и $M_2$ находим в них ненулевые максимальные миноры и соответствующую специализацию. Мы пропускаем элементарные вычисления, указывая только конечный результат – элементы $g_1=x_1$, $g_2=x_2x_3$, $g_3= x_4$, порождающие свободную нильпотентную группу $N_{3,2}$. Эти элементы очевидно независимы по модулю $F'$, а коммутаторы от них $[g_2,g_1]=[x_3, x_1]$, $[g_3, x_1]=[x_4, x_1]$, $[g_3, g_2]=[x_4, x_2]$ линейно независимы в $F'$. Так как группа $F$ метабелева, указанное вложение верно также для многообразия $\mathfrak{N}_2\cap \mathfrak{A}^2$.
Заметим, что если взять группу $\widetilde{F}=F(\Gamma, \mathfrak{N}_3\cap \mathfrak{A}^2)$, то группа $N_{3,3}$ в нее не вложима, так как в ней $6$ базисных коммутаторов веса $3$, а в группе $\widetilde{F}$ их всего $2$: $[4, 1, 2]$ и $[4,1,3]$ (см. [4]).
5. Открытые вопросы
Проблема 1. a) Существует ли алгоритм, определяющий по двум заданиям конечно порожденных частично коммутативных групп многообразия $\mathfrak{N}_k$, вложима ли одна в другую?
b) Тот же вопрос для групп многообразия $\mathfrak{N}_k\cap \mathfrak{A}^2$.
Проблема 2. a) Существует ли алгоритм, определяющий по двум заданиям конечно порожденных нильпотентных групп одной ступени, вложима ли одна в другую?
b) Тот же вопрос без ограничения на ступени.
Благодарности. Автор признателен Е. И. Тимошенко за полезные консультации.
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
1.
R. Charney, “An introduction to right-angled Artin groups”, Geom. Dedicata, 125 (2007), 141–158
2.
A. J Duncan, V. N. Remeslennikov, A. V. Treier, “A survey of Free Partially Commutative Groups”, J. Phys.: Conf. Ser., 1441 (2020), 012136
3.
C. Droms, “Isomorphisms of graph groups”, Proc. Amer. Math. Soc., 100:3 (1987), 407–408
4.
Е. И. Тимошенко, “Мальцевская база частично коммутативной нильпотентной метабелевой группы”, Алгебра и логика, 50:5 (2011), 647–658
5.
E. I. Timoshenko, “Mal'tsev bases for partially commutative nilpotent groups”, Internat. J. Algebra Comput., 32:1 (2022), 1–9
6.
В. А. Романьков, “Об уравнениях в свободных метабелевых группах”, Сиб. матем. журн., 20:3 (1979), 671–673
7.
В. А. Романьков, “О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и свободных кольцах”, Алгебра и логика, 16:4 (1977), 457–471
8.
В. А. Романьков, “Неразрешимость проблемы вхождения в подмоноид свободной нильпотентной группы ступени $l\geq 2$ достаточно большого ранга”, Изв. РАН. Сер. матем., 87:4 (2023), 166–185
9.
А. И. Мальцев, “Два замечания о нильпотентных группах”, Матем. сб., 37(79):3 (1955), 567–572
10.
G. Baumslag, “Some subgroup theorems for free $\mathfrak{b}$-groups”, Trans. Amer. Math. Soc., 108 (1963), 516–525
11.
М. И. Каргаполов, Ю. И. Мерзляков, Основы теории групп, Наука, 1972
12.
Ph. Hall, The Edmonton Notes on Nilpotent Groups (University of Alberta, 1957), Queen Mary College, London, 1969
Образец цитирования:
В. А. Романьков, “Вложение свободных нильпотентных (метабелевых) групп в частично коммутативные нильпотентные (метабелевы) группы”, Матем. заметки, 114:5 (2023), 773–779; Math. Notes, 114:5 (2023), 914–919