|
N: RngIntElt Default: 0
Extension: BoolElt Default: false
Epsilon: FldRElt Default: 0.01
Asymptotic: BoolElt Default: false
The input group G is isomorphic to H, the alternating
or symmetric group for some n ≥5.
Note that G can be either a matrix or permutation representation of H.
The algorithm used is that of [JLNP13].
Since this is Las Vegas,
there is a small probability controlled by the optional parameter
Epsilon that it returns false incorrectly.
If the algorithm succeeds, then it returns true,
an isomorphism from G to H, an isomorphism from H to G,
the map from G to its word group, and the map from the word group to G.
The sixth value returned is true if H is the
symmetric group, otherwise false.
The optional parameter N is an upper bound for the degree of H.
If N is 0, then the maximal theoretically possible bound for the
degree is assumed; this is the degree of G if G is a permutation group,
and max(9, d + 2) or max(9, d + 1)
if G is a matrix group of degree d,
depending on the characteristic of the field.
If the optional parameter Extension is true, then G is isomorphic to
a central extension of H for some n ≥5.
Now the first two maps returned are an epimorphism
from G onto H with kernel Z(G) and a map from H to G that induces an
isomorphism from H onto G/Z(G).
If the optional parameter Asymptotic is true, then the
map from H to G
implements the asymptotically efficient algorithm of Beals
et al. [BLGN+03].
Otherwise, the algorithm employed for this map is
that of [BP00],
which is usually faster for moderate degrees.
If the algorithm is not successful, then false is returned.
The algorithm consists of two parts.
The first part finds the degree of the alternating group and
constructs standard generators, cf. [JLNP13].
The second part verifies that these elements generate G,
and constructs isomorphisms
between G and H, cf. [BLGN+03].
The implementation of the first part was developed by Sebastian Jambor.
The implementation of the second part was developed by Jonathan Conder;
he also extended the
algorithm to work for both n ∈{5, ..., 10} and central extensions.
If g ∈G and G has been recognised
by RecogniseAlternatingOrSymmetric, this function returns true
and an element of the word group for G which evaluates to g.
Otherwise, it returns false. This facilitates membership testing in G.
The implementation was developed by Jonathan Conder.
We illustrate the use of these functions for a representation
of A 13.
> A:= AlternatingGroup (13);
> H:= Stabiliser(A, {1,2});
> G := CosetImage (A, H);
> Degree (G);
78
> success, bb_to_perm, perm_to_bb, bb_to_wg, wg_to_bb, is_sym :=
> RecogniseAlternatingOrSymmetric (G);
>
> success;
true
> is_sym;
false
>
> x:= Sym(78)!(1, 35, 16, 28, 14, 26, 69, 5, 74)(2, 54,
> 67, 18, 51, 63, 6, 50, 77)(3, 33, 78, 12, 34, 29, 19, 15, 73)
> (4, 52, 61, 24, 49, 60, 68, 38, 64)(7, 20, 71, 17,
> 32, 11, 72, 8, 36)(9, 76, 47, 31, 56, 62, 13, 53, 59)
> (10, 70, 57, 23, 37, 22, 21, 27, 25)(30, 45, 46, 43, 42,
> 44, 40, 41, 75)(39, 55, 65)(48, 66, 58);
>
> flag, w := AlternatingOrSymmetricElementToWord (G, x);
> "Is x in G?", flag;
Is x in G? true
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq x;
true
>
> perm_image:= bb_to_perm(x);
> perm_image;
(1, 4, 9)(2, 6, 3, 5, 10, 7, 8, 11, 12)
>
> y := Random (G);
> w := bb_to_wg (y);
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq y;
true
maxtries: RngIntElt Default: 100n + 5000
Extension: BoolElt Default: false
The group G should be known to be isomorphic to the symmetric group
Sn for some n ≥8. The Bratus-Pak algorithm [BP00]
(implemented by Derek Holt)
is used to define an isomorphism between G and Sn.
If successful,
return true, homomorphism from G to Sn, homomorphism from
Sn to G, the map from G to its word group and the
map from the word group to G.
If the optional parameter Extension is set, then the group G
should be known to be isomorphic either to Sn or to a perfect central
extension 2.Sn. In that case, the first two maps returned will be
a homomorphism from G to Sn and a map from Sn to G that induces
a homomorphism onto G/Z(G). The sixth value returned will be true,
if G isomorphic to 2.Sn and false, if G isomorphic to 2.An.
If unsuccessful, false is returned. This will always occur if the input
group is not isomorphic to Sn (or 2.Sn when Extension is set)
with n ≥8, and may occur occasionally
even when G is isomorphic to Sn. The optional parameter maxtries
(default 100n + 5000) can be used to control the number of random elements
chosen before giving up.
If g is an element of G which has been constructively recognised to
be isomorphic to Sn (or 2.Sn), then return true and
element of word group for G which evaluates to g.
Otherwise return false.
This facilitates membership testing in G.
maxtries: RngIntElt Default: 100n + 5000
Extension: BoolElt Default: false
The group G should be known to be isomorphic to the alternating group
An for some n ≥9. The Bratus-Pak algorithm [BP00]
(implemented by Derek Holt)
is used to define an isomorphism between G and An.
If successful,
return true, homomorphism from G to An, homomorphism from
An to G, the map from G to its word group and the
map from the word group to G.
If the optional parameter Extension is set, then the group G
should be known to be isomorphic either to An or to a perfect central
extension 2.An. In that case, the first two maps returned will be
a homomorphism from G to An and a map from An to G that induces
a homomorphism onto G/Z(G). The sixth value returned will be true,
if G isomorphic to 2.An and false otherwise.
If unsuccessful, false is returned. This will always occur if the input
group is not isomorphic to An (or 2.An when Extension is set)
with n ≥9, and may occur occasionally
even when G is isomorphic to An. The optional parameter {tt maxtries}
(default 100n + 5000) can be used to control the number of random elements
chosen before giving up.
If g is an element of G which has been constructively recognised to
be isomorphic to An (or 2.An), then return true and
element of word group for G which evaluates to g.
Otherwise return false.
This facilitates membership testing in G.
maxtries: RngIntElt Default: 5000
Extension: BoolElt Default: false
The group G should be believed to be isomorphic to Sn or An for
some n > 6, or to 2.Sn or 2.An if the optional parameter
Extension is set.
This function attempts to determine n and whether G is
symmetric or alternating. It does this by sampling orders of elements.
It returns either false, if it is unable to make a decision after
sampling maxtries elements (default 5000), or true, type and n,
where type is "Symmetric" or "Alternating", and n is the degree.
If G is not isomorphic to Sn or An (or 2.Sn or 2.An
when Extension is set) for n > 6, then the output is
meaningless - there is no guarantee that false will be returned. There is also
a small probability of a wrong result or false being returned even when G is
Sn or An with n > 6. This function was written by Derek Holt.
For a group G which is believed to be isomorphic to S n or A n for
some unknown value of n > 6, the function GuessAltsymDegree can be
used to try to guess n, and then RecogniseSymmetric or
RecogniseAlternating can be used to confirm the guess.
> G:= sub< GL(10,5) |
> PermutationMatrix(GF(5),Sym(10)![2,3,4,5,6,7,8,9,1,10]),
> PermutationMatrix(GF(5),Sym(10)![1,3,4,5,6,7,8,9,10,2]) >;
> GuessAltsymDegree(G);
true Alternating 10
> flag, m1, m2, m3, m4 := RecogniseAlternating(G,10);
> flag;
true
> x:=Random(G); Order(x);
8
> m1(x);
(1, 2, 4, 9, 10, 8, 6, 3)(5, 7)
> m2(m1(x)) eq x;
true
> m4(m3(x)) eq x;
true
> flag, w := AlternatingElementToWord(G,x);
> flag;
true
> m4(w) eq x;
true
> y := Random(Generic(G));
> flag, w := AlternatingElementToWord(G,y);
> flag;
false
> flag, m1, m2, m3, m4 := RecogniseAlternating(G,11);
> flag;
false
> flag, m1, m2, m3, m4 := RecogniseSymmetric(G,10);
> flag;
false
The nature of the GuessAltsymDegree function is that it assumes that
its input is either an alternating or symmetric group and then tries to guess
which one and the degree. As such, it is almost always correct when the input
is an alternating or symmetric group, but will often return a bad guess when
the input group is not of this form, as in the following example.
> GuessAltsymDegree(Sym(50));
true Symmetric 50
> GuessAltsymDegree(Alt(73));
true Alternating 73
> GuessAltsymDegree(PSL(5,5));
true Alternating 82
Given a finite quasisimple group of Lie type in any representation, the
functions in this section apply probabilistic algorithms to determine its
defining characteristic and type as a Lie group.
NumberRandom: RngIntElt Default: 100
Verify: BoolElt Default: true
Given a finite quasisimple permutation or matrix group G which
is of Lie type, determine its defining characteristic.
The Monte Carlo algorithm implemented by this function is
that of Liebeck and O'Brien [LO07].
Since it is Monte Carlo, there is a small probability of error.
The number of random elements considered is NumberRandom.
If Verify is true, then we first verify that
G is perfect by applying IsProbablyPerfect.
> F := GF (4);
> w := PrimitiveElement (F);
> a := [
> 0,w^3,0,0,0,
> w^3,0,0,0,0,
> 0,0,0,w^3,0,
> 0,0,w^3,0,0,
> w^2,w^2,w^3,w^3,w^3];
> b := [
> 0,0,w^3,0,0,
> w^1,w^2,w^2,0,0,
> w^2,w^1,w^2,0,0,
> 0,0,0,0,w^3,
> w^2,w^2,w^2,w^3,w^3];
> G := sub <GL(5, F) | a, b>;
> LieCharacteristic(G);
11
LieType(G, p : parameters) : GrpMat, RngIntElt -> BoolElt, Tup
LieType(G, p : parameters) : GrpMat, RngIntElt -> BoolElt, Tup
NumberRandom: RngIntElt Default: 100
If the matrix or permutation group G is nearly simple,
and its non-abelian composition factor
is isomorphic to a group of Lie type in characteristic p,
then this function returns true and its standard Chevalley name.
Otherwise it returns false.
The algorithm is that of Babai, Kantor, Pálfy and Seress
[BKPS02]; this implementation was developed
by Malle and O'Brien.
Since it is Monte Carlo, there is
a small probability of error.
The number of random elements considered is NumberRandom.
The standard name is
a tuple that defines
the isomorphism type of the composition factor.
It is similar to that employed
by CompositionFactors, described in
the Permutation Groups chapter.
If the composition factor is a group of Lie type,
then the tuple is <s, n, q> and it defines
the adjoint Chevalley group of Lie series s
and Lie rank n over GF (q). The tuple
entries are valid arguments for ChevalleyGroup.
If the composition factor is an alternating group,
and so lies in family 17, then the tuple is
<17, n, 0> and it defines
the alternating group of degree n.
If the composition factor is a sporadic group
and so lies in family 18,
then the tuple is <18, n, s>; the string
s is its standard Atlas name and n is the
number of the group in family 18.
SimpleGroupName(G : parameters): GrpPerm -> BoolElt, List
NumberRandom: RngIntElt Default: 100
If the matrix or permutation group G is nearly simple,
this function returns true and a list of
possible names for its non-abelian
simple composition factor; otherwise it returns false.
Since it is Monte Carlo, there is a small probability of error.
The number of random elements considered is NumberRandom.
The list of standard names follows the convention described above.
The algorithm and implementation were developed
by Malle and O'Brien; it uses
LieType and LieCharacteristic.
We create the classical group Ω(7, 5) in its natural representation
and apply SimpleGroupName to it.
> SetSeed(1);
> G := Omega(7, 5);
> flag, name := SimpleGroupName(G);
> name;
[* <B, 3, 5> *]
We create a certain 5-dimensional matrix group over GF(3) and determine
which simple group it is.
> F := GF(3);
> P := GL(5,F);
> gens := [
> P![2,1,2,1,2,2,0,0,0,2,0,2,0,0,0,0,1,2,0,1,1,0,2,2,1],
> P![2,1,0,2,1,1,2,0,2,2,1,1,2,1,1,0,2,0,1,1,1,1,2,2,2]];
> G := sub <P | gens>;
> flag, name := SimpleGroupName(G);
> flag;
true
> name;
[* <18, 1, M11> *]
> /* naming an alternating group */
> G := MatrixGroup<4, GF(2) |
> [ 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0 ],
> [ 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0 ] >;
> flag, name := SimpleGroupName(G);
> flag;
true
> /* this is A5 */
> name;
[* <17, 5, 0> *]
> /* naming a classical group */
> F := GF(7^2);
> P := GL (6,F);
> w := PrimitiveElement (F);
> gens := [
> P![w^12,w^36, 0, 5, 2, 0,w^44,w^36, 0, 6, 2, 0,
> w^42,w^42,w^28,w^22,w^22, 3, 4, 3, 0,w^36,w^12, 0,
> 2, 3, 0,w^20,w^12, 0,w^14,w^14, 1,w^18,w^18, w^4],
>
> P![w^38,w^26,w^25,w^21, w^9, 3,w^21,w^45,w^33, w^4,w^28,
> 2, 6, 4, w^1, w^7,w^15, 4, 1,w^36,w^35, w^5,w^41, 5,
> w^31, w^7,w^43,w^36,w^12, 1,w^34,w^42,w^11,w^39,w^47, 2]
> ];
> G := sub <P | gens>;
> flag, name := LieType(G, 5);
> flag;
true
> name;
<A, 1, 5>
> /* so this is SL(2, 5) */
Let G be an absolutely irreducible subgroup of GL(d, q).
The following functions compute symplectic, unitary and orthogonal
forms of the underlying vector space V left invariant by the action
of G.
A bilinear form is a bilinear function κ from V x V -> F. It is G-invariant modulo scalars if for each g ∈G there is a μg ∈F such that κ(vg, wg) = μg
κ(v, w) for all v, w ∈V.
Now suppose that a |-> bar(a) is an automorphism of F of
order 2. A sesquilinear form is a biadditive function κ
from V x V -> F such that κ( au, bv) = a bar(b)
κ(u, v) for all u, v ∈V and a, b∈F. It is G-invariant
modulo scalars if for each g ∈G there is a μg ∈F such
that κ(vg, wg) = μg κ(v, w) for all v, w ∈V.
A quadratic form is a function χ : V -> F such that
- (1)
- χ(av) = a2 χ(v) for all a∈F, v∈V; and
- (2)
- the form κ, defined by
κ(u, v) = χ( u + v ) - χ(u) - χ(v) for all u, v ∈V,
is bilinear.
It is G-invariant if for each g ∈G, χ(vg) = χ(v) for all
v ∈V.
It is G-invariant modulo scalars if for each g ∈G
there is a μ g ∈F such that χ(vg) = μ g χ(v) for all
v ∈V.
A bilinear form which is G-invariant (modulo scalars)
is represented by a matrix B such that g * B * (g)tr
= μg B for all g∈G and is unique up to multiplication by an
element of F. Assume F has an automorphism a |-> bar(a) of
order 2; a sesquilinear form is a matrix B such that g *
B * bar(g)tr = μg B for all g∈G and is unique up to
multiplication by an element of F
(where bar(g) denotes the matrix obtained from g by replacing
each entry gij by bar(gij)).
A quadratic form is represented
by an upper triangular matrix Q such that the matrix g * Q *
gtr, normalized into an upper triangular matrix, equals μg Q.
The functions below will exit with an error message if the input group
G is reducible. They may also exit with error if G is not absolutely
irreducible, or if Scalars is true and the derived subgroup [G, G]
of G is not absolutely irreducible. They may however sometimes succeed in
finding a fixed form when G is irreducible but not absolutely irreducible.
ClassicalForms(G: parameters): GrpMat -> Rec
Scalars: BoolElt Default: false
Given as input a matrix group G acting absolutely irreducibly on the
underlying vector space V over the field F,
ClassicalForms will try to find a classical form which is
G-invariant or prove that no such form exists.
If the optional
argument Scalars is true then it will look for a form which is
G-invariant modulo scalars. When Scalars is true,
it is only guaranteed to succeed
when [G, G] acts absolutely irreducibly on V.
If it finds a fixed form, then
it will stop and will not look for alternative fixed forms of different types.
The classical forms are: symplectic (non-degenerate, alternating
bilinear), unitary (non-degenerate sesquilinear) or orthogonal (a symmetric bilinear form and a quadratic
form).
The function ClassicalForms returns a record forms which
contains the components formType, sign,
bilinearForm, sesquilinearForm, quadraticForm
and scalars. Depending
on the entry formType the record components are set to indicate:
- "unknown":
it is not known whether G fixes a classical form.
- "linear":
it is known that G does not fix a classical form modulo scalars.
- "symplectic":
G fixes a symplectic form modulo scalars.
The matrix of the form is stored in bilinearForm and the
scalars for each generator of G are stored in scalars.
In characteristic two this also
implies that no quadratic form is fixed.
- "unitary":
G fixes a unitary form (modulo scalars). The matrix of the
form is stored in sesquilinearForm. The scalars for
each generator of G are stored in scalars.
- "orthogonalcircle":
- "orthogonalplus":
- "orthogonalminus":
G fixes an orthogonal form modulo scalars. The
matrix of the bilinear form is stored in
bilinearForm and the corresponding quadratic form in
quadraticForm. The scalars for each generator of G are
stored in scalars.
In the orthogonal case, sign is set to 0, 1, or -1 when
formType is "orthogonalcircle",
"orthogonalplus", or "orthogonalminus", respectively.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a symplectic
form (modulo scalars if the optional argument Scalars is true),
this function returns true and the matrix of the form.
If it is known that G does not preserve such a form it returns
false. If it cannot decide (perhaps because the group
does not act absolutely irreducibly), then it exits with an error message.
If Scalars is true,
then the list of scalars for the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves an orthogonal form (modulo
scalars if the optional argument Scalars is true),
then this function returns
true, the matrix of the symmetric bilinear form, and the type of the form
(as in ClassicalForms).
If it is known that G does not preserve such a form,
it returns false.
If it cannot decide, then it exits with an error message.
If Scalars is true, then
the list of scalars for the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a quadratic
form (modulo scalars if the optional argument Scalars is true),
this function returns true, the matrix of the form in upper triangular
form, and the type of the form (as in ClassicalForms).
If it is known that G does not preserve such a form it returns false.
If it cannot decide, then it exits with an error message.
If Scalars is true, then
the list of scalars for the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a unitary form
(non-degenerate sesquilinear)
(modulo scalars if the optional argument Scalars is true), then
this function returns true and the matrix of the form. If it is known
that G does not preserve such a form, it returns false.
If it cannot decide, then it exits with an error message.
If Scalars is true, then the list of scalars for
the generators of G is also returned.
Scalars: BoolElt Default: false
If the absolutely irreducible group G preserves a classical form
(modulo scalars if the optional argument Scalars is true),
this function returns its type (see ClassicalForms).
Otherwise it returns "unknown".
> G := Omega( 9, 11 );
> ClassicalForms( G );
rec<recformat<bilinearForm, quadraticForm, sesquilinearForm, bilinFlag,
sesquiFlag, scalars, formType, bc, n> | bilinearForm :=
[ 0 0 0 0 0 0 0 0 1]
[ 0 0 0 0 0 0 0 1 0]
[ 0 0 0 0 0 0 1 0 0]
[ 0 0 0 0 0 1 0 0 0]
[ 0 0 0 0 6 0 0 0 0]
[ 0 0 0 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0 0]
[ 0 1 0 0 0 0 0 0 0]
[ 1 0 0 0 0 0 0 0 0],
quadraticForm :=
[ 0 0 0 0 0 0 0 0 1]
[ 0 0 0 0 0 0 0 1 0]
[ 0 0 0 0 0 0 1 0 0]
[ 0 0 0 0 0 1 0 0 0]
[ 0 0 0 0 3 0 0 0 0]
[ 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 0],
sesquilinearForm := false, bilinFlag := true, sesquiFlag := false,
scalars := [ 1, 1 ], formType := orthogonalcircle, sign := 0>
> FormType( G );
orthogonalcircle
> SymplecticForm( G );
false
Return a matrix m such that Gm lies in the classical group returned by
the Magma function GU, Sp, or GO(Plus/Minus).
The argument form should be a classical form of type type fixed
by an absolutely irreducible subgroup G of GL(d, q).
It should be the bilinear or sesquilinear form fixed by G,
except when G is orthogonal in characteristic 2, in which case it should
be the quadratic form. The argument type should be as in the
formType component of the record returned by
ClassicalForms;
i.e. one of "symplectic", "unitary", "orthogonalcircle",
"orthogonalplus", or "orthogonalminus".
The code for this function for all cases other than orthogonal in
characteristic 2 was written by Giovanni de Franceschi and James Wilson.
Scalars: BoolElt Default: false
This function calls ClassicalForms to find a form fixed by
the absolutely irreducible subgroup G of GL(d, q).
If Scalars is true, then ClassicalForms is called
with Scalars set to true, so that a form fixed module scalars is
found.
If a form form of type type is fixed,
then it returns TransformForm(form, type).
Otherwise it returns false.
The group element g should be an element of the finite orthogonal
group that preserves the given symmetric bilinear form with matrix
form. If the characteristic is odd, this function returns the
spinor norm of g. If the characteristic is even it returns the
Dickson invariant of g; namely the rank modulo 2 of g - I. Thus
for an element g of the special orthogonal group the return value
is 0 if g belongs to the Omega(Plus/Minus) subgroup of index 2;
otherwise the return value is 1. However, as illustrated in the
following example, the spinor norm alone cannot be used to check
whether an element of the orthogonal group is in Ω.
This function can be used to check whether an element of the
orthogonal group, say GO^ + (d, q), belongs to Ω^ + (d, q).
First check that the element belongs to SO^ + (d, q).
> isInOmega := func< g,form |
> Determinant(g) eq 1 and SpinorNorm(g,form) eq 0 >;
> G := GOPlus(6,3);
> g := G![
> [ 1, 0, 0, 0, 0, 0],
> [ 0, 0, 0, 0, 2, 0],
> [ 0, 0, 1, 0, 0, 0],
> [ 0, 0, 0, 1, 0, 0],
> [ 0, 2, 0, 0, 0, 0],
> [ 0, 0, 0, 0, 0, 1] ];
> _, form := SymmetricBilinearForm(G);
> SpinorNorm(g,form);
0
> isInOmega(g,form);
false
Let G be an irreducible subgroup of GL(d, q). The following
algorithm is designed to test whether G contains the corresponding
classical group Ω and is contained in Δ.
Here Ω and Δ are defined as follows:
- Case "linear": Δ = GL(d, q), Ω = SL( d, q)
- Case "symplectic": Δ = CSp(d, q), Ω = Sp( d, q)
- Case "orthogonalplus": Δ = CO^ + (d, q), Ω = Ω^ + (d, q)
- Case "orthogonalminus": Δ = CO^ - (d, q),
Ω = Ω^ - (d, q)
- Case "orthogonalcircle":Δ = CO
 (d, q),
Ω = Ω(d, q)
- Case "unitary": Δ = CU(d, q), Ω = SU(d, q)
RecogniseClassical(G : parameters): GrpMat -> BoolElt
Case: MonStgElt Default: "unknown"
NumberOfElements: RngIntElt Default: 25
SetVerbose("Classical", n): Maximum: 3
RecognizeClassical takes as input
a group G, which is a subgroup of GL(d, q).
The parameter
Case is one of "linear", "symplectic",
"orthogonalplus", "orthogonalminus", "orthogonalcircle", "unitary" or "unknown";
if Case is supplied, then the algorithm seeks to decide
for this case only.
The parameter
NumberOfElements is the number of random elements selected
from G during the execution of the algorithm.
The output of RecognizeClassical is either true, false or "Does not apply". If the algorithm returns true,
then we know with certainty that G contains Ω and is
contained in Δ. Note that the proof of correctness of the
algorithm depends on the finite simple group classification. If it
returns false then either G does not contain Ω, or G
is not contained in Δ, or G is not irreducible, or there is a
small chance that G is contained in Δ and contains Ω.
More precisely, if the irreducible group G is contained in Δ
and really does contain Ω then the probability with which the
algorithm returns false is less than ε, where
ε is a real number between 0 and 1. The smaller the value
of ε, the larger NumberOfElements must be. If the
algorithm returns "Does not apply" then it is not applicable to
the given group.
If "Classical" is set to verbose then, where RecognizeClassical returns true, it also prints the statement
"Proved that the group contains a classical group of type case in
n random selections", where n is the number of selections needed.
If it returns false, it prints a statement giving some
indication of why the algorithm reached this conclusion.
Theoretical details of the algorithms used may be found in
Niemeyer & Praeger [NP97][NP98]
[NP99] and Praeger [Pra99].
Its approach is based on the SL-recognition algorithm (Neumann &
Praeger, [NP92]).
This implementation also uses algorithms described in
Celler & Leedham-Green [CLG97a][CLG97b] and Celler et al.
[CLGM+95].
For small fields (q < 216), the cost of this implementation for a
given value of NumberOfElements is O( d3 log d ) bit operations.
This function tests whether the subgroup G of GL(d, q) contains
SL(d, q). If the function can establish this fact, it returns true and otherwise false.
Hence, if IsLinearGroup returns
false, there is a small chance that G nevertheless contains
SL(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of CSp(d, q) contains
Sp(d, q). If the function can establish this fact, it returns true and otherwise false.
Hence, if IsSymplecticGroup
returns false, there is a small chance that G nevertheless
contains Sp(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of COε(d, q)
contains Ωε(d, q). If the function can establish this
fact, it returns true and otherwise false.
Hence, if IsOrthogonalGroup returns false, there is a small chance that
G nevertheless contains Ωε(d, q). See RecognizeClassical for more details.
This function tests whether the subgroup G of CU(d, q) contains
SU(d, q). If the function can establish this fact, it returns true and otherwise false.
If G is known to be a classical subgroup of GL(d, q) this function
returns the appropriate classical type as a string, i.e.
"linear", "symplectic", "orthogonalplus",
"orthogonalminus", "orthogonalcircle",
or "unitary". Otherwise the function returns false.
This is a refinement of ClassicalType developed by O'Brien and Taylor.
If G can be identified as a
natural classical group in its natural representation, return true and the
type of the group -- one of the strings listed under `subtype';
otherwise return false.
type subtype
---------------------------------------------------
linear GL, SL
symplectic CSp, Sp, ExtSp
orthogonalplus CGO+, GO+, SO+, Omega+, ExtOmega+
orthogonalminus CGO-, GO-, SO-, Omega-, ExtOmega-
orthogonalcircle CGO, GO, SO, Omega, ExtOmega
unitary CGU, GU, SU, ExtSU, AltSU
---------------------------------------------------
A group of type "ExtSp" is properly contained between the symplectic
group and the conformal symplectic group. A group of type "ExtSU" is
properly contained between the special unitary group and the general unitary group
whereas a group of type "AltSU" is a subgroup of the conformal unitary group
which contains the special unitary group but is not contained in the general unitary
group. A group of type "ExtOmega" is a subgroup of the conformal orthogonal
group not of type "CGO", "GO", "SO" or "Omega". (Similarly for types
"ExtOmega+" and "ExtOmega-".)
> G := SU (60, 9);
> G := RandomConjugate (G);
> RecognizeClassical (G);
true
> IsLinearGroup (G);
false
> IsUnitaryGroup (G);
true
> IsSymplecticGroup (G);
false
> IsOrthogonalGroup (G);
false
> ClassicalType (G);
unitary
> G := Sp (462, 3);
> RecognizeClassical (G);
true
> ClassicalType (G);
symplectic
> ClassicalGroupType (G);
true Sp
> G := CGOPlus (14, 8);
> G := RandomConjugate (G);
> ClassicalGroupType (G);
true CGO+
The functions in this section recognise whether or not a given group G is
a specified linear group T. If it is, then an isomorphism between G and
T is returned.
The function ClassicalConstructiveRecognition performs
constructive recognition for all classical groups,
and incorporates the
recognition functions listed below for specific classical groups.
See also ExceptionalConstructiveRecognition which deals
with most finite exceptional groups of Lie type; the remaining cases
-- Suzuki groups, large and small Ree groups -- are discussed here.
RecogniseSL2(G) : GrpMat -> BoolElt, Map, Map, Map, Map
RecognizeSL2(G) : GrpPerm -> BoolElt, Map, Map, Map, Map
RecogniseSL2(G) : GrpPerm -> BoolElt, Map, Map, Map, Map
RecognizeSL2(G, q) : GrpMat, RngIntElt -> BoolElt, Map, Map, Map, Map
RecogniseSL2(G, q) : GrpMat, RngIntElt -> BoolElt, Map, Map, Map, Map
RecognizeSL2(G, q) : GrpPerm, RngIntElt -> BoolElt, Map, Map, Map, Map
RecogniseSL2(G, q) : GrpPerm, RngIntElt -> BoolElt, Map, Map, Map, Map
If G, a matrix or permutation group, is isomorphic,
possibly modulo scalars, to (P)SL(2, q),
then homomorphisms between G and (P)SL(2, q)
are constructed. The function returns a homomorphism from G to
(P)SL(2, q), a homomorphism from (P)SL(2, q) to G,
the map from G to its word group, and the map from the word
group to G.
If q, the cardinality of the defining field for G, is known, it
should be supplied. Otherwise, the function SL2Characteristic
is used to determine q; if q is large, this calculation may be
expensive.
SL2ElementToWord(G, g) : GrpPerm, GrpPermElt -> BoolElt, GrpSLPElt
If g is an element of the matrix or permutation group
G which has been constructively recognised to
have central quotient isomorphic to PSL(2, q), then return
true and element of word group for G which
evaluates to g, else false.
This facilitates membership testing in G.
SL2Characteristic(G : parameters) : GrpPerm -> RngIntElt, RngIntElt
NumberRandom: RngIntElt Default: 100
Verify: BoolElt Default: true
Subject to the assumption that the group G has central
quotient (P)SL(2, q), determine its characteristic and field size.
The Monte Carlo algorithm implemented by this function is
that of Liebeck and O'Brien [LO07].
Since it is Monte Carlo, there is a small probability of error.
The number of random elements considered is NumberRandom.
If Verify is true, then we first verify that
G is perfect by applying IsProbablyPerfect.
The constructive recognition algorithms for SL(2, q) were developed
by Conder, Leedham-Green and O'Brien [CLGO06].
The algorithm used for other representations
was developed by Brooksbank and O'Brien.
Our first example uses G = SL(2, 32) in its natural representation.
We first recognise the group and then express a random matrix of G as
a word in the generators of G.
> G := SL(2, 3^2);
> flag, phi, tau, gamma, delta := RecogniseSL2(G, 3^2);
> g := G![1, 2, 0, 1];
> w := gamma(g);
> delta(w) eq g;
true
We now consider a representation of a 2-dimensional linear group inside
GL(6, GF(57) ).
> K<w> := GF(5, 7);
> G :=
> MatrixGroup<6, GF(5, 7) |
> [w^19035, w^14713, w^50617, w^14957, w^51504, w^48397, w^16317, w^3829,
> w^35189, w^2473, w^19497, w^77192, w^46480, w^6772, w^29577, w^61815,
> w^54313, w^16757, w^43765, w^64406, w^58788, w^30789, w^13579, w^66728,
> w^7733, w^45434, w^42411, w^61613, w^12905, w^6889, w^50116, w^16117,
> w^56717, w^25226, w^49940, w^36836 ],
> [w^63955, w^40568, w^45004, w^11642, w^39536, w^11836, w^52594, w^71166,
> w^47015, w^74450, w^32373, w^37021, w^76381, w^18155, w^57943, w^31194,
> w^62524, w^65864, w^11868, w^76867, w^26483, w^41335, w^64856, w^41125,
> w^43990, w^40104, w^24842, w^3153, w^23777, w^60024, w^14454, w^68648,
> w^43403, w^26710, w^39779, w^22074 ] >;
>
> flag, phi, tau, gamma, delta := RecogniseSL2(G, 5^7);
> phi;
Mapping from: GrpMat: G to SL(2, GF(5, 7)) given by a rule [no inverse]
> g := Random(G);
> h := phi (g);
> h;
[w^40430 w^970]
[ w^5607 w^11606]
> k := tau(h);
> w := gamma(k);
> m := delta(w);
Recall that we are working modulo scalars.
> IsScalar(m * g^-1);
true
> H := SL(2, 5^7);
> h := H![1,1,0,1];
> g := tau(h);
> Order(g);
5
We now test a random element of GL(6, GF(57) ) for membership of our
group.
> g := Random(GL(6, 5^7));
> SL2ElementToWord(G, g);
false
RecogniseSL3(G, q : parameters) : GrpMat, RngIntElt -> BoolElt, Map, Map, Map, Map
Verify: BoolElt Default: true
If G ≤GL(d, F), is isomorphic,
possibly modulo scalars, to (P)SL(3, q),
then construct homomorphisms between
G and (P)SL(3, q).
Return homomorphism from G to (P)SL(3, q), homomorphism from
(P)SL(3, q) to G, the map from G to its word group and the
map from the word group to G.
If q, the cardinality of the defining field for G, is known, it
should be supplied. Otherwise, it is computed
using the functions LieCharacteristic and LieType.
If Verify is false, then assume G is isomorphic,
possibly modulo scalars, to (P)SL(3, q).
If g is an element of G which has been constructively recognised to
have central quotient isomorphic to PSL(3, q), then return
true and
element of word group for G which evaluates to g, else false.
This facilitates membership testing in G.
The constructive recognition algorithms for SL(3, q) were
developed by Lübeck, Magaard, and O'Brien
[LMO07]. Its current implementation,
which is part of the CompositionTree package, was developed
by Bäärnhielm and O'Brien.
We create SL(3, 5 4) in its natural representation and recognise it.
We then form its symmetric square and apply the recognition machinery
to that.
> G := SL(3, 5^4);
> flag, phi, tau, gamma, delta := RecogniseSL3(G);
> w := PrimitiveElement (GF(5^4));
> g := GL(3, 5^4)! [1,2,1,0,w,1,0,0,w^-1];
> w := gamma (g);
> delta (w) eq g;
true
> G := ActionGroup(SymmetricSquare(GModule(G)));
> flag, phi, tau, gamma, delta := RecogniseSL3(G);
> phi;
Mapping from: GL(6, GF(5, 4)) to SL(3, GF(5, 4)) given by a rule [no inverse]
> g := Random(G);
> h := phi(g);
> h;
[$.1^40430 $.1^970]
[ $.1^5607 $.1^11606]
> k := tau(h);
> w := gamma(k);
> m := delta(w);
Recall that we are working modulo scalars. We conclude by testing
whether a random element of GL(6, 54) is contained in our group.
> IsScalar(m * g^-1);
true
> g := Random(GL(6, 5^4));
> SL3ElementToWord(G, g);
false
RecognizeSL(G, d, q) : Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map
Use the Kantor-Seress algorithm to try to find an isomorphism between the
finite group G (regarded as a black-box group) and SL(d, q) or
PSL(d, q). The first return value indicates whether the attempt was
successful. If so, then the second and third return values are mutually inverse
homomorphisms (modulo scalars if G isomorphic to (PSL)(d, q)) from G to
SL(d, q) and from SL(d, q) to G.
Warning: This function often returns false even when G is
isomorphic to SL(d, q) or PSL(d, q), so it should be called repeatedly
until it returns true!
RecognizeSpOdd(G, d, q) : Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map
Use the Kantor-Seress algorithm to try to find an isomorphism between the
finite group G (regarded as a black-box group) and Sp(d, q) or
PSp(d, q) for odd q. The first return value indicates whether the attempt was
successful. If so, then the second and third return values are mutually inverse
homomorphisms (modulo scalars if G isomorphic to (PSp)(d, q)) from G to
Sp(d, q) and from Sp(d, q) to G.
Warning: This function often returns false even when G is
isomorphic to Sp(d, q) or PSp(d, q), so it should be called repeatedly
until it returns true!
RecognizeSp4(G, q) : Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map, Map, Map, SeqEnum, SeqEnum
Use an algorithm of Peter Brooksbank to try to find an isomorphism between the
finite group G (regarded as a black-box group) and Sp(4, q).
The first return value indicates whether the attempt was
successful. If so, then the second and third return values are mutually
inverse homomorphisms from G to (P)Sp(d, q) and from (P)Sp(d, q) to G.
The fourth and fifth return values are mutually inverse homomorphisms from G
to the word group W of G and from W to G. The sixth and seventh return
values are standard generators for G and straight-line programs for these
generators in the generators of G.
RecognizeSU3(G, d, q) : Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map
Use an algorithm of Peter Brooksbank to try to find an isomorphism between the
finite group G (regarded as a black-box group) and SU(3, q) or
PSU(3, q) for q>2. The first return value indicates whether the attempt was
successful. If so, then the second and third return values are mutually inverse
homomorphisms (modulo scalars if G isomorphic to (PSU)(3, q)) from G to
SU(3, q) and from SU(3, q) to G.
The third and fourth return values are mutually inverse homomorphisms from G
to the word group W of G and from W to G.
RecognizeSU4(G, d, q) : Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map
Use an algorithm of Peter Brooksbank to try to find an isomorphism between the
finite group G (regarded as a black-box group) and SU(4, q) or
PSU(4, q). The first return value indicates whether the attempt was
successful. If so, then the second and third return values are mutually inverse
homomorphisms (modulo scalars if G isomorphic to (PSU)(4, q)) from G to
SU(4, q) and from SU(4, q) to G.
The third and fourth return values are mutually inverse homomorphisms from G
to the word group W of G and from W to G.
Let H be a perfect classical group of degree d, and let H act
absolutely irreducibly on a defining characteristic
module W of dimension at most d2.
Magaard, O'Brien & Seress [MOAS08] and Brian Corr [Cor13]
and Csaba Schneider (in preparation)
describe algorithms which, given as input the representation
of H on W, construct a d-dimensional projective representation of H.
Schneider's algorithms, and his implementations,
are used for the exterior and symmetric square representations of H;
those of [MOAS08], [Cor13], and their implementation
prepared by Brian Corr and Eamonn O'Brien, are used for the other cases.
Note that the algorithms have various limitations in terms of type of group,
degree d,
and defining field size; if an algorithm does not apply to the input case, it
returns false.
RecogniseSmallDegree(G, type, d, q) : GrpMat, MonStgElt, RngIntElt,RngIntElt -> BoolElt, GrpMat, Map, Map
If G is a perfect defining characteristic absolutely irreducible representation of
a classical group H of degree d and G has degree in [d + 1, ..., d2], then
return true, H, map from H to G, and map from G to H;
otherwise return false.
In the second signature, we supply the information that
H has degree d, defining field GF(q),
and its type is one of SL, Sp, SU, Omega, Omega+, Omega-.
The group G is a perfect defining characteristic absolutely irreducible representation of a
classical group H of small degree, to which RecogniseSmallDegree has
been successfully applied; if g is in G, return true and a
preimage of g in H, otherwise false.
The group G is a perfect defining characteristic absolutely irreducible representation of a
classical group H of small degree, to which RecogniseSmallDegree has
been successfully applied; if h is in H, return true and the
image of h in G, otherwise false.
Note that SmallDegreePreimage and this function are inverses only
up to a choice of scalars.
> G := SL(4, 9);
> M := GModule (G);
> M := SymmetricPower (M, 2);
> G := MatrixGroup (M);
> G := RandomConjugate (G);
> flag, H := RecogniseSmallDegree (G, "SL", 4, 9);
> flag;
true
> H;
MatrixGroup(4, GF(3^2))
Generators:
[ 0 1 0 0]
[ 0 0 0 1]
[$.1^6 2 2 $.1]
[ 2 $.1 0 $.1]
[ 0 0 1 0]
[$.1^2 $.1^7 1 $.1^6]
[ 1 2 $.1^6 $.1^6]
[ $.1 0 $.1^7 0]
> g := Random (G);
> flag, h := SmallDegreePreimage (G, g);
> h;
[$.1^6 0 0 $.1^2]
[$.1^6 0 $.1^3 0]
[$.1^2 $.1^5 2 $.1]
[ 0 $.1^3 $.1^5 $.1]
> flag, gbar := SmallDegreeImage (G, h);
> flag;
true
> IsScalar (g * gbar^-1);
true
A description of the functionality for constructive recognition and
constructive membership testing of the Suzuki groups (Sz)(q),
with q = 22m + 1 for some m > 0 follows.
The main intrinsics of the package are RecogniseSz(G)
which performs constructive recognition of G isomorphic to (Sz)(q),
SzElementToWord(G, g) which returns a
GrpSLPElt for g in the generators of G, and
IsSuzukiGroup(G) which is a non-constructive test
for isomorphism between G and (Sz)(q).
Informative printing can be obtained using one of a number of verbose flags:
- SuzukiGeneral, for the general routines.
- SuzukiStandard, for the routines related to the standard copy.
- SuzukiConjugate, for the routines related to conjugation.
- SuzukiTensor, for the routines related to tensor decomposition.
- SuzukiMembership, for the routines related to membership testing.
- SuzukiCrossChar, for the routines related to cross-characteristic
representations.
- SuzukiTrick, for the routines related to the double coset trick.
- SuzukiNewTrick, for the routines related to the stabiliser trick.
For each of the flags, the verbose level takes any value up to 10, with
higher values resulting in more output.
Given a matrix group G, this function determines (non-constructively)
whether or not G is isomorphic to (Sz)(q). The corresponding
finite field cardinality q is also returned.
If the group G is defined over a field of odd characteristic or has
degree greater than 4, the Monte Carlo algorithm of LieType
is used. If G has degree 4 and is over a field of characteristic 2,
then a fast Las Vegas algorithm is used, described in [Baccent127aaccent127a06].
RecognizeSz(G : parameters) : GrpMat -> BoolElt, Map, Map, Map, Map
Verify: BoolElt Default: true
FieldSize: RngIntElt Default:
Optimise: BoolElt Default: false
Let G be a group that is absolutely irreducible and is defined over a
minimal field. This function constructively recognises G as a Suzuki group.
If G is isomorphic to (Sz)(q), where q is the size of the defining
field of G, then return:
- Isomorphism from G to (Sz)(q).
- Isomorphism from (Sz)(q) to G.
- Map from G to the word group of G.
- Map from the word group of G to G.
The isomorphisms are composed of maps that are defined by rules, so
Function should be used on each component to avoid
unnecessary built-in membership testing.
The word group is the GrpSLP group which is the parent of the
elements returned by SzElementToWord. In general this is not
the same as WordGroup(G), but is created from it using
AddRedundantGenerators.
If Verify is true, then it is checked if G is isomorphic to
(Sz)(q), using IsSuzukiGroup.
In that case, FieldSize must be set to the correct value of q.
Constructive recognition of 2.(Sz)(8) is also handled.
If Optimise is true, then the third map returns element in an
optimised word group (using AddRedundantGenerators). Then each
invocation of the map will be faster, but the initialisation will take
longer.
The algorithms used for constructive recognition are
described in [Baccent127aaccent127a06] and [Baccent127aaccent127a05].
If G has been constructively recognised as a Suzuki group,
and if g is an element of G, then return true and a
GrpSLPElt from the word group of G which evaluates to g,
else return false.
This facilitates membership testing in G.
If q = 22m + 1 for some m > 0, return a short presentation of
(Sz)(q) on the Magma standard generators,
i.e. the generators returned by the Sz intrinsic.
G is constructively recognised as (Sz)(q) for some q.
Verify that it satisfies a presentation for this group.
CheckInput: BoolElt Default: true
Let F be a finite field of cardinality q = 22m + 1 for some m > 0,
and let twists be a sequence of n distinct integers in the range
[0 ... 2m]. The function returns an absolutely irreducible representation
of (Sz)(q) having dimension 4n, being a tensor product of twisted
powers of the copy returned by the Sz intrinsic, where the twists are
given by the input sequence.
If CheckInput is true, then it is verified that F and twists
satisfy the above requirements. Otherwise this is not checked.
We illustrate the basic facilities starting with a random conjugate
of the standard version of the Suzuki group Sz(32). We first perform
non-constructive recognition.
> G := Sz(32);
> G ^:= Random(Generic(G));
> flag, q := SuzukiRecognition(G);
> flag, q eq 32;
true true
The next step is to perform constructive recognition. The explicit
isomorphisms will be the values of iso and inv.
> flag, iso, inv, g2slp, slp2g := RecognizeSz(G);
> flag;
true
> iso, inv;
Mapping from: GrpMat: G to MatrixGroup(4, GF(2^5)) given by a rule [no inverse]
Mapping from: MatrixGroup(4, GF(2^5)) to GrpMat: G given by a rule [no inverse]
We now experiment with membership testing. We use Function to avoid Magma's
built-in membership testing but in doing so, we may not obtain the shortest
possible SLP.
> w := Function(g2slp)(G.1);
> #w;
284
The algorithm is probabilistic, so different executions will most
likely give different results.
> ww := Function(g2slp)(G.1);
> w eq ww;
false
Note that the resulting SLPs are from a word group that is not the word
group W corresponding to the defining generators of G. However, they
can be coerced into W.
> W := WordGroup(G);
> NumberOfGenerators(Parent(w)), NumberOfGenerators(W);
7 3
> flag, ww := IsCoercible(W, w);
> flag;
true
> slp2g(w) eq Evaluate(ww, UserGenerators(G));
true
So there are two ways to get the element back. An alternative is to use
the intrinsic SzElementToWord, which is better if the elements
are not known to lie in the group.
> flag, ww := SzElementToWord(G, G.1);
> flag, slp2g(w) eq slp2g(ww);
true true
We take an element just outside the group.
> H := Sp(4, 32);
> flag, ww := SzElementToWord(G, H.1);
> flag;
false
> // in this case we will not get an SLP
> ww := Function(g2slp)(H.1);
> ww;
false
> SatisfiesSzPresentation(G);
true
As a variation we apply the machinery to 2.Sz(8). We demonstrate
constructive recognition and constructive membership testing.
> A := ATLASGroup("2Sz8");
> reps := MatRepKeys(A);
> G := MatrixGroup(reps[3]);
> Degree(G), CoefficientRing(G);
40 Finite field of size 7
> flag, iso, inv, g2slp, slp2g := RecognizeSz(G);
> flag;
true
> R := RandomProcess(G);
> g := Random(R);
> w := Function(g2slp)(g);
> slp2g(w) eq g;
true
For the next example we consider a case where the dimension is large.
We construct the Suzuki group in a 64-dimensional matrix representation
and then take a random conjugate and also rewrite is over a smaller
field.
> F := GF(2, 9);
> twists := [0, 3, 6];
> G := SuzukiIrreducibleRepresentation(F, twists);
> Degree(G), IsAbsolutelyIrreducible(G);
64 true
> G ^:= Random(Generic(G));
> flag, GG := IsOverSmallerField(G);
> flag, CoefficientRing(GG);
true Finite field of size 2^3
Non-constructive recognition is harder in this case and will give us the defining
field size. Constructive recognition will decompose the tensor product.
> time SuzukiRecognition(GG);
true 512
Time: 2.330
> time flag, iso, inv, g2slp, slp2g := RecogniseSz(GG);
Time: 4.800
> iso;
Mapping from: GrpMat: GG to MatrixGroup(4, GF(2^9)) given by a rule [no inverse]
Constructive membership is again easy
> R := RandomProcess(GG);
> g := Random(R);
> time w := Function(g2slp)(g);
Time: 0.020
> // but SLP evaluation is harder in large dimensions
> time slp2g(w) eq g;
true
Time: 0.370
> time SatisfiesSzPresentation(GG);
true
Time: 10.930
The final example will be in cross characteristic. We build a representation
of Sz(8) in cross characteristic.
> G := Sz(8);
> _, P := SuzukiPermutationRepresentation(G);
> // for example over GF(9)
> M := PermutationModule(P, GF(3, 2));
> factors := CompositionFactors(M);
> exists(m64){f : f in factors | Dimension(f) eq 64};
true
> m64;
GModule m64 of dimension 64 over GF(3^2)
> H := ActionGroup(m64);
> IsAbsolutelyIrreducible(H);
true
> flag, G := IsOverSmallerField(H);
> Degree(G), CoefficientRing(G);
64 Finite field of size 3
We actually end up with a group in characteristic 3.
> time flag, iso, inv, g2slp, slp2g := RecogniseSz(G);
Time: 3.490
> iso;
Mapping from: GrpMat: G to MatrixGroup(4, GF(2^3)) given by a rule [no inverse]
> R := RandomProcess(G);
> g := Random(R);
> time w := Function(g2slp)(g);
Time: 0.010
> time slp2g(w) eq g;
true
Time: 0.110
> time SatisfiesSzPresentation(G);
true
Time: 0.330
This machinery provides functionality for constructive recognition and constructive
membership testing of the small Ree groups ((2)G2)(q) = (Ree)(q), with
q = 32m + 1 for some m > 0.
The important intrinsics are RecogniseRee which performs constructive
recognition of G isomorphic to (Ree)(q), ReeElementToWord which returns
a GrpSLPElt for g in the generators of G, and IsReeGroup
which is a non-constructive test for isomorphism between G and (Ree)(q).
There are a few verbose flags used in the package.
- ReeGeneral, for the general routines.
- ReeStandard, for the routines related to the standard copy.
- ReeConjugate, for the routines related to conjugation.
- ReeTensor, for the routines related to tensor decomposition.
- ReeMembership, for the routines related to membership testing.
- ReeCrossChar, for the routines related to cross-characteristic representations.
- ReeTrick, for the routines related to the stabiliser trick.
- ReeInvolution, for the routines related to involution centralisers.
- ReeSymSquare, for the routines related to symmetric square decomposition.
All the flags can be set to values up to 10, with higher values resulting in more output.
RecognizeRee(G : parameters) : GrpMat -> BoolElt, Map, Map, Map, Map
Verify: BoolElt Default: true
FieldSize: RngIntElt Default:
Optimise: BoolElt Default: false
The matrix group G is absolutely irreducible and defined over minimal field.
Constructively recognise G as a Ree group. If G is isomorphic to (Ree)(q) where q is the size of the defining field of G, then return:
- Isomorphism from G to (Ree)(q).
- Isomorphism from (Ree)(q) to G.
- Map from G to the word group of G.
- Map from the word group of G to G.
The isomorphisms are composed of maps that are defined by rules, so
Function should be used on each component to avoid
unnecessary built-in membership testing.
The word group is the GrpSLP which is the parent of the
elements returned by ReeElementToWord. In general this is not
the same as WordGroup(G), but is created from it using
AddRedundantGenerators.
If Verify is true, then it is checked that G is isomorphic to
(Ree)(q), using IsReeGroup, otherwise this is not checked. In that case, FieldSize must be set to the correct value of q.
If Optimise is true, then the third map returns element in an
optimised word group (using AddRedundantGenerators). Then each
invocation of the map will be faster, but the initialisation will take
longer.
The algorithm for constructive recognition is described in [Baccent127aaccent127a14].
If G has been constructively recognised as a Ree group,
and if g is an element of G, then return true and a GrpSLPElt from the word group of G which evaluates to g, else return false.
This facilitates membership testing in G.
Determine (non-constructively) if G is isomorphic to (Ree)(q). The corresponding q is also returned.
If G is over a field of characteristic not 3 or has degree greater
than 7, the Monte Carlo algorithm of LieType is
used. If G has degree 7 and is over a field of characteristic
3, then a fast Las Vegas algorithm is used.
CheckInput: BoolElt Default: true
The finite field F must have size q = 32m + 1 for some m > 0, and twists should be a sequence of n distinct pairs of integers (i, j) where i is 7 or 27 and j in the range [0 ... 2m].
Return an absolutely irreducible representation of (Ree)(q), a tensor product of twisted powers of the representation of dimension 7 or 27, where the twists are given by
the input sequence.
If CheckInput is true, then it is verified that F and twists satisfy the above requirements. Otherwise this is not checked.
Our first example shows off the recognition machinery for the Ree group
defined over GF(27).
> SetSeed(1);
> F := GF(3, 3);
> G := ReeGroup(F);
> G ^:= Random(Generic(G));
> flag, q := ReeRecognition(G);
> flag, q eq #F;
true true
> flag, iso, inv, g2slp, slp2g := RecognizeRee(G);
> flag;
true
> iso, inv;
Mapping from: GrpMat: G to MatrixGroup(7, GF(3^3)) given by a rule [no inverse]
Mapping from: MatrixGroup(7, GF(3^3)) to GrpMat: G given by a rule [no inverse]
We now experiment with membership testing. As the algorithm is probabilistic,
different executions will most likely give different results.
> w := Function(g2slp)(G.1);
> #w;
342
> ww := Function(g2slp)(G.1);
> w eq ww;
false
The resulting SLPs are from another word group but can be coerced
into W.
> W := WordGroup(G);
> NumberOfGenerators(Parent(w)), NumberOfGenerators(W);
7 3
> flag, ww := IsCoercible(W, w);
> flag;
true
> // so there are two ways to get the element back
> slp2g(w) eq Evaluate(ww, UserGenerators(G));
true
If the elements are not known to lie in the group, a better alternative
is to use the intrinsic ReeElementToWord. We take a generator of
Ω(7, F) as an example of an element not lying in G2(27).
> flag, ww := ReeElementToWord(G, G.1);
> flag, slp2g(w) eq slp2g(ww);
true true
> H := Omega(7, #F);
> flag, ww := ReeElementToWord(G, H.1);
> flag;
false
> ww := Function(g2slp)(H.1);
> ww;
false
This machinery provides functionality for constructive recognition and constructive
membership testing of the large Ree groups ((2)F4)(q) = (LargeRee)(q), with
q = 22m + 1 for some m > 0.
The important intrinsics are RecogniseLargeRee which performs constructive
recognition of G isomorphic to (LargeRee)(q), LargeReeElementToWord which returns
a GrpSLPElt for g in the generators of G, and IsLargeReeGroup
which is a non-constructive test for isomorphism between G and (LargeRee)(q).
There are a few verbose flags used in the package.
- LargeReeGeneral, for the general routines.
- LargeReeStandard, for the routines related to the standard copy.
- LargeReeConjugate, for the routines related to conjugation.
- LargeReeRyba, for the routines related to membership testing.
- LargeReeTrick, for the routines related to the stabiliser trick.
- LargeReeInvolution, for the routines related to involution centralisers.
All the flags can be set to values up to 10, with higher values resulting in more output.
RecognizeLargeRee(G : parameters) : GrpMat -> BoolElt, Map, Map, Map, Map
Verify: BoolElt Default: true
FieldSize: RngIntElt Default:
Optimise: BoolElt Default: false
The matrix group G is absolutely irreducible and defined over minimal field.
Constructively recognise G as a Large Ree group. If G is isomorphic to (LargeRee)(q) where q is the size of the defining field of G, then return:
- Isomorphism from G to (LargeRee)(q).
- Isomorphism from (LargeRee)(q) to G.
- Map from G to the word group of G.
- Map from the word group of G to G.
The isomorphisms are composed of maps that are defined by rules, so
Function should be used on each component to avoid
unnecessary built-in membership testing.
The word group is the GrpSLP which is the parent of the
elements returned by LargeReeElementToWord. In general this is not
the same as WordGroup(G), but is created from it using
AddRedundantGenerators.
If Verify is true, then it is checked that G is isomorphic to
(LargeRee)(q), using IsLargeRee, otherwise this is not checked. In that case, FieldSize must be set to the correct value of q.
If Optimise is true, then the third map returns element in an
optimised word group (using AddRedundantGenerators). Then each
invocation of the map will be faster, but the initialisation will take
longer.
If G has been constructively recognised as a Large Ree group,
and if g is an element of G, then return true and a GrpSLPElt from the word group of G which evaluates to g, else return false.
This facilitates membership testing in G.
Determine (non-constructively) if G is isomorphic to (LargeRee)(q). The corresponding q is also returned.
If G is over a field of characteristic not 2 or has degree greater
than 26, the Monte Carlo algorithm of LieType is
used. If G has degree 26 and is over a field of characteristic
2, then a fast Las Vegas algorithm is used.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|