Constructive Recognition for Simple Groups

For each finite non-abelian simple group \(S\), we designate a specific standard copy of \(S\). The standard copy has a designated set of standard generators. For example, the standard copy of \({\operatorname{Alt}}(n)\) is on \(n\) points; its standard generators are \((1,2,3)\) and either of \((3,\ldots, n)\) or \((1, 2)(3,\ldots, n)\) according to the parity of \(n\). For a projective representation, the standard copy is the quotient of a matrix group by its scalar subgroup. For example, the standard copy of \({\operatorname{PSL}}(n,q)\) is the quotient of \({\operatorname{SL}}(n,q)\) by its scalar subgroup.

To compute in a copy \(G\) of \(S\), we first construct effective isomorphisms between \(G\) and its standard copy. We do this by finding generators in \(G\) that correspond to the standard generators of \(S\) under an isomorphism. More formally, a constructive recognition algorithm for a non-abelian simple group \(G\) (possibly with decorations) solves the following problem: construct an isomorphism \(\phi\) from \(G\) to a standard copy \(S\) of \(G\), such that \(\phi(g)\) can be computed efficiently for every \(g \in G\). This is done by constructing standard generators in both \(G\) and its standard copy \(S\).

A rewriting algorithm for \(G\) solves the constructive membership problem: given \(g \in U \geq G = \langle X \rangle\), decide whether or not \(g \in G\), and if so express \(g\) as an SLP in \(X\). (Here \(U\) is the generic overgroup of \(G\), such as \({\operatorname{GL}}(d,q)\) or \({\operatorname{Sym}}(n)\).) The rewriting algorithm is used to make the isomorphism between \(S\) and \(G\) effective. To compute the image of an arbitrary element \(s\) of \(S\) in \(G\), we first write \(s\) as an SLP in the standard generators of \(S\) and then evaluate the SLP in the copy of the standard generators in \(G\).

To verify that the homomorphism from \(S\) to \(G\) is an isomorphism, we can evaluate in \(G\) a standard presentation for \(S\) on its standard generators. If the copy of the standard generators in \(G\) satisfy the presentation, then we have proved that we have an isomorphism.

For a detailed discussion of these topics, see [Leedham-Green and O'Brien, 2009, O'Brien, 2011]. Here we discuss recognition of classical and exceptional groups. See RecogniseAlternatingOrSymmetric for alternating groups.

Constructive Recognition for Classical Groups

ClassicalStandardGenerators(type, d, q): MonStgElt, RngIntElt, RngIntElt -> []

This intrinsic produces the standard generators of Leedham-Green and O’Brien for the quasisimple classical group of specified type in dimension \(d\) over a field of size \(q\). The type is designated by the argument type which must be one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”. The standard generators generate a specific copy of a classical group and are defined in [Leedham-Green and O'Brien, 2009] and [Dietrich et al., 2013].

ClassicalConstructiveRecognition(G, type, d, q): GrpMat[FldFin], MonStgElt, RngIntElt, RngIntElt -> BoolElt, Map, Map, Map, Map, SeqEnum, SeqEnum

ClassicalConstructiveRecognition(G): GrpMat[FldFin] -> BoolElt, SeqEnum, SeqEnum

The input group \(G = \langle X \rangle\) is a permutation group, or a matrix group defined over a finite field. It must be isomorphic to a central quotient of a classical group of specified type in dimension \(d\) over a field of size \(q\). The type is designated by one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”. The function constructs standard generators for \(G\). If it is successful, then return true; four maps \(m_1, m_2, m_3, m_4\); standard generators \({\cal S}\) for \(G\); and their SLPs in \(X\); otherwise return false. The map \(m_1\) is from \(G\) to the standard copy \(S\) of \(G\); the map \(m_2\) is from \(S\) to \(G\); the map \(m_3\) is from \(G\) to WordGroup(G); the map \(m_4\) is from WordGroup(G) to \(G\). Since, in general, \(G\) is isomorphic to a central quotient of \(S\), the maps \(m_1\) and \(m_2\) are homomorphisms modulo scalars.

In the second signature, \(G\) must be a matrix group defined over a finite field such that \(G = \langle X \rangle\) is conjugate to a quasisimple classical group in its natural representation in dimension at least 2. The intrinsic constructs a copy \({\cal S}\) in \(G\) of the generators defined by StandardGenerators. If \(G\) is quasisimple and classical, then the function returns true, the standard generators \({\cal S}\), and SLPs for these in \(X\); otherwise it returns false.

The algorithms used are described in [Leedham-Green and O'Brien, 2009], [Dietrich et al., 2013], and [Dietrich et al., 2015]. The implementations for even and odd characteristic were developed by Heiko Dietrich and Eamonn O’Brien respectively. Some base case functions were implemented by Kenneth Clarkson.

Example: Classical Constructive Recognition (ex-0be2ca)

We illustrate these functions with two examples.

> G := Sp (6, 5^3);
> G := ExteriorSquare (G);
> f, m1, m2, m3, m4, E, W := ClassicalConstructiveRecognition( G, "Sp", 6, 5^3 );

> Q, R := ClassicalStandardPresentation ("Sp", 6, 5^3);
> #{Evaluate( r, E ) : r in R} eq 1;
true
> x := Random (G);
> y := m1 (x);
> y;
> w := m3 (x);
> "Length of SLP is ", #w;
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq x;
true
> E eq Evaluate( W, [G.i : i in [ 1 .. Ngens( G )]]);

> G := PSL( 6, 4 );
> f, m1, m2, m3, m4, E, W := ClassicalConstructiveRecognition( G, "SL", 6, 4 );
> E eq Evaluate( W, [G.i : i in [ 1 .. Ngens( G )]]);
true
>
> Q, rels := ClassicalStandardPresentation( "SL" , 6, 4);
> #{Evaluate( r, E ) : r in rels} eq 1;
true
>
> g := Random( G );
> s := m1( g );
> s in SL(6,4);
true
> m2( s ) eq g;
true
>
> h := Random( SL( 6, 4 ) );
> g := m2( h );
> g in G;
true
> m1( g ) eq h;
false
> IsScalar( m1( g ) * h^-1 );
true
>
> w := m3( g );
> w in WordGroup( G );
true
> m4( w ) eq g;
true
> g eq Evaluate( w, [G.i : i in [ 1 .. Ngens( G )]]);
true

Run in calculatorCopy input

ClassicalChangeOfBasis(G): GrpMat[FldFin] -> GrpMatElt[FldFin]

Let \(G\) be a classical group in its natural representation; return a change-of-basis matrix to conjugate the generators returned by ClassicalStandardGenerators to those returned by ClassicalConstructiveRecognition \((G)\). The latter intrinsic must have been applied to \(G\).

ClassicalRewrite({G, gens, type, dim,}{ q, g : parameters}): Grp, SeqEnum, MonStgElt, RngIntElt, RngIntElt, GrpElt -> BoolElt, GrpElt

Method: MonStgElt                    Default: "choose"

Let \(G\) be a classical group of type type, which is one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”, with dimension dim over the field \({\bf F}_{q}\) generated by gens which satisfy ClassicalStandardPresentation (type, dim, q). Further, let \(g\) be an element of Generic\((G)\).

If \(g \in G\), then the function returns true and an SLP for \(g\) in gens; if \(g\not\in G\) then the function searches for an SLP \(w\) such that \(g \cdot\)Evaluate\((w, gens)^{-1}\) centralizes \(G\); if it is successful, it returns false and \(w\). Otherwise the function returns false, false.

The function chooses one of the following methods:

(i)

If \(G\) is in its natural representation and gens is ClassicalStandardGenerators (type, dim, q) then an algorithm of Costi [Costi, 2009] is used.

(ii)

If (i) is not valid, but \(G\) is an absolutely irreducible representation in the defining characteristic, then an algorithm of Costi [Costi, 2009] is used.

(iii)

If neither of (i) and (ii) is valid, then a “black-box” method, independent of the representation of \(G\), developed by Csaba Schneider is used.

The optional parameter Method can be used to override the default choice of method. The possible values of Method are CharP and BB.

A description of the algorithm used in the defining characteristic case appears in [Costi, 2009]; a short description of the black-box algorithm appears in [Ambrose et al., 2010].

The code was developed and written by Csaba Schneider.

ClassicalRewriteNatural(type, CB, g): MonStgElt, GrpMatElt, GrpMatElt -> BoolElt, GrpElt

ClassicalRewriteNatural({G, type, }{CB, g}): MonStgElt, GrpMatElt, GrpMatElt -> BoolElt, GrpElt

This is a faster specialized version of the intrinsic ClassicalRewrite discussed above; it is designed for classical groups in their natural representation.

The argument type must be one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”. Both CB and \(g\) are elements of some \({\operatorname{GL}}(d, q)\).

If \(g\) is a member of the group generated by ClassicalStandardGenerators (type, d, q)\(^{{\tt CB}}\) then the function returns true and an SLP \(w\) such that Evaluate (w, ClassicalStandardGenerators (type, d, q)\(^{{\tt CB}}) = g\). Otherwise the function returns false, false.

If many elements of the same group \(G\) are rewritten in terms of standard generators, then the second signature with \(G\) as an argument is recommended on efficiency grounds since the results of some necessary precomputations are stored in \(G\).

This algorithm, based on that developed by Elliot Costi [Costi, 2009], was implemented by Csaba Schneider.

ClassicalStandardPresentation(type, d, q : parameters): MonStgElt, RngIntElt, RngIntElt -> SLPGroup, []

Projective: BoolElt                    Default: false

Given the specification type, d, q of a quasisimple group \(G\), this intrinsic constructs a presentation on the standard generators for \(G\). The string type must be one of “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”, while \(d\) is the dimension and \(q\) is the cardinality of the finite field. The presentations are described in [Leedham-Green and O'Brien, 2020]. The relations are returned as SLPs together with the parent SLPGroup.

If the parameter Projective is set to true, the intrinsic constructs a presentation for the corresponding projective group.

Example: Classical Constructive Recognition (ex-7ccc3b)

As our first illustration, we produce standard generators for \({\operatorname{SL}}(6, 5^3)\):

> E := ClassicalStandardGenerators ("SL", 6, 5^3);
> E;
[
    [      0       1       0       0       0       0]
    [      4       0       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1],

    [      0       0       0       0       0       1]
    [      4       0       0       0       0       0]
    [      0       4       0       0       0       0]
    [      0       0       4       0       0       0]
    [      0       0       0       4       0       0]
    [      0       0       0       0       4       0],

    [      1       1       0       0       0       0]
    [      0       1       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1],

    [    $.1       0       0       0       0       0]
    [      0 $.1^123       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1]
]

Run in calculatorCopy input

We now perform constructive recognition on \({\operatorname{SL}}(6, 5^3)\), and so obtain \(S\), conjugate to \(E\) in \({\operatorname{GL}}(6, 5^3)\). Observe that the change-of-basis matrix returned by ClassicalChangeOfBasis performs this conjugation.

> G := SL (6, 5^3);
> f, S, W := ClassicalConstructiveRecognition (G);
> f;
true
> CB := ClassicalChangeOfBasis (G);
> E^CB eq S;
true

Run in calculatorCopy input

Note that \(W\) is list of SLPs expressing \(S\) in terms of defining generators of \(G\).

> S eq Evaluate (W, [G.i: i in [1..Ngens (G)]]);
true

Run in calculatorCopy input

We next express a random element of \(G\) as a SLP in \(S\) and then check that the standard generators satisfy the standard presentation.

> g := Random (G);
> f, w := ClassicalRewriteNatural ("SL", CB, g);
> Evaluate (w, S) eq g;
true
>
> P, R := ClassicalStandardPresentation ("SL", 6, 5^3);
> Set (Evaluate (R, S));
{
    [      1       0       0       0       0       0]
    [      0       1       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1]
}

Run in calculatorCopy input

We perform constructive recognition on a random conjugate of \({\operatorname{Sp}}(10, 3^6)\) and again check that the standard generators satisfy the standard presentation.

> G := RandomConjugate (Sp(10, 3^6));
> f, S, W := ClassicalConstructiveRecognition (G);
> f;
true

Run in calculatorCopy input

The return variable \(W\) is list of SLPs expressing \(S\) in terms of defining generators of \(G\).

> S eq Evaluate (W, [G.i: i in [1..Ngens (G)]]);
true
>
> g := Random (G);
> CB := ClassicalChangeOfBasis (G);
> f, w := ClassicalRewriteNatural ("Sp", CB, g);
> Evaluate (w, S) eq g;
true
>
> P, R := ClassicalStandardPresentation ("Sp", 10, 3^6);
> Set (Evaluate (R, S));
{
    [1 0 0 0 0 0 0 0 0 0]
    [0 1 0 0 0 0 0 0 0 0]
    [0 0 1 0 0 0 0 0 0 0]
    [0 0 0 1 0 0 0 0 0 0]
    [0 0 0 0 1 0 0 0 0 0]
    [0 0 0 0 0 1 0 0 0 0]
    [0 0 0 0 0 0 1 0 0 0]
    [0 0 0 0 0 0 0 1 0 0]
    [0 0 0 0 0 0 0 0 1 0]
    [0 0 0 0 0 0 0 0 0 1]
}

Run in calculatorCopy input

As another demonstration, we constructively recognise \(\Omega^{-}(16, 2^6)\).

> G := RandomConjugate (OmegaMinus (16, 2^6));
> f, S, W := ClassicalConstructiveRecognition (G);
> f;
true

Run in calculatorCopy input

A random element of \(G\) is expressed as an SLP in \(S\):

> g := Random (G);
> CB := ClassicalChangeOfBasis (G);
> f, w := ClassicalRewriteNatural ("Omega-", CB, g);
> Evaluate (w, S) eq g;
true

Run in calculatorCopy input

Finally, we illustrate using ClassicalRewrite to write an element of a classical group in a non-natural representation as an SLP in its standard generators.

> gens := [ExteriorSquare (x) : x in ClassicalStandardGenerators ("Sp", 6, 25)];
> G := sub<Universe (gens) | gens>;
> x := Random (G);
> f, w := ClassicalRewrite (G, gens, "Sp", 6, 25, x);
> f;
true
> Evaluate (w, gens) eq x;
true
> f, w := ClassicalRewrite (G, gens, "Sp", 6, 25, x : Method := "BB");
> f;
true
> Evaluate (w, gens) eq x;
true

Run in calculatorCopy input

Constructive Recognition for Exceptional Groups

Here we discuss machinery for constructive recognition of most of the finite exceptional groups. For the remainder, see RecogniseSz, RecogniseRee, and RecogniseLargeRee.

ExceptionalStandardGenerators(type, rank, q): MonStgElt, RngIntElt, RngIntElt -> []

Return standard generators for the finite exceptional simple group of specified type type and rank rank over a field of size \(q\). The type is designated by the argument type which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. The standard generators, \(X\) and \(X_m\), are defined in [Liebeck and O'Brien, 2016]; they label the positive and negative root groups of the group respectively and satisfy the presentation returned by ExceptionalStandardPresentation. The copy of the exceptional group generated by \(X\) and \(X_m\) is that defined in [Howlett et al., 2001]. This function is essentially a wrapper for CST_Generators prepared by Don Taylor.

> X, Xm := ExceptionalStandardGenerators ("F", 4, 5^3);
> #X;
8
> #X[1];
3

> X, Xm := ExceptionalStandardGenerators ("2E", 6, 3^4);
> #X;
8
> #X[1];
4

ExceptionalConstructiveRecognition(G, type, rank, q): GrpMat[FldFin], MonStgElt, RngIntElt, RngIntElt -> BoolElt, Map, Map, Map, Map, SeqEnum, SeqEnum

The input group \(G = \langle Y \rangle\) is a a matrix group defined over a finite field. It must be isomorphic to a central quotient of an exceptional group of specified type type and rank rank over a field of size \(q\). The type is designated by the argument type which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. The function constructs standard generators for \(G\). If it is successful, then return true; four maps \(m_1, m_2, m_3, m_4\); the standard generators \(E\) for \(G\); and their SLPs \(W\) in \(Y\); otherwise return false. The map \(m_1\) is from \(G\) to the standard copy \(S\) of \(G\); the map \(m_2\) is from \(S\) to \(G\); the map \(m_3\) is from \(G\) to WordGroup(G); the map \(m_4\) is from WordGroup(G) to \(G\). Since, in general, \(G\) is isomorphic to a central quotient of \(S\), the maps \(m_1\) and \(m_2\) are homomorphisms modulo scalars. The maps \(m_1\), \(m_2\) and \(m_3\) are returned only if \(G\) is a defining characteristic absolutely irreducible matrix representation of the exceptional group. The standard generators \(E\) are returned as a sequence of length 2: its entries, \(X\) and \(X_m\), label the positive and negative root groups respectively.

The algorithm used is that of [Liebeck and O'Brien, 2016]; the implementation was developed by Eamonn O’Brien. The maps \(m_1\), \(m_2\) and \(m_3\) are provided by ExceptionalRewrite, developed and implemented by Don Taylor.

The verbose flag SetVerbose("Except", 1) may be used to print information on the progress of the function.

Example: Exceptional Constructive Recognition (ex-111a3c)

We illustrate these functions with two examples.

> G := MatrixGroup ("G25", 6);
> G: Minimal;
MatrixGroup(27, GF(5)) of order 2^6 * 3^3 * 5^6 * 7 * 31
> f, m1, m2, m3, m4, E, W := ExceptionalConstructiveRecognition( G, "G", 2, 5 );
> Q, R := ExceptionalStandardPresentation ("G", 2, 5);
> X := E[1]; Xm := E[2];
> #Set (Evaluate( R, &cat X cat &cat Xm)) eq 1;
true
> x := Random (G);
> m1;
Mapping from: GL(27, GF(5)) to GL(7, GF(5)) given by a rule [no inverse]
> y := m1 (x);
> m3;
Mapping from: GL(27, GF(5)) to SLPGroup(2) given by a rule [no inverse]
> w := m3 (x);
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq x;
true
> &cat X eq Evaluate( &cat W[1], [G.i : i in [ 1 .. Ngens( G )]]);
true
> &cat Xm eq Evaluate( &cat W[2], [G.i : i in [ 1 .. Ngens( G )]]);
true
>
> G := ChevalleyGroup ("3D", 4, 4);
> G := RandomConjugate (G);
> G: Minimal;
MatrixGroup(8, GF(2^6))
> f, m1, m2, m3, m4, E, W := ExceptionalConstructiveRecognition( G, "3D", 4, 4);
> Q, R := ExceptionalStandardPresentation ("3D", 4, 4);
> X := E[1]; Xm := E[2];
> #Set (Evaluate( R, &cat X cat &cat Xm)) eq 1;
true

Run in calculatorCopy input

ExceptionalRewrite(type, rank, q, X, Xm, g): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum, GrpElt -> BoolElt, GrpElt

Let \(G\) be a finite exceptional group of type type and rank rank over a field of size \(q\). The type is designated by the argument type which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. Also \(X\) and \(X_m\) are generators which satisfy ExceptionalStandardPresentation (type, rank, q). Further, let \(g\) be an element of Generic\((G)\).

If \(g \in G\), then the function returns true and an SLP for \(g\) in &cat X cat &cat Xm; if \(g\not\in G\) then the function searches for an SLP \(w\) such that \(g \cdot\) Evaluate(w, &cat X cat &cat Xm)\(^{-1}\) centralizes \(G\); if it is successful, it returns false and \(w\). Otherwise the function returns false, false.

A description of the algorithm used appears in [Cohen et al., 2004, Cohen and Taylor, 2019]. This function is essentially a wrapper for LieTypeRewrite prepared by Don Taylor.

> g := Random (G);
> f, w := ExceptionalRewrite ("G", 2, 5, X, Xm, g);
> f;
true
> g eq Evaluate (w, &cat X cat &cat Xm);
true

ExceptionalStandardPresentation(type, rank, q): MonStgElt, RngIntElt, RngIntElt -> SLPGroup, []

Let \(G\) be a finite exceptional group of type type and rank rank defined over a field of size \(q\). The type is designated by the argument type which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. This intrinsic constructs a presentation on the standard generators for \(G\). The relations are returned as SLPs together with the parent SLPGroup. The standard presentations returned by this function are listed explicitly in [Liebeck and O'Brien, 2016]. This function is essentially a wrapper for CST_Presentation prepared by Don Taylor.

ExceptionalStandardGenerators returns matrices satisfying this presentation. ExceptionalConstructiveRecognition constructs such generators in an arbitrary matrix representation \(G\).

Example: Exp Standard (ex-b84999)

> Q, R := ExceptionalStandardPresentation ("G", 2, 5^3);
> X, Xm := ExceptionalStandardGenerators ("G", 2, 5^3);
> #Set (Evaluate (R, &cat X cat &cat Xm));
1
> G := ChevalleyGroup ("G", 2, 5^3);
> G := RandomConjugate (ExteriorSquare (G));
> G:Minimal;
MatrixGroup(21, GF(5^3))
> f, m1, m2, m3, m4, E, W := ExceptionalConstructiveRecognition(G, "G",
>                                                                 2, 5^3);
> X := E[1]; Xm := E[2];
> #Set (Evaluate (R, &cat X cat &cat Xm));
1

Run in calculatorCopy input