67.23 RecogniseClassicalNP

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:

returns one of "linear", "symplectic", "orthogonalplus", "orthogonalminus", "orthogonalcircle" or "unitary" if G is known to be a classical group of this type modulo scalars, otherwise "unknown".

IsSLContainedFlag:

returns true if G contains the special linear group SL(d,q).

IsSymplecticGroupFlag:

returns true if G is contained in GSp(d,q) modulo scalars and contains Sp(d,q). IsOrthogonalGroupFlag:
returns true if G is contained in an orthogonal group modulo scalars and contains the corresponding Omega. IsUnitaryGroupFlag:
returns 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 

Previous Up Top Next
Index

GAP 3.4.4
April 1997