P-group generation algorithm

In mathematics, specifically group theory, finite groups of prime power order $p^{n}$, for a fixed prime number $p$ and varying integer exponents $n\geq 0$, are briefly called finite p-groups.

The p-group generation algorithm is a recursive process for constructing the descendant tree of an assigned finite p-group which is taken as the root of the tree.

Lower exponent-p central series

For a finite p-group $G$, the lower exponent-p central series (briefly lower p-central series) of $G$ is a descending series $(P_{j}(G))_{j\geq 0}$ of characteristic subgroups of $G$, defined recursively by $P_{0}(G):=G$ and $P_{j}(G):=\lbrack P_{j-1}(G),G\rbrack \cdot P_{j-1}(G)^{p}$, for $j\geq 1$. Since any non-trivial finite p-group $G>1$ is nilpotent, there exists an integer $c\geq 1$ such that $P_{c-1}(G)>P_{c}(G)=1$ and $\mathrm {cl} _{p}(G):=c$ is called the exponent-p class (briefly p-class) of $G$. Only the trivial group $1$ has $\mathrm {cl} _{p}(1)=0$. Generally , for any finite p-group $G$, its p-class can be defined as $\mathrm {cl} _{p}(G):=\min \lbrace c\geq 0\mid P_{c}(G)=1\rbrace$.

The complete series is given by $G=P_{0}(G)>\Phi (G)=P_{1}(G)>P_{2}(G)>\ldots >P_{c-1}(G)>P_{c}(G)=1$,

since $P_{1}(G)=\lbrack P_{0}(G),G\rbrack \cdot P_{0}(G)^{p}=\lbrack G,G\rbrack \cdot G^{p}=\Phi (G)$ is the Frattini subgroup of $G$.

For the convenience of the reader and for pointing out the shifted numeration, we recall that the (usual) lower central series of $G$ is also a descending series $(\gamma _{j}(G))_{j\geq 1}$ of characteristic subgroups of $G$, defined recursively by $\gamma _{1}(G):=G$ and $\gamma _{j}(G):=\lbrack \gamma _{j-1}(G),G\rbrack$, for $j\geq 2$. As above, for any non-trivial finite p-group $G>1$, there exists an integer $c\geq 1$ such that $\gamma _{c}(G)>\gamma _{c+1}(G)=1$ and $\mathrm {cl} _{p}(G):=c$ is called the nilpotency class of $G$, whereas $c+1$ is called the index of nilpotency of $G$. Only the trivial group $1$ has $\mathrm {cl} (1)=0$.

The complete series is given by $G=\gamma _{1}(G)>G^{\prime }=\gamma _{2}(G)>\gamma _{3}(G)>\ldots >\gamma _{c}(G)>\gamma _{c+1}(G)=1$,

since $\gamma _{2}(G)=\lbrack \gamma _{1}(G),G\rbrack =\lbrack G,G\rbrack =G^{\prime }$ is the commutator subgroup or derived subgroup of $G$.

The following Rules should be remembered for the exponent-p class:

Let $G$ be a finite p-group.

1. Rule: $\mathrm {cl} (G)\leq \mathrm {cl} _{p}(G)$, since the $\gamma _{j}(G)$ descend more quickly than the $P_{j}(G)$.
2. Rule: $\vartheta \in \mathrm {Hom} (G,{\tilde {G}})$, for some group ${\tilde {G}}$ $\Rightarrow$ $\vartheta (P_{j}(G))=P_{j}(\vartheta (G))$, for any $j\geq 0$.
3. Rule: For any $c\geq 0$, the conditions $N\triangleleft G$ and $\mathrm {cl} _{p}(G/N)=c$ imply $P_{c}(G)\leq N$.
4. Rule: For any $c\geq 0$, $\mathrm {cl} _{p}(G)=c$ $\Rightarrow$ $\mathrm {cl} _{p}(G/P_{k}(G))=\min(k,c)$, for all $k\geq 0$, and $\mathrm {cl} _{p}(G/P_{k}(G))=k$, for all $0\leq k\leq c$.

Parents and descendant trees

The parent $\pi (G)$ of a finite non-trivial p-group $G>1$ with exponent-p class $\mathrm {cl} _{p}(G)=c\geq 1$ is defined as the quotient $\pi (G):=G/P_{c-1}(G)$ of $G$ by the last non-trivial term $P_{c-1}(G)>1$ of the lower exponent-p central series of $G$. Conversely, in this case, $G$ is called an immediate descendant of $\pi (G)$. The p-classes of parent and immediate descendant are connected by $\mathrm {cl} _{p}(G)=\mathrm {cl} _{p}(\pi (G))+1$.

A descendant tree is a hierarchical structure for visualizing parent-descendant relations between isomorphism classes of finite p-groups. The vertices of a descendant tree are isomorphism classes of finite p-groups. However, a vertex will always be labelled by selecting a representative of the corresponding isomorphism class. Whenever a vertex $\pi (G)$ is the parent of a vertex $G$ a directed edge of the descendant tree is defined by $G\to \pi (G)$ in the direction of the canonical projection $\pi :G\to \pi (G)$ onto the quotient $\pi (G)=G/P_{c-1}(G)$.

In a descendant tree, the concepts of parents and immediate descendants can be generalized. A vertex $R$ is a descendant of a vertex $P$, and $P$ is an ancestor of $R$, if either $R$ is equal to $P$ or there is a path $R=Q_{0}\to Q_{1}\to \ldots \to Q_{m-1}\to Q_{m}=P$, with $m\geq 1$, of directed edges from $R$ to $P$. The vertices forming the path necessarily coincide with the iterated parents $Q_{j}=\pi ^{j}(R)$ of $R$, with $0\leq j\leq m$. They can also be viewed as the successive quotients $Q_{j}=R/P_{c-j}(R)$ of p-class $c-j$ of $R$ when the p-class of $R$ is given by $c\geq m$. In particular, every non-trivial finite p-group $G>1$ defines a maximal path $G=G/1=G/P_{c}(G)\to \pi (G)=G/P_{c-1}(G)\to \pi ^{2}(G)=G/P_{c-2}(G)\to \ldots \to \pi ^{c-1}(G)=G/P_{1}(G)\to \pi ^{c}(G)=G/P_{0}(G)=G/G=1$ ending in the trivial group $\pi ^{c}(G)=1$. The last but one quotient of the maximal path of $G$ is the elementary abelian p-group $\pi ^{c-1}(G)=G/P_{1}(G)\simeq C_{p}^{d}$ of rank $d=d(G)$, where $d(G)=\dim _{\mathbb {F} _{p}}(H^{1}(G,\mathbb {F} _{p}))$ denotes the generator rank of $G$.

Generally, the descendant tree ${\mathcal {T}}(G)$ of a vertex $G$ is the subtree of all descendants of $G$, starting at the root $G$. The maximal possible descendant tree ${\mathcal {T}}(1)$ of the trivial group $1$ contains all finite p-groups and is exceptional, since the trivial group $1$ has all the infinitely many elementary abelian p-groups with varying generator rank $d\geq 1$ as its immediate descendants. However, any non-trivial finite p-group (of order divisible by $p$) possesses only finitely many immediate descendants.

p-covering group

Let $G$ be a finite p-group with $d$ generators. Our goal is to compile a complete list of pairwise non-isomorphic immediate descendants of $G$. It turned out that all immediate descendants can be obtained as quotients of a certain extension $G^{\ast }$ of $G$ which is called the p-covering group of $G$ and can be constructed in the following manner.

We can certainly find a presentation of $G$ in the form of an exact sequence $1\longrightarrow R\longrightarrow F\longrightarrow G\longrightarrow 1$, where $F$ denotes the free group with $d$ generators and $\vartheta :\ F\longrightarrow G$ is an epimorphism with kernel $R:=\ker(\vartheta )$. Then $R\triangleleft F$ is a normal subgroup of $F$ consisting of the defining relations for $G=F/R$. For elements $r\in R$ and $f\in F$, the conjugate $f^{-1}rf\in R$ and thus also the commutator $\lbrack r,f\rbrack =r^{-1}f^{-1}rf\in R$ are contained in $R$. Consequently, $R^{\ast }:=\lbrack R,F\rbrack \cdot R^{p}$ is a characteristic subgroup of $R$, and the p-multiplicator $R/R^{\ast }$ of $G$ is an elementary abelian p-group, since $\lbrack R,R\rbrack \cdot R^{p}\leq \lbrack R,F\rbrack \cdot R^{p}=R^{\ast }$. Now we can define the p-covering group of $G$ by $G^{\ast }:=F/R^{\ast }$, and the exact sequence $1\longrightarrow R/R^{\ast }\longrightarrow F/R^{\ast }\longrightarrow F/R\longrightarrow 1$ shows that $G^{\ast }$ is an extension of $G$ by the elementary abelian p-multiplicator. We call $\mu (G):=\dim _{\mathbb {F} _{p}}(R/R^{\ast })$ the p-multiplicator rank of $G$.

Let us assume now that the assigned finite p-group $G=F/R$ is of p-class $\mathrm {cl} _{p}(G)=c$. Then the conditions $R\triangleleft F$ and $\mathrm {cl} _{p}(F/R)=c$ imply $P_{c}(F)\leq R$, according to Rule 3, and we can define the nucleus of $G$ by $P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }\leq R/R^{\ast }$ as a subgroup of the p-multiplier. Consequently, the nuclear rank $\nu (G):=\dim _{\mathbb {F} _{p}}(P_{c}(G^{\ast }))\leq \mu (G)$ of $G$ is bounded from above by the p-multiplicator rank.