P-group generation algorithm

In mathematics, specifically group theory, finite groups of prime power order , for a fixed prime number and varying integer exponents , 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

edit

For a finite p-group  , the lower exponent-p central series (briefly lower p-central series) of   is a descending series   of characteristic subgroups of  , defined recursively by

  and  , for  .

Since any non-trivial finite p-group   is nilpotent, there exists an integer   such that   and   is called the exponent-p class (briefly p-class) of  . Only the trivial group   has  . Generally, for any finite p-group  , its p-class can be defined as  .

The complete lower p-central series of   is therefore given by

 ,

since   is the Frattini subgroup of  .

For the convenience of the reader and for pointing out the shifted numeration, we recall that the (usual) lower central series of   is also a descending series   of characteristic subgroups of  , defined recursively by

  and  , for  .

As above, for any non-trivial finite p-group  , there exists an integer   such that   and   is called the nilpotency class of  , whereas   is called the index of nilpotency of  . Only the trivial group   has  .

The complete lower central series of   is given by

 ,

since   is the commutator subgroup or derived subgroup of  .

The following Rules should be remembered for the exponent-p class:

Let   be a finite p-group.

R

  1. Rule:  , since the   descend more quickly than the  .
  2. Rule: If  , for some group  , then  , for any  .
  3. Rule: For any  , the conditions   and   imply  .
  4. Rule: Let  . If  , then  , for all  , in particular,  , for all  .

Parents and descendant trees

edit

The parent   of a finite non-trivial p-group   with exponent-p class   is defined as the quotient   of   by the last non-trivial term   of the lower exponent-p central series of  . Conversely, in this case,   is called an immediate descendant of  . The p-classes of parent and immediate descendant are connected by  .

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   is the parent of a vertex   a directed edge of the descendant tree is defined by   in the direction of the canonical projection   onto the quotient  .

In a descendant tree, the concepts of parents and immediate descendants can be generalized. A vertex   is a descendant of a vertex  , and   is an ancestor of  , if either   is equal to   or there is a path

 , where  ,

of directed edges from   to  . The vertices forming the path necessarily coincide with the iterated parents   of  , with  :

 , where  .

They can also be viewed as the successive quotients   of p-class   of   when the p-class of   is given by  :

 , where  .

In particular, every non-trivial finite p-group   defines a maximal path (consisting of   edges)

 

 

ending in the trivial group  . The last but one quotient of the maximal path of   is the elementary abelian p-group   of rank  , where   denotes the generator rank of  .

Generally, the descendant tree   of a vertex   is the subtree of all descendants of  , starting at the root  . The maximal possible descendant tree   of the trivial group   contains all finite p-groups and is exceptional, since the trivial group   has all the infinitely many elementary abelian p-groups with varying generator rank   as its immediate descendants. However, any non-trivial finite p-group (of order divisible by  ) possesses only finitely many immediate descendants.

p-covering group, p-multiplicator and nucleus

edit

Let   be a finite p-group with   generators. Our goal is to compile a complete list of pairwise non-isomorphic immediate descendants of  . It turns out that all immediate descendants can be obtained as quotients of a certain extension   of   which is called the p-covering group of   and can be constructed in the following manner.

We can certainly find a presentation of   in the form of an exact sequence

 ,

where   denotes the free group with   generators and   is an epimorphism with kernel  . Then   is a normal subgroup of   consisting of the defining relations for  . For elements   and  , the conjugate   and thus also the commutator   are contained in  . Consequently,   is a characteristic subgroup of  , and the p-multiplicator   of   is an elementary abelian p-group, since

 .

Now we can define the p-covering group of   by

 ,

and the exact sequence

 

shows that   is an extension of   by the elementary abelian p-multiplicator. We call

 

the p-multiplicator rank of  .

Let us assume now that the assigned finite p-group   is of p-class  . Then the conditions   and   imply  , according to the rule (R3), and we can define the nucleus of   by

 

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

 

of   is bounded from above by the p-multiplicator rank.

Allowable subgroups of the p-multiplicator

edit

As before, let   be a finite p-group with   generators.

Proposition. Any p-elementary abelian central extension

 

of   by a p-elementary abelian subgroup   such that   is a quotient of the p-covering group   of  .

For the proof click show on the right hand side.

Proof

The reason is that, since  , there exists an epimorphism   such that  , where   denotes the canonical projection. Consequently, we have

 

and thus  . Further,  , since   is p-elementary, and  , since   is central. Together this shows that   and thus   induces the desired epimorphism   such that  .

In particular, an immediate descendant   of   is a p-elementary abelian central extension

 

of  , since

  implies   and  ,

where  .

Definition. A subgroup   of the p-multiplicator of   is called allowable if it is given by the kernel   of an epimorphism   onto an immediate descendant   of  .

An equivalent characterization is that   is a proper subgroup which supplements the nucleus

 .

Therefore, the first part of our goal to compile a list of all immediate descendants of   is done, when we have constructed all allowable subgroups of   which supplement the nucleus  , where  . However, in general the list

 ,

where  , will be redundant, due to isomorphisms   among the immediate descendants.

Orbits under extended automorphisms

edit

Two allowable subgroups   and   are called equivalent if the quotients  , that are the corresponding immediate descendants of  , are isomorphic.

Such an isomorphism   between immediate descendants of   with   has the property that   and thus induces an automorphism   of   which can be extended to an automorphism   of the p-covering group  of  . The restriction of this extended automorphism   to the p-multiplicator   of   is determined uniquely by  .

Since  , each extended automorphism   induces a permutation   of the allowable subgroups  . We define   to be the permutation group generated by all permutations induced by automorphisms of  . Then the map  ,   is an epimorphism and the equivalence classes of allowable subgroups   are precisely the orbits of allowable subgroups under the action of the permutation group  .

Eventually, our goal to compile a list   of all immediate descendants of   will be done, when we select a representative   for each of the   orbits of allowable subgroups of   under the action of  . 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

edit

A finite p-group   is called capable (or extendable) if it possesses at least one immediate descendant, otherwise it is terminal (or a leaf). The nuclear rank   of   admits a decision about the capability of  :

  •   is terminal if and only if  .
  •   is capable if and only if  .

In the case of capability,   has immediate descendants of   different step sizes  , in dependence on the index   of the corresponding allowable subgroup   in the p-multiplicator  . When   is of order  , then an immediate descendant of step size   is of order    .

For the related phenomenon of multifurcation of a descendant tree at a vertex   with nuclear rank   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  , which is very convenient in the case of huge descendant numbers (see the next section).

Numbers of immediate descendants

edit

We denote the number of all immediate descendants, resp. immediate descendants of step size  , of   by  , resp.  . Then we have  . 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   of capable immediate descendants in the usual format   as given by actual implementations of the p-group generation algorithm in the computer algebra systems GAP and MAGMA.

First, let  .

We begin with groups having abelianization of type  . See Figure 4 in the article on descendant trees.

  • The group   of coclass   has ranks  ,   and descendant numbers  ,  .
  • The group   of coclass   has ranks  ,   and descendant numbers  ,  .
  • One of its immediate descendants, the group  , has ranks  ,   and descendant numbers  ,  .

In contrast, groups with abelianization of type   are partially located beyond the limit of computability.

  • The group   of coclass   has ranks  ,   and descendant numbers  ,  .
  • The group   of coclass   has ranks  ,   and descendant numbers  ,   unknown.
  • The group   of coclass   has ranks  ,   and descendant numbers  ,   unknown.

Next, let  .

Corresponding groups with abelianization of type   have bigger descendant numbers than for  .

  • The group   of coclass   has ranks  ,   and descendant numbers  ,  .
  • The group   of coclass   has ranks  ,   and descendant numbers  ,  .

Schur multiplier

edit

Via the isomorphism  ,   the quotient group   can be viewed as the additive analogue of the multiplicative group   of all roots of unity.

Let   be a prime number and   be a finite p-group with presentation   as in the previous section. Then the second cohomology group   of the  -module   is called the Schur multiplier of  . It can also be interpreted as the quotient group  .

I. R. Shafarevich[4] has proved that the difference between the relation rank   of   and the generator rank   of   is given by the minimal number of generators of the Schur multiplier of  , that is  .

N. Boston and H. Nover[5] have shown that  , for all quotients   of p-class  ,  , of a pro-p group   with finite abelianization  .

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   with trivial Schur multiplier   is a terminal vertex in the descendant tree   of the trivial group  , that is,      .

Examples

edit
  • A finite p-group   has a balanced presentation   if and only if  , that is, if and only if its Schur multiplier   is trivial. Such a group is called a Schur group and it must be a leaf in the descendant tree  .
  • A finite p-group   satisfies   if and only if  , that is, if and only if it has a non-trivial cyclic Schur multiplier  . Such a group is called a Schur+1 group.

References

edit
  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 (5–6): 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.{{cite book}}: CS1 maint: multiple names: authors list (link)
  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. ^ 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.{{cite book}}: CS1 maint: multiple names: authors list (link)
  6. ^ Boston, N., Bush, M. R., Hajir, F. (2013). "Heuristics for p-class towers of imaginary quadratic fields". Math. Ann. arXiv:1111.4679.{{cite journal}}: CS1 maint: multiple names: authors list (link)