Алгоритм генерации P-группы

В математике, особенно в теории групп , конечные группы простого степенного порядка. $p^{n}$, для фиксированного простого числа $p$ и различные целые показатели $n\geq 0$кратко называются конечными p-группами .

Алгоритм p генерации -групп М.Ф. Ньюмана и Э.А. О'Брайен это рекурсивный процесс построения дерева потомков заданной конечной p -группы, взятой за корень дерева.

Нижний показатель степени p - центральный ряд

Для конечной p -группы $G$, нижний показатель - p центральный ряд (кратко нижний p -центральный ряд ) $G$это нисходящий ряд $(P_{j}(G))_{j\geq 0}$ характерных подгрупп $G$,определяется рекурсивно

$(1)\qquad P_{0}(G):=G$ и $P_{j}(G):=\lbrack P_{j-1}(G),G\rbrack \cdot P_{j-1}(G)^{p}$, для $j\geq 1$.

Поскольку любая нетривиальная конечная p -группа $G>1$ является нильпотентным,существует целое число $c\geq 1$ такой, что $P_{c-1}(G)>P_{c}(G)=1$и $\mathrm {cl} _{p}(G):=c$ называется экспоненты -p классом (кратко p -классом ) $G$.Только тривиальная группа $1$ имеет $\mathrm {cl} _{p}(1)=0$.Вообще говоря, для любой конечной p -группы $G$,его p -класс можно определить как $\mathrm {cl} _{p}(G):=\min \lbrace c\geq 0\mid P_{c}(G)=1\rbrace$.

Полная нижняя p -центральная серия $G$ поэтому дается

$(2)\qquad G=P_{0}(G)>\Phi (G)=P_{1}(G)>P_{2}(G)>\cdots >P_{c-1}(G)>P_{c}(G)=1$,

с $P_{1}(G)=\lbrack P_{0}(G),G\rbrack \cdot P_{0}(G)^{p}=\lbrack G,G\rbrack \cdot G^{p}=\Phi (G)$ является Фраттини подгруппой $G$.

Для удобства читателя и указания на сдвинутую нумерацию напомним, что(обычный) нижний центральный ряд $G$ это тоже нисходящий ряд $(\gamma _{j}(G))_{j\geq 1}$ характерных подгрупп $G$,определяется рекурсивно

$(3)\qquad \gamma _{1}(G):=G$ и $\gamma _{j}(G):=\lbrack \gamma _{j-1}(G),G\rbrack$, для $j\geq 2$.

Как и выше, для любой нетривиальной конечной p -группы $G>1$,существует целое число $c\geq 1$ такой, что $\gamma _{c}(G)>\gamma _{c+1}(G)=1$и $\mathrm {cl} (G):=c$ называется нильпотентности классом $G$,тогда как $c+1$ называется нильпотентности показателем $G$.Только тривиальная группа $1$ имеет $\mathrm {cl} (1)=0$.

Полный нижний центральный ряд $G$ дается

$(4)\qquad G=\gamma _{1}(G)>G^{\prime }=\gamma _{2}(G)>\gamma _{3}(G)>\cdots >\gamma _{c}(G)>\gamma _{c+1}(G)=1$,

с $\gamma _{2}(G)=\lbrack \gamma _{1}(G),G\rbrack =\lbrack G,G\rbrack =G^{\prime }$ является подгруппой коммутатора или производной подгруппой группы $G$.

следующие правила следует помнить Для класса экспоненты :

Позволять $G$ — конечная p -группа.

Р

1. Правило: $\mathrm {cl} (G)\leq \mathrm {cl} _{p}(G)$, поскольку $\gamma _{j}(G)$ спускаться быстрее, чем $P_{j}(G)$.
2. Правило: если $\vartheta \in \mathrm {Hom} (G,{\tilde {G}})$, для некоторой группы ${\tilde {G}}$, затем $\vartheta (P_{j}(G))=P_{j}(\vartheta (G))$, для любого $j\geq 0$.
3. Правило: для любого $c\geq 0$, условия $N\triangleleft G$ и $\mathrm {cl} _{p}(G/N)=c$ подразумевать $P_{c}(G)\leq N$.
4. Правило: Пусть $c\geq 0$. Если $\mathrm {cl} _{p}(G)=c$, затем $\mathrm {cl} _{p}(G/P_{k}(G))=\min(k,c)$, для всех $k\geq 0$, в частности, $\mathrm {cl} _{p}(G/P_{k}(G))=k$, для всех $0\leq k\leq c$.

Родители и потомки деревьев

Родитель ​ $\pi (G)$ конечной нетривиальной p -группы $G>1$ с показателем степени p класса $\mathrm {cl} _{p}(G)=c\geq 1$определяется как частное $\pi (G):=G/P_{c-1}(G)$ из $G$ по последнему нетривиальному члену $P_{c-1}(G)>1$ нижнего показателя - p центрального ряда $G$.И наоборот, в этом случае $G$ называется непосредственным потомком $\pi (G)$.p -классы родителя и непосредственного потомка связаны $\mathrm {cl} _{p}(G)=\mathrm {cl} _{p}(\pi (G))+1$.

Дерево потомков представляет собой иерархическую структуру. для визуализации отношений родитель-потомокмежду классами изоморфизма конечных p -групп.Вершины - дерева потомка являются классами изоморфизма конечных p -групп.Однако вершина всегда будет помечена путем выбора представителя соответствующего класса изоморфизма.Всякий раз, когда вершина $\pi (G)$ является родителем вершины $G$ дерева направленное ребро -потомка определяется выражением $G\to \pi (G)$в направлении канонической проекции $\pi :G\to \pi (G)$ на частное $\pi (G)=G/P_{c-1}(G)$.

понятия родителей и непосредственных потомков В дереве потомков можно обобщить .Вершина $R$ является потомком вершины $P$,и $P$ является предком ​ $R$,если либо $R$ равно $P$или есть путь

$(5)\qquad R=Q_{0}\to Q_{1}\to \cdots \to Q_{m-1}\to Q_{m}=P$, где $m\geq 1$,

направленных ребер из $R$ к $P$.Вершины, образующие путь, обязательно совпадают с итерированными родителями. $Q_{j}=\pi ^{j}(R)$ из $R$, с $0\leq j\leq m$:

$(6)\qquad R=\pi ^{0}(R)\to \pi ^{1}(R)\to \cdots \to \pi ^{m-1}(R)\to \pi ^{m}(R)=P$, где $m\geq 1$.

Их также можно рассматривать как последовательные частные $Q_{j}=R/P_{c-j}(R)$ p-класса $c-j$ из $R$когда p -класс $R$ дается $\mathrm {cl} _{p}(R)=c\geq m$:

$(7)\qquad R\simeq R/P_{c}(R)\to R/P_{c-1}(R)\to \cdots \to R/P_{c+1-m}(R)\to R/P_{c-m}(R)\simeq P$, где $c\geq m\geq 1$.

В частности, каждая нетривиальная конечная p -группа $G>1$ определяет максимальный путь (состоящий из $c=\mathrm {cl} _{p}(G)$ края)

$(8)\qquad G\simeq G/1=G/P_{c}(G)\to \pi (G)=G/P_{c-1}(G)\to \pi ^{2}(G)=G/P_{c-2}(G)\to \cdots$

$\cdots \to \pi ^{c-1}(G)=G/P_{1}(G)\to \pi ^{c}(G)=G/P_{0}(G)=G/G\simeq 1$

заканчивающийся в тривиальной группе $\pi ^{c}(G)=1$.Предпоследнее частное максимального пути $G$ — элементарная абелева p -группа $\pi ^{c-1}(G)=G/P_{1}(G)\simeq C_{p}^{d}$ ранга $d=d(G)$,где $d(G)=\dim _{\mathbb {F} _{p}}(H^{1}(G,\mathbb {F} _{p}))$ обозначает ранг генератора $G$.

Обычно дерево-потомок ${\mathcal {T}}(G)$ вершины $G$ является поддеревом всех потомков $G$, начиная с корня $G$.Максимально возможное дерево потомков ${\mathcal {T}}(1)$ тривиальной группы $1$ содержит все конечные p -группы и является исключительным,поскольку тривиальная группа $1$ имеет все бесконечное число элементарных абелевых p -групп с меняющимся рангом образующего $d\geq 1$ как его непосредственные потомки.Однако любая нетривиальная конечная p -группа (порядка, кратного $p$) имеет лишь конечное число непосредственных потомков.

p -покрывающая группа, p -мультипликатор и ядро

Позволять $G$ — конечная p -группа с $d$ генераторы .Наша цель — составить полный список попарно неизоморфных непосредственных потомков $G$.Оказывается, всех непосредственных потомков можно получить как частное определенного расширения. $G^{\ast }$ из $G$которая называется p- накрывающей группой $G$ и может быть построен следующим образом.

Мы обязательно презентацию найдем $G$ в виде точной последовательности

$(9)\qquad 1\longrightarrow R\longrightarrow F\longrightarrow G\longrightarrow 1$,

где $F$ обозначает свободную группу с $d$ генераторы и $\vartheta :\ F\longrightarrow G$ является эпиморфизмом с ядром $R:=\ker(\vartheta )$.Затем $R\triangleleft F$ является нормальной подгруппой $F$ состоящее из определяющих соотношений для $G\simeq F/R$.Для элементов $r\in R$ и $f\in F$,сопряженное $f^{-1}rf\in R$ и, следовательно, также коммутатор $\lbrack r,f\rbrack =r^{-1}f^{-1}rf\in R$ содержатся в $R$.Следовательно, $R^{\ast }:=\lbrack R,F\rbrack \cdot R^{p}$ является характерной подгруппой $R$,и p -мультипликатор $R/R^{\ast }$ из $G$ является элементарной абелевой p -группой, поскольку

$(10)\qquad \lbrack R,R\rbrack \cdot R^{p}\leq \lbrack R,F\rbrack \cdot R^{p}=R^{\ast }$.

Теперь мы можем определить p -накрывающую группу $G$ к

$(11)\qquad G^{\ast }:=F/R^{\ast }$,

и точная последовательность

$(12)\qquad 1\longrightarrow R/R^{\ast }\longrightarrow F/R^{\ast }\longrightarrow F/R\longrightarrow 1$

показывает, что $G^{\ast }$ является продолжением $G$ элементарным абелевым p -мультипликатором.Мы звоним

$(13)\qquad \mu (G):=\dim _{\mathbb {F} _{p}}(R/R^{\ast })$

ранг p - множителя $G$.

Предположим теперь, что назначенная конечная p -группа $G\simeq F/R$ имеет p -класс $\mathrm {cl} _{p}(G)=c$.Тогда условия $R\triangleleft F$ и $\mathrm {cl} _{p}(F/R)=c$ подразумевать $P_{c}(F)\leq R$, согласно правилу (R3),и мы можем ядро определить $G$ к

$(14)\qquad P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }\leq R/R^{\ast }$

как подгруппа p -мультипликатора.Следовательно, ядерный ранг

$(15)\qquad \nu (G):=\dim _{\mathbb {F} _{p}}(P_{c}(G^{\ast }))\leq \mu (G)$

из $G$ ограничен сверху рангом p -мультипликатора.

Допустимые подгруппы p -мультипликатора

Как и раньше, пусть $G$ — конечная p -группа с $d$ генераторы .

Предложение. Любое p -элементарное абелево центральное расширение

$(16)\qquad 1\to Z\to H\to G\to 1$

из $G$ подгруппой p -элементарной абелевой $Z\leq \zeta _{1}(H)$ такой, что $d(H)=d(G)=d$является фактором p -накрывающей группы $G^{\ast }$ из $G$.

Для доказательства нажмите «Показать» справа.

показывать

Доказательство

The reason is that, since $d(H)=d(G)=d$, there exists an epimorphism $\psi :\ F\to H$ such that$\vartheta =\omega \circ \psi$, where $\omega :\ H\to H/Z\simeq G$ denotes the canonical projection.Consequently, we have

$R=\ker(\vartheta )=\ker(\omega \circ \psi )=(\omega \circ \psi )^{-1}(1)=\psi ^{-1}(\omega ^{-1}(1))=\psi ^{-1}(Z)$

and thus $\psi (R)=\psi (\psi ^{-1}(Z))=Z$.Further, $\psi (R^{p})=Z^{p}=1$, since $Z$ is p-elementary,and $\psi (\lbrack R,F\rbrack )=\lbrack Z,H\rbrack =1$, since $Z$ is central.Together this shows that $\psi (R^{\ast })=\psi (\lbrack R,F\rbrack \cdot R^{p})=1$and thus $\psi$ induces the desired epimorphism $\psi ^{\ast }:\ G^{\ast }\to H$such that $H\simeq G^{\ast }/\ker(\psi ^{\ast })$.

В частности, прямой потомок $H$ из $G$ является p -элементарным абелевым центральным расширением

$(17)\qquad 1\to P_{c-1}(H)\to H\to G\to 1$

из $G$,с

$1=P_{c}(H)=\lbrack P_{c-1}(H),H\rbrack \cdot P_{c-1}(H)^{p}$ подразумевает $P_{c-1}(H)^{p}=1$ и $P_{c-1}(H)\leq \zeta _{1}(H)$,

где $c=\mathrm {cl} _{p}(H)$.

Определение. Подгруппа $M/R^{\ast }\leq R/R^{\ast }$ мультипликатора p - $G$ называется допустимым если это задано ядром $M/R^{\ast }=\ker(\psi ^{\ast })$ эпиморфизма $\psi ^{\ast }:\ G^{\ast }\to H$на непосредственного потомка $H$ из $G$.

Эквивалентная характеристика состоит в том, что $1<M/R^{\ast }<R/R^{\ast }$ является собственной подгруппой, дополняющей ядро

$(18)\qquad (M/R^{\ast })\cdot (P_{c}(F)\cdot R^{\ast }/R^{\ast })=R/R^{\ast }$.

Поэтому первая часть нашей цели — составить список всех непосредственных потомков $G$ сделано,когда мы построили все допустимые подгруппы $R/R^{\ast }$ которые дополняют ядро $P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }$,где $c=\mathrm {cl} _{p}(G)$.Однако в целом список

$(19)\qquad \lbrace F/M\quad \mid \quad M/R^{\ast }\leq R/R^{\ast }{\text{ is allowable }}\rbrace$,

где $G^{\ast }/(M/R^{\ast })=(F/R^{\ast })/(M/R^{\ast })\simeq F/M$,будет лишним,из-за изоморфизмов $F/M_{1}\simeq F/M_{2}$ среди ближайших потомков.

Орбиты при расширенных автоморфизмах

Две допустимые подгруппы $M_{1}/R^{\ast }$ и $M_{2}/R^{\ast }$ называются эквивалентными, если факторы $F/M_{1}\simeq F/M_{2}$,которые являются соответствующими непосредственными потомками $G$, изоморфны.

Такой изоморфизм $\varphi :\ F/M_{1}\to F/M_{2}$ между непосредственными потомками $G=F/R$ с $c=\mathrm {cl} _{p}(G)$ имеет свойство, которое $\varphi (R/M_{1})=\varphi (P_{c}(F/M_{1}))=P_{c}(\varphi (F/M_{1}))=P_{c}(F/M_{2})=R/M_{2}$и, таким образом, индуцирует автоморфизм $\alpha \in \mathrm {Aut} (G)$ из $G$который можно продолжить до автоморфизма $\alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })$ - накрывающей p группы $G^{\ast }=F/R^{\ast }$из $G$.Ограничение этого расширенного автоморфизма $\alpha ^{\ast }$ к p -мультипликатору $R/R^{\ast }$ из $G$ определяется однозначно $\alpha$.

С $\alpha ^{\ast }(M/R^{\ast })\cdot P_{c}(F/R^{\ast })=\alpha ^{\ast }\lbrack M/R^{\ast }\cdot P_{c}(F/R^{\ast })\rbrack =\alpha ^{\ast }(R/R^{\ast })=R/R^{\ast }$,каждый расширенный автоморфизм $\alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })$ вызывает перестановку $\alpha ^{\prime }$ из допустимых подгрупп $M/R^{\ast }\leq R/R^{\ast }$.Мы определяем $P:=\langle \alpha ^{\prime }\mid \alpha \in \mathrm {Aut} (G)\rangle$ быть группой перестановок, порожденной всеми перестановками, индуцированными автоморфизмами $G$.Тогда карта $\mathrm {Aut} (G)\to P$, $\alpha \mapsto \alpha ^{\prime }$ является эпиморфизмоми классы эквивалентности допустимых подгрупп $M/R^{\ast }\leq R/R^{\ast }$ являются в точности орбитами допустимых подгрупп под действием группы подстановок $P$.

В конечном итоге наша цель — составить список $\lbrace F/M_{i}\mid 1\leq i\leq N\rbrace$ всех прямых потомков $G$ будет сделано,когда мы выбираем представителя $M_{i}/R^{\ast }$ для каждого из $N$ орбиты допустимых подгрупп $R/R^{\ast }$ под действием $P$. Именно это и p делает алгоритм генерации -группы за один шаг рекурсивной процедуры построения дерева-потомка назначенного корня.

Возможные p -группы и размеры шага

Конечная p -группа $G$ называется способным (или расширяемым ), если он имеет хотя бы одного непосредственного потомка, в противном случае он является терминальным (или листовым ). Ядерный ранг $\nu (G)$ из $G$ принимает решение о возможности $G$:

• $G$ является терминальным тогда и только тогда, когда $\nu (G)=0$.
• $G$ способен тогда и только тогда, когда $\nu (G)\geq 1$.

В случае возможностей, $G=F/R$ имеет прямых потомков $\nu =\nu (G)$ разные размеры шага $1\leq s\leq \nu$, в зависимости от индекса $(R/R^{\ast }:M/R^{\ast })=p^{s}$ соответствующей допустимой подгруппы $M/R^{\ast }$ в p -множителе $R/R^{\ast }$. Когда $G$ в порядке $\vert G\vert =p^{n}$, то непосредственный потомок размера шага $s$ в порядке $\#(F/M)=(F/R^{\ast }:M/R^{\ast })=(F/R^{\ast }:R/R^{\ast })\cdot (R/R^{\ast }:M/R^{\ast })$ $=\#(F/R)\cdot p^{s}=\vert G\vert \cdot p^{s}=p^{n}\cdot p^{s}=p^{n+s}$.

О связанном явлении мультифуркации дерева-потомка в вершине $G$ с ядерным рангом $\nu (G)\geq 2$ см. статью о деревьях-потомках .

Алгоритм p генерации -группы обеспечивает гибкость, позволяющую ограничить построение непосредственных потомков до тех, которые имеют один фиксированный размер шага. $1\leq s\leq \nu$, что очень удобно в случае огромных чисел потомков (см. следующий раздел).

Число непосредственных потомков

Обозначим число всех непосредственных потомков , соотв. непосредственные потомки размера шага $s$, из $G$ к $N$, соотв. $N_{s}$. Тогда у нас есть $N=\sum _{s=1}^{\nu }\,N_{s}$.В качестве конкретных примеров приведем некоторые интересные конечные метабелевы p -группы с обширными наборами непосредственных потомков, используя идентификаторы SmallGroups и дополнительно указывая числа $0\leq C_{s}\leq N_{s}$ дееспособных непосредственных потомков в обычном формате $(N_{1}/C_{1};\ldots ;N_{\nu }/C_{\nu })$ как указано в реальных реализациях p алгоритма генерации -группы в системах компьютерной алгебры GAP и MAGMA.

Во-первых, пусть $p=3$.

Начнем с групп, имеющих абелианизацию типа $(3,3)$.См. рисунок 4 в статье о деревьях-потомках .

• Группа $\langle 27,3\rangle$ одноклассника $1$ имеет звания $\nu =2$, $\mu =4$ и числа потомков $(4/1;7/5)$, $N=11$.
• Группа $\langle 243,3\rangle =\langle 27,3\rangle -\#2;1$ одноклассника $2$ имеет звания $\nu =2$, $\mu =4$ и числа потомков $(10/6;15/15)$, $N=25$.
• Один из ее непосредственных потомков, группа $\langle 729,40\rangle =\langle 243,3\rangle -\#1;7$, имеет звания $\nu =2$, $\mu =5$ и числа потомков $(16/2;27/4)$, $N=43$.

Напротив, группы с абелианизацией типа $(3,3,3)$ частично находятся за пределом вычислимости.

• Группа $\langle 81,12\rangle$ одноклассника $2$ имеет звания $\nu =2$, $\mu =7$ и числа потомков $(10/2;100/50)$, $N=110$.
• Группа $\langle 243,37\rangle$ одноклассника $3$ имеет звания $\nu =5$, $\mu =9$ и числа потомков $(35/3;2783/186;81711/10202;350652/202266;\ldots )$, $N>4\cdot 10^{5}$ неизвестный.
• Группа $\langle 729,122\rangle$ одноклассника $4$ имеет звания $\nu =8$, $\mu =11$ и числа потомков $(45/3;117919/1377;\ldots )$, $N>10^{5}$ неизвестный.

Дальше пусть $p=5$.

Соответствующие группы с абелианизацией типа $(5,5)$ иметь большее число потомков, чем для $p=3$.

• Группа $\langle 125,3\rangle$ одноклассника $1$ имеет звания $\nu =2$, $\mu =4$ и числа потомков $(4/1;12/6)$, $N=16$.
• Группа $\langle 3125,3\rangle =\langle 125,3\rangle -\#2;1$ одноклассника $2$ имеет звания $\nu =3$, $\mu =5$ и числа потомков $(8/3;61/61;47/47)$, $N=116$.

Множитель Шура

Через изоморфизм $\mathbb {Q} /\mathbb {Z} \to \mu _{\infty }$, ${\frac {n}{d}}\mapsto \exp \left({\frac {n}{d}}\cdot 2\pi i\right)$факторгруппа $\mathbb {Q} /\mathbb {Z} =\left\lbrace {\frac {n}{d}}\cdot \mathbb {Z} \mid d\geq 1,\ 0\leq n\leq d-1\right\rbrace$можно рассматривать как аддитивный аналог мультипликативной группы $\mu _{\infty }=\lbrace z\in \mathbb {C} \mid z^{d}=1{\text{ for some integer }}d\geq 1\rbrace$ всех корней единства .

Позволять $p$ быть простым числом и $G$ — конечная p -группа с представлением $G=F/R$ как в предыдущем разделе.Тогда вторая группа когомологий $M(G):=H^{2}(G,\mathbb {Q} /\mathbb {Z} )$ принадлежащий $G$-модуль $\mathbb {Q} /\mathbb {Z}$называется Шура множителем $G$. Ее также можно интерпретировать как факторгруппу $M(G)=(R\cap \lbrack F,F\rbrack )/\lbrack F,R\rbrack$.

И.Р. Шафаревич доказал, что разница между рангом отношения $r(G)=\dim _{\mathbb {F} _{p}}(H^{2}(G,\mathbb {F} _{p}))$ из $G$и ранг генератора $d(G)=\dim _{\mathbb {F} _{p}}(H^{1}(G,\mathbb {F} _{p}))$ из $G$ задаётся минимальным числом образующих множителя Шура $G$,то есть $r(G)-d(G)=d(M(G))$.

Н. Бостон и Х. Новер показали, что $\mu (G_{j})-\nu (G_{j})\leq r(G)$,для всех частных $G_{j}:=G/P_{j}(G)$ класса p - $\mathrm {cl} _{p}(G_{j})=j$, $j\geq 0$,про -п -группы $G$ с конечной абелианизацией $G/G^{\prime }$.

Кроме того, Дж. Блэкхерст (в приложении « О ядре некоторых p-групп» статьи Н. Бостона, М. Р. Буша и Ф. Хаджира) )доказал, что нециклическая конечная p -группа $G$ с тривиальным множителем Шура $M(G)$является конечной вершиной в дереве потомков ${\mathcal {T}}(1)$ тривиальной группы $1$,то есть, $M(G)=1$ $\Rightarrow$ $\nu (G)=0$.

Примеры

• Конечная p -группа $G$ имеет сбалансированную презентацию $r(G)=d(G)$ тогда и только тогда, когда $r(G)-d(G)=0=d(M(G))$, то есть тогда и только тогда, когда его множитель Шура $M(G)=1$ тривиально. Такая группа называется группой Шура и должна быть листом дерева-потомка. ${\mathcal {T}}(1)$.
• Конечная p -группа $G$ удовлетворяет $r(G)=d(G)+1$ тогда и только тогда, когда $r(G)-d(G)=1=d(M(G))$, то есть тогда и только тогда, когда он имеет нетривиальный циклический множитель Шура $M(G)$. Такая группа называется группой Шура+1 .