Der ${\displaystyle p}$-Gruppen-Erzeugungs-Algorithmus von M. F. Newman und E. A. O'Brien ist innerhalb der algorithmischen Gruppentheorie ein rekursiver Prozess für die Konstruktion des Stammbaums einer vorgegebenen endlichen ${\displaystyle p}$-Gruppe, die als Wurzel des Baums dient.

Dabei sind endliche ${\displaystyle p}$-Gruppen endliche Gruppen mit Primpotenz-Ordnung ${\displaystyle p^{n}}$, für eine feste Primzahl ${\displaystyle p}$ und veränderliche ganzzahlige Exponenten ${\displaystyle n\geq 1}$.

Dieser Algorithmus ist im Softwarepaket ANUPQ (Australian National University P-Quotient) der Computer-Algebra-Systeme GAP (Groups-Algorithms-Programming) und Magma implementiert. Er ist unentbehrlich für die vertiefte Erforschung von endlichen ${\displaystyle p}$-Gruppen, weil die SmallGroups Datenbank von H. U. Besche, B. Eick and E. A. O'Brien für jede Primzahl ${\displaystyle p}$ nur ${\displaystyle p}$-Gruppen mit Ordnungen bis zu einer von ${\displaystyle p}$ abhängigen oberen Schranke ${\displaystyle m(p)}$ enthält, beispielsweise ${\displaystyle m(2)=2^{9}=512}$ für ${\displaystyle p=2}$, ${\displaystyle m(3)=3^{8}=6561}$ für ${\displaystyle p=3}$ und ${\displaystyle m(5)=5^{7}=78125}$ für ${\displaystyle p=5}$. Alle ${\displaystyle p}$-Gruppen mit höherer Ordnung als ${\displaystyle m(p)}$ müssen mit dem sehr leistungsfähigen und schnellen ${\displaystyle p}$-Gruppen-Erzeugungs-Algorithmus konstruiert werden, wobei für kleine Primzahlen ${\displaystyle p=2,3}$ durchaus noch Ordnungen um ${\displaystyle p^{100}}$ innerhalb der experimentellen Reichweite liegen.

Untere Exponent-p-Zentralreihe

Für eine endliche ${\displaystyle p}$-Gruppe ${\displaystyle G}$ ist die untere Exponent-${\displaystyle p}$-Zentralreihe (kurz untere ${\displaystyle p}$-Zentralreihe) von ${\displaystyle G}$ eine absteigende Reihe ${\displaystyle (P_{j}(G))_{j\geq 0}}$ charakteristischer Untergruppen von ${\displaystyle G}$ und wird rekursiv erklärt durch

${\displaystyle (1)\qquad P_{0}(G):=G}$ und ${\displaystyle P_{j}(G):=\lbrack P_{j-1}(G),G\rbrack \cdot P_{j-1}(G)^{p}}$, für ${\displaystyle j\geq 1}$.

Weil jede nicht-triviale endliche ${\displaystyle p}$-Gruppe ${\displaystyle G>1}$ nilpotent ist, gibt es eine ganze Zahl ${\displaystyle c\geq 1}$, sodass der ${\displaystyle c}$-Term der Reihe, ${\displaystyle P_{c-1}(G)>P_{c}(G)=1}$, erstmals trivial wird, und diese Zahl ${\displaystyle \mathrm {cl} _{p}(G):=c}$ wird als Exponent-${\displaystyle p}$-Klasse (kurz ${\displaystyle p}$-Klasse) von ${\displaystyle G}$ bezeichnet. Nur die triviale Gruppe ${\displaystyle 1}$ hat die ${\displaystyle p}$-Klasse ${\displaystyle \mathrm {cl} _{p}(1)=0}$. Generell kann für eine endliche ${\displaystyle p}$-Gruppe ${\displaystyle G}$ ihre ${\displaystyle p}$-Klasse als das Minimum ${\displaystyle \mathrm {cl} _{p}(G):=\min \lbrace c\geq 0\mid P_{c}(G)=1\rbrace }$ definiert werden.

Die vollständige untere ${\displaystyle p}$-Zentralreihe von ${\displaystyle G}$ ist daher gegeben durch

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

weil ${\displaystyle P_{1}(G)=\lbrack P_{0}(G),G\rbrack \cdot P_{0}(G)^{p}=\lbrack G,G\rbrack \cdot G^{p}=\Phi (G)}$ die Frattini Untergruppe von ${\displaystyle G}$ ist.

Zum Vergleich und vor allem, um die verschobene Nummerierung hervorzuheben, sei erwähnt, dass die (gewöhnliche) untere Zentralreihe von ${\displaystyle G}$ ebenfalls eine absteigende Reihe ${\displaystyle (\gamma _{j}(G))_{j\geq 1}}$ charakteristischer Untergruppen von ${\displaystyle G}$ ist und rekursiv definiert wird durch

${\displaystyle (3)\qquad \gamma _{1}(G):=G}$ und ${\displaystyle \gamma _{j}(G):=\lbrack \gamma _{j-1}(G),G\rbrack }$, für ${\displaystyle j\geq 2}$.

Analog wie oben existiert zu jeder nicht-trivialen endlichen ${\displaystyle p}$-Gruppe ${\displaystyle G>1}$ eine ganze Zahl ${\displaystyle c\geq 1}$ sodass der ${\displaystyle (c+1)}$-Term der Reihe, ${\displaystyle \gamma _{c}(G)>\gamma _{c+1}(G)=1}$, erstmals trivial wird, und diese Zahl ${\displaystyle \mathrm {cl} (G):=c}$ wird die Nilpotenzklasse (kurz Klasse) von ${\displaystyle G}$ genannt, während ${\displaystyle c+1}$ als Index der Nilpotenz von ${\displaystyle G}$ bezeichnet wird. Die triviale Gruppe ${\displaystyle 1}$ hat als einzige den Nilpotenzindex ${\displaystyle 1}$ und somit die Klasse ${\displaystyle \mathrm {cl} (1)=0}$.

Die untere Zentralreihe von ${\displaystyle G}$ ist in ihrer Gesamtheit gegeben durch

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

weil ${\displaystyle \gamma _{2}(G)=\lbrack \gamma _{1}(G),G\rbrack =\lbrack G,G\rbrack =G^{\prime }}$ die Kommutatoruntergruppe oder abgeleitete Untergruppe von ${\displaystyle G}$ ist.

Die folgenden vier Rechenregeln sind für das Arbeiten mit der Exponent-${\displaystyle p}$ Klasse nützlich:

Es sei ${\displaystyle G}$ eine endliche ${\displaystyle p}$-Gruppe.

R

1. Regel: ${\displaystyle \mathrm {cl} (G)\leq \mathrm {cl} _{p}(G)}$, weil die Terme ${\displaystyle \gamma _{j}(G)}$ rascher absteigen als die ${\displaystyle P_{j}(G)}$ (R1).
2. Regel: Ist ${\displaystyle \vartheta \in \mathrm {Hom} (G,{\tilde {G}})}$, mit irgendeiner Gruppe ${\displaystyle {\tilde {G}}}$, dann gilt ${\displaystyle \vartheta (P_{j}(G))=P_{j}(\vartheta (G))}$, für alle ${\displaystyle j\geq 0}$ (R2).
3. Regel: Für ${\displaystyle c\geq 0}$ implizieren die Bedingungen ${\displaystyle N\triangleleft G}$ und ${\displaystyle \mathrm {cl} _{p}(G/N)=c}$, dass ${\displaystyle P_{c}(G)\leq N}$ (R3).
4. Regel: Sei ${\displaystyle c\geq 0}$. Wenn ${\displaystyle \mathrm {cl} _{p}(G)=c}$, dann ist ${\displaystyle \mathrm {cl} _{p}(G/P_{k}(G))=\min(k,c)}$, für alle ${\displaystyle k\geq 0}$, speziell, ${\displaystyle \mathrm {cl} _{p}(G/P_{k}(G))=k}$, für alle ${\displaystyle 0\leq k\leq c}$ (R4).

Vorgänger und Stammbäume

Der (unmittelbare) Vorgänger ${\displaystyle \pi (G)}$ einer endlichen nicht-trivialen ${\displaystyle p}$-Gruppe ${\displaystyle G>1}$ mit Exponent-${\displaystyle p}$-Klasse ${\displaystyle \mathrm {cl} _{p}(G)=c\geq 1}$ ist definiert als der Quotient ${\displaystyle \pi (G):=G/P_{c-1}(G)}$ von ${\displaystyle G}$ nach dem letzten nicht-trivialen Term ${\displaystyle P_{c-1}(G)>1}$ der unteren Exponent-${\displaystyle p}$-Zentralreihe von ${\displaystyle G}$. Umgekehrt wird in diesem Fall ${\displaystyle G}$ ein unmittelbarer Nachfolger von ${\displaystyle \pi (G)}$ genannt. Die ${\displaystyle p}$-Klassen von Vorgänger und unmittelbarem Nachfolger sind verbunden durch die Beziehung ${\displaystyle \mathrm {cl} _{p}(G)=\mathrm {cl} _{p}(\pi (G))+1}$.

Ein Stammbaum ist eine hierarchische Struktur zur anschaulichen Visualisierung von Vorgänger-Nachfolger Relationen zwischen Isomorphieklassen endlicher ${\displaystyle p}$-Gruppen. Die Vertices (Knoten, Ecken) eines Stammbaums sind Isomorphieklassen von endlichen ${\displaystyle p}$-Gruppen. In Baum-Diagrammen wird jedoch ein Vertex stets durch Auswahl eines konkreten Repräsentanten der entsprechenden Isomorphieklasse etikettiert. Wenn ein Vertex ${\displaystyle \pi (G)}$ der unmittelbare Vorgänger eines anderen Vertex ${\displaystyle G}$ ist, so wird eine gerichtete Kante des Stammbaums definiert durch ${\displaystyle G\to \pi (G)}$ in Richtung der kanonischen Projektion ${\displaystyle \pi :G\to \pi (G)}$ auf den Quotienten ${\displaystyle \pi (G)=G/P_{c-1}(G)}$.

In einem Stammbaum können die Begriffe unmittelbarer Vorgänger und unmittelbarer Nachfolger folgendermaßen verallgemeinert werden. Ein Vertex ${\displaystyle R}$ ist ein Nachfolger eines Vertex ${\displaystyle P}$, und umgekehrt ist ${\displaystyle P}$ ein Vorgänger von ${\displaystyle R}$, wenn entweder ${\displaystyle R}$ mit ${\displaystyle P}$ übereinstimmt oder wenn ein Pfad

${\displaystyle (5)\qquad R=Q_{0}\to Q_{1}\to \cdots \to Q_{m-1}\to Q_{m}=P}$, mit der Länge ${\displaystyle m\geq 1}$,

von gerichteten Kanten von ${\displaystyle R}$ zu ${\displaystyle P}$ existiert. Die Vertices, welche den Pfad bilden, stimmen notwendigerweise überein mit den iterierten Vorgängern ${\displaystyle Q_{j}=\pi ^{j}(R)}$ von ${\displaystyle R}$, wobei ${\displaystyle 0\leq j\leq m}$:

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

Sie können auch aufgefasst werden als die sukzessiven Quotienten ${\displaystyle Q_{j}=R/P_{c-j}(R)}$ der p-Klasse ${\displaystyle c-j}$ von ${\displaystyle R}$, wenn die p-Klasse von ${\displaystyle R}$ gegeben ist durch ${\displaystyle \mathrm {cl} _{p}(R)=c\geq m}$:

${\displaystyle (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}$, wobei ${\displaystyle c\geq m\geq 1}$.

Insbesondere definiert jede nicht-triviale endliche ${\displaystyle p}$-Gruppe ${\displaystyle G>1}$ einen maximalen Pfad, der aus ${\displaystyle c=\mathrm {cl} _{p}(G)}$ gerichteten Kanten besteht,

${\displaystyle (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 }$

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

und in der trivialen Gruppe ${\displaystyle \pi ^{c}(G)=1}$ endigt. Der vorletzte Quotient des Maximalpfades von ${\displaystyle G}$ ist die elementar-abelsche ${\displaystyle p}$-Gruppe ${\displaystyle \pi ^{c-1}(G)=G/P_{1}(G)\simeq C_{p}^{d}}$, also der Frattini-Quotient vom Rang ${\displaystyle d=d(G)}$, wobei ${\displaystyle d(G)=\dim _{\mathbb {F} _{p}}(H^{1}(G,\mathbb {F} _{p}))}$ den Generatoren-Rang (oder Erzeugenden-Rang) von ${\displaystyle G}$ bezeichnet (Basissatz von Burnside).

Generell ist der Stammbaum ${\displaystyle {\mathcal {T}}(G)}$ eines Vertex ${\displaystyle G}$ der Teilbaum aller Nachfolger von ${\displaystyle G}$, beginnend an der Wurzel ${\displaystyle G}$. Der maximal mögliche Stammbaum ${\displaystyle {\mathcal {T}}(1)}$ der trivialen Gruppe ${\displaystyle 1}$ enthält alle endlichen ${\displaystyle p}$-Gruppen und ist exzeptionell, weil die triviale Gruppe ${\displaystyle 1}$ die unendlich vielen elementar-abelschen ${\displaystyle p}$-Gruppen mit variablem Generatoren-Rang ${\displaystyle d\geq 1}$ als ihre unmittelbaren Nachfolger besitzt. Eine nicht-triviale endliche ${\displaystyle p}$-Gruppe (mit durch ${\displaystyle p}$ teilbarer Ordnung) besitzt jedoch nur endlich viele unmittelbare Nachfolger.

Einhüllende p-Gruppe, p-Multiplikator und Nucleus

Ist ${\displaystyle G}$ eine endliche ${\displaystyle p}$-Gruppe mit ${\displaystyle d}$ Erzeugenden, so möchte man in einem einzelnen Rekursionsschritt des ${\displaystyle p}$-Gruppen-Erzeugungs-Algorithmus eine vollständige Liste paarweise nicht-isomorpher unmittelbarer Nachfolger von ${\displaystyle G}$ zusammenstellen. Es stellt sich heraus, dass sich alle unmittelbaren Nachfolger konstruieren lassen als Quotienten einer gewissen Erweiterung ${\displaystyle G^{\ast }}$ von ${\displaystyle G}$, welche die einhüllende ${\displaystyle p}$-Gruppe (${\displaystyle p}$-covering group) von ${\displaystyle G}$ genannt und in folgender Weise definiert wird.

Es existiert stets eine Präsentation von ${\displaystyle G}$ in Form einer exakten Sequenz

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

wobei ${\displaystyle F}$ die freie Gruppe mit ${\displaystyle d}$ Erzeugern und ${\displaystyle \vartheta$ :\ F\longrightarrow G} einen Epimorphism mit Kern ${\displaystyle R:=\ker(\vartheta )}$ bezeichnet. Dann ist ${\displaystyle R\triangleleft F}$ ein Normalteiler von ${\displaystyle F}$, der aus den definierenden Relationen für ${\displaystyle G\simeq F/R}$ besteht. Für beliebige Elemente ${\displaystyle r\in R}$ und ${\displaystyle f\in F}$, ist das konjugierte Element ${\displaystyle f^{-1}rf\in R}$ und daher auch der Kommutator ${\displaystyle \lbrack r,f\rbrack =r^{-1}f^{-1}rf\in R}$ in ${\displaystyle R}$ enthalten. Folglich ist ${\displaystyle R^{\ast }:=\lbrack R,F\rbrack \cdot R^{p}}$ eine charakteristische Untergruppe von ${\displaystyle R}$, und der ${\displaystyle p}$-Multiplikator ${\displaystyle R/R^{\ast }}$ von ${\displaystyle G}$ ist eine elementar-abelsche ${\displaystyle p}$-Gruppe, weil

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

Nun kann die einhüllende ${\displaystyle p}$-Gruppe von ${\displaystyle G}$ definiert werden als Quotient

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

und die exakte Sequenz

${\displaystyle (12)\qquad 1\longrightarrow R/R^{\ast }\longrightarrow F/R^{\ast }=G^{\ast }\longrightarrow (F/R^{\ast })/(R/R^{\ast })\simeq F/R\simeq G\longrightarrow 1}$

zeigt, dass ${\displaystyle G^{\ast }}$ eine (Gruppen-)Erweiterung von ${\displaystyle G}$ mittels des elementar-abelschen ${\displaystyle p}$-Multiplikators ist. Man nennt

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

den ${\displaystyle p}$-Multiplikator-Rang von ${\displaystyle G}$, der mit dem Relationen-Rang ${\displaystyle r(G)=\dim _{\mathbb {F} _{p}}(H^{2}(G,\mathbb {F} _{p}))}$ von ${\displaystyle G}$ übereinstimmt.

Unter der Annahme, dass die vorgegebene endliche ${\displaystyle p}$-Gruppe ${\displaystyle G\simeq F/R}$ von der ${\displaystyle p}$-Klasse ${\displaystyle \mathrm {cl} _{p}(G)=c\geq 1}$ ist, dann implizieren die Bedingungen ${\displaystyle R\triangleleft F}$ und ${\displaystyle \mathrm {cl} _{p}(F/R)=c}$, dass ${\displaystyle P_{c}(F)\leq R}$ ist, gemäß Regel (R3), und der Nucleus von ${\displaystyle G}$ kann definiert werden durch

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

als eine (ebenfalls elementar-abelsche) Untergruppe des ${\displaystyle p}$-Multiplikators. Folglich ist der nukleare Rang

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

von ${\displaystyle G}$ durch den ${\displaystyle p}$-Multiplikator-Rang nach oben beschränkt.

Erlaubte Untergruppen des p-Multiplikators

Auch weiterhin sei ${\displaystyle G}$ eine endliche ${\displaystyle p}$-Gruppe mit ${\displaystyle d}$ Erzeugenden.

Vorbereitungssatz. Jede ${\displaystyle p}$-elementare abelsche zentrale Erweiterung

${\displaystyle (16)\qquad 1\to Z\to H\to G\to 1}$

von ${\displaystyle G}$ mit einer ${\displaystyle p}$-elementaren abelschen Untergruppe ${\displaystyle Z\leq \zeta _{1}(H)}$ sodass ${\displaystyle d(H)=d(G)=d}$ ist ein Quotient der einhüllenden ${\displaystyle p}$-Gruppe ${\displaystyle G^{\ast }}$ von ${\displaystyle G}$. (${\displaystyle \zeta _{1}(H)}$ bezeichnet das Zentrum von ${\displaystyle H}$.)

Beweis. Wegen ${\displaystyle d(H)=d(G)=d}$ existiert ein (von ${\displaystyle \vartheta$ :\ F\to G} induzierter) Epimorphismus ${\displaystyle \psi$ :\ F\to H} , sodass ${\displaystyle \vartheta =\omega \circ \psi }$, wobei ${\displaystyle \omega$ :\ H\to H/Z\simeq G} die kanonische Projektion bezeichnet. Unter Verwendung aller Voraussetzungen ergibt sich

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

und daher ${\displaystyle \psi (R)=\psi (\psi ^{-1}(Z))=Z}$. Ferner ist ${\displaystyle \psi (R^{p})=\psi (R)^{p}=Z^{p}=1}$ trivial, weil ${\displaystyle Z}$ als ${\displaystyle p}$-elementar angenommen wurde, und ${\displaystyle \psi (\lbrack R,F\rbrack )=\lbrack \psi (R),\psi (F)\rbrack =\lbrack Z,H\rbrack =1}$, weil ${\displaystyle Z}$ zentral ist. Zusammengenommen folgt ${\displaystyle \psi (R^{\ast })=\psi (\lbrack R,F\rbrack \cdot R^{p})=1}$ und somit induziert ${\displaystyle \psi }$ den gewünschten Epimorphismus ${\displaystyle \psi ^{\ast }:\ G^{\ast }\to H}$, sodass sich ${\displaystyle H\simeq G^{\ast }/\ker(\psi ^{\ast })}$ als Quotient von ${\displaystyle G^{\ast }=F/R^{\ast }}$ darstellen lässt. (Ende des Beweises.)

Insbesondere ist ein unmittelbarer Nachfolger ${\displaystyle H}$ von ${\displaystyle G}$ eine ${\displaystyle p}$-elementare abelsche zentrale Erweiterung

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

von ${\displaystyle G}$, weil aus ${\displaystyle 1=P_{c}(H)=\lbrack P_{c-1}(H),H\rbrack \cdot P_{c-1}(H)^{p}}$ folgt, dass ${\displaystyle P_{c-1}(H)^{p}=1}$ und ${\displaystyle P_{c-1}(H)\leq \zeta _{1}(H)}$, wobei ${\displaystyle c=\mathrm {cl} _{p}(H)}$.

Definition. Eine Untergruppe ${\displaystyle M/R^{\ast }\leq R/R^{\ast }}$ des ${\displaystyle p}$-Multiplikators von ${\displaystyle G}$ wird als erlaubt bezeichnet, wenn sie als Kern ${\displaystyle M/R^{\ast }=\ker(\psi ^{\ast })}$ eines Epimorphismus ${\displaystyle \psi ^{\ast }:\ G^{\ast }\to H}$ auf einen unmittelbaren Nachfolger ${\displaystyle H}$ von ${\displaystyle G}$ gegeben ist.

Eine äquivalente Charakterisierung ist, dass ${\displaystyle 1<M/R^{\ast }<R/R^{\ast }}$ eine echte Untergruppe ist, welche den Nucleus ergänzt

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

Demnach ist der erste Teil des Vorhabens, eine vollständige Liste aller unmittelbaren Nachfolger von ${\displaystyle G}$ zusammenzustellen, erledigt, wenn alle erlaubten Untergruppen von ${\displaystyle R/R^{\ast }}$ konstruiert sind, welche den Nucleus ${\displaystyle P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }}$ ergänzen, wobei ${\displaystyle c=\mathrm {cl} _{p}(G)}$. Im Allgemeinen wird aber die Liste

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

wobei ${\displaystyle G^{\ast }/(M/R^{\ast })=(F/R^{\ast })/(M/R^{\ast })\simeq F/M}$, redundant sein, infolge von gewissen Isomorphismen ${\displaystyle F/M_{1}\simeq F/M_{2}}$ zwischen den unmittelbaren Nachfolgern.

Orbits unter fortgesetzten Automorphismen

Zwei erlaubte Untergruppen ${\displaystyle M_{1}/R^{\ast }}$ und ${\displaystyle M_{2}/R^{\ast }}$ des ${\displaystyle p}$-Multiplikators ${\displaystyle R/R^{\ast }}$ von ${\displaystyle G}$ heißen äquivalent, wenn die Quotienten ${\displaystyle F/M_{1}\simeq F/M_{2}}$, also die entsprechenden unmittelbaren Nachfolger von ${\displaystyle G}$, isomorph sind.

Ein solcher Isomorphismus ${\displaystyle \varphi$ :\ F/M_{1}\to F/M_{2}} zwischen unmittelbaren Nachfolgern von ${\displaystyle G=F/R}$ mit ${\displaystyle c=\mathrm {cl} _{p}(G)}$ hat die Eigenschaft, dass ${\displaystyle \varphi (R/M_{1})=\varphi (P_{c}(F/M_{1}))=P_{c}(\varphi (F/M_{1}))=P_{c}(F/M_{2})=R/M_{2}}$. Er induziert daher einen Automorphismus ${\displaystyle \alpha \in \mathrm {Aut} (G)}$ von ${\displaystyle G}$, der fortgesetzt werden kann zu einem Automorphismus ${\displaystyle \alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })}$ der einhüllenden ${\displaystyle p}$-Gruppe ${\displaystyle G^{\ast }=F/R^{\ast }}$ von ${\displaystyle G}$. Die Einschränkung dieses fortgesetzten Automorphismus ${\displaystyle \alpha ^{\ast }}$ auf den ${\displaystyle p}$-Multiplikator ${\displaystyle R/R^{\ast }}$ von ${\displaystyle G}$ ist durch ${\displaystyle \alpha }$ eindeutig bestimmt.

Wegen der Beziehung ${\displaystyle \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 }}$ induziert jeder fortgesetzte Automorphismus ${\displaystyle \alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })}$ eine Permutation ${\displaystyle \alpha ^{\prime }}$ der erlaubten Untergruppen ${\displaystyle M/R^{\ast }\leq R/R^{\ast }}$. Man definiert ${\displaystyle P:=\langle \alpha ^{\prime }\mid \alpha \in \mathrm {Aut} (G)\rangle }$ als die Permutationsgruppe, welche von allen durch Automorphismen von ${\displaystyle G}$ induzierten Permutationen erzeugt wird. Dann ist die Abbildung ${\displaystyle \mathrm {Aut} (G)\to P}$, ${\displaystyle \alpha \mapsto \alpha ^{\prime }}$ ein Epimorphismus und die Äquivalenzklassen erlaubter Untergruppen ${\displaystyle M/R^{\ast }\leq R/R^{\ast }}$ sind genau die Orbits erlaubter Untergruppen unter der Operation der Permutationsgruppe ${\displaystyle P}$.

Letztendlich wird das Ziel, eine vollständige und irredundante Liste ${\displaystyle \lbrace F/M_{i}\mid 1\leq i\leq N\rbrace }$ aller unmittelbaren Nachfolger von ${\displaystyle G}$ zusammenzustellen, erreicht, wenn man einen Repräsentanten ${\displaystyle M_{i}/R^{\ast }}$ aus jedem der ${\displaystyle N}$ Orbits erlaubter Untergruppen des ${\displaystyle p}$-Multiplikators ${\displaystyle R/R^{\ast }}$ unter der Operation der Permutationsgruppe ${\displaystyle P}$ auswählt. Das ist genau der Prozess, welchen der ${\displaystyle p}$-Gruppen-Erzeugungs-Algorithmus in einem Einzelschritt der rekursiven Prozedur für die Konstruktion des Stammbaums einer vorgegebenen Wurzel ${\displaystyle G}$ durchführt.

Erweiterbare p-Gruppen und Schrittweite

Eine endliche ${\displaystyle p}$-Gruppe ${\displaystyle G}$ heißt erweiterbar, wenn sie zumindest einen unmittelbaren Nachfolger besitzt. Anderenfalls wird sie als terminal (oder Blatt) bezeichnet. Der nukleare Rang ${\displaystyle \nu (G)}$ von ${\displaystyle G}$ erlaubt eine Entscheidung über die Erweiterbarkeit von ${\displaystyle G}$:

• ${\displaystyle G}$ ist genau dann terminal, wenn ${\displaystyle \nu (G)=0}$.
• ${\displaystyle G}$ ist genau dann erweiterbar, wenn ${\displaystyle \nu (G)\geq 1}$.

Im Fall der Erweiterbarkeit besitzt ${\displaystyle G=F/R}$ unmittelbare Nachfolger mit ${\displaystyle \nu =\nu (G)}$ verschiedenen Schrittweiten ${\displaystyle 1\leq s\leq \nu }$, in Abhängigkeit vom Index ${\displaystyle (R/R^{\ast }:M/R^{\ast })=p^{s}}$ der entsprechenden erlaubten Untergruppen ${\displaystyle M/R^{\ast }}$ im ${\displaystyle p}$-Multiplikator ${\displaystyle R/R^{\ast }}$. Ist ${\displaystyle G}$ von der Ordnung ${\displaystyle \vert G\vert =p^{n}}$, dann hat ein unmittelbarer Nachfolger der Schrittweite ${\displaystyle s}$ die Ordnung ${\displaystyle \#(F/M)=(F/R^{\ast }:M/R^{\ast })=(F/R^{\ast }:R/R^{\ast })\cdot (R/R^{\ast }:M/R^{\ast })}$ ${\displaystyle =\#(F/R)\cdot p^{s}=\vert G\vert \cdot p^{s}=p^{n}\cdot p^{s}=p^{n+s}}$.

Für das verwandte Phänomen der Multifurkation eines Stammbaums an einem Vertex ${\displaystyle G}$ mit nuklearem Rang ${\displaystyle \nu (G)\geq 2}$ siehe den Artikel über Stammbäume.

Der ${\displaystyle p}$-Gruppen-Erzeugungs-Algorithmus bietet die Flexibilität, die Konstruktion unmittelbarer Nachfolger auf jene mit einer einzelnen festen Schrittweite ${\displaystyle 1\leq s\leq \nu }$ zu beschränken. Diese Freiheit ist sehr vorteilhaft im Fall von außergewöhnlich großen Anzahlen von Nachfolgern (siehe den nächsten Abschnitt).

Anzahl der unmittelbaren Nachfolger

Man bezeichnet die Anzahl aller unmittelbaren Nachfolger, beziehungsweise der unmittelbaren Nachfolger der Schrittweite ${\displaystyle s}$, von ${\displaystyle G}$ durch ${\displaystyle N}$, beziehungsweise ${\displaystyle N_{s}}$. Dann gilt also die Summenbeziehung ${\displaystyle N=\sum _{s=1}^{\nu }\,N_{s}}$. Es ist illustrativ, einige interessante endliche metabelsche ${\displaystyle p}$-Gruppen mit ausgedehnten Kollektionen unmittelbarer Nachfolger vorzustellen. Zur Identifikation der Gruppen verwendet man üblicherweise die SmallGroups Datenbank. Zusätzlich empfiehlt es sich, die Anzahlen ${\displaystyle 0\leq C_{s}\leq N_{s}}$ der erweiterbaren unmittelbaren Nachfolger hervorzuheben, im üblichen Format ${\displaystyle (N_{1}/C_{1};\ldots ;N_{\nu }/C_{\nu })}$, das von aktuellen Implementierungen des ${\displaystyle p}$-Gruppen-Erzeugungs-Algorithmus in den Computer-Algebra Systemen GAP und MAGMA ausgegeben wird.

Zuerst sei ${\displaystyle p=3}$.

Die einfachsten Gruppen besitzen Kommutator-Quotienten des Typs ${\displaystyle (3,3)}$. Siehe die Figur 4 im Artikel über Stammbäume.

• Die Gruppe ${\displaystyle \langle 27,3\rangle }$ mit Koklasse ${\displaystyle 1}$ hat die Ränge ${\displaystyle \nu =2}$, ${\displaystyle \mu =4}$ und Nachfolgerzahlen ${\displaystyle (4/1;7/5)}$, ${\displaystyle N=11}$.
• Die Gruppe ${\displaystyle \langle 243,3\rangle =\langle 27,3\rangle -\#2;1}$ mit Koklasse ${\displaystyle 2}$ hat die Ränge ${\displaystyle \nu =2}$, ${\displaystyle \mu =4}$ und Nachfolgerzahlen ${\displaystyle (10/6;15/15)}$, ${\displaystyle N=25}$.
• Einer ihrer unmittelbaren Nachfolger, die Gruppe ${\displaystyle \langle 729,40\rangle =\langle 243,3\rangle -\#1;7}$, hat die Ränge ${\displaystyle \nu =2}$, ${\displaystyle \mu =5}$ und Nachfolgerzahlen ${\displaystyle (16/2;27/4)}$, ${\displaystyle N=43}$.

Im Gegensatz dazu befinden sich Gruppen mit Kommutator-Quotient des Typs ${\displaystyle (3,3,3)}$ teilweise bereits jenseits des Bereichs der Berechenbarkeit.

• Die Gruppe ${\displaystyle \langle 81,12\rangle }$ mit Koklasse ${\displaystyle 2}$ hat die Ränge ${\displaystyle \nu =2}$, ${\displaystyle \mu =7}$ und Nachfolgerzahlen ${\displaystyle (10/2;100/50)}$, ${\displaystyle N=110}$.
• Die Gruppe ${\displaystyle \langle 243,37\rangle }$ mit Koklasse ${\displaystyle 3}$ hat die Ränge ${\displaystyle \nu =5}$, ${\displaystyle \mu =9}$ und Nachfolgerzahlen ${\displaystyle (35/3;2783/186;81711/10202;350652/202266;\ldots )}$, ${\displaystyle N>4\cdot 10^{5}}$ unbekannt.
• Die Gruppe ${\displaystyle \langle 729,122\rangle }$ mit Koklasse ${\displaystyle 4}$ hat die Ränge ${\displaystyle \nu =8}$, ${\displaystyle \mu =11}$ und Nachfolgerzahlen ${\displaystyle (45/3;117919/1377;\ldots )}$, ${\displaystyle N>10^{5}}$ unbekannt.

Nun sei ${\displaystyle p=5}$.

Vergleichbare Gruppen mit Kommutator-Quotient des Typs ${\displaystyle (5,5)}$ besitzen größere Anzahlen von Nachfolgern als jene mit ${\displaystyle p=3}$.

• Die Gruppe ${\displaystyle \langle 125,3\rangle }$ mit Koklasse ${\displaystyle 1}$ hat die Ränge ${\displaystyle \nu =2}$, ${\displaystyle \mu =4}$ und Nachfolgerzahlen ${\displaystyle (4/1;12/6)}$, ${\displaystyle N=16}$.
• Die Gruppe ${\displaystyle \langle 3125,3\rangle =\langle 125,3\rangle -\#2;1}$ mit Koklasse ${\displaystyle 2}$ hat die Ränge ${\displaystyle \nu =3}$, ${\displaystyle \mu =5}$ und Nachfolgerzahlen ${\displaystyle (8/3;61/61;47/47)}$, ${\displaystyle N=116}$.

Schur-Multiplikator

Vermittelt durch den Isomorphismus ${\displaystyle \mathbb {Q} /\mathbb {Z} \to \mu _{\infty }}$, ${\displaystyle {\frac {n}{d}}\mapsto \exp \left({\frac {n}{d}}\cdot 2\pi i\right)}$, kann die Quotientengruppe ${\displaystyle \mathbb {Q} /\mathbb {Z} =\left\lbrace {\frac {n}{d}}\cdot \mathbb {Z} \mid d\geq 1,\ 0\leq n\leq d-1\right\rbrace }$ als additives Analogon zur multiplikativen Gruppe ${\displaystyle \mu _{\infty }=\lbrace z\in \mathbb {C} \mid z^{d}=1{\text{ für eine ganze Zahl }}d\geq 1\rbrace }$ aller Einheitswurzeln angesehen werden.

Ist ${\displaystyle p}$ eine Primzahl und ${\displaystyle G}$ eine endliche ${\displaystyle p}$-Gruppe mit Präsentation ${\displaystyle G=F/R}$, wie in einigen obenstehenden Abschnitten, dann wird die zweite Kohomologiegruppe ${\displaystyle M(G):=H^{2}(G,\mathbb {Q} /\mathbb {Z} )}$ des ${\displaystyle G}$-Moduls ${\displaystyle \mathbb {Q} /\mathbb {Z} }$ als Schur-Multiplikator von ${\displaystyle G}$ bezeichnet. Dieser kann auch als Quotientengruppe ${\displaystyle M(G)=(R\cap \lbrack F,F\rbrack )/\lbrack F,R\rbrack }$ interpretiert werden.

I. R. Shafarevich hat bewiesen, dass die Differenz zwischen dem Relationen-Rang ${\displaystyle r(G)=\dim _{\mathbb {F} _{p}}(H^{2}(G,\mathbb {F} _{p}))}$ von ${\displaystyle G}$ und dem Erzeugenden-Rang ${\displaystyle d(G)=\dim _{\mathbb {F} _{p}}(H^{1}(G,\mathbb {F} _{p}))}$ von ${\displaystyle G}$ durch die minimale Anzahl von Generatoren des Schur Multiplikators von ${\displaystyle G}$ gegeben ist, also ${\displaystyle r(G)-d(G)=d(M(G))}$.

N. Boston und H. Nover haben gezeigt, dass ${\displaystyle \mu (G_{j})-\nu (G_{j})\leq r(G)}$, für alle Quotienten ${\displaystyle G_{j}:=G/P_{j}(G)}$ mit ${\displaystyle p}$-Klasse ${\displaystyle \mathrm {cl} _{p}(G_{j})=j}$, ${\displaystyle j\geq 0}$, einer pro-${\displaystyle p}$-Gruppe ${\displaystyle G}$ mit endlichem Kommutator-Quotienten ${\displaystyle G/G^{\prime }}$.

Ferner hat J. Blackhurst im Anhang On the nucleus of certain ${\displaystyle p}$-groups der Abhandlung von N. Boston, M. R. Bush und F. Hajir bewiesen, dass eine nicht-zyklische endliche ${\displaystyle p}$-Gruppe ${\displaystyle G}$ mit trivialem Schur Multiplikator ${\displaystyle M(G)=1}$ ein terminaler Vertex im Stammbaum ${\displaystyle {\mathcal {T}}(1)}$ der trivialen Gruppe ${\displaystyle 1}$ ist, das heißt, ${\displaystyle M(G)=1}$ ${\displaystyle \Rightarrow }$ ${\displaystyle \nu (G)=0}$.

Einzelnachweise

1. ↑ Newman, M. F.: Determination of groups of prime-power order. in: Group Theory, Canberra, 1975, Lecture Notes in Math., Vol. 573, Springer, Berlin, 1977, S. 73–84. 
2. ↑ O'Brien, E. A.: The ${\displaystyle p}$-group generation algorithm. In: J. Symbolic Comput. 9. Jahrgang, 1990, S. 677–698, doi:10.1016/s0747-7171(08)80082-x. 
3. ↑ Holt, D. F., Eick, B., O'Brien, E. A.: Handbook of computational group theory. Discrete mathematics and its applications, Chapman and Hall/CRC Press, 2005. 
4. ↑ Gamble, G., Nickel, W., O'Brien, E. A.: ANU p-Quotient -- p-Quotient and p-Group Generation Algorithms. 2006, An Accepted GAP 4 Package, Available also in MAGMA. 
5. ↑ Besche, H. U., Eick, B., O'Brien, E. A.: The SmallGroups Library – a library of groups of small order. An accepted and refereed GAP 4 package, available also in MAGMA, 2005. 
6. ↑ Besche, H. U., Eick, B., O'Brien, E. A.: A millennium project: constructing small groups. In: Int. J. Algebra Comput. 12. Jahrgang, Nr. 5, 2002, S. 623–644, doi:10.1142/s0218196702001115. 
7. ↑ Shafarevich, I. R.: Extensions with given points of ramification. In: Inst. Hautes Études Sci. Publ. Math. 18. Jahrgang, 1963, S. 71–95.  Translated in Amer. Math. Soc. Transl. (2), 59: 128-149, (1966).
8. ↑ Boston, N., Nover, H.: Computing pro-p Galois groups. Proceedings of the 7th Algorithmic Number Theory Symposium 2006, Lecture Notes in Computer Science 4076, 1-10, Springer, Berlin, 2006. 
9. ↑ Boston, N., Bush, M. R., Hajir, F.: Heuristics for ${\displaystyle p}$-class towers of imaginary quadratic fields. In: Math. Ann. 2013, arxiv:1111.4679.