Automorphism Group

General Soluble Group

In the case of a soluble non-\(p\)-group there are two algorithms available. By default, a lifting-based algorithm developed by M. Smith [Smith, 1994] and extended by Smith and Slattery to use second cohomology is used. Alternatively, there is also an algorithm developed by D. Howden [Howden, 2012], which uses the automorphism group of a Sylow \(p\)-subgroup of \(G\) to construct the automorphism group of \(G\).

Lifting Algorithm

The automorphism group is computed step-by-step considering a series of factors of \(G\) by terms of a characteristic series

\[G = G_1 > G_2 > \cdots > G_k > 1\]

such that \(G_i/G_{i+1}\) is elementary abelian for each \(i\). We compute the automorphism group \({\operatorname{Aut}}(G/G_2)\cong{\operatorname{GL}}(d,p)\) for some integer \(d\) and prime \(p\), and then lift through each of the elementary abelian layers \(G/G_3,\dots, G/G_{k-1}\), finally arriving at \({\operatorname{Aut}}(G/G_k) = {\operatorname{Aut}}(G)\). A group of type GrpAuto is returned. Details of the computation can be seen by setting the verbose flag AutomorphismGroup to true, and the characteristic series is available as the attribute CharacteristicSeries on the returned group. In addition to the usual properties of GrpAuto (such as Order, Ngens, etc.), two special fields, GenWeights and WeightSubgroupOrders, are provided for automorphism groups of (non \(p\)-group) pc-groups. These each relate to weight subgroups of the automorphism group. Let \(i\) be the largest subscript such that the automorphism acts trivially on \(G/G_i\). Then the automorphism is said to have weight \(2i+1\) if it acts non-trivially on \(G_i/G_{i+1}\), and weight \(2i+2\) if it acts trivially on \(G_i/G_{i+1}\). Note that there are no automorphisms of weight 2. The automorphisms of weight greater than or equal to a given value form a normal subgroup of \(A\).

AutomorphismGroup(G): GrpPC -> GrpAuto

Given a soluble group \(G\) presented by a pc-presentation, this function returns the automorphism group of \(G\) as a group of type GrpAuto.

HasAttribute(A, "GenWeights"): GrpAuto, MonStgElt -> BoolElt, [ RngIntElt ]

If the attribute GenWeights is defined for \(A\) then the function returns true, and a sequence of integers. This integer sequence indicates where each generator lies in the normal series of \(A\) corresponding to the action of the group on \(G\) (as described at the beginning of the section). If the attribute is not set then the sequence is unassigned. The function call AutomorphismGroup(G), where \(G\) has type GrpPC, always returns an automorphism group with this attribute set. In this case the sequence may also be obtained by the short form A`GenWeights.

HasAttribute({A, }{"WeightSubgroupOrders"}): GrpAuto, MonStgElt -> BoolElt, [ RngIntElt ]

If the attribute WeightSubgroupOrders is defined for \(A\) then the function returns true, and a sequence of integers. This sequence of integers gives the orders for the normal series of weight subgroups described at the beginning of the section. If the attribute is not set then the sequence is unassigned. The function call AutomorphismGroup(G), where \(G\) has type GrpPC, always returns an automorphism group with this attribute set. In this case the sequence may also be obtained by the short form A`WeightSubgroupOrders.

Example: Automorphism Group (ex-29a2d6)

An example using AutomorphismGroup and some related features. We build a group based on the structure of a finite field (multiplicative group acting on the additive group) and then compute its automorphism group. First, we set up the field.

> E := GF(2);
> F := GF(8);
> V,phi := VectorSpace(F,E);
> d := Dimension(V);
> x := PrimitiveElement(F);

Run in calculatorCopy input

Then, define a pc-group to act and define the action based on the multiplication in the field. Compute the matrix by mapping the vectors back to the field, multiplying by x, and then recording the result.

> C := CyclicGroup(GrpPC,Order(x));
> MR := MatrixRing(E, d);
> s := [];
> for i := 1 to d do
>  y := ((V.i)@@phi)*x;
>  s cat:= Eltseq(y);
> end for;

Run in calculatorCopy input

Turn the sequence of image components into a matrix and use the matrix to create a C-module. Then use that module to create the split extension.

> t := MR!s;
> M := GModule(C,[t]);
> G := Extension(M,C);
> G;
GrpPC : G of order 56 = 2^3 * 7
PC-Relations:
    G.1^7 = Id(G),
    G.2^2 = Id(G),
    G.3^2 = Id(G),
    G.4^2 = Id(G),
    G.2^G.1 = G.3,
    G.3^G.1 = G.4,
    G.4^G.1 = G.2 * G.3

Run in calculatorCopy input

Then we can compute the automorphism group of \(G\).

> A := AutomorphismGroup(G: Algorithm := "Default");
> A;
A group of automorphisms of GrpPC : G
Generators:
    Automorphism of GrpPC : G which maps:
        G.1 |--> G.1^2
        G.2 |--> G.3 * G.4
        G.3 |--> G.2 * G.4
        G.4 |--> G.3
    Automorphism of GrpPC : G which maps:
        G.1 |--> G.1
        G.2 |--> G.2 * G.3
        G.3 |--> G.3 * G.4
        G.4 |--> G.2 * G.3 * G.4
    Automorphism of GrpPC : G which maps:
        G.1 |--> G.1 * G.2 * G.3
        G.2 |--> G.2
        G.3 |--> G.3
        G.4 |--> G.4
    Automorphism of GrpPC : G which maps:
        G.1 |--> G.1 * G.3 * G.4
        G.2 |--> G.2
        G.3 |--> G.3
        G.4 |--> G.4
    Automorphism of GrpPC : G which maps:
        G.1 |--> G.1 * G.4
        G.2 |--> G.2
        G.3 |--> G.3
        G.4 |--> G.4
> [Order(x):x in Generators(A)];
[ 3, 2, 7, 2, 2 ]

Run in calculatorCopy input

Next, we can use the automorphisms to create an extension of \(G\).

> b := A.1;
> Order(b);
3
> tau := hom<G->G|[b(G.i):i in [1..NPCgens(G)]]>;
> D := CyclicGroup(GrpPC,Order(b));
> K := Extension(G,D,[tau]);
> K;
GrpPC : K of order 168 = 2^3 * 3 * 7
PC-Relations:
    K.1^3 = Id(K),
    K.2^7 = Id(K),
    K.3^2 = Id(K),
    K.4^2 = Id(K),
    K.5^2 = Id(K),
    K.2^K.1 = K.2^2,
    K.3^K.1 = K.4 * K.5,
    K.3^K.2 = K.4,
    K.4^K.1 = K.3 * K.5,
    K.4^K.2 = K.5,
    K.5^K.1 = K.4,
    K.5^K.2 = K.3 * K.4
> #Classes(K);
8

Run in calculatorCopy input

Finally, we examine information about the weight subgroups. We list only the orders of the terms of the characteristic series in \(G\) in order to save space.

> [Order(H): H in A`CharacteristicSeries];
[ 56, 8, 1 ]
> A`GenWeights;
[ 1, 3, 4, 4, 4 ]
> A`WeightSubgroupOrders;
[ 168, 56, 56, 8 ]

Run in calculatorCopy input

Lifting from the Automorphism Group of a Sylow \(p\)-subgroup

The algorithm developed by D. Howden [Howden, 2012] follows a different strategy to the Smith-Slattery lifting approach. Given a soluble group \(G\), the algorithm determines a suitable Sylow \(p\)-subgroup \(P\) of \(G\), and uses the automorphism group of \(P\) (using the algorithm for \(p\)-groups detailed below) to construct the automorphism group of \(G\). In cases where the automorphism group is soluble, the algorithm automatically constructs a pc-representation for it. Solubility of the returned group can then be tested via the IsSoluble intrinsic. The pc-representation obtained using the PCGroup intrinsic, and pc-generators (as automorphism maps) via the PCGenerators intrinsic. In some cases where the automorphism group is not soluble, the algorithm will construct a permutation representation during its construction. A group of type GrpAuto is returned. Details of the computation can be seen by setting the verbose flag AutomorphismGroupSolubleGroup to 1. A variation of this algorithm can be used for isomorphism testing.

AutomorphismGroupSolubleGroup(G: parameters): GrpPC -> GrpAuto

p: [RngIntElt]                    Default: 1

Given a soluble group \(G\) presented by a pc-presentation, this function returns the automorphism group of \(G\) as a group of type GrpAuto.

A prime \(p\) dividing the order of \(G\). The automorphism group of the Sylow \(p\)-subgroup is then used to construct the automorphism group of \(G\). If the \(p\)-core of \(G\) is trivial then an error is given. The default value of \(p = 1\) indicates that the algorithm should take \(p\) to be the prime giving the largest Sylow \(p\)-subgroup of \(G\).

IsIsomorphicSolubleGroup(G, H: parameters): GrpPC, GrpPC -> BoolElt, Map

p: [RngIntElt]                    Default: 1

Returns true if the soluble groups \(G\), \(H\) presented by pc-presentations, are isomorphic, and false otherwise. Where the groups are isomorphic, a mapping \(G\to H\) is also returned.

A prime \(p\) dividing the order of \(G\) (assuming that the orders of \(G\) and \(H\) are the same). The algorithm then tests Sylow \(p\)-subgroups of \(G\) and \(H\) for isomorphism and attempts to extend these isomorphisms to an isomorphism \(G\to H\). If the \(p\)-cores of \(G\) and \(H\) are trivial then an error is given. The default value of \(p = 1\) indicates that the algorithm should take \(p\) to be the prime giving the largest Sylow \(p\)-subgroup of \(G\).

Example: Automorphism Group Soluble Group (ex-249c9b)

An example using AutomorphismGroupSolubleGroup and some related features. We use a group from the solgps library.

> load solgps;
> G := G10();
> FactoredOrder(G);
[ <2, 18>, <7, 4> ]
> time A := AutomorphismGroupSolubleGroup(G);
Time: 18.220
> time R_A, phi_A := PCGroup(A);
Time: 0.000
> FactoredOrder(R_A);
[ <2, 20>, <3, 2>, <7, 6> ]

Run in calculatorCopy input

\(p\)-group

For a description of the algorithm used to construct the automorphism group of a \(p\)-group, see [Eick et al., 2002].

While it is difficult to state very firm guidelines for the performance of the algorithm, our experience suggests that it has most difficulty in constructing automorphism groups of \(p\)-groups of “large” Frattini rank (say rank larger than about 6) and \(p\)-class 2. If the group has larger \(p\)-class, then it usually has more characteristic structure and the algorithm exploits this. The order of a group is not a useful guide to the difficulty of the computation.

SetVerbose ("AutomorphismGroup", 1) provides information on the progress of the algorithm.

AutomorphismGroup(G: parameters): GrpPC -> GrpAuto

CharacteristicSubgroups: [GrpPC]                    Default: []

The group \(G\) is a \(p\)-group described by a pc-presentation. The function returns the automorphism group of \(G\) as a group of type GrpAuto.

A list of known characteristic subgroups of \(G\); these may improve the efficiency of the construction. Note that the algorithm simply accepts that the supplied subgroups are fixed under the action of the automorphism group; it does not verify that they are in fact characteristic.

Example: p Automorphism Group (ex-f1bbe5)

> G := SmallGroup (64, 78);
> A := AutomorphismGroup (G);
> #A;
1024
> A.1;
    Automorphism of GrpPC : G which maps:
        G.1 |--> G.1
        G.2 |--> G.2
        G.3 |--> G.1 * G.3
        G.4 |--> G.4
        G.5 |--> G.5
        G.6 |--> G.4 * G.6
> Order (A.1);
4
> a := A.1^2; [a (G.i): i in [1..6]];
[ G.1, G.2, G.3 * G.5, G.4, G.5, G.6 ]

Run in calculatorCopy input

OrderAutomorphismGroupAbelianPGroup(A): SeqEnum -> RngIntElt

Order of automorphism group of abelian \(p\)-group \(G\) where \(A = [a_1, a_2, \ldots]\) and \(G = C_{a_1} \times C_{a_2} \times \ldots\).

Example: subgroupsabelianpgroups (ex-c99f0c)

Subgroups of \(C_4 \times C_8 \times C_{64}\).

> NumberOfSubgroupsAbelianPGroup ([4, 8, 64]);
[ 7, 35, 91, 139, 171, 171, 139, 91, 35, 7, 1 ]

Run in calculatorCopy input

Hence, for example, there are 7 subgroups of order 2 and 139 subgroups of order \(2^4\).

> OrderAutomorphismGroupAbelianPGroup ([4, 8, 64]);
4194304

Run in calculatorCopy input

Isomorphism and Standard Presentations

The pQuotient command returns a power-conjugate presentation for a given \(p\)-group but this presentation depends on the user-supplied description of the group. The Standard Presentation algorithm computes a “canonical” presentation for the \(p\)-group, which is independent of the user-supplied description. For a description of this algorithm, see [O'Brien, 1994]. The canonical or standard presentation of a given \(p\)-group is the power-conjugate presentation obtained when a description of the group is computed using the default implementation of the \(p\)-group generation algorithm. Hence, two groups in the same isomorphism class have identical standard presentations. Given two \(p\)-groups, if their standard presentations are identical, then the groups are isomorphic, otherwise they are not. Hence to decide whether two groups are isomorphic, we can first construct the standard presentation of each using the StandardPresentation function and then compare these presentations using the IsIdenticalPresentation function.

While it is difficult to state very firm guidelines for the performance of the algorithm, our experience suggests that the difficulty of deciding isomorphism between \(p\)-groups is governed by their Frattini rank and is most practical for \(p\)-groups of rank at most 5. The order of a group is not a useful guide to the difficulty of the computation.

SetVerbose ("Standard", 1) will provide information on the progress of the algorithm.

StandardPresentation(G): GrpPC -> GrpPC, Map

StandardPresentation(G: parameters): GrpPC -> GrpAuto

StartClass: RngIntElt                    Default: 1

The group \(G\) is a \(p\)-group presented by an arbitrary pc-presentation. The group \(H\) defined by its standard presentation is returned together with a map from \(G\) to \(H\).

If StartClass is \(k\), then use pQuotient to construct the class \(k - 1\) \(p\)-quotient of \(G\) and standardize the presentation only from class \(k\) onwards.

IsIdenticalPresentation(G, H): GrpPC, GrpPC -> BoolElt

Returns true if \(G\) and \(H\) have identical presentations, false otherwise.

IsIsomorphic(G, H): GrpPC, GrpPC -> BoolElt, Map, GrpPC

The function returns true if the \(p\)-groups \(G\) and \(H\) are isomorphic, false otherwise. It constructs their standard presentations class by class, and checks for equality. If they are isomorphic, it also returns an isomorphism from \(G\) to \(H\) and the isomorphism class representative.

Example: Standard Presentation (ex-75ee54)

In the next two examples, we investigate whether particular \(p\)-quotients of fp-groups are isomorphic.

> F<x, y, t> := FreeGroup(3);
> G := quo< F | x*y^2*x^-1=y^-2, y*x^2*y^-1=x^-2, x^2=t^2, y^2=(t^-1*x)^2,
>                      t*(x*y)^2=(x*y)^2*t >;
> Q1 := pQuotient(G, 2, 3: Print := 1);
Lower exponent-2 central series for G
Group: G to lower exponent-2 central class 1 has order 2^3
Group: G to lower exponent-2 central class 2 has order 2^7
Group: G to lower exponent-2 central class 3 has order 2^11
> H := quo< F | x*y^2*x^-1=y^-2, y*x^2*y^-1=x^-2, x^2=t^2*(x*y)^2,
>                      y^2=(t^-1*x)^2, t*(x*y)^2=(x*y)^2*t >;
> Q2 := pQuotient(H, 2, 3: Print := 1);
Lower exponent-2 central series for H
Group: H to lower exponent-2 central class 1 has order 2^3
Group: H to lower exponent-2 central class 2 has order 2^7
Group: H to lower exponent-2 central class 3 has order 2^11

Run in calculatorCopy input

Now check whether the class 3 2-quotients are isomorphic.

> IsIsomorphic(Q1, Q2);
false

Run in calculatorCopy input

In the next example, we construct an explicit isomorphism between two 5-groups.

> F<a, b> := Group<a, b | a^5, b^5, (a * b * a)^5 = (b, a, b) >;
> G := pQuotient (F, 5, 6 : Print := 1);
Lower exponent-5 central series for F
Group: F to lower exponent-5 central class 1 has order 5^2
Group: F to lower exponent-5 central class 2 has order 5^3
Group: F to lower exponent-5 central class 3 has order 5^4
Group: F to lower exponent-5 central class 4 has order 5^5
Group: F to lower exponent-5 central class 5 has order 5^7
Group: F to lower exponent-5 central class 6 has order 5^8
> G;
GrpPC : G of order 390625 = 5^8
PC-Relations:
G.2^G.1 = G.2 * G.3,
G.3^G.1 = G.3 * G.4,
G.3^G.2 = G.3 * G.6 * G.7^4 * G.8^4,
G.4^G.1 = G.4 * G.5,
G.4^G.2 = G.4 * G.7 * G.8,
G.4^G.3 = G.4 * G.7^4 * G.8,
G.5^G.1 = G.5 * G.6,
G.5^G.2 = G.5 * G.7,
G.5^G.3 = G.5 * G.8^2,
G.6^G.2 = G.6 * G.8,
G.7^G.1 = G.7 * G.8^3
> K<a, b> := Group<a, b | a^5, b^5, (b * a * b)^5 = (b, a, b) >;
> H := pQuotient (K, 5, 6 : Print := 1);
Lower exponent-5 central series for K
Group: K to lower exponent-5 central class 1 has order 5^2
Group: K to lower exponent-5 central class 2 has order 5^3
Group: K to lower exponent-5 central class 3 has order 5^4
Group: K to lower exponent-5 central class 4 has order 5^5
Group: K to lower exponent-5 central class 5 has order 5^7
Group: K to lower exponent-5 central class 6 has order 5^8
> H;
GrpPC : H of order 390625 = 5^8
PC-Relations:
H.2^H.1 = H.2 * H.3,
H.3^H.1 = H.3 * H.4,
H.3^H.2 = H.3 * H.6^2 * H.7^2 * H.8^2,
H.4^H.1 = H.4 * H.5,
H.4^H.2 = H.4 * H.7,
H.4^H.3 = H.4 * H.7^4 * H.8,
H.5^H.1 = H.5 * H.6,
H.5^H.2 = H.5 * H.7,
H.5^H.3 = H.5 * H.8^2,
H.6^H.2 = H.6 * H.8,
H.7^H.1 = H.7 * H.8^3
> flag, phi := IsIsomorphic (G, H);
> flag;
true
> for g in PCGenerators (G) do print g, "--->", phi (g); end for;
G.1 ---> H.1
G.2 ---> H.2^3 * H.4^3 * H.5^3 * H.6^2 * H.7^4 * H.8^3
G.3 ---> H.3^3 * H.5^3 * H.6^4 * H.8^3
G.4 ---> H.4^3 * H.6^3 * H.7^2 * H.8^3
G.5 ---> H.5^3 * H.8
G.6 ---> H.6^3
G.7 ---> H.7^4
G.8 ---> H.8^4

Run in calculatorCopy input

The functions IsIsomorphic and StandardPresentation are expensive. Here we have a list of groups and we want to find any isomorphisms among the collection. Rather than repeatedly applying IsIsomorphic, we first construct and store standard presentations for each group in the sequence, and then quickly compare these using IsIdenticalPresentation.

> F<a, b> := FreeGroup (2);
> p := 7;
> Q := [];
> for k := 1 to p - 1 do
>       G := quo< F | a^p = (b, a, a), b^p = a^(k*p), (b, a, b)>;
>       H := pQuotient (G, p, 10);
>       Q[k] := StandardPresentation (H);
> end for;

Run in calculatorCopy input

Now run over the list of standard presentations and check for equality.

> for i in [2..p - 1] do
>    for j in [1.. i - 1] do
>       if IsIdenticalPresentation (Q[i], Q[j]) then
>          print "Standard Presentations  ", i, " and ", j, " are identical";
>       end if;
>    end for;
> end for;
Standard Presentations   2  and  1  are identical
Standard Presentations   4  and  1  are identical
Standard Presentations   4  and  2  are identical
Standard Presentations   5  and  3  are identical
Standard Presentations   6  and  3  are identical
Standard Presentations   6  and  5  are identical

Run in calculatorCopy input