User:DanielConstantinMayer/ sandbox

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.

Additionally to their order $p^{n}$, finite p-groups have two further related invariants, the nilpotency class $c$ and the coclass $r=n-c$.

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.

Tree Diagram

A vertex is capable (or extendable) if it has at least one immediate descendant, otherwise it is terminal (or a leaf). Vertices sharing a common parent are called siblings.

Figure 2: The coclass graph of finite 2-groups with coclass 1

Multifurcation and coclass graphs

Assume that parents of finite p-groups are defined as last non-trivial lower central quotients (2.). For a p-group $G$ of coclass $\mathrm {cc} (G)=r$, we can distinguish its (entire) descendant tree ${\mathcal {T}}(G)$ and its coclass-$r$ descendent tree ${\mathcal {T}}^{r}(G)$, the subtree consisting of descendants of coclass $r$ only. The group $G$ is coclass settled if ${\mathcal {T}}(G)={\mathcal {T}}^{r}(G)$.

The nuclear rank $n(G)$ of $G$ in the theory of the p-group generation algorithm by E. A. O'Brien provides the following criteria.

• $G$ is terminal (and thus trivially coclass settled) if and only if $n(G)=0$.
• If $n(G)=1$, then $G$ is capable. (But it remains unknown whether $G$ is coclass settled.)
• If $n(G)=m\geq 2$, then $G$ is capable but not coclass settled.

In the last case, a more precise assertion is possible: If $G$ has coclass $r$ and nuclear rank $n(G)=m\geq 2$, then it gives rise to an m-fold multifurcation into a regular coclass-r descendant tree ${\mathcal {T}}^{r}(G)$ and $m-1$ irregular descendant trees ${\mathcal {T}}^{r+j}(G)$ of coclass $r+j$, for $1\leq j\leq m-1$. Consequently, the descendant tree of $G$ is the disjoint union ${\mathcal {T}}(G)={\dot {\cup }}_{j=0}^{m-1}\,{\mathcal {T}}^{r+j}(G)$.

Multifurcation is correlated with different orders of the last non-trivial lower central of immediate descendants. Since the nilpotency class increases exactly by a unit, $c=\mathrm {cl} (Q)=\mathrm {cl} (P)+1$, from a parent $P=\pi (Q)$ to any immediate descendant $Q$, the coclass remains stable, $r=\mathrm {cc} (Q)=\mathrm {cc} (P)$, if $\vert \gamma _{c}(Q)\vert =p$. In this case, $Q$ is a regular immediate descendant with directed edge $P\leftarrow Q$ of depth 1 (as usual). However, the coclass increases by $m-1$, if $\vert \gamma _{c}(Q)\vert =p^{m}$ with $m\geq 2$. Then $Q$ is called an irregular immediate descendant with directed edge of depth $m$.

If the condition of depth (or step size) 1 is imposed on all directed edges, then the maximal descendant tree ${\mathcal {T}}(1)$ of the trivial group $1$ splits into a countably infinite disjoint union ${\dot {\cup }}_{r=0}^{\infty }\,{\mathcal {G}}(p,r)$ of directed coclass graphs ${\mathcal {G}}(p,r)$, which are rather forests than trees. More precisely, the above mentioned Coclass Theorems imply that ${\mathcal {G}}(p,r)=\left({\dot {\cup }}_{i}\,{\mathcal {T}}(S_{i})\right){\dot {\cup }}{\mathcal {G}}_{0}(p,r)$ is the disjoint union of finitely many coclass trees ${\mathcal {T}}(S_{i})$ of (pairwise non-isomorphic) infinite pro-p groups $S_{i}$ of coclass $r$ (Theorem D) and a finite subgraph ${\mathcal {G}}_{0}(p,r)$ of sporadic groups lying outside of any coclass tree.

Figure 3: The coclass graph of finite 3-groups with coclass 1

Identifiers

The SmallGroups Library identifiers of finite groups, in particular p-groups, given in the form $\langle {\text{order}},{\text{counting number}}\rangle$ in the following concrete examples of descendant trees, are due to H. U. Besche, B. Eick and E. A. O'Brien . When the group orders are given in a scale on the left hand side as in Figure 2 and Figure 3, the identifiers are briefly denoted by $\langle {\text{counting number}}\rangle$.

Depending on the prime $p$, there is an upper bound on the order of groups for which a SmallGroup identifier exists, e. g. $512=2^{9}$ for $p=2$, and $2187=3^{7}$ for $p=3$. For groups of bigger orders, a notation resembling the descendant structure is employed: A regular immediate descendant, connected by an edge of depth $1$ with its parent $P$, is denoted by $P-\#1;{\text{counting number}}$, and an irregular immediate descendant, connected by an edge of depth $d\geq 2$ with its parent $P$, is denoted by $P-\#d;{\text{counting number}}$.

Concrete examples

In all examples, the underlying parent definition (2.) corresponds to the usual lower central series. Occasional differences to the parent definition (3.) with respect to the lower exponent-p central series are pointed out.

Coclass 0

The coclass graph ${\mathcal {G}}(p,0)={\mathcal {G}}_{0}(p,0)$ of finite p-groups of coclass $0$ does not contain a coclass tree and consists of the trivial group $1$ and the cyclic group $C_{p}$ of order $p$, which is a leaf (however, it is capable with respect to the lower exponent-p central series). For $p=2$ the SmallGroup identifier of $C_{p}$ is $\langle 2,1\rangle$, for $p=3$ it is $\langle 3,1\rangle$.

Figure 4: The interface between finite 3-groups of coclass 1 and 2 of type (3,3)

Coclass 1

The coclass graph ${\mathcal {G}}(p,1)={\mathcal {T}}^{1}(R){\dot {\cup }}{\mathcal {G}}_{0}(p,1)$ of finite p-groups of coclass $1$ consists of the unique coclass tree with root $R=C_{p}\times C_{p}$, the elementary abelian p-group of rank $2$, and a single isolated vertex (a terminal orphan without proper parent in the same coclass graph, since the directed edge to the trivial group $1$ has depth $2$), the cyclic group $C_{p^{2}}$ of order $p^{2}$ in the sporadic part ${\mathcal {G}}_{0}(p,1)$ (however, this group is capable with respect to the lower exponent-p central series). The tree ${\mathcal {T}}^{1}(R)={\mathcal {T}}^{1}(S_{1})$ is the coclass tree of the unique infinite pro-p group $S_{1}$ of coclass $1$.

For $p=2$, resp. $p=3$, the SmallGroup identifier of the root $R$ is $\langle 4,2\rangle$, resp. $\langle 9,2\rangle$, and a tree diagram of the coclass graph from branch ${\mathcal {B}}(2)$ up to branch ${\mathcal {B}}(7)$ (counted with respect to the p-logarithm of the order of the branch root) is drawn in Figure 2, resp. Figure 3, where all groups of order at least $p^{3}$ are metabelian, that is non-abelian with derived length $2$ (vertices represented by black discs in contrast to contour squares indicating abelian groups). In Figure 3, smaller black discs denote metabelian 3-groups where even the maximal subgroups are non-abelian, a feature which does not occur for the metabelian 2-groups in Figure 2, since they all possess an abelian subgroup of index $p$ (usually exactly one). The coclass tree of ${\mathcal {G}}(2,1)$, resp. ${\mathcal {G}}(3,1)$, has periodic root $\langle 8,3\rangle$ and period of length $1$ starting with branch ${\mathcal {B}}(3)$, resp. periodic root $\langle 81,9\rangle$ and period of length $2$ starting with branch ${\mathcal {B}}(4)$. Both trees have branches of bounded depth $1$, so their virtual periodicity is in fact a strict periodicity.

However, the coclass tree of ${\mathcal {G}}(5,1)$ has unbounded depth and contains non-metabelian groups, and the coclass tree of ${\mathcal {G}}(7,1)$ has unbounded depth and even unbounded width, that is the number of descendants of a fixed order increases indefinitely with growing order .

The concrete examples ${\mathcal {G}}(2,1)$ and ${\mathcal {G}}(3,1)$ provide an opportunity to give a parametrized power-commutator presentation (here a polycyclic presentation) for the complete coclass tree, mentioned in the lead section as a benefit of the descendant tree concept and as a consequence of the periodicity of the pruned coclass tree. In both cases, the group $G$ is generated by two elements $x,y$ but the presentation contains the series of higher commutators $s_{j}$, $2\leq j\leq n-1=\mathrm {cl} (G)$, starting with the main commutator $s_{2}=\lbrack y,x\rbrack$. The nilpotency is formally expressed by $s_{n}=1$, when the group is of order $\vert G\vert =p^{n}$.

For $p=2$, there are two parameters $0\leq w,z\leq 1$ and the pc-presentation is given by

2 ${\begin{aligned}G^{n}(z,w)=&\langle x,y,s_{2},\ldots ,s_{n-1}\mid \\&x^{2}=s_{n-1}^{w},\ y^{2}=s_{2}^{-1}s_{n-1}^{z},\ \lbrack s_{2},y\rbrack =1,\\&s_{2}=\lbrack y,x\rbrack ,\ s_{j}=\lbrack s_{j-1},x\rbrack {\text{ for }}3\leq j\leq n-1\rangle \end{aligned}}$

The 2-groups of maximal class, that is of coclass $1$, form three periodic infinite sequences,

• the dihedral groups, $D(2^{n})=G^{n}(0,0)$, $n\geq 3$, forming the mainline (with infinitely capable vertices),
• the generalized quaternion groups, $Q(2^{n})=G^{n}(0,1)$, $n\geq 3$, which are all terminal vertices,
• the semidihedral groups, $S(2^{n})=G^{n}(1,0)$, $n\geq 4$, which are also leaves.

For $p=3$, there are three parameters $0\leq a\leq 1$ and $-1\leq w,z\leq 1$ and the pc-presentation is given by

3 ${\begin{aligned}G_{a}^{n}(z,w)=&\langle x,y,s_{2},\ldots ,s_{n-1}\mid \\&x^{3}=s_{n-1}^{w},\ y^{3}=s_{2}^{-3}s_{3}^{-1}s_{n-1}^{z},\ \lbrack y,s_{2}\rbrack =s_{n-1}^{a},\\&s_{2}=\lbrack y,x\rbrack ,\ s_{j}=\lbrack s_{j-1},x\rbrack {\text{ for }}3\leq j\leq n-1\rangle \end{aligned}}$

3-groups with parameter $a=0$ possess an abelian maximal subgroup, those with parameter $a=1$ do not. More precisely, an existing abelian maximal subgroup is unique, except for the two groups $G^{3}(0,0)$ and $G^{3}(0,1)$, where all four maximal subgroups are abelian.

In contrast to any bigger coclass $r\geq 2$, the coclass graph ${\mathcal {G}}(p,1)$ exclusively contains p-groups $G$ with abelianization $G/G^{\prime }$ of type $(p,p)$, except for its unique isolated vertex. The case $p=2$ is distinguished by the truth of the reverse statement: Any $2$-group with abelianization of type $(2,2)$ is of coclass $1$ (O. Taussky's Theorem ).

Coclass 2

The genesis of the coclass graph ${\mathcal {G}}(p,r)$ with $r\geq 2$ is not uniform. p-groups with several distinct abelianizations contribute to its constitution. For coclass $r=2$, there are essential contributions from groups $G$ with abelianizations $G/G^{\prime }$ of the types $(p,p)$, $(p,p^{2})$, $(p,p,p)$, and an isolated contribution by the cyclic group of order $p^{3}$.

Abelianization of type $(p,p)$

As opposed to p-groups of coclass $2$ with abelianization of type $(p,p^{2})$ or $(p,p,p)$, which arise as regular descendants of abelian p-groups of the same types, p-groups of coclass $2$ with abelianization of type $(p,p)$ arise from irregular descendants of a non-abelian p-group of coclass $1$ which is not coclass settled.

For the prime $p=2$, such groups do not exist at all, since the group $\langle 8,3\rangle$ is coclass-settled, which is the deeper reason for Taussky's Theorem.

For odd primes $p$, the existence of p-groups of coclass $2$ with abelianization of type $(p,p)$ is due to the fact that the group $G_{0}^{3}(0,0)$ is not coclass-settled. Its nuclear rank equals $2$, which gives rise to a bifurcation of the descendant tree ${\mathcal {T}}(G_{0}^{3}(0,0))$ into two coclass graphs. The regular component ${\mathcal {T}}^{1}(G_{0}^{3}(0,0))$ is a subtree of the unique tree ${\mathcal {T}}^{1}(C_{p}\times C_{p})$ in the coclass graph ${\mathcal {G}}(p,1)$. The irregular component ${\mathcal {T}}^{2}(G_{0}^{3}(0,0))$ becomes a subgraph ${\mathcal {G}}={\mathcal {G}}_{(p,p)}(p,2)$ of the coclass graph ${\mathcal {G}}(p,2)$ when the connecting edges of depth $2$ of the irregular immediate descendants of $G_{0}^{3}(0,0)$ are removed.

For $p=3$, this subgraph ${\mathcal {G}}$ is drawn in Figure 4. It has seven top level vertices of three important kinds, all having order $243=3^{5}$.

• Firstly, there are two terminal Schur σ-groups $\langle 243,5\rangle$ and $\langle 243,7\rangle$ in the sporadic part ${\mathcal {G}}_{0}(3,2)$ of the coclass graph ${\mathcal {G}}(3,2)$.
• Secondly, the two groups $\langle 243,4\rangle$ and $\langle 243,9\rangle$ are roots of finite trees in ${\mathcal {G}}_{0}(3,2)$.
• And, finally, the three groups $\langle 243,3\rangle$, $\langle 243,6\rangle$ and $\langle 243,8\rangle$ give rise to (infinite) coclass trees in the coclass graph ${\mathcal {G}}(3,2)$.

Generally, a Schur group (called a closed group by I. Schur, who coined the concept) is a pro-p group $G$ whose relation rank $r(G)=\mathrm {dim} _{\mathbb {F} _{p}}(\mathrm {H} ^{2}(G,\mathbb {F} _{p}))$ coincides with its generator rank $d(G)=\mathrm {dim} _{\mathbb {F} _{p}}(\mathrm {H} ^{1}(G,\mathbb {F} _{p}))$. A σ-group is a pro-p group $G$ which possesses an automorphism $\sigma \in \mathrm {Aut} (G)$ inducing the inversion $x\mapsto x^{-1}$ on the abelianization $G/G^{\prime }$. A Schur σ-group is a Schur group $G$ which is also a σ-group and has a finite abelianization $G/G^{\prime }$.

History

Descendant trees with central quotients as parents (1.) are implicit in P. Hall's 1940 paper about isoclinism of groups. Trees with last non-trivial lower central quotients as parents (2.) were first presented by C. R. Leedham-Green at the International Congress of Mathematicians in Vancouver, 1974 . The first extensive tree diagrams have been drawn manually by J. A. Ascione, G. Havas and C. R. Leedham-Green (1977) , by J. A. Ascione (1979) , and by B. Nebelung (1989) . In the former two cases, the parent definition by means of the lower exponent-p central series (3.) was adopted in view of computational advantages, in the latter case, where theoretical aspects were focussed, the parents were taken with respect to the usual lower central series (2.).

References

Category: group theory Category: P-groups Category: Subgroup series Category: Trees (data structures)