P-group generation algorithm

In mathematics, specifically group theory, finite groups of prime power order formula_1, for a fixed prime number formula_2 and varying integer exponents formula_3, 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 formula_4, the lower exponent-"p" central series (briefly lower "p"-central series) of formula_4
is a descending series formula_6 of characteristic subgroups of formula_4,
defined recursively by
formula_8 and formula_9, for formula_10.
Since any non-trivial finite "p"-group formula_11 is nilpotent,
there exists an integer formula_12 such that formula_13
and formula_14 is called the exponent-"p" class (briefly "p"-class) of formula_4.
Only the trivial group formula_16 has formula_17.
Generally, for any finite "p"-group formula_4,
its "p"-class can be defined as formula_19.
The complete lower "p"-central series of formula_4 is therefore given by
formula_21,
since formula_22 is the Frattini subgroup of formula_4.
For the convenience of the reader and for pointing out the shifted numeration, we recall that
the (usual) lower central series of formula_4 is also a descending series formula_25 of characteristic subgroups of formula_4,
defined recursively by
formula_27 and formula_28, for formula_29.
As above, for any non-trivial finite "p"-group formula_11,
there exists an integer formula_12 such that formula_32
and formula_33 is called the nilpotency class of formula_4,
whereas formula_35 is called the index of nilpotency of formula_4.
Only the trivial group formula_16 has formula_38.
The complete lower central series of formula_4 is given by
formula_40,
since formula_41 is the commutator subgroup or derived subgroup of formula_4.
The following Rules should be remembered for the exponent-"p" class:
Let formula_4 be a finite "p"-group.
Parents and descendant trees.
The parent formula_61 of a finite non-trivial "p"-group formula_11 with exponent-"p" class formula_63
is defined as the quotient formula_64 of formula_4 by the last non-trivial term formula_66 of the lower exponent-"p" central series of formula_4.
Conversely, in this case, formula_4 is called an immediate descendant of formula_61.
The "p"-classes of parent and immediate descendant are connected by formula_70.
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 formula_61 is the parent of a vertex formula_4
a "directed edge" of the descendant tree is defined by formula_73
in the direction of the canonical projection formula_74 onto the quotient formula_75.
In a descendant tree, the concepts of "parents" and "immediate descendants" can be generalized.
A vertex formula_76 is a descendant of a vertex formula_77,
and formula_77 is an ancestor of formula_76,
if either formula_76 is equal to formula_77
or there is a "path"
formula_82, where formula_83,
of directed edges from formula_76 to formula_77.
The vertices forming the path necessarily coincide with the iterated parents formula_86 of formula_76, with formula_88:
formula_89, where formula_83.
They can also be viewed as the successive "quotients" formula_91 "of p-class" formula_92 of formula_76
when the "p"-class of formula_76 is given by formula_95:
formula_96, where formula_97.
In particular, every non-trivial finite "p"-group formula_11 defines a maximal path (consisting of formula_99 edges)
formula_100
ending in the trivial group formula_102.
The last but one quotient of the maximal path of formula_4 is the elementary abelian "p"-group formula_104 of rank formula_105,
where formula_106 denotes the generator rank of formula_4.
Generally, the descendant tree formula_108 of a vertex formula_4 is the subtree of all descendants of formula_4, starting at the root formula_4.
The maximal possible descendant tree formula_112 of the trivial group formula_16 contains all finite "p"-groups and is exceptional,
since the trivial group formula_16 has all the infinitely many elementary abelian "p"-groups with varying generator rank formula_115 as its immediate descendants.
However, any non-trivial finite "p"-group (of order divisible by formula_2) possesses only finitely many immediate descendants.
"p"-covering group, "p"-multiplicator and nucleus.
Let formula_4 be a finite "p"-group with formula_118 "generators".
Our goal is to compile a complete list of pairwise non-isomorphic immediate descendants of formula_4.
It turns out that all immediate descendants can be obtained as quotients of a certain extension formula_120 of formula_4
which is called the "p"-covering group of formula_4 and can be constructed in the following manner.
We can certainly find a presentation of formula_4 in the form of an exact sequence
formula_124,
where formula_125 denotes the free group with formula_118 generators and formula_127 is an epimorphism with kernel formula_128.
Then formula_129 is a normal subgroup of formula_125 consisting of the defining "relations" for formula_131.
For elements formula_132 and formula_133,
the conjugate formula_134 and thus also the commutator formula_135 are contained in formula_76.
Consequently, formula_137 is a characteristic subgroup of formula_76,
and the "p"-multiplicator formula_139 of formula_4 is an elementary abelian "p"-group, since
formula_141.
Now we can define the "p"-covering group of formula_4 by
formula_143,
and the exact sequence
formula_144
shows that formula_120 is an extension of formula_4 by the elementary abelian "p"-multiplicator.
We call
formula_147
the "p"-multiplicator rank of formula_4.
Let us assume now that the assigned finite "p"-group formula_131 is of "p"-class formula_56.
Then the conditions formula_129 and formula_152 imply formula_153, according to the rule (R3),
and we can define the nucleus of formula_4 by
formula_155
as a subgroup of the "p"-multiplicator.
Consequently, the nuclear rank
formula_156
of formula_4 is bounded from above by the "p"-multiplicator rank.
Allowable subgroups of the "p"-multiplicator.
As before, let formula_4 be a finite "p"-group with formula_118 "generators".
Proposition.
Any "p"-elementary abelian central extension
formula_160
of formula_4
by a "p"-elementary abelian subgroup formula_162 such that formula_163
is a quotient of the "p"-covering group formula_120 of formula_4.
For the proof click "show" on the right hand side.
The reason is that, since formula_163, there exists an epimorphism formula_167 such that
formula_168, where formula_169 denotes the canonical projection.
Consequently, we have
formula_170
and thus formula_171.
Further, formula_172, since formula_173 is "p"-elementary,
and formula_174, since formula_173 is central.
Together this shows that formula_176
and thus formula_177 induces the desired epimorphism formula_178
such that formula_179.
In particular, an immediate descendant formula_180 of formula_4 is a "p"-elementary abelian central extension
formula_182
of formula_4,
since
formula_184 implies formula_185 and formula_186,
where formula_187.
Definition.
A subgroup formula_188 of the "p"-multiplicator of formula_4 is called allowable
if it is given by the kernel formula_190 of an epimorphism formula_178
onto an immediate descendant formula_180 of formula_4.
An equivalent characterization is that formula_194 is a proper subgroup which supplements the nucleus
formula_195.
Therefore, the first part of our goal to compile a list of all immediate descendants of formula_4 is done,
when we have constructed all allowable subgroups of formula_139 which supplement the nucleus formula_198,
where formula_99.
However, in general the list
formula_200,
where formula_201,
will be redundant,
due to isomorphisms formula_202 among the immediate descendants.
Orbits under extended automorphisms.
Two allowable subgroups formula_203 and formula_204 are called equivalent if the quotients formula_202,
that are the corresponding immediate descendants of formula_4, are isomorphic.
Such an isomorphism formula_207 between immediate descendants of formula_208 with formula_99 has the property that
formula_210
and thus induces an automorphism formula_211 of formula_4
which can be extended to an automorphism formula_213 of the "p"-covering group formula_214of formula_4.
The restriction of this extended automorphism formula_216 to the "p"-multiplicator formula_217 of formula_4 is determined uniquely by formula_219.
Since formula_220,
each extended automorphism formula_213 induces a permutation formula_222 of the allowable subgroups formula_188.
We define formula_224 to be the permutation group generated by all permutations induced by automorphisms of formula_4.
Then the map formula_226, formula_227 is an epimorphism
and the equivalence classes of allowable subgroups formula_188 are precisely the orbits of allowable subgroups under the action of the permutation group formula_77.
Eventually, our goal to compile a list formula_230 of all immediate descendants of formula_4 will be done,
when we select a representative formula_232 for each of the formula_233 orbits of allowable subgroups of formula_139 under the action of formula_77. 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 formula_4 is called capable (or extendable) if it possesses at least one immediate descendant, otherwise it is terminal (or a leaf). The nuclear rank formula_237 of formula_4 admits a decision about the capability of formula_4:
In the case of capability, formula_208 has immediate descendants of formula_245 different step sizes formula_246, in dependence on the index formula_247 of the corresponding allowable subgroup formula_248 in the "p"-multiplicator formula_217. When formula_4 is of order formula_251, then an immediate descendant of step size formula_252 is of order formula_253 formula_254.
For the related phenomenon of multifurcation of a descendant tree at a vertex formula_4 with nuclear rank formula_256 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 formula_246, 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 formula_252, of formula_4 by formula_233, resp. formula_261. Then we have formula_262.
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 formula_263 of capable immediate descendants in the usual format formula_264 as given by actual implementations of the "p"-group generation algorithm in the computer algebra systems GAP and MAGMA.
First, let formula_265.
We begin with groups having abelianization of type formula_266.
See Figure 4 in the article on descendant trees.
In contrast, groups with abelianization of type formula_284 are partially located beyond the limit of computability.
Next, let formula_303.
Corresponding groups with abelianization of type formula_304 have bigger descendant numbers than for formula_265.
Schur multiplier.
Via the isomorphism formula_318, formula_319
the quotient group formula_320
can be viewed as the additive analogue of the multiplicative group formula_321 of all roots of unity.
Let formula_2 be a prime number and formula_4 be a finite "p"-group with presentation formula_208 as in the previous section.
Then the second cohomology group formula_325 of the formula_4-module formula_327
is called the Schur multiplier of formula_4. It can also be interpreted as the quotient group formula_329.
I. R. Shafarevich
has proved that the difference between the relation rank formula_330 of formula_4
and the generator rank formula_106 of formula_4 is given by the minimal number of generators of the Schur multiplier of formula_4,
that is formula_335.
N. Boston and H. Nover
have shown that formula_336,
for all quotients formula_337 of "p"-class formula_338, formula_50,
of a pro-"p" group formula_4 with finite abelianization formula_341.
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 formula_4 with trivial Schur multiplier formula_343
is a terminal vertex in the descendant tree formula_112 of the trivial group formula_16,
that is, formula_346 formula_347 formula_241.