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 Alt(n) is on n points; its standard generators are (1, 2, 3) and either of (3, ..., n) or (1, 2)(3, ..., 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 PSL(n, q) is the quotient of 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 φ from G to a standard copy S of G, such that φ(g) can be computed efficiently for every g ∈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 ∈U ≥G = < X >, decide whether or not g ∈G, and if so express g as an SLP in X. (Here U is the generic overgroup of G, such as GL(d, q) or 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 [O'B11], [LGO09]. Here we discuss recognition of classical and exceptional groups. See RecogniseAlternatingOrSymmetric for alternating groups.
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 [LGO09] and [DLLGO13].
The input group G = < X > 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 m1, m2, m3, m4; standard generators (S) for G; and their SLPs in X; otherwise return {false}. The map m1 is from G to the standard copy S of G; the map m2 is from S to G; the map m3 is from G to WordGroup(G); the map m4 is from WordGroup(G) to G. Since, in general, G is isomorphic to a central quotient of S, the maps m1 and m2 are homomorphisms modulo scalars.In the second signature, G must be a matrix group defined over a finite field such that G = < X > is conjugate to a quasisimple classical group in its natural representation in dimension at least 2. The intrinsic constructs a copy (S) in G of the generators defined by StandardGenerators. If G is quasisimple and classical, then the function returns {true}, the standard generators (S), and SLPs for these in X; otherwise it returns {false}.
The algorithms used are described in [LGO09], [DLLGO13], and [DLGO15]. 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.
> 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
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.
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 GF(q) generated by gens which satisfy ClassicalStandardPresentation (type, dim, q). Further, let g be an element of Generic(G).If g ∈G, then the function returns true and an SLP for g in gens; if g not∈G then the function searches for an SLP w such that g .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:
The optional parameter Method can be used to override the default choice of method. The possible values of Method are CharP and BB.
- (i)
- If G is in its natural representation and gens is ClassicalStandardGenerators (type, dim, q) then an algorithm of Costi [Cos09] is used.
- (ii)
- If (i) is not valid, but G is an absolutely irreducible representation in the defining characteristic, then an algorithm of Costi [Cos09] 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.
A description of the algorithm used in the defining characteristic case appears in [Cos09]; a short description of the black-box algorithm appears in [AMPS10].
The code was developed and written by Csaba Schneider.
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 GL (d, q).
If g is a member of the group generated by ClassicalStandardGenerators (type, d, q)^((CB)) then the function returns true and an SLP w such that Evaluate (w, ClassicalStandardGenerators (type, d, q)^((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 [Cos09], was implemented by Csaba Schneider.
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 [LGO20]. 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.
As our first illustration, we produce standard generators for SL(6, 53):
> 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]
]
We now perform constructive recognition on SL(6, 53), and so obtain S, conjugate to E in GL(6, 53). 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
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
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]
}
We perform constructive recognition on a random conjugate of Sp(10, 36) and again check that the standard generators satisfy the standard presentation.
> G := RandomConjugate (Sp(10, 3^6)); > f, S, W := ClassicalConstructiveRecognition (G); > f; true
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]
}
As another demonstration, we constructively recognise Ω - (16, 26).
> G := RandomConjugate (OmegaMinus (16, 2^6)); > f, S, W := ClassicalConstructiveRecognition (G); > f; true
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
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
Here we discuss machinery for constructive recognition of most of the finite exceptional groups. For the remainder, see RecogniseSz, RecogniseRee, and RecogniseLargeRee.
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 Xm, are defined in
[LO16]; 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 Xm is that defined in [HRT01].
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
The input group G = < Y > 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 m1, m2, m3, m4; the standard generators E for G; and their SLPs W in Y; otherwise return {false}. The map m1 is from G to the standard copy S of G; the map m2 is from S to G; the map m3 is from G to WordGroup(G); the map m4 is from WordGroup(G) to G. Since, in general, G is isomorphic to a central quotient of S, the maps m1 and m2 are homomorphisms modulo scalars. The maps m1, m2 and m3 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 Xm, label the positive and negative root groups respectively.The algorithm used is that of [LO16]; the implementation was developed by Eamonn O'Brien. The maps m1, m2 and m3 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.
> 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
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 Xm are generators which satisfy ExceptionalStandardPresentation (type, rank, q). Further, let g be an element of Generic(G).If g ∈G, then the function returns true and an SLP for g in &cat X cat &cat Xm; if g not∈G then the function searches for an SLP w such that g .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 [CMT04], [CT19]. 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
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 [LO16].ExceptionalStandardGenerators returns matrices satisfying this presentation. ExceptionalConstructiveRecognition constructs such generators in an arbitrary matrix representation G. This function is essentially a wrapper for CST_Presentation prepared by Don Taylor.
> 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