# Group Recognition

## Constructive Recognition of Alternating Groups

### `RecogniseAlternatingOrSymmetric(G : parameters): Grp, RngIntElt -> BoolElt, Map, Map, Map, Map, BoolElt`

```magma
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 \geq 5$. Note that $G$ can be either a matrix or permutation representation of $H$.

The algorithm used is that of [[Jambor *et al.*, 2013](../../references.md#cite-altsymrecogn)]. 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 \geq 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. [[Beals *et al.*, 2003](../../references.md#cite-altsymrecog1)]. Otherwise, the algorithm employed for this map is that of [[Bratus and Pak, 2000](../../references.md#cite-bratus-pak)], 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. [[Jambor *et al.*, 2013](../../references.md#cite-altsymrecogn)]. The second part verifies that these elements generate $G$, and constructs isomorphisms between $G$ and $H$, cf. [[Beals *et al.*, 2003](../../references.md#cite-altsymrecog1)]. 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 \in \{5,\ldots,10\}$ and central extensions.

### `AlternatingOrSymmetricElementToWord(G, g): Grp, GrpElt -> BoolElt, GrpSLPElt`

If $g \in 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.

### `Example: Recognise Altsym2 (ex-98afe7)`

We illustrate the use of these functions for a representation of $A_{13}$.

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

```

### `RecogniseSymmetric(G, n: parameters): Grp, RngIntElt -> BoolElt, Map, Map, Map, Map, BoolElt`

```magma
maxtries : RngIntElt                    Default: 100n + 5000
Extension: BoolElt                      Default: false
```

The group $G$ should be known to be isomorphic to the symmetric group $S_n$ for some $n \ge 8$. The Bratus-Pak algorithm [[Bratus and Pak, 2000](../../references.md#cite-bratus-pak)] (implemented by Derek Holt) is used to define an isomorphism between $G$ and $S_n$. If successful, return `true`, homomorphism from $G$ to $S_n$, homomorphism from $S_n$ 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 $S_n$ or to a perfect central extension $2.S_n$. In that case, the first two maps returned will be a homomorphism from $G$ to $S_n$ and a map from $S_n$ to $G$ that induces a homomorphism onto $G/Z(G)$. The sixth value returned will be `true`, if $G \cong 2.S_n$ and `false`, if $G \cong 2.A_n$.

If unsuccessful, `false` is returned. This will always occur if the input group is not isomorphic to $S_n$ (or $2.S_n$ when `Extension` is set) with $n \ge 8$, and may occur occasionally even when $G$ is isomorphic to $S_n$. The optional parameter `maxtries` (default $100n + 5000$) can be used to control the number of random elements chosen before giving up.

### `SymmetricElementToWord(G, g): Grp, GrpElt -> BoolElt, GrpSLPElt`

If $g$ is an element of $G$ which has been constructively recognised to be isomorphic to $S_n$ (or $2.S_n$), then return `true` and element of word group for $G$ which evaluates to $g$. Otherwise return `false`. This facilitates membership testing in $G$.

### `RecogniseAlternating(G, n: parameters): Grp, RngIntElt -> BoolElt, Map, Map, Map, Map, BoolElt`

```magma
maxtries : RngIntElt                    Default: 100n + 5000
Extension: BoolElt                      Default: false
```

The group $G$ should be known to be isomorphic to the alternating group $A_n$ for some $n \ge 9$. The Bratus-Pak algorithm [[Bratus and Pak, 2000](../../references.md#cite-bratus-pak)] (implemented by Derek Holt) is used to define an isomorphism between $G$ and $A_n$. If successful, return `true`, homomorphism from $G$ to $A_n$, homomorphism from $A_n$ 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 $A_n$ or to a perfect central extension $2.A_n$. In that case, the first two maps returned will be a homomorphism from $G$ to $A_n$ and a map from $A_n$ to $G$ that induces a homomorphism onto $G/Z(G)$. The sixth value returned will be `true`, if $G \cong 2.A_n$ and `false` otherwise.

If unsuccessful, `false` is returned. This will always occur if the input group is not isomorphic to $A_n$ (or $2.A_n$ when `Extension` is set) with $n \ge 9$, and may occur occasionally even when $G$ is isomorphic to $A_n$. The optional parameter `maxtries` (default $100n + 5000$) can be used to control the number of random elements chosen before giving up.

### `AlternatingElementToWord(G, g): Grp, GrpElt -> BoolElt, GrpSLPElt`

If $g$ is an element of $G$ which has been constructively recognised to be isomorphic to $A_n$ (or $2.A_n$), then return `true` and element of word group for $G$ which evaluates to $g$. Otherwise return `false`. This facilitates membership testing in $G$.

### `GuessAltsymDegree(G: parameters): Grp -> BoolElt, MonStgElt, RngIntElt`

```magma
maxtries : RngIntElt                    Default: 5000
Extension: BoolElt                      Default: false
```

The group $G$ should be believed to be isomorphic to $S_n$ or $A_n$ for some $n > 6$, or to $2.S_n$ or $2.A_n$ 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 $S_n$ or $A_n$ (or $2.S_n$ or $2.A_n$ 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 $S_n$ or $A_n$ with $n > 6$. This function was written by Derek Holt.

### `Example: Recognise Altsym2 (ex-785664)`

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.

```magma
> 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.

```magma
> GuessAltsymDegree(Sym(50));
true Symmetric 50
> GuessAltsymDegree(Alt(73));
true Alternating 73
> GuessAltsymDegree(PSL(5,5));
true Alternating 82

```

## Determining the Type of a Finite Group of Lie Type

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.

### `LieCharacteristic(G : parameters): Grp -> RngIntElt`

```magma
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 [[Liebeck and O'Brien, 2007](../../references.md#cite-liebeck-obrien)]. 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`.

### `Example: Write Over Smaller Field (ex-337eef)`

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

```magma
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 [[Babai *et al.*, 2002](../../references.md#cite-bkps)]; 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): GrpMat -> BoolElt, List`

### `SimpleGroupName(G : parameters): GrpPerm -> BoolElt, List`

```magma
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`.

### `Example: Identify Simple (ex-ffaa04)`

We create the classical group $\Omega(7, 5)$ in its natural representation and apply `SimpleGroupName` to it.

```magma
> 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.

```magma
> 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) */

```

## Classical Forms

Let $G$ be an absolutely irreducible subgroup of ${\operatorname{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 $\kappa$ from $V\times V \rightarrow F$. It is $G$-invariant modulo scalars if for each $g \in G$ there is a $\mu_g    \in F$ such that $\kappa(vg,wg)  = \mu_g \kappa(v,w)$ for all $v, w \in V$.

Now suppose that $a\mapsto \bar{a}$ is an automorphism of $F$ of order 2. A *sesquilinear* form is a biadditive function $\kappa$ from $V\times V \rightarrow F$ such that $\kappa(  au, bv) =  a\bar{b} \kappa(u,v)$ for all $u,v \in  V$ and $a,b\in  F$. It is $G$-invariant modulo scalars if for each $g  \in G$ there is a $\mu_g \in F$ such that $\kappa(vg,wg) = \mu_g  \kappa(v,w)$ for all $v, w  \in V$.

A quadratic form is a function $\chi  : V  \rightarrow  F$ such that

**(1)**
$\chi(av) =  a^2 \chi(v)$ for all $a\in F$, $v\in V$; and

**(2)**
the form $\kappa$, defined by $\kappa(u,v)  = \chi( u +  v ) - \chi(u)  - \chi(v)$ for all $u,v \in V$, is bilinear.

It is $G$-invariant if for each $g \in G$, $\chi(vg) = \chi(v)$ for all $v \in V$. It is $G$-invariant modulo scalars if for each $g \in G$ there is a $\mu_g \in F$ such that $\chi(vg) = \mu_g \chi(v)$ for all $v \in V$.

A bilinear form which is $G$-invariant (modulo scalars) is represented by a matrix $B$ such that $g * B*{g}^{tr} = \mu_g B$ for all $g\in G$ and is unique up to multiplication by an element of $F$. Assume $F$ has an automorphism $a \mapsto \bar{a}$ of order $2;$ a sesquilinear form is a matrix $B$ such that $g   * B*\bar{g}^{tr} = \mu_g  B$ for all $g\in   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 $g_{ij}$ by $\bar{g_{ij}}$). A quadratic form is represented by an upper triangular matrix $Q$ such that the matrix $g *   Q * g^{tr}$, normalized into an upper triangular matrix, equals $\mu_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`

```magma
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.

### `SymplecticForm(G: parameters): GrpMat -> BoolElt, AlgMatElt [,SeqEnum]`

```magma
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.

### `SymmetricBilinearForm(G: parameters): GrpMat -> BoolElt, AlgMatElt, MonStgElt [,SeqEnum]`

```magma
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`](#function-grpmat-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.

### `QuadraticForm(G): GrpMat -> BoolElt, AlgMatElt, MonStgElt [,SeqEnum]`

```magma
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`](#function-grpmat-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.

### `UnitaryForm(G): GrpMat -> BoolElt, AlgMatElt [,SeqEnum]`

```magma
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.

### `FormType(G): GrpMat -> MonStgElt`

```magma
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`](#function-grpmat-classicalforms)). Otherwise it returns `"unknown"`.

### `Example: Classical Forms (ex-9382cf)`

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

```

### `TransformForm(form, type): AlgMatElt, MonStgElt -> GrpMatElt`

Return a matrix $m$ such that $G^m$ 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`](#function-grpmat-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.

### `TransformForm(G): GrpMat -> GrpMatElt`

```magma
Scalars: BoolElt                    Default: false
```

This function calls [`ClassicalForms`](#function-grpmat-classicalforms) to find a form fixed by the absolutely irreducible subgroup $G$ of $GL(d,q)$. If `Scalars` is `true`, then [`ClassicalForms`](#function-grpmat-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`.

### `SpinorNorm(g, form): GrpMatElt, AlgMatElt -> RngIntElt`

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 $\Omega$.

### `Example: Spinor (ex-b5d734)`

This function can be used to check whether an element of the orthogonal group, say ${\operatorname{GO}}^+(d,q)$, belongs to $\Omega^+(d,q)$. First check that the element belongs to ${\operatorname{SO}}^+(d,q)$.

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

```

## Recognizing Classical Groups in their Natural Representation

Let $G$ be an irreducible subgroup of ${\operatorname{GL}}(d,q)$. The following algorithm is designed to test whether $G$ contains the corresponding classical group $\Omega$ and is contained in $\Delta$. Here $\Omega$ and $\Delta$ are defined as follows:

**•**
Case “linear”: $\Delta = {\operatorname{GL}}(d,q),$ $\Omega = {\operatorname{SL}}( d, q)$

**•**
Case “symplectic”: $\Delta = {\operatorname{CSp}}(d,q),$ $\Omega = {\operatorname{Sp}}( d, q)$

**•**
Case “orthogonalplus”: $\Delta = {\operatorname{CO}}^+(d,q),$ $\Omega = \Omega^+(d,q)$

**•**
Case “orthogonalminus”: $\Delta = {\operatorname{CO}}^-(d,q),$ $\Omega = \Omega^-(d,q)$

**•**
Case “orthogonalcircle”:$\Delta = {\operatorname{CO}}^\circ(d,q),$ $\Omega = \Omega^\circ(d,q)$

**•**
Case “unitary”: $\Delta = {\operatorname{CU}}(d,q),$ $\Omega = {\operatorname{SU}}(d,q)$

### `RecognizeClassical(G : parameters): GrpMat -> BoolElt`

### `RecogniseClassical(G : parameters): GrpMat -> BoolElt`

```magma
Case            : MonStgElt                    Default: "unknown"
NumberOfElements: RngIntElt                    Default: 25
verbose         : Classical                    Default: Verbose : 3
```

`RecognizeClassical` takes as input a group $G$, which is a subgroup of ${\operatorname{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 $\Omega$ and is contained in $\Delta$. 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 $\Omega$, or $G$ is not contained in $\Delta$, or $G$ is not irreducible, or there is a small chance that $G$ is contained in $\Delta$ and contains $\Omega$. More precisely, if the irreducible group $G$ is contained in $\Delta$ and really does contain $\Omega$ then the probability with which the algorithm returns `false` is less than $\varepsilon$, where $\varepsilon$ is a real number between 0 and 1. The smaller the value of $\varepsilon$, 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 [[Niemeyer and Praeger, 1997](../../references.md#cite-niemeyer-praeger-97)][[Niemeyer and Praeger, 1998](../../references.md#cite-niemeyer-praeger-98)][[Niemeyer and Praeger, 1999](../../references.md#cite-niemeyer-praeger-99)] and Praeger [[Praeger, 1999](../../references.md#cite-praeger-prim)]. Its approach is based on the ${\operatorname{SL}}$-recognition algorithm (Neumann & Praeger, [[Neumann and Praeger, 1992](../../references.md#cite-neumann-praeger-92)]).This implementation also uses algorithms described in Celler & Leedham-Green [[Celler and Leedham-Green, 1997](../../references.md#cite-clg-order)][[Celler and Leedham-Green, 1997](../../references.md#cite-clg-recog)] and Celler et al. [[Celler *et al.*, 1995](../../references.md#cite-randomelements)].

For small fields $(q < 2^{16}),$ the cost of this implementation for a given value of `NumberOfElements` is $O( d^3 \log d )$ bit operations.

### `IsLinearGroup(G): GrpMat -> BoolElt`

This function tests whether the subgroup $G$ of ${\operatorname{GL}}(d,q)$ contains ${\operatorname{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 ${\operatorname{SL}}(d,q)$. See `RecognizeClassical` for more details.

### `IsSymplecticGroup(G): GrpMat -> BoolElt`

This function tests whether the subgroup $G$ of ${\operatorname{CSp}}(d,q)$ contains ${\operatorname{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 ${\operatorname{Sp}}(d,q)$. See `RecognizeClassical` for more details.

### `IsOrthogonalGroup(G): GrpMat -> BoolElt`

This function tests whether the subgroup $G$ of ${\operatorname{CO}}^\epsilon(d,q)$ contains $\Omega^\epsilon(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 $\Omega^\epsilon(d,q)$. See `RecognizeClassical` for more details.

### `IsUnitaryGroup(G): GrpMat -> BoolElt`

This function tests whether the subgroup $G$ of ${\operatorname{CU}}(d,q)$ contains ${\operatorname{SU}}(d,q)$. If the function can establish this fact, it returns `true` and otherwise `false`.

### `ClassicalType(G): GrpMat -> MonStgElt`

If $G$ is known to be a classical subgroup of ${\operatorname{GL}}(d,q)$ this function returns the appropriate classical type as a string. i.e., One of `"linear"`, `"symplectic"`, `"orthogonalplus"`, `"orthogonalminus"`, `"orthogonalcircle"`, or `"unitary"`. Otherwise the function returns `false`.

### `ClassicalGroupType(G): GrpMat -> BoolElt, MonStgElt`

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-"`.)

### `Example: Recognize Classical (ex-9f3ea6)`

```magma
> 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+

```

## Constructive Recognition of Linear Groups

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.

### `RecognizeSL2(G): GrpMat -> BoolElt, Map, Map, Map, Map`

### `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): GrpMat, GrpMatElt -> BoolElt, GrpSLPElt`

### `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): GrpMat -> RngIntElt, RngIntElt`

### `SL2Characteristic(G : parameters): GrpPerm -> RngIntElt, RngIntElt`

```magma
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 [[Liebeck and O'Brien, 2007](../../references.md#cite-liebeck-obrien)]. 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 [[Conder *et al.*, 2006](../../references.md#cite-conder-lg-obrien)]. The algorithm used for other representations was developed by Brooksbank and O’Brien.

### `Example: RecognizeSL2 1 (ex-6829cc)`

Our first example uses $G = {\operatorname{SL}}(2, 3^2)$ 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$.

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

```

### `Example: RecogniseSL2 2 (ex-82f78a)`

We now consider a representation of a $2$-dimensional linear group inside $GL(6, {\bf F}_{5^7} )$.

```magma
> 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.

```magma
> 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, {\bf F}_{5^7} )$ for membership of our group.

```magma
> g := Random(GL(6, 5^7));
> SL2ElementToWord(G, g);
false

```

### `RecogniseSL3(G): GrpMat -> BoolElt, Map, Map, Map, Map`

### `RecogniseSL3(G, q : parameters): GrpMat, RngIntElt -> BoolElt, Map, Map, Map, Map`

```magma
Verify: BoolElt                    Default: true
```

If $G \leq 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)$.

### `SL3ElementToWord(G, g): GrpMat, GrpMatElt -> BoolElt, GrpSLPElt`

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 [[Lübeck *et al.*, 2007](../../references.md#cite-lubeck-magaard-obrien)]. Its current implementation, which is part of the `CompositionTree` package, was developed by Bäärnhielm and O’Brien.

### `Example: Recognise SL3 (ex-46bbe9)`

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.

```magma
> 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, 5^4)$ is contained in our group.

```magma
> IsScalar(m * g^-1);
true
> g := Random(GL(6, 5^4));
> SL3ElementToWord(G, g);
false

```

### `RecogniseSL(G, d, q): Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map`

### `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 \cong {\rm 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`!

## Constructive Recognition of Symplectic Groups

### `RecogniseSpOdd(G, d, q): Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map`

### `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 \cong {\rm 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`!

### `RecogniseSp4(G, q): Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map, Map, Map, SeqEnum, SeqEnum`

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

## Constructive Recognition of Unitary Groups

### `RecogniseSU3(G, d, q): Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map`

### `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 \cong {\rm 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$.

### `RecogniseSU4(G, d, q): Grp, RngIntElt, RngIntElt -> BoolElt, Map, Map`

### `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 \cong {\rm 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$.

## Recognition Of Classical Groups in Low Degree

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 $d^2$.

Magaard, O’Brien & Seress [[Magaard *et al.*, 2008](../../references.md#cite-small-deg-reps)] and Brian Corr [[Corr, 2013](../../references.md#cite-corr-phd)] 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 [[Magaard *et al.*, 2008](../../references.md#cite-small-deg-reps)], [[Corr, 2013](../../references.md#cite-corr-phd)], 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): GrpMat -> BoolElt, GrpMat`

### `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, \ldots, d^2]$, 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 ${\bf F}_{q}$, and its type is one of `SL, Sp, SU, Omega, Omega+, Omega-`.

### `SmallDegreePreimage(G, g): GrpMat, GrpMatElt -> GrpMatElt`

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

### `SmallDegreeImage(G, h): GrpMat, GrpMatElt -> GrpMatElt`

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.

### `Example: Recognise Small Degree (ex-5df193)`

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

```

## Constructive Recognition of Suzuki Groups

### Introduction

A description of the functionality for constructive recognition and constructive membership testing of the Suzuki groups ${\rm Sz}(q)$, with $q = 2^{2m + 1}$ for some $m > 0$ follows.

The main intrinsics of the package are `RecogniseSz(G)` which performs constructive recognition of $G \cong {\rm 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 ${\rm Sz}(q)$.

Informative printing can be obtained using one of a number of verbose flags:

**•**
$\quad$ `SuzukiGeneral`, for the general routines.

**•**
$\quad$ `SuzukiStandard`, for the routines related to the standard copy.

**•**
$\quad$ `SuzukiConjugate`, for the routines related to conjugation.

**•**
$\quad$ `SuzukiTensor`, for the routines related to tensor decomposition.

**•**
$\quad$ `SuzukiMembership`, for the routines related to membership testing.

**•**
$\quad$ `SuzukiCrossChar`, for the routines related to cross-characteristic representations.

**•**
$\quad$ `SuzukiTrick`, for the routines related to the double coset trick.

**•**
$\quad$ `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.

### Recognition Functions

#### `IsSuzukiGroup(G): GrpMat -> BoolElt, RngIntElt`

Given a matrix group $G$, this function determines (non-constructively) whether or not $G$ is isomorphic to ${\rm 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`](#function-grpmatff-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 [[B\accent 127a\accent 127arnhielm, 2006](../../references.md#cite-baarnhielm05)].

#### `RecogniseSz(G : parameters): GrpMat -> BoolElt, Map, Map, Map, Map`

#### `RecognizeSz(G : parameters): GrpMat -> BoolElt, Map, Map, Map, Map`

```magma
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 ${\rm Sz}(q)$, where $q$ is the size of the defining field of $G$, then return:

**•**
Isomorphism from $G$ to ${\rm Sz}(q)$.

**•**
Isomorphism from ${\rm 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 ${\rm Sz}(q)$, using `IsSuzukiGroup`. In that case, `FieldSize` must be set to the correct value of $q$. Constructive recognition of $2.{\rm 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 [[B\accent 127a\accent 127arnhielm, 2006](../../references.md#cite-baarnhielm05)] and [[B\accent 127a\accent 127arnhielm, 2005](../../references.md#cite-sz-tensor-decompose)].

#### `SzElementToWord(G, g): GrpMat, GrpMatElt -> BoolElt, GrpSLPElt`

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$.

#### `SzPresentation(q): RngIntElt -> GrpFP, HomGrp`

If $q = 2^{2m + 1}$ for some $m > 0$, return a short presentation of ${\rm Sz}(q)$ on the Magma standard generators, i.e. the generators returned by the `Sz` intrinsic.

#### `SatisfiesSzPresentation(G): GrpMat -> BoolElt`

$G$ is constructively recognised as ${\rm Sz}(q)$ for some $q$. Verify that it satisfies a presentation for this group.

#### `SuzukiIrreducibleRepresentation(F, twists : parameters): FldFin, SeqEnum[RngIntElt] -> GrpMat`

```magma
CheckInput: BoolElt                    Default: true
```

Let $F$ be a finite field of cardinality $q = 2^{2m + 1}$ for some $m > 0$, and let *twists* be a sequence of $n$ distinct integers in the range $[0 \ldots 2m]$. The function returns an absolutely irreducible representation of ${\rm Sz}(q)$ having dimension $4^n$, 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.

#### `Example: Ex 1 (ex-9d33f6)`

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.

```magma
> 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`.

```magma
> 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.

```magma
> w := Function(g2slp)(G.1);
> #w;
284

```

The algorithm is probabilistic, so different executions will most likely give different results.

```magma
> 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$.

```magma
> 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.

```magma
> flag, ww := SzElementToWord(G, G.1);
> flag, slp2g(w) eq slp2g(ww);
true true

```

We take an element just outside the group.

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

```

#### `Example: Ex 2 (ex-d3b056)`

As a variation we apply the machinery to $2.Sz(8)$. We demonstrate constructive recognition and constructive membership testing.

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

```

#### `Example: Ex 3 (ex-f8d565)`

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.

```magma
> 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.

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

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

```

#### `Example: Ex 4 (ex-183108)`

The final example will be in cross characteristic. We build a representation of $Sz(8)$ in cross characteristic.

```magma
> 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$.

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

```

## Constructive Recognition of Small Ree Groups

### Introduction

This machinery provides functionality for constructive recognition and constructive membership testing of the small Ree groups ${\rm {^2}G_2}(q) = {\rm Ree}(q)$, with $q = 3^{2m + 1}$ for some $m > 0$.

The important intrinsics are `RecogniseRee` which performs constructive recognition of $G \cong {\rm 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 ${\rm Ree}(q)$.

There are a few verbose flags used in the package.

**•**
$\quad$ `ReeGeneral`, for the general routines.

**•**
$\quad$ `ReeStandard`, for the routines related to the standard copy.

**•**
$\quad$ `ReeConjugate`, for the routines related to conjugation.

**•**
$\quad$ `ReeTensor`, for the routines related to tensor decomposition.

**•**
$\quad$ `ReeMembership`, for the routines related to membership testing.

**•**
$\quad$ `ReeCrossChar`, for the routines related to cross-characteristic representations.

**•**
$\quad$ `ReeTrick`, for the routines related to the stabiliser trick.

**•**
$\quad$ `ReeInvolution`, for the routines related to involution centralisers.

**•**
$\quad$ `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.

### Recognition Functions

#### `RecogniseRee(G : parameters): GrpMat -> BoolElt, Map, Map, Map, Map`

#### `RecognizeRee(G : parameters): GrpMat -> BoolElt, Map, Map, Map, Map`

```magma
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 ${\rm Ree}(q)$ where $q$ is the size of the defining field of $G$, then return:

**•**
Isomorphism from $G$ to ${\rm Ree}(q)$.

**•**
Isomorphism from ${\rm 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 ${\rm 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 [[B\accent 127a\accent 127arnhielm, 2014](../../references.md#cite-baarnhielm14)].

#### `ReeElementToWord(G, g): GrpMat, GrpMatElt -> BoolElt, GrpSLPElt`

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$.

#### `IsReeGroup(G): GrpMat -> BoolElt, RngIntElt`

Determine (non-constructively) if $G$ is isomorphic to ${\rm 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`](#function-grpmatff-lietype) is used. If $G$ has degree $7$ and is over a field of characteristic $3$, then a fast Las Vegas algorithm is used.

#### `ReeIrreducibleRepresentation(F, twists : parameters): FldFin, SeqEnum[RngIntElt] -> GrpMat`

```magma
CheckInput: BoolElt                    Default: true
```

The finite field $F$ must have size $q = 3^{2m + 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 \ldots 2m]$.

Return an absolutely irreducible representation of ${\rm 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.

#### `Example: Ex 1 (ex-79d9a3)`

Our first example shows off the recognition machinery for the Ree group defined over ${\bf F}_{27}$.

```magma
> 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.

```magma
> 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$.

```magma
> 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 $\Omega(7, F)$ as an example of an element not lying in $G_2(27)$.

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

```

## Constructive Recognition of Large Ree Groups

### Introduction

This machinery provides functionality for constructive recognition and constructive membership testing of the large Ree groups ${\rm {^2}F_4}(q) = {\rm LargeRee}(q)$, with $q = 2^{2m + 1}$ for some $m > 0$.

The important intrinsics are `RecogniseLargeRee` which performs constructive recognition of $G \cong {\rm 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 ${\rm LargeRee}(q)$.

There are a few verbose flags used in the package.

**•**
$\quad$ `LargeReeGeneral`, for the general routines.

**•**
$\quad$ `LargeReeStandard`, for the routines related to the standard copy.

**•**
$\quad$ `LargeReeConjugate`, for the routines related to conjugation.

**•**
$\quad$ `LargeReeRyba`, for the routines related to membership testing.

**•**
$\quad$ `LargeReeTrick`, for the routines related to the stabiliser trick.

**•**
$\quad$ `LargeReeInvolution`, for the routines related to involution centralisers.

**•**
$\quad$

All the flags can be set to values up to $10$, with higher values resulting in more output.

### Recognition Functions

#### `RecogniseLargeRee(G : parameters): GrpMat -> BoolElt, Map, Map, Map, Map`

#### `RecognizeLargeRee(G : parameters): GrpMat -> BoolElt, Map, Map, Map, Map`

```magma
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 ${\rm LargeRee}(q)$ where $q$ is the size of the defining field of $G$, then return:

**•**
Isomorphism from $G$ to ${\rm LargeRee}(q)$.

**•**
Isomorphism from ${\rm 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 ${\rm 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.

#### `LargeReeElementToWord(G, g): GrpMat, GrpMatElt -> BoolElt, GrpSLPElt`

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$.

#### `IsLargeReeGroup(G): GrpMat -> BoolElt, RngIntElt`

Determine (non-constructively) if $G$ is isomorphic to ${\rm 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`](#function-grpmatff-lietype) is used. If $G$ has degree $26$ and is over a field of characteristic $2$, then a fast Las Vegas algorithm is used.