In the case of a soluble non-p-group there are two algorithms available. By default, a lifting-based algorithm developed by M. Smith [Smi94] and extended by Smith and Slattery to use second cohomology is used. Alternatively, there is also an algorithm developed by D. Howden [How12], which uses the automorphism group of a Sylow p-subgroup of G to construct the automorphism group of G.
The automorphism group is computed step-by-step considering a series of factors of G by terms of a characteristic series
G = G1 > G2 > ... > Gk > 1
such that Gi/Gi + 1 is elementary abelian for each i. We compute the automorphism group Aut(G/G2) isomorphic to GL(d, p) for some integer d and prime p, and then lift through each of the elementary abelian layers G/G3, ..., G/Gk - 1, finally arriving at Aut(G/Gk) = 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/Gi. Then the automorphism is said to have weight 2i + 1 if it acts non-trivially on Gi/Gi + 1, and weight 2i + 2 if it acts trivially on Gi/Gi + 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.
Given a soluble group G presented by a pc-presentation, this function returns the automorphism group of G as a group of type GrpAuto.
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.
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.
> E := GF(2); > F := GF(8); > V,phi := VectorSpace(F,E); > d := Dimension(V); > x := PrimitiveElement(F);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;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
Then we can compute the automorphism group of G.
> A := AutomorphismGroup(G);
> 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 ]
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
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 ]
The algorithm developed by D. Howden [How12] 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.
Given a soluble group G presented by a pc-presentation, this function
returns the automorphism group of G as a group of type GrpAuto.
p: [RngIntElt] Default: 1;
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.
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.
p: [RngIntElt] Default: 1;
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.
> 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> ]
For a description of the algorithm used to construct the automorphism group of a p-group, see [ELGO02].
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.
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.
CharacteristicSubgroups: [GrpPC] Default: [];
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.
> 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 ]
Order of automorphism group of abelian p-group G where A = [a1, a2, ... ] and G = Ca1 x Ca2 x ... .
> NumberOfSubgroupsAbelianPGroup ([4, 8, 64]); [ 7, 35, 91, 139, 171, 171, 139, 91, 35, 7, 1 ]Hence, for example, there are 7 subgroups of order 2 and 139 subgroups of order 24.
> OrderAutomorphismGroupAbelianPGroup ([4, 8, 64]); 4194304
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'B94].
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.
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.
StartClass: RngIntElt Default: 1
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.
Returns true if G and H have identical presentations, false otherwise.
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.
> 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^11Now check whether the class 3 2-quotients are isomorphic.
> IsIsomorphic(Q1, Q2); falseIn 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
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;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