# 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 by M. F. Newman
and E. A. O'Brien
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
$(1)\qquad 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 lower p-central series of $G$ is therefore given by
$(2)\qquad G=P_{0}(G)>\Phi (G)=P_{1}(G)>P_{2}(G)>\cdots >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
$(3)\qquad \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} (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 lower central series of $G$ is given by
$(4)\qquad G=\gamma _{1}(G)>G^{\prime }=\gamma _{2}(G)>\gamma _{3}(G)>\cdots >\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.
R
   * Rule: $\mathrm {cl} (G)\leq \mathrm {cl} _{p}(G)$, since the $\gamma _{j}(G)$ descend more quickly than the $P_{j}(G)$.
   * Rule: If $\vartheta \in \mathrm {Hom} (G,{\tilde {G}})$, for some group ${\tilde {G}}$, then $\vartheta (P_{j}(G))=P_{j}(\vartheta (G))$, for any $j\geq 0$.
   * Rule: For any $c\geq 0$, the conditions $N\triangleleft G$ and $\mathrm {cl} _{p}(G/N)=c$ imply $P_{c}(G)\leq N$.
   * Rule: Let $c\geq 0$. If $\mathrm {cl} _{p}(G)=c$, then $\mathrm {cl} _{p}(G/P_{k}(G))=\min(k,c)$, for all $k\geq 0$, in particular, $\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
$(5)\qquad R=Q_{0}\to Q_{1}\to \cdots \to Q_{m-1}\to Q_{m}=P$, where $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$:
$(6)\qquad R=\pi ^{0}(R)\to \pi ^{1}(R)\to \cdots \to \pi ^{m-1}(R)\to \pi ^{m}(R)=P$, where $m\geq 1$.
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 $\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$, where $c\geq m\geq 1$.
In particular, every non-trivial finite p-group $G>1$ defines a maximal path (consisting of $c=\mathrm {cl} _{p}(G)$ edges)
$(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$
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, p-multiplicator and nucleus

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 turns 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
$(9)\qquad 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\simeq 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
$(10)\qquad \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
$(11)\qquad G^{\ast }:=F/R^{\ast }$,
and the exact sequence
$(12)\qquad 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
$(13)\qquad \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\simeq 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 the rule (R3), and we can define the nucleus of $G$ by
$(14)\qquad P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }\leq R/R^{\ast }$
as a subgroup of the p-multiplicator. Consequently, the nuclear rank
$(15)\qquad \nu (G):=\dim _{\mathbb {F} _{p}}(P_{c}(G^{\ast }))\leq \mu (G)$
of $G$ is bounded from above by the p-multiplicator rank.

## Allowable subgroups of the p-multiplicator

As before, let $G$ be a finite p-group with $d$ generators.
Proposition. Any p-elementary abelian central extension
$(16)\qquad 1\to Z\to H\to G\to 1$
of $G$ by a p-elementary abelian subgroup $Z\leq \zeta _{1}(H)$ such that $d(H)=d(G)=d$ is a quotient of the p-covering group $G^{\ast }$ of $G$.
For the proof click show on the right hand side.
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 })$.
In particular, an immediate descendant $H$ of $G$ is a p-elementary abelian central extension
$(17)\qquad 1\to P_{c-1}(H)\to H\to G\to 1$
of $G$, since
$1=P_{c}(H)=\lbrack P_{c-1}(H),H\rbrack \cdot P_{c-1}(H)^{p}$ implies $P_{c-1}(H)^{p}=1$ and $P_{c-1}(H)\leq \zeta _{1}(H)$,
where $c=\mathrm {cl} _{p}(H)$.
Definition. A subgroup $M/R^{\ast }\leq R/R^{\ast }$ of the p-multiplicator of $G$ is called allowable if it is given by the kernel $M/R^{\ast }=\ker(\psi ^{\ast })$ of an epimorphism $\psi ^{\ast }:\ G^{\ast }\to H$ onto an immediate descendant $H$ of $G$.
An equivalent characterization is that $1<M/R^{\ast }<R/R^{\ast }$ is a proper subgroup which supplements the nucleus
$(18)\qquad (M/R^{\ast })\cdot (P_{c}(F)\cdot R^{\ast }/R^{\ast })=R/R^{\ast }$.
Therefore, the first part of our goal to compile a list of all immediate descendants of $G$ is done, when we have constructed all allowable subgroups of $R/R^{\ast }$ which supplement the nucleus $P_{c}(G^{\ast })=P_{c}(F)\cdot R^{\ast }/R^{\ast }$, where $c=\mathrm {cl} _{p}(G)$. However, in general the list
$(19)\qquad \lbrace F/M\quad \mid \quad M/R^{\ast }\leq R/R^{\ast }{\text{ is allowable }}\rbrace$,
where $G^{\ast }/(M/R^{\ast })=(F/R^{\ast })/(M/R^{\ast })\simeq F/M$, will be redundant, due to isomorphisms $F/M_{1}\simeq F/M_{2}$ among the immediate descendants.

## Orbits under extended automorphisms

Two allowable subgroups $M_{1}/R^{\ast }$ and $M_{2}/R^{\ast }$ are called equivalent if the quotients $F/M_{1}\simeq F/M_{2}$, that are the corresponding immediate descendants of $G$, are isomorphic.
Such an isomorphism $\varphi :\ F/M_{1}\to F/M_{2}$ between immediate descendants of $G=F/R$ with $c=\mathrm {cl} _{p}(G)$ has the property that $\varphi (R/M_{1})=\varphi (P_{c}(F/M_{1}))=P_{c}(\varphi (F/M_{1}))=P_{c}(F/M_{2})=R/M_{2}$ and thus induces an automorphism $\alpha \in \mathrm {Aut} (G)$ of $G$ which can be extended to an automorphism $\alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })$ of the p-covering group $G^{\ast }=F/R^{\ast }$of $G$. The restriction of this extended automorphism $\alpha ^{\ast }$ to the p-multiplicator $R/R^{\ast }$ of $G$ is determined uniquely by $\alpha$.
Since $\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 }$, each extended automorphism $\alpha ^{\ast }\in \mathrm {Aut} (G^{\ast })$ induces a permutation $\alpha ^{\prime }$ of the allowable subgroups $M/R^{\ast }\leq R/R^{\ast }$. We define $P:=\langle \alpha ^{\prime }\mid \alpha \in \mathrm {Aut} (G)\rangle$ to be the permutation group generated by all permutations induced by automorphisms of $G$. Then the map $\mathrm {Aut} (G)\to P$, $\alpha \mapsto \alpha ^{\prime }$ is an epimorphism and the equivalence classes of allowable subgroups $M/R^{\ast }\leq R/R^{\ast }$ are precisely the orbits of allowable subgroups under the action of the permutation group $P$.
Eventually, our goal to compile a list $\lbrace F/M_{i}\mid 1\leq i\leq N\rbrace$ of all immediate descendants of $G$ will be done, when we select a representative $M_{i}/R^{\ast }$ for each of the $N$ orbits of allowable subgroups of $R/R^{\ast }$ under the action of $P$. This is precisely what the p-group generation algorithm does in a single step of the recursive procedure for constructing the descendant tree of an assigned root.

## Capable p-groups and step sizes

A finite p-group $G$ is called capable (or extendable) if it possesses at least one immediate descendant, otherwise it is terminal (or a leaf). The nuclear rank $\nu (G)$ of $G$ admits a decision about the capability of $G$:
   * $G$ is terminal if and only if $\nu (G)=0$.
   * $G$ is capable if and only if $\nu (G)\geq 1$.
In the case of capability, $G=F/R$ has immediate descendants of $\nu =\nu (G)$ different step sizes $1\leq s\leq \nu$, in dependence on the index $(R/R^{\ast }:M/R^{\ast })=p^{s}$ of the corresponding allowable subgroup $M/R^{\ast }$ in the p-multiplicator $R/R^{\ast }$. When $G$ is of order $\vert G\vert =p^{n}$, then an immediate descendant of step size $s$ is of order $\#(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}$.
For the related phenomenon of multifurcation of a descendant tree at a vertex $G$ with nuclear rank $\nu (G)\geq 2$ see the article on descendant trees.
The p-group generation algorithm provides the flexibility to restrict the construction of immediate descendants to those of a single fixed step size $1\leq s\leq \nu$, which is very convenient in the case of huge descendant numbers (see the next section).

## Numbers of immediate descendants

We denote the number of all immediate descendants, resp. immediate descendants of step size $s$, of $G$ by $N$, resp. $N_{s}$. Then we have $N=\sum _{s=1}^{\nu }\,N_{s}$. As concrete examples, we present some interesting finite metabelian p-groups with extensive sets of immediate descendants, using the SmallGroups identifiers and additionally pointing out the numbers $0\leq C_{s}\leq N_{s}$ of capable immediate descendants in the usual format $(N_{1}/C_{1};\ldots ;N_{\nu }/C_{\nu })$ as given by actual implementations of the p-group generation algorithm in the computer algebra systems GAP and MAGMA.
First, let $p=3$.
We begin with groups having abelianization of type $(3,3)$. See Figure 4 in the article on descendant trees.
   * The group $\langle 27,3\rangle$ of coclass $1$ has ranks $\nu =2$, $\mu =4$ and descendant numbers $(4/1;7/5)$, $N=11$.
   * The group $\langle 243,3\rangle =\langle 27,3\rangle -\#2;1$ of coclass $2$ has ranks $\nu =2$, $\mu =4$ and descendant numbers $(10/6;15/15)$, $N=25$.
   * One of its immediate descendants, the group $\langle 729,40\rangle =\langle 243,3\rangle -\#1;7$, has ranks $\nu =2$, $\mu =5$ and descendant numbers $(16/2;27/4)$, $N=43$.
In contrast, groups with abelianization of type $(3,3,3)$ are partially located beyond the limit of computability.
   * The group $\langle 81,12\rangle$ of coclass $2$ has ranks $\nu =2$, $\mu =7$ and descendant numbers $(10/2;100/50)$, $N=110$.
   * The group $\langle 243,37\rangle$ of coclass $3$ has ranks $\nu =5$, $\mu =9$ and descendant numbers $(35/3;2783/186;81711/10202;350652/202266;\ldots )$, $N>4\cdot 10^{5}$ unknown.
   * The group $\langle 729,122\rangle$ of coclass $4$ has ranks $\nu =8$, $\mu =11$ and descendant numbers $(45/3;117919/1377;\ldots )$, $N>10^{5}$ unknown.
Next, let $p=5$.
Corresponding groups with abelianization of type $(5,5)$ have bigger descendant numbers than for $p=3$.
   * The group $\langle 125,3\rangle$ of coclass $1$ has ranks $\nu =2$, $\mu =4$ and descendant numbers $(4/1;12/6)$, $N=16$.
   * The group $\langle 3125,3\rangle =\langle 125,3\rangle -\#2;1$ of coclass $2$ has ranks $\nu =3$, $\mu =5$ and descendant numbers $(8/3;61/61;47/47)$, $N=116$.

## Schur multiplier

Via the isomorphism $\mathbb {Q} /\mathbb {Z} \to \mu _{\infty }$, ${\frac {n}{d}}\mapsto \exp \left({\frac {n}{d}}\cdot 2\pi i\right)$ the quotient group $\mathbb {Q} /\mathbb {Z} =\left\lbrace {\frac {n}{d}}\cdot \mathbb {Z} \mid d\geq 1,\ 0\leq n\leq d-1\right\rbrace$ can be viewed as the additive analogue of the multiplicative group $\mu _{\infty }=\lbrace z\in \mathbb {C} \mid z^{d}=1{\text{ for some integer }}d\geq 1\rbrace$ of all roots of unity.
Let $p$ be a prime number and $G$ be a finite p-group with presentation $G=F/R$ as in the previous section. Then the second cohomology group $M(G):=H^{2}(G,\mathbb {Q} /\mathbb {Z} )$ of the $G$-module $\mathbb {Q} /\mathbb {Z}$ is called the Schur multiplier of $G$. It can also be interpreted as the quotient group $M(G)=(R\cap \lbrack F,F\rbrack )/\lbrack F,R\rbrack$.
I. R. Shafarevich has proved that the difference between the relation rank $r(G)=\dim _{\mathbb {F} _{p}}(H^{2}(G,\mathbb {F} _{p}))$ of $G$ and the generator rank $d(G)=\dim _{\mathbb {F} _{p}}(H^{1}(G,\mathbb {F} _{p}))$ of $G$ is given by the minimal number of generators of the Schur multiplier of $G$, that is $r(G)-d(G)=d(M(G))$.
N. Boston and H. Nover have shown that $\mu (G_{j})-\nu (G_{j})\leq r(G)$, for all quotients $G_{j}:=G/P_{j}(G)$ of p-class $\mathrm {cl} _{p}(G_{j})=j$, $j\geq 0$, of a pro-p group $G$ with finite abelianization $G/G^{\prime }$.
Furthermore, J. Blackhurst (in the appendix On the nucleus of certain p-groups of a paper by N. Boston, M. R. Bush and F. Hajir ) has proved that a non-cyclic finite p-group $G$ with trivial Schur multiplier $M(G)$ is a terminal vertex in the descendant tree ${\mathcal {T}}(1)$ of the trivial group $1$, that is, $M(G)=1$ $\Rightarrow$ $\nu (G)=0$.

### Examples

* A finite p-group $G$ has a balanced presentation $r(G)=d(G)$ if and only if $r(G)-d(G)=0=d(M(G))$, that is, if and only if its Schur multiplier $M(G)=1$ is trivial. Such a group is called a Schur group and it must be a leaf in the descendant tree ${\mathcal {T}}(1)$.
* A finite p-group $G$ satisfies $r(G)=d(G)+1$ if and only if $r(G)-d(G)=1=d(M(G))$, that is, if and only if it has a non-trivial cyclic Schur multiplier $M(G)$. Such a group is called a Schur+1 group.