[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Automorphisms and Isomorphisms

Automorphisms and Isomorphisms

Subsections

Standard Presentation Algorithm

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 E.A. O'Brien (1994), "Isomorphism testing for p-groups", J. Symbolic Comput., 17, 133-147.]

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, it is possible to compute their standard presentations and to compare these -- if the two presentations are identical, then the groups are isomorphic, otherwise they are not. Hence to check whether two groups are isomorphic, first construct the standard presentation of each using the StandardPresentation function; then compare these using the IsIdenticalPresentation function.

Alternatively, a user can invoke the IsIsomorphic function. This function takes as input two p-groups, constructs their standard presentations class by class, and checks for equality.

StandardPresentation(F, p, c: parameters): GrpFP, RngIntElt, RngIntElt -> GrpPC, Map, [Map]
    Automorphisms: [ Map ]              Default: 
    Automorphisms: [ AlgMatElt ]        Default: 
    PAGSequence: BoolElt                Default: false
    StartClass: RngIntElt               Default: 1
    Metabelian: BoolElt                 Default: false
    Exponent: RngIntElt                 Default: 0
    Print: RngIntElt                    Default: 1
Here F is a finitely presented group with a user-supplied presentation. The function returns the standard presentation for the largest p-quotient of F having class c. It also returns a map from the user-supplied presentaton to the standard presentation, and a generating set for a supplement to the inner automorphism group of the group defined by the standard presentation.

    StartClass: RngIntElt               Default: 1

The default for StartClass is one. If a positive integer k is supplied for this parameter, then a pcp is constructed for the class k - 1 p-quotient using the pQuotient function. The Standard Presentation algorithm is then applied for each class from k to c.

Clearly, the presentation obtained in this manner may not be "standard" in the sense defined at the beginning of this section. However, such a facility may be useful when seeking to check whether two groups are isomorphic. Their presentations constructed by pQuotient may be identical to the end of class k - 1; hence there is no need to standardise them up to this point in order to verify isomorphism.

    Automorphisms: [ Map ]              Default: 

    Automorphisms: [ AlgMatElt ]        Default: 

Usually the StandardPresentation is invoked with the default StartClass value of 1 and no automorphisms need to be supplied by the user.

If StartClass is supplied with a value k different from 1, a generating set for the automorphism group of the largest class k - 1 p-quotient must also be supplied. The description of the automorphism group is similar to that supplied for GeneratepGroups: it is

See the example DefiningAutomorphisms below which illustrates these alternative descriptions.

    PAGSequence: BoolElt                Default: false

A PAG-generating sequence for a soluble group is a generating sequence which ascends the group via a polycyclic series with prime factors. If such a generating sequence exists and is supplied for the automorphism group of the class k - 1 p-quotient, it will improve significantly the performance of the algorithm.

    Print: RngIntElt                    Default: 1

Print := 0

No output.

Print := 1

Default value. Standard presentation is printed at the end of each class.

Print := 2

Report in detail on the construction of each class. In particular, provide detail on steps of algorithm, including the standard automorphism used.

    Metabelian: BoolElt                 Default: false

The p-quotient whose standard presentation is to be computed is assumed to be metabelian.

    Exponent: RngIntElt                 Default: 0

The p-quotient whose standard presentation is to be computed is assumed to satisfy the supplied exponent law.

StandardPresentation(G, k : parameters): GrpPC, RngIntElt -> GrpPC, Map, [Map]
StandardPresentation(G : parameters): GrpPC, RngIntElt -> GrpPC, Map, [Map],
Here, G is a p-group presented by an arbitrary pc presentation. By default, the standard presentation is constructed for G. If the argument k is supplied, then the standard presentation is computed for the largest p-quotient of G having class at most k.

This invocation of StandardPresentation supports the following optional parameters: Automorphisms, PAGSequence, Print, StartClass. All operate as described above.

IsIdenticalPresentation(G, H) : GrpPC, GrpPC -> BoolElt
True if G and H have identical presentations, false otherwise. If given the standard presentations for the groups G and H, IsIdenticalPresentation will determine if G and H are isomorphic.
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 returns an isomorphism from G to H.

Example GrpPC_StandardPresentation (H19E6)

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
> /* now check whether the class 3 2-quotients are isomorphic */
> IsIsomorphic(Q1, Q2);
false
> /* 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

The functions IsIsomorphic and StandardPresentation are expensive; here we have a list of groups and we want to find any isomorphisms amoung 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)>;
>       Q[k] := StandardPresentation (G, p, 10);
> 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

StandardPresentationProcess(F, p, k : parameters): GrpFP, RngIntElt, RngIntElt -> StdPresP
This function allows the user to interactively construct the standard presentation for a particular p-quotient of F. As part of the initialisation process, it sets up the standard presentation for the largest p-quotient of the finitely presented group F having class at most k. It returns a standard presentation process.
StandardPresentationProcess(G, k : parameters): GrpFP, RngIntElt -> StdPresP
Here, G is a p-group presented by an arbitrary pc presentation. The standard presentation process is computed for the largest p-quotient of G having class at most k. It returns a standard presentation process.
ExtendPresentation(~P, k): StdPresP, RngIntElt ->
ExtendPresentation(~P): StdPresP ->
This procedure allows the user to iterate the construction process. The standard presentation process P for a particular p-quotient of G is supplied as input to this function and the standard presentation for the p-quotient of G having some larger exponent-p class is constructed.

By default, this function takes as input a standard presentation process and extends the standard presentation by one class. An optional argument k may be supplied which specifies the desired class of the larger quotient. The process for the larger quotient is returned.

ExtractGroup(P) : StdPresP -> GrpPC
This function extracts the group S defined by the standard presentation associated with the process P and sets up S as a member of the category GrpPC of soluble groups.
ExtractAutomorphisms(P) : StdPresP -> [Map]
This function extracts a generating set for a supplement of the inner automorphism group of the group S defined by the standard presentation associated with the process P.
ExtractMapping(P) : StdPresP -> Map
This function extracts the mapping from the user-supplied group to the group defined by the standard presentation associated with the process P.

Example GrpPC_Interactive (H19E7)

This example demonstrates the use of the interactive processes to test whether 5-quotients of two fp-groups are isomorphic.

> /* group 1 */
> F1<a, b> := FreeGroup(2);
> G := quo< F1 | a^25, (b, a, a, a, b), (b, a, b, b, b),
>                      (b, a, b, a), b^5 = (a, b, a) >;
>
> /* group 2 */
> F2<a, b> := FreeGroup(2);
> H := quo< F2 | a^25, (b, a, a), (b, a, b, b, b, b) = 1, b^5 >;
>
> /* first compute standard presentation for class 1 quotient of group 1 */
> Q1 := StandardPresentationProcess(G, 5, 1: Print := 1);
>
> /* now compute standard presentation for class 1 quotient of group 2 */
> Q2 := StandardPresentationProcess(H, 5, 1: Print := 1);
>
> /* extend each presentation, checking for equality at end of each class */
> repeat
>    ExtendPresentation( Q1);
>    ExtendPresentation( Q2);
>    S1 := ExtractGroup(Q1);
>    S2 := ExtractGroup(Q2);
>    /* are the presentations identical? */
>    Equal := IsIdenticalPresentation(S1, S2);
>    print "Result is ", Equal;
> until Equal eq false;

The standard presentation for the class 2 5-quotient is Group: G # 1;2 to lower exponent-5 central class 2 has order 5^4

Non-trivial powers: .1^5 = .4

Non-trivial commutators: [ .2, .1 ] = .3

The standard presentation for the class 2 5-quotient is Group: H # 1;2 to lower exponent-5 central class 2 has order 5^4

Non-trivial powers: .1^5 = .4

Non-trivial commutators: [ .2, .1 ] = .3 Result is true

The standard presentation for the class 3 5-quotient is Group: $ # 1;2 to lower exponent-5 central class 3 has order 5^6

Non-trivial powers: .1^5 = .4 .2^5 = .5

Non-trivial commutators: [ .2, .1 ] = .3 [ .3, .1 ] = .5 [ .3, .2 ] = .6

The standard presentation for the class 3 5-quotient is Group: $ # 1;1 to lower exponent-5 central class 3 has order 5^5

Non-trivial powers: .1^5 = .4

Non-trivial commutators: [ .2, .1 ] = .3 [ .3, .1 ] = .5 [ .3, .2 ] = .5 Result is false


Automorphism Group Algorithm

The standard presentation machinery may also be used to compute a description of the automorphism group of a given p-group. [For a description of this algorithm, see E.A. O'Brien (1995), "Computing automorphism groups for p-groups", Proceedings of "Computational Algebra and Number Theory" (Sydney, 1992), pp. 83--90, Kluwer Academic Publishers, Dordrecht.]

A generating set for a supplement to the inner automorphism group is returned as a sequence of homomorphisms; each describes the action of a generator of the automorphism group on the generators of the group.

AutomorphismGroup(G): GrpPC -> [Mtrx]
G is a p-group presented by an arbitrary finite or pc-presentation. The function returns a generating set for a supplement to the inner automorphism group of G. This generating set is returned as a sequence of homomorphisms, where each describes the action of an automorphism on the generators of G.
[Next] [Prev] [Right] [Left] [Up] [Index] [Root]