In this section, we describe functions developed by Niemeyer and Praeger (see [11, 12] for details) to recognise classical groups in their natural representation over finite fields.
RecogniseClassicalNP( G [,case] [,N] )
This is the top-level function taking as input a group G, which is a
subgroup of GL(d,q) with d > 2. The other optional arguments have
the same meaning as those supplied to RecogniseClassical.
The aim of RecogniseClassicalNP is to test whether G contains the
subgroup O corresponding to the value of case. The algorithm
employed is Monte-Carlo based on random selections of elements from G.
RecogniseClassicalNP returns either true or false or "does not
apply". If it returns true and G satisfies the constraints listed
for case (see RecogniseClassical) then we know with certainty that
G contains the corresponding classical subgroup Omega. It is not
checked whether G satisfies all these conditions. If it returns
"does not apply" then either the theoretical background of this
algorithm does not allow us to decide whether or not G contains
Omega (because the parameter values are too small) or G is not a
group of type case. If it returns false then there is still a
possibility that G contains Omega. The probability that G contains
Omega and RecogniseClassicalNP returns false can be controlled by
the parameter N, which is the number of elements selected from G. The
larger N is, the smaller this probability becomes. If N is not
passed as an argument, the default value for N is 15 if case is
"linear" and 25 otherwise. These values were experimentally
determined over a large number of trials. But if d has several
distinct prime divisors, larger values of N may be required (see [12]).
The complexity of the function for small fields (q < 2^{16}) and for a given value of N is O( d^3, loglog d, ) bit operations.
Assume InfoRecog1 is set to Print; if RecogniseClassicalNP returns
true, it prints
"Proved that the group contains a classical group of type <case>
in <n> selections\",
where n is the actual number of elements used; if
RecogniseClassicalNP returns false, it prints "The group probably
does not contain a classical group" and possibly also a statement
suggesting what the group might be.
If case is not supplied, then ClassicalForms seeks to determine which
form is preserved. If ClassicalForms fails to find a form, then
RecogniseClassicalNP returns false.
Details of the computation, including the identification of the classical
group type, are stored in the component G.recognise. Its contents can
be accessed using the following flag functions.
ClassicalTypeFlag:"linear", "symplectic", "orthogonalplus",
"orthogonalminus", "orthogonalcircle" or "unitary" if G is
known to be a classical group of this type modulo scalars,
otherwise "unknown".
IsSLContainedFlag:true if G contains the special linear group SL(d,q).
IsSymplecticGroupFlag:true if G is contained in GSp(d,q) modulo scalars and
contains Sp(d,q).
IsOrthogonalGroupFlag:true if G is contained in an orthogonal group modulo
scalars and contains the corresponding Omega.
IsUnitaryGroupFlag:true if G is contained in an unitary group modulo scalars
and contains the corresponding Omega.
These last four functions return true, false, or "unknown". Both
true and false are conclusive. The answer "unknown" indicates
either that the algorithm failed to determine whether or not G is a
classical group or that the algorithm is not applicable to the supplied
group.
If RecogniseClassicalNP returns true, then G.recognise contains all
the information that proves that G contains the classical group having
type G.recognise.type. The record components d, p, a and q
identify G as a subgroup of GL(d,q), where q= p^a. For each e in
G.recognise.E the group G contains a ppd( d, q; e)-element (see
IsPpdElement) and for each e in G.recognise.LE it contains a large
ppd(d, q; e)-element. Further, it contains a basic ppd(d,
q;e)-element if e is in G.recognise.basic. Finally, the component
G.recognise.isReducible is false, indicating that G is now known to
act irreducibly.
If RecogniseClassicalNP returns "does not apply", then G has no
record G.recognise.
If RecogniseClassicalNP returns false, then G.recognise gives some
indication as to why the algorithm failed to prove that G contains a
classical group. Either G could not be shown to be generic and
G.recognise.isGeneric is false and G.recognise.E, G.recognise.LE
and G.recognise.basic will indicate which kinds of ppd-elements could
not be found; or G.recognise.isGeneric is true and the algorithm
failed to rule out that G preserves an extension field structure and
G.recognise.possibleOverLargerField is true; or G.isGeneric is
true and G.possibleOverLargerField is false and the possibility
that G is nearly simple could not be ruled out and
G.recognise.possibleNearlySimple contains a list of names of possible
nearly simple groups; or ClassicalForms failed to find a form and
G.recognise.noFormFound is true; or finally G.isGeneric is true
and G.possibleOverLargerField is false and G.possibleNearlySimple
is empty and G was found to act reducibly and G.recognise.isReducible
is true.
If RecogniseClassicalNP returns false, then a recall to
RecogniseClassicalNP for the given group uses the previously computed
facts about the group stored in G.recognise.
gap> RecogniseClassicalNP( GL(10,5), "linear", 10 );
true
gap> RecogniseClassicalNP( SP(6,2), "symplectic", 10 );
#I This algorithm does not apply in this case
"does not apply"
gap> G := SL(20, 5);;
gap> RecogniseClassicalNP( G );
true
gap> G.recognise;
rec(
d := 20,
p := 5,
a := 1,
q := 5,
E := [ 11, 12, 16, 18 ],
LE := [ 11, 12, 16, 18 ],
basic := 12,
isReducible := false,
isGeneric := true,
type := "linear" )
gap> InfoRecog1 := Print;; InfoRecog2 := Print;;
gap> G := GeneralUnitaryMatGroup(7,2);;
gap> RecogniseClassicalNP( G );
#I The case is unitary
#I <G> acts irreducibly, block criteria failed
#I The group is generic in 4 selections
#I The group is not an extension field group
#I The group does not preserve an extension field
#I The group is not nearly simple
#I The group acts irreducibly
#I Proved that group contains classical group of type unitary
#I in 6 random selections.
true
gap > G.recognise;
rec(
d := 7,
p := 2,
a := 2,
q := 4,
E := [ 5, 7 ],
LE := [ 5, 7 ],
basic := 7,
isReducible := false,
isGeneric := true,
type := "unitary" )
gap> InfoRecog1 := Print;; InfoRecog2 := Print;;
gap> G := Group (
[[0,1,0,0],
[1,1,0,0],
[0,0,0,1],
[0,0,1,1]] * GF(2).one,
[[0,0,1,0],
[0,1,1,0],
[1,0,1,1],
[0,1,1,1]] * GF(2).one );
gap> RecogniseClassicalNP (G);
#I The case is linear
#I <G> acts irreducibly, block criteria failed
#I The group is generic in 8 selections
#I The group is not an extension field group
#I The group does not preserve an extension field
#I G\'\ might be A\_7;
#I G\'\ is not a Mathieu group;
#I G\'\ is not PSL(2,r)
#I The group could be a nearly simple group.
false
gap> G.recognise;
rec(
d := 4,
p := 2,
a := 1,
q := 2,
E := [ 3, 4 ],
LE := [ 3 ],
basic := 4,
isReducible := false,
isGeneric := true,
possibleNearlySimple := [ "A7" ],
dimsReducible := [ 0, 4 ],
possibleOverLargerField := false )
We now describe some of the lower-level functions used.
GenericParameters( G, case )
This function takes as input a subgroup G of GL(d,q) and a string
case, one of the list given under RecogniseClassicalGroup. The group
G has generic parameters if the subgroup Omega of GL(d,q)
contains two different ppd-elements (see IsPpdElement), that is a
ppd(d, q; e_1)-element and a ppd(d, q; e_2)-element for d/2 < e_1
< e_2 le d such that at least one of them is a large ppd-element and
one is a basic ppd-element. The function GenericParameters returns
true if G has generic parameters. In this case RecogniseClassicalNP
can be applied to G and case. If G does not have generic
parameters, the function returns false.
gap> GenericParameters( SP(6,2), "symplectic" );
false
gap> GenericParameters( SP(12,2), "symplectic" );
true
[Comment: In the near future we propose to extend and modify our algorithm to deal with cases where the group Omega does not contain sufficient ppd-elements.]
IsGeneric( G, N )
This function takes as input a subgroup G of GL(d,q) and an integer
N. The group G is generic if it is irreducible and contains two
different ppd-elements (see IsPpdElement), that is a ppd(d, q;
e_1)-element and a ppd(d, q; e_2)-element for d/2 < e_1 < e_2 le
d such that at least one of them is a large ppd-element and one is a
basic ppd-element. It chooses up to N elements in G and increases
G.recognise.n by the number of random selections it made. If among
these it finds the two required different ppd-elements, which is
established by examining the sets G.recognise.E, G.recognise.LE,
and G.recognise.basic, then it sets G.recognise.isGeneric to
true and returns true. If after N random selections it fails to
find two different ppd-elements, the function returns false. It is not
tested whether G actually is irreducible.
gap> IsGeneric( SP(12,2), 20 );
true
IsExtensionField( G, case, N )
This function takes as input a subgroup G of GL(d,q), a string
case, one of the list given under RecogniseClassicalGroup, and an
integer N. It assumes, but does not test that G is generic (see
IsGeneric). We say that the group G can be defined over an extension
field if there is a prime b dividing d such that G is conjugate to
a subgroup of Z.GL(d/b,q^b).b, where Z is the group of scalar
matrices in GL(d,q). Then IsExtensionField returns m if certain
elements are found in m random selections which together prove that G
cannot be a subgroup of an extension field group. In this case
G.recognise.possibleOverLargerField is set to false. If, after N
random selections of elements from G, this could not be established,
then IsExtensionField returns true. Hence, if it returns true,
then either G is an extension field group or one needs to select more
elements of G to establish that this is not the case. The component
G.recognise.possibleOverLargerField is set to true.
gap> IsExtensionField( GL(12,2), "linear", 30 );
8
IsGenericNearlySimple( G, case, N )
The subgroup G of GL(d,q) is said to be nearly simple if there is
some nonabelian simple group S such that S le G/(G cap Z) le {rm
Aut}(S), where Z denotes the subgroup of nonsingular scalar matrices
of GL(d,q). This function takes as input a subgroup G of GL(d,q),
a string case, one of the list given under RecogniseClassicalGroup,
and an integer N. It assumes but does not test that G is irreducible
on the underlying vector space, is generic (see IsGeneric), and is not
contained in an extension field group (see IsExtensionField). This
means that G is known to contain two different ppd-elements (see
IsPpdElement), that is a ppd(d, q; e_1)-element and a ppd(d, q;
e_2)-element for d/2 < e_1 < e_2 le d such that at least one of
them is a large ppd-element and one is a basic ppd-element, and the
values e_1 and e_2 for the elements are stored in G.recognise.E.
At this stage, the theoretical analysis in [12] tells us that either G
contains Omega, or the string case is "linear" and G is an
absolutely irreducible generic nearly simple group. All possibilities
for the latter groups are known explicitly, and IsGenericNearlySimple
tries to establish that G is not one of these groups. Thus it first
checks that case is "linear", and if so performs further tests.
IsGenericNearlySimple returns false if certain elements are found
which together prove that G cannot be a generic nearly simple group.
If, after N random selections of elements from G, this could not be
shown, then IsGenericNearlySimple returns true and G might be a
generic nearly simple group. It increases G.recognise.n by the
number of elements selected. In this case either G is nearly simple or
there is a small chance that the output true is incorrect. In fact the
probability with which the algorithm will return the statement true
when G is not nearly simple can be made arbitrarily small depending on
the number N of random selections performed. The list of irreducible
generic nearly simple groups is very short. The name of each nearly
simple group which might be isomorphic to G is stored as a string in
G.recognise.possibleNearlySimple. If InfoRecog2 is set to Print,
then in the case that G is such a group IsGeneric will print the
isomorphism type of the nearly simple group.
gap> IsGenericNearlySimple( GL(12,2), "symplectic", 30 );
11
GAP 3.4.4