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