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\ge 0$, are briefly called finite p-groups.

The p-group generation algorithm by M. F. Newman ^[1] and E. A. O'Brien ^{[2] [3]} 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\ge 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\ge 1$.

Since any non-trivial finite p-group $G>1$ is nilpotent, there exists an integer $c\ge 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\ge 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\ge 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\ge 2$.

As above, for any non-trivial finite p-group $G>1$, there exists an integer $c\ge 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

1. Rule: $\mathrm{cl}(G)\le\mathrm{cl}_p(G)$, since the $\gamma_j(G)$ descend more quickly than the $P_j(G)$.
2. 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\ge 0$.
3. Rule: For any $c\ge 0$, the conditions $N\triangleleft G$ and $\mathrm{cl}_p(G/N)=c$ imply $P_c(G)\le N$.
4. Rule: Let $c\ge 0$. If $\mathrm{cl}_p(G)=c$, then $\mathrm{cl}_p(G/P_k(G))=\min(k,c)$, for all $k\ge 0$, in particular, $\mathrm{cl}_p(G/P_k(G))=k$, for all $0\le k\le 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\ge 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\ge 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\le j\le 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\ge 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\ge 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\ge m\ge 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\ge 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\le\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)\le 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}\le 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}))\le\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\le\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.

Proof 

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)\le\zeta_1(H)$,

where $c=\mathrm{cl}_p(H)$.

Definition. A subgroup $M/R^{\ast}\le 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}\le 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}\le 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}\le 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\le i\le 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)\ge 1$.

In the case of capability, $G=F/R$ has immediate descendants of $\nu=\nu(G)$ different step sizes $1\le s\le\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)\ge 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\le s\le\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\le C_s\le 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(\frac{n}{d}\cdot 2\pi i)$ the quotient group $\mathbb{Q}/\mathbb{Z}=\lbrace\frac{n}{d}\cdot\mathbb{Z}\mid d\ge 1,\ 0\le n\le d-1\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\ge 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 ^[4] 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 ^[5] have shown that $\mu(G_j)-\nu(G_j)\le r(G)$, for all quotients $G_j:=G/P_j(G)$ of p-class $\mathrm{cl}_p(G_j)=j$, $j\ge 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 ^[6]) 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.

References

1. Newman, M. F. (1977). Determination of groups of prime-power order. pp. 73-84, in: Group Theory, Canberra, 1975, Lecture Notes in Math., Vol. 573, Springer, Berlin.
2. O'Brien, E. A. (1990). "The p-group generation algorithm". J. Symbolic Comput. 9: 677–698. doi:10.1016/s0747-7171(08)80082-x.
3. Holt, D. F., Eick, B., O'Brien, E. A. (2005). Handbook of computational group theory. Discrete mathematics and its applications, Chapman and Hall/CRC Press.
4. Shafarevich, I. R. (1964). "Extensions with given points of ramification (Russian)". Inst. Hautes \'Etudes Sci., Publ. Math. (English transl. in Amer. Math. Soc. Transl. (2) 59 (1966), 128-149) 18: 71–95.
5. Boston, N., Nover, H. (2006). Computing pro-p Galois groups. Proceedings of the 7th Algorithmic Number Theory Symposium 2006, Lecture Notes in Computer Science 4076, 1-10, Springer, Berlin.
6. Boston, N., Bush, M. R., Hajir, F. (2013). "Heuristics for p-class towers of imaginary quadratic fields". Math. Ann.: (preprint: arXiv:1111.4679v1 [math.NT], 2011).