Generating p-groups

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]

Generating p-groups

The p-group generation algorithm allows the construction of certain extensions, known as descendants, of a p-group. [For a description of this algorithm, see M.F. Newman (1977), "Determination of groups of prime-power order", Group Theory, Lecture Notes in Math., 573, (Canberra, 1975), pp. 73--84. Springer-Verlag, Berlin, Heidelberg, New York, and E.A. O'Brien (1990), "The p-group generation algorithm", J. Symbolic Comput., 9, 677--698.]

The input to the algorithm is a p-group G. The output is a sequence of p-group generation processes: each process provides access to a power-conjugate presentation for a descendant which satisfies chosen parameters and a description of the automorphism group of the descendant.

If G is not an elementary abelian p-group, then a description of its automorphism group must also be supplied.

A p-group generation process may also be supplied to GeneratepGroups in order to iterate the construction of descendants.

GeneratepGroups (G : parameters) : GrpPC -> [pgaProc]

GeneratepGroups (P : parameters) : pgaProc -> [pgaProc]

Supply the p-group G or a p-group generation process P.
The function GeneratepGroups returns a sequence of p-group generation processes. Each process provides access to a pcp for a descendant of G and to a sequence of generators for the automorphism group of this descendant. Each generator is a homomorphism which describes its action on the pcp generators of the group. The descendant may be extracted using ExtractGroup and a description of its automorphism group extracted using ExtractAutomorphisms. At least one of the three parameters OrderBound, ClassBound and StepSequence described below must be set.
    Automorphisms: [ AlgMatElt ]        Default: 
    Automorphisms: [ Map ]              Default: 
If G is an elementary abelian p-group, the user need not supply a description of its automorphism group. If G is not elementary abelian, then the user must supply a generating set for the automorphism group of G. Such a description can be one of two types:

a sequence of automorphisms specified using the mapping machinery in Magma; these could be computed directly using the AutomorphismGroup function or set up by the user.
a sequence of matrices which represent the action of the generators of the automophism group of G on the generators of the class 1 quotient of G.

See the example DefiningAutomorphisms below which illustrates these alternative descriptions.
    PAGSequence: BoolElt                Default: false
If the supplied description of the automorphism group is a PAG-generating sequence which ascends the automorphism group via a polycyclic series with prime factors, set PAGSequence true. If such a description is supplied, the performance of the algorithm is significantly improved.
    Exponent: RngIntElt                 Default: 0
Ensure that all descendants constructed have the supplied exponent.
    Metabelian: RngIntElt               Default: false
If true, ensure all descendants constructed are metabelian.
    OrderBound: RngIntElt               Default: 999
Given OrderBound := n, ensure all descendants constructed have order at most p^n.
    ClassBound: RngIntElt               Default: 63
Given ClassBound := c, ensure all descendants constructed have class at most c.
    StepSequence: [RngIntElt]           Default: null
The length of the given sequence is the number of iterations required. Each entry in the sequence is the required step size for the corresponding iteration of the algorithm. If the length of the supplied sequence is less than that required by a supplied class bound, the sequence is padded out to the required length by adjoining to it copies of the last element of the sequence.
    AllDescendants: BoolElt             Default: false
If true, calculate all descendants. Otherwise, calculate only the capable descendants.
    DisplayAutomorphisms: BoolElt       Default: false
If true, print extensions of automorphisms and automorphism matrices.
    DisplayPermutations: BoolElt        Default: false
If true, print degree of permutation group and constructed permutations.
    DisplayOrbitSummary: BoolElt        Default: false
If true, print summary of orbits constructed.
    DisplayOrbits: BoolElt              Default: false
If true, print complete orbits.
    DisplayGroups: BoolElt              Default: false
If true, print presentations of all groups constructed.
    DisplayAutGroups: BoolElt           Default: false
If true, print descriptions of all automorphism groups constructed.
    DisplayDetails: BoolElt             Default: false
If true, equivalent to choosing all of the above display flags.
    DisplayAlgorithmTrace: BoolElt      Default: false
If true, print trace details of algorithm.

ExtractGroup(P) : Process(pgaProc) -> GrpPC

This function extracts the group H defined by the pc-presentation associated with the p-group generation process P and sets up H as a member of the category GrpPC of soluble groups.

ExtractAutomorphisms(P) : Process(pgaProc) -> [Mat]

This function extracts a generating set for a supplement to the inner automorphism group of the group H having the pcp associated with the p-group generation process P. It returns a sequence of homomorphisms which describe the action of each generator on the pcp generators of H.

NuclearRank(P) : Process(pgaProc) -> RngIntElt

Return the rank of the nucleus of the p-group G defined by the process P.

pMultiplicatorRank(P) : Process(pgaProc) -> RngIntElt

Return the rank of the p-multiplicator of the p-group G defined by the process P.

Example `GrpPC_DefiningAutomorphisms (H19E9)`

In this example, the possible ways of defining generators of the automorphism group of G are illustrated.

> G := DihedralGroup(GrpPC, 16);
> G;
GrpPC : G of order 32 = 2^5
PC-Relations:
  G.2^2 = G.3, 
  G.3^2 = G.4, 
  G.4^2 = G.5, 
  G.2^G.1 = G.2 * G.3 * G.4 * G.5, 
  G.3^G.1 = G.3 * G.4 * G.5, 
  G.4^G.1 = G.4 * G.5
> /* the actions of the generators of the automorphism group of G
>    on the 2 generators of the class 1 quotient of G are supplied
>    as 2 x 5 matrices; row i of the matrix contains the exponents
>    of the images of generator i */
> R := RMatrixSpace(GF(2), 2, 5);
> a := R![1, 0, 0, 0, 1,
>         0, 1, 0, 0, 1];
> b := R![1, 0, 0, 1, 0,
>         0, 1, 0, 1, 0];
> c := R![1, 1, 1, 1, 1,
>         0, 1, 1, 1, 1];
> A := [a, b, c];
> T := GeneratepGroups(G: Automorphisms := A, PAGSequence := true,
>                         ClassBound := 5);

**************************************************
Starting group: G
Order: 2^5
Nuclear rank: 1
2-multiplicator rank: 3
# of immediate descendants of order 2^6 is 3
# of capable immediate descendants is 1

**************************************************
> /* alternatively, use the output of AutomorphismGroup as
>    the automorphism group description */
> A := AutomorphismGroup(G);
> A;
[
  Mapping from: GrpPC: G to GrpPC: G,
  Mapping from: GrpPC: G to GrpPC: G,
  Mapping from: GrpPC: G to GrpPC: G,
  Mapping from: GrpPC: G to GrpPC: G,
  Mapping from: GrpPC: G to GrpPC: G
]
> T := GeneratepGroups(G: Automorphisms := A, ClassBound := 5);

**************************************************
Starting group: G
Order: 2^5
Nuclear rank: 1
2-multiplicator rank: 3
# of immediate descendants of order 2^6 is 3
# of capable immediate descendants is 1

**************************************************

Example `GrpPC_GeneratepGroups (H19E10)`

In the following examples the Magma output has been edited slightly: the cases of `invalid starting group' have been omitted.

> /* what is the soluble length of 2-generator group of exponent 4? */ > > /* first set up c2 x c2 */ > > F := FreeGroup(2); > G := pQuotient(F, 2, 1); > > /* now, generate the groups having exponent 4 */ > > a := GeneratepGroups(G: Exponent := 4, > AllDescendants, ClassBound := 10);

************************************************** Starting group: G Order: 2^2 Nuclear rank: 3 2-multiplicator rank: 3 # of immediate descendants of order 2^3 is 3 # of immediate descendants of order 2^4 is 3 # of capable immediate descendants is 1 # of immediate descendants of order 2^5 is 1 # of capable immediate descendants is 1

************************************************** Starting group: G # 5;2 Order: 2^4 Nuclear rank: 1 2-multiplicator rank: 2 # of immediate descendants of order 2^5 is 1 # of capable immediate descendants is 1

************************************************** Starting group: G # 7;3 Order: 2^5 Nuclear rank: 2 2-multiplicator rank: 2 # of immediate descendants of order 2^6 is 1 # of capable immediate descendants is 1 # of immediate descendants of order 2^7 is 1 # of capable immediate descendants is 1

************************************************** Starting group: G # 5;2 # 1;1 Order: 2^5 Nuclear rank: 1 2-multiplicator rank: 2 # of immediate descendants of order 2^6 is 2

************************************************** Starting group: G # 7;3 # 1;1 Order: 2^6 Nuclear rank: 1 2-multiplicator rank: 2 # of immediate descendants of order 2^7 is 1

************************************************** Starting group: G # 7;3 # 2;2 Order: 2^7 Nuclear rank: 3 2-multiplicator rank: 3 # of immediate descendants of order 2^8 is 3 # of immediate descendants of order 2^9 is 3 # of capable immediate descendants is 1 # of immediate descendants of order 2^10 is 1 # of capable immediate descendants is 1

************************************************** Starting group: G # 7;3 # 2;2 # 6;2 Order: 2^9 Nuclear rank: 2 2-multiplicator rank: 3 # of immediate descendants of order 2^10 is 2 # of immediate descendants of order 2^11 is 2

************************************************** Starting group: G # 7;3 # 2;2 # 7;3 Order: 2^10 Nuclear rank: 2 2-multiplicator rank: 2 # of immediate descendants of order 2^11 is 1 # of immediate descendants of order 2^12 is 1

************************************************** > /* print the number of groups */ > "The number of 2-generator exponent 4 groups is ", # a; The number of 2-generator exponent 4 groups is 26 > > /* what are their soluble lengths? */ > for i := 1 to # a do > H := ExtractGroup(a[i]); > print "Group ", i, " has soluble length ", DerivedLength (H); > end for; Group 1 has soluble length 1 Group 2 has soluble length 2 Group 3 has soluble length 2 Group 4 has soluble length 1 Group 5 has soluble length 2 Group 6 has soluble length 2 Group 7 has soluble length 2 Group 8 has soluble length 2 Group 9 has soluble length 2 Group 10 has soluble length 2 Group 11 has soluble length 2 Group 12 has soluble length 2 Group 13 has soluble length 2 Group 14 has soluble length 2 Group 15 has soluble length 2 Group 16 has soluble length 2 Group 17 has soluble length 2 Group 18 has soluble length 2 Group 19 has soluble length 2 Group 20 has soluble length 2 Group 21 has soluble length 3 Group 22 has soluble length 3 Group 23 has soluble length 3 Group 24 has soluble length 3 Group 25 has soluble length 3 Group 26 has soluble length 3 > > /* alternatively, we can construct just > the metabelian groups of exponent 4 */ > b := GeneratepGroups(G: Exponent := 4, AllDescendants, > ClassBound := 10, Metabelian);

************************************************** Starting group: G # 5;2 # 1;1 Order: 2^5 Nuclear rank: 1 2-multiplicator rank: 2 # of immediate descendants of order 2^6 is 2

************************************************** Starting group: G # 7;3 # 1;1 Order: 2^6 Nuclear rank: 1 2-multiplicator rank: 2 # of immediate descendants of order 2^7 is 1

************************************************** > "Number of 2-generator metabelian groups of exponent 4 is ", # b; Number of 2-generator metabelian groups of exponent 4 is 20

Example `GrpPC_IsGood (H19E11)`

> /* can we find all 2-generator 3-groups of abundance zero;
>    such groups have order at most 3^5 */
>
> /* does a group have abundance k? that is, does the group have
>    a certain number of conjugacy classes */
>
> IsGoodGroup := function(G, k)
>
>    ncl := # Classes(G);
>
>    O := FactoredOrder(G);
>    p := O[1][1];
>    m := O[1][2];
>    n := Floor(m / 2);
>    e := m - n * 2;
>    Desired := n * (p^2 - 1) + p^e + k * (p - 1) * (p^2 - 1);
>
>    return (Desired eq ncl);
>
> end function;
>
> /* set up c3 x c3 */
>
> F := FreeGroup(2);
> G := pQuotient(F, 3, 1);
>
> a := GeneratepGroups(G: ClassBound := 4, AllDescendants,
>          OrderBound := 5);

**************************************************
Starting group: G
Order: 3^2
Nuclear rank: 3
3-multiplicator rank: 3
#  of immediate descendants of order 3^3 is 3
#  of capable immediate descendants is 2
#  of immediate descendants of order 3^4 is 3
#  of capable immediate descendants is 3
#  of immediate descendants of order 3^5 is 1
#  of capable immediate descendants is 1

**************************************************
Starting group: G # 1;1
Order: 3^3
Nuclear rank: 1
3-multiplicator rank: 3
#  of immediate descendants of order 3^4 is 2
#  of capable immediate descendants is 1

**************************************************
Starting group: G # 2;1
Order: 3^3
Nuclear rank: 2
3-multiplicator rank: 4
#  of immediate descendants of order 3^4 is 4
#  of capable immediate descendants is 1
#  of immediate descendants of order 3^5 is 7
#  of capable immediate descendants is 5

**************************************************
Starting group: G # 4;2
Order: 3^4
Nuclear rank: 2
3-multiplicator rank: 3
#  of immediate descendants of order 3^5 is 2
#  of capable immediate descendants is 2

**************************************************
Starting group: G # 5;2
Order: 3^4
Nuclear rank: 3
3-multiplicator rank: 4
#  of immediate descendants of order 3^5 is 9
#  of capable immediate descendants is 5

**************************************************
Starting group: G # 6;2
Order: 3^4
Nuclear rank: 2
3-multiplicator rank: 3
#  of immediate descendants of order 3^5 is 2
#  of capable immediate descendants is 1

**************************************************
Starting group: G # 1;1 # 1;1
Order: 3^4
Nuclear rank: 1
3-multiplicator rank: 3
#  of immediate descendants of order 3^5 is 2
#  of capable immediate descendants is 1

**************************************************
Starting group: G # 2;1 # 3;1
Order: 3^4
Nuclear rank: 1
3-multiplicator rank: 4
#  of immediate descendants of order 3^5 is 6
#  of capable immediate descendants is 1

**************************************************
Construction of descendants took 1710 milliseconds
>
> for i := 1 to # a do
>        G := ExtractGroup(a[i]);
>        if IsGoodGroup(G, 0) then
>              print "Group ", i, " of order ", Order(G),
>                  " has abundance 0";
>        end if;
> end for;
Group  2  of order  27  has abundance 0
Group  3  of order  27  has abundance 0
Group  10  of order  81  has abundance 0
Group  11  of order  81  has abundance 0
Group  12  of order  81  has abundance 0
Group  13  of order  81  has abundance 0
Group  39  of order  243  has abundance 0
Group  40  of order  243  has abundance 0
Group  41  of order  243  has abundance 0

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]