|
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].
ClassicalConstructiveRecognition(G) : GrpMat[FldFin] ->BoolElt, SeqEnum, SeqEnum
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.
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
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:
- (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.
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 [Cos09]; a short description of the black-box algorithm
appears in [AMPS10].
The code was developed and written by Csaba Schneider.
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 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.
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
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].
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.
> 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|