P-group generation algorithm explained

In mathematics, specifically group theory, finite groups of prime power order

pn

, for a fixed prime number

p

and varying integer exponents

n\ge0

, 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 treeof 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

(Pj(G))j\ge

of characteristic subgroups of

G

,defined recursively by

(1)    P0(G):=G

and

Pj(G):=\lbrackPj-1(G),G\rbrackPj-1(G)p

, for

j\ge1

.

Since any non-trivial finite p-group

G>1

is nilpotent,there exists an integer

c\ge1

such that

Pc-1(G)>Pc(G)=1

and

clp(G):=c

is called the exponent-p class (briefly p-class) of

G

.Only the trivial group

1

has

clp(1)=0

.Generally, for any finite p-group

G

,its p-class can be defined as

clp(G):=min\lbracec\ge0\midPc(G)=1\rbrace

.

The complete lower p-central series of

G

is therefore given by

(2)    G=P0(G)>\Phi(G)=P1(G)>P2(G)>>Pc-1(G)>Pc(G)=1

,

since

P1(G)=\lbrackP0(G),G\rbrack

p=\lbrack
P
0(G)

G,G\rbrackGp=\Phi(G)

is the Frattini subgroup of

G

.

For the convenience of the reader and for pointing out the shifted numeration, we recall thatthe (usual) lower central series of

G

is also a descending series

(\gammaj(G))j\ge

of characteristic subgroups of

G

,defined recursively by

(3)    \gamma1(G):=G

and

\gammaj(G):=\lbrack\gammaj-1(G),G\rbrack

, for

j\ge2

.

As above, for any non-trivial finite p-group

G>1

,there exists an integer

c\ge1

such that

\gammac(G)>\gammac+1(G)=1

and

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

cl(1)=0

.

The complete lower central series of

G

is given by

(4)   

\prime
G=\gamma
1(G)>G

=\gamma2(G)>\gamma3(G)>>\gammac(G)>\gammac+1(G)=1

,

since

\gamma2(G)=\lbrack\gamma1(G),G\rbrack=\lbrackG,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:

cl(G)\leclp(G)

, since the

\gammaj(G)

descend more quickly than the

Pj(G)

.
  1. Rule: If

\vartheta\inHom(G,\tilde{G})

, for some group

\tilde{G}

, then

\vartheta(Pj(G))=Pj(\vartheta(G))

, for any

j\ge0

.
  1. Rule: For any

c\ge0

, the conditions

N\triangleleftG

and

clp(G/N)=c

imply

Pc(G)\leN

.
  1. Rule: Let

c\ge0

. If

clp(G)=c

, then

clp(G/Pk(G))=min(k,c)

, for all

k\ge0

, in particular,

clp(G/Pk(G))=k

, for all

0\lek\lec

.

Parents and descendant trees

The parent

\pi(G)

of a finite non-trivial p-group

G>1

with exponent-p class

clp(G)=c\ge1

is defined as the quotient

\pi(G):=G/Pc-1(G)

of

G

by the last non-trivial term

Pc-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

clp(G)=clp(\pi(G))+1

.

A descendant tree is a hierarchical structurefor visualizing parent-descendant relationsbetween 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/Pc-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)    R=Q0\toQ1\to\toQm-1\toQm=P

, where

m\ge1

,

of directed edges from

R

to

P

.The vertices forming the path necessarily coincide with the iterated parents
j
Q
j=\pi

(R)

of

R

, with

0\lej\lem

:

(6)    R=\pi0(R)\to\pi1(R)\to\to\pim-1(R)\to\pim(R)=P

, where

m\ge1

.

They can also be viewed as the successive quotients

Qj=R/Pc-j(R)

of p-class

c-j

of

R

when the p-class of

R

is given by

clp(R)=c\gem

:

(7)    R\simeqR/Pc(R)\toR/Pc-1(R)\to\toR/Pc+1-m(R)\toR/Pc-m(R)\simeqP

, where

c\gem\ge1

.

In particular, every non-trivial finite p-group

G>1

defines a maximal path (consisting of

c=clp(G)

edges)

(8)    G\simeqG/1=G/Pc(G)\to\pi(G)=G/Pc-1

2(G)=G/P
(G)\to\pi
c-2

(G)\to

\to\pic-1

c(G)=G/P
(G)=G/P
0(G)=G/G\simeq

1

ending in the trivial group

\pic(G)=1

.The last but one quotient of the maximal path of

G

is the elementary abelian p-group

\pic-1(G)=G/P1(G)\simeq

d
C
p
of rank

d=d(G)

,where
d(G)=\dim
Fp
1(G,F
(H
p))
denotes the generator rank of

G

.

Generally, the descendant tree

l{T}(G)

of a vertex

G

is the subtree of all descendants of

G

, starting at the root

G

.The maximal possible descendant tree

l{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\ge1

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)    1\longrightarrowR\longrightarrowF\longrightarrowG\longrightarrow1

,

where

F

denotes the free group with

d

generators and

\vartheta:F\longrightarrowG

is an epimorphism with kernel

R:=\ker(\vartheta)

.Then

R\triangleleftF

is a normal subgroup of

F

consisting of the defining relations for

G\simeqF/R

.For elements

r\inR

and

f\inF

,the conjugate

f-1rf\inR

and thus also the commutator

\lbrackr,f\rbrack=r-1f-1rf\inR

are contained in

R

.Consequently,

R\ast:=\lbrackR,F\rbrackRp

is a characteristic subgroup of

R

,and the p-multiplicator

R/R\ast

of

G

is an elementary abelian p-group, since

(10)    \lbrackR,R\rbrackRp\le\lbrackR,F\rbrackRp=R\ast

.

Now we can define the p-covering group of

G

by

(11)    G\ast:=F/R\ast

,

and the exact sequence

(12)    1\longrightarrowR/R\ast\longrightarrowF/R\ast\longrightarrowF/R\longrightarrow1

shows that

G\ast

is an extension of

G

by the elementary abelian p-multiplicator.We call

(13)   

\mu(G):=\dim
Fp

(R/R\ast)

the p-multiplicator rank of

G

.

Let us assume now that the assigned finite p-group

G\simeqF/R

is of p-class

clp(G)=c

.Then the conditions

R\triangleleftF

and

clp(F/R)=c

imply

Pc(F)\leR

, according to the rule (R3),and we can define the nucleus of

G

by

(14)   

\ast
P
c(G

)=Pc(F)R\ast/R\ast\leR/R\ast

as a subgroup of the p-multiplicator.Consequently, the nuclear rank

(15)   

\nu(G):=\dim
Fp
\ast
(P
c(G

))\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)    1\toZ\toH\toG\to1

of

G

by a p-elementary abelian subgroup

Z\le\zeta1(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\toH

such that

\vartheta=\omega\circ\psi

, where

\omega:H\toH/Z\simeqG

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(Rp)=Zp=1

, since

Z

is p-elementary,and

\psi(\lbrackR,F\rbrack)=\lbrackZ,H\rbrack=1

, since

Z

is central.Together this shows that

\psi(R\ast)=\psi(\lbrackR,F\rbrackRp)=1

and thus

\psi

induces the desired epimorphism

\psi\ast:G\ast\toH

such that

H\simeqG\ast/\ker(\psi\ast)

.

In particular, an immediate descendant

H

of

G

is a p-elementary abelian central extension

(17)    1\toPc-1(H)\toH\toG\to1

of

G

,since

1=Pc(H)=\lbrackPc-1(H),H\rbrackPc-1(H)p

implies

Pc-1(H)p=1

and

Pc-1(H)\le\zeta1(H)

,

where

c=clp(H)

.

Definition.A subgroup

M/R\ast\leR/R\ast

of the p-multiplicator of

G

is called allowableif it is given by the kernel

M/R\ast=\ker(\psi\ast)

of an epimorphism

\psi\ast:G\ast\toH

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)    (M/R\ast)(Pc(F)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
\ast
P
c(G

)=Pc(F)R\ast/R\ast

,where

c=clp(G)

.However, in general the list

(19)    \lbraceF/M\midM/R\ast\leR/R\astisallowable\rbrace

,

where

G\ast/(M/R\ast)=(F/R\ast)/(M/R\ast)\simeqF/M

,will be redundant,due to isomorphisms

F/M1\simeqF/M2

among the immediate descendants.

Orbits under extended automorphisms

Two allowable subgroups

\ast
M
1/R
and
\ast
M
2/R
are called equivalent if the quotients

F/M1\simeqF/M2

,that are the corresponding immediate descendants of

G

, are isomorphic.

Such an isomorphism

\varphi:F/M1\toF/M2

between immediate descendants of

G=F/R

with

c=clp(G)

has the property that

\varphi(R/M1)=\varphi(Pc(F/M1))=Pc(\varphi(F/M1))=Pc(F/M2)=R/M2

and thus induces an automorphism

\alpha\inAut(G)

of

G

which can be extended to an automorphism

\alpha\ast\inAut(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)

\ast
P
c(F/R

)=\alpha\ast\lbrackM/R\ast

\ast
P
c(F/R

)\rbrack=\alpha\ast(R/R\ast)=R/R\ast

,each extended automorphism

\alpha\ast\inAut(G\ast)

induces a permutation

\alpha\prime

of the allowable subgroups

M/R\ast\leR/R\ast

.We define

P:=\langle\alpha\prime\mid\alpha\inAut(G)\rangle

to be the permutation group generated by all permutations induced by automorphisms of

G

.Then the map

Aut(G)\toP

,

\alpha\mapsto\alpha\prime

is an epimorphismand the equivalence classes of allowable subgroups

M/R\ast\leR/R\ast

are precisely the orbits of allowable subgroups under the action of the permutation group

P

.

Eventually, our goal to compile a list

\lbraceF/Mi\mid1\lei\leN\rbrace

of all immediate descendants of

G

will be done,when we select a representative
\ast
M
i/R
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)\ge1

.In the case of capability,

G=F/R

has immediate descendants of

\nu=\nu(G)

different step sizes

1\les\le\nu

, in dependence on the index

(R/R\ast:M/R\ast)=ps

of the corresponding allowable subgroup

M/R\ast

in the p-multiplicator

R/R\ast

. When

G

is of order

\vertG\vert=pn

, 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)(R/R\ast:M/R\ast)

=\#(F/R)ps=\vertG\vertps=pnps=pn+s

.

For the related phenomenon of multifurcation of a descendant tree at a vertex

G

with nuclear rank

\nu(G)\ge2

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\les\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.

Ns

. Then we have
\nuN
N=\sum
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\leCs\leNs

of capable immediate descendants in the usual format

(N1/C1;\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.

\langle27,3\rangle

of coclass

1

has ranks

\nu=2

,

\mu=4

and descendant numbers

(4/1;7/5)

,

N=11

.

\langle243,3\rangle=\langle27,3\rangle-\#2;1

of coclass

2

has ranks

\nu=2

,

\mu=4

and descendant numbers

(10/6;15/15)

,

N=25

.

\langle729,40\rangle=\langle243,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.

\langle81,12\rangle

of coclass

2

has ranks

\nu=2

,

\mu=7

and descendant numbers

(10/2;100/50)

,

N=110

.

\langle243,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 ⋅ 105

unknown.

\langle729,122\rangle

of coclass

4

has ranks

\nu=8

,

\mu=11

and descendant numbers

(45/3;117919/1377;\ldots)

,

N>105

unknown.

Next, let

p=5

.

Corresponding groups with abelianization of type

(5,5)

have bigger descendant numbers than for

p=3

.

\langle125,3\rangle

of coclass

1

has ranks

\nu=2

,

\mu=4

and descendant numbers

(4/1;12/6)

,

N=16

.

\langle3125,3\rangle=\langle125,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

Q/Z\to\muinfty

,
n\mapsto\exp\left(
d
n
d

2\pii\right)

the quotient group
Q/Z=\left\lbracen
d

Z\midd\ge1, 0\len\led-1\right\rbrace

can be viewed as the additive analogue of the multiplicative group

\muinfty=\lbracez\inC\midzd=1forsomeintegerd\ge1\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):=H2(G,Q/Z)

of the

G

-module

Q/Z

is called the Schur multiplier of

G

. It can also be interpreted as the quotient group

M(G)=(R\cap\lbrackF,F\rbrack)/\lbrackF,R\rbrack

.

I. R. Shafarevich[4] has proved that the difference between the relation rank

r(G)=\dim
Fp
2(G,F
(H
p))
of

G

and the generator rank
d(G)=\dim
Fp
1(G,F
(H
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(Gj)-\nu(Gj)\ler(G)

,for all quotients

Gj:=G/Pj(G)

of p-class

clp(Gj)=j

,

j\ge0

,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

l{T}(1)

of the trivial group

1

,that is,

M(G)=1

\nu(G)=0

.

Examples

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

l{T}(1)

.

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.

Notes and References

  1. Book: 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. 5–6. 677–698. 10.1016/s0747-7171(08)80082-x. free.
  3. Book: 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.. 1963. Extensions with given points of ramification. Inst. Hautes Études Sci. Publ. Math.. 18. 71–95. Translasted in Amer. Math. Soc. Transl. (2), 59: 128-149, (1966).
  5. Book: 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. . 1111.4679.