# 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 ```

GAP 3.4.4
April 1997