Isomorphism testing 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'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.

Subsections

• Automorphism Group Algorithm

StandardPresentation(G): GrpPC -> GrpPC, Map

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.

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

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

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

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.

Example GrpPGp_StandardPresentation (H20E4)

> 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

> IsIsomorphic(Q1, Q2);
false

> 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 of the sequence of groups, 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;

> 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

Automorphism Group Algorithm

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.

AutomorphismGroup(G): GrpPC -> GrpAuto

AutomorphismGroup(G: parameters): GrpPC -> GrpAuto

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.

Example GrpPGp_AutomorphismGroup (H20E5)

> 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 ]