# Constructive Recognition for Simple Groups

For each finite non-abelian simple group $S$, we designate a specific *standard copy* of $S$. The standard copy has a designated set of *standard generators*. For example, the standard copy of ${\operatorname{Alt}}(n)$ is on $n$ points; its standard generators are $(1,2,3)$ and either of $(3,\ldots, n)$ or $(1, 2)(3,\ldots, n)$ according to the parity of $n$. For a projective representation, the standard copy is the quotient of a matrix group by its scalar subgroup. For example, the standard copy of ${\operatorname{PSL}}(n,q)$ is the quotient of ${\operatorname{SL}}(n,q)$ by its scalar subgroup.

To compute in a copy $G$ of $S$, we first construct effective isomorphisms between $G$ and its standard copy. We do this by finding generators in $G$ that correspond to the standard generators of $S$ under an isomorphism. More formally, a *constructive recognition algorithm* for a non-abelian simple group $G$ (possibly with decorations) solves the following problem: construct an isomorphism $\phi$ from $G$ to a standard copy $S$ of $G$, such that $\phi(g)$ can be computed efficiently for every $g \in G$. This is done by constructing standard generators in both $G$ and its standard copy $S$.

A *rewriting algorithm* for $G$ solves the *constructive membership problem*: given $g \in U \geq G = \langle X \rangle$, decide whether or not $g \in G$, and if so express $g$ as an SLP in $X$. (Here $U$ is the generic overgroup of $G$, such as ${\operatorname{GL}}(d,q)$ or ${\operatorname{Sym}}(n)$.) The rewriting algorithm is used to make the isomorphism between $S$ and $G$ effective. To compute the image of an arbitrary element $s$ of $S$ in $G$, we first write $s$ as an SLP in the standard generators of $S$ and then evaluate the SLP in the copy of the standard generators in $G$.

To verify that the homomorphism from $S$ to $G$ is an isomorphism, we can evaluate in $G$ a *standard presentation* for $S$ on its standard generators. If the copy of the standard generators in $G$ satisfy the presentation, then we have proved that we have an isomorphism.

For a detailed discussion of these topics, see [[Leedham-Green and O'Brien, 2009](../../references.md#cite-lgo-odd), [O'Brien, 2011](../../references.md#cite-obrien10)]. Here we discuss recognition of classical and exceptional groups. See `RecogniseAlternatingOrSymmetric` for alternating groups.

## Constructive Recognition for Classical Groups

### `ClassicalStandardGenerators(type, d, q): MonStgElt, RngIntElt, RngIntElt -> []`

This intrinsic produces the standard generators of Leedham-Green and O’Brien for the quasisimple classical group of specified type in dimension $d$ over a field of size $q$. The type is designated by the argument `type` which must be one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”. The standard generators generate a specific copy of a classical group and are defined in [[Leedham-Green and O'Brien, 2009](../../references.md#cite-lgo-odd)] and [[Dietrich *et al.*, 2013](../../references.md#cite-dlgo-even)].

### `ClassicalConstructiveRecognition(G, type, d, q): GrpMat[FldFin], MonStgElt, RngIntElt, RngIntElt -> BoolElt, Map, Map, Map, Map, SeqEnum, SeqEnum`

### `ClassicalConstructiveRecognition(G): GrpMat[FldFin] -> BoolElt, SeqEnum, SeqEnum`

The input group $G = \langle X \rangle$ is a permutation group, or a matrix group defined over a finite field. It must be isomorphic to a central quotient of a classical group of specified type in dimension $d$ over a field of size $q$. The type is designated by one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”. The function constructs standard generators for $G$. If it is successful, then return `true`; four maps $m_1, m_2, m_3, m_4$; standard generators ${\cal S}$ for $G$; and their SLPs in $X$; otherwise return `false`. The map $m_1$ is from $G$ to the standard copy $S$ of $G$; the map $m_2$ is from $S$ to $G$; the map $m_3$ is from $G$ to `WordGroup(G)`; the map $m_4$ is from `WordGroup(G)` to $G$. Since, in general, $G$ is isomorphic to a central quotient of $S$, the maps $m_1$ and $m_2$ are homomorphisms modulo scalars.

In the second signature, $G$ must be a matrix group defined over a finite field such that $G = \langle X \rangle$ is conjugate to a quasisimple classical group in its natural representation in dimension at least 2. The intrinsic constructs a copy ${\cal S}$ in $G$ of the generators defined by `StandardGenerators`. If $G$ is quasisimple and classical, then the function returns `true`, the standard generators ${\cal S}$, and SLPs for these in $X$; otherwise it returns `false`.

The algorithms used are described in [[Leedham-Green and O'Brien, 2009](../../references.md#cite-lgo-odd)], [[Dietrich *et al.*, 2013](../../references.md#cite-dlgo-even)], and [[Dietrich *et al.*, 2015](../../references.md#cite-dlgo-black)]. The implementations for even and odd characteristic were developed by Heiko Dietrich and Eamonn O’Brien respectively. Some base case functions were implemented by Kenneth Clarkson.

### `Example: Classical Constructive Recognition (ex-0be2ca)`

We illustrate these functions with two examples.

```magma
> G := Sp (6, 5^3);
> G := ExteriorSquare (G);
> f, m1, m2, m3, m4, E, W := ClassicalConstructiveRecognition( G, "Sp", 6, 5^3 );

> Q, R := ClassicalStandardPresentation ("Sp", 6, 5^3);
> #{Evaluate( r, E ) : r in R} eq 1;
true
> x := Random (G);
> y := m1 (x);
> y;
> w := m3 (x);
> "Length of SLP is ", #w;
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq x;
true
> E eq Evaluate( W, [G.i : i in [ 1 .. Ngens( G )]]);

> G := PSL( 6, 4 );
> f, m1, m2, m3, m4, E, W := ClassicalConstructiveRecognition( G, "SL", 6, 4 );
> E eq Evaluate( W, [G.i : i in [ 1 .. Ngens( G )]]);
true
>
> Q, rels := ClassicalStandardPresentation( "SL" , 6, 4);
> #{Evaluate( r, E ) : r in rels} eq 1;
true
>
> g := Random( G );
> s := m1( g );
> s in SL(6,4);
true
> m2( s ) eq g;
true
>
> h := Random( SL( 6, 4 ) );
> g := m2( h );
> g in G;
true
> m1( g ) eq h;
false
> IsScalar( m1( g ) * h^-1 );
true
>
> w := m3( g );
> w in WordGroup( G );
true
> m4( w ) eq g;
true
> g eq Evaluate( w, [G.i : i in [ 1 .. Ngens( G )]]);
true

```

### `ClassicalChangeOfBasis(G): GrpMat[FldFin] -> GrpMatElt[FldFin]`

Let $G$ be a classical group in its natural representation; return a change-of-basis matrix to conjugate the generators returned by `ClassicalStandardGenerators` to those returned by `ClassicalConstructiveRecognition` $(G)$. The latter intrinsic must have been applied to $G$.

### `ClassicalRewrite({G, gens, type, dim,}{ q, g : parameters}): Grp, SeqEnum, MonStgElt, RngIntElt, RngIntElt, GrpElt -> BoolElt, GrpElt`

```magma
Method: MonStgElt                    Default: "choose"
```

Let $G$ be a classical group of type `type`, which is one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”, with dimension `dim` over the field ${\bf F}_{q}$ generated by `gens` which satisfy `ClassicalStandardPresentation (type, dim, q)`. Further, let $g$ be an element of `Generic`$(G)$.

If $g \in G$, then the function returns `true` and an SLP for $g$ in `gens`; if $g\not\in G$ then the function searches for an SLP $w$ such that $g \cdot$`Evaluate`$(w, gens)^{-1}$ centralizes $G$; if it is successful, it returns `false` and $w$. Otherwise the function returns `false, false`.

The function chooses one of the following methods:

**(i)**
If $G$ is in its natural representation and `gens` is `ClassicalStandardGenerators (type, dim, q)` then an algorithm of Costi [[Costi, 2009](../../references.md#cite-costi-phd)] is used.

**(ii)**
If (i) is not valid, but $G$ is an absolutely irreducible representation in the defining characteristic, then an algorithm of Costi [[Costi, 2009](../../references.md#cite-costi-phd)] is used.

**(iii)**
If neither of (i) and (ii) is valid, then a “black-box” method, independent of the representation of $G$, developed by Csaba Schneider is used.

The optional parameter `Method` can be used to override the default choice of method. The possible values of `Method` are `CharP` and `BB`.

A description of the algorithm used in the defining characteristic case appears in [[Costi, 2009](../../references.md#cite-costi-phd)]; a short description of the black-box algorithm appears in [[Ambrose *et al.*, 2010](../../references.md#cite-ambroseetal)].

The code was developed and written by Csaba Schneider.

### `ClassicalRewriteNatural(type, CB, g): MonStgElt, GrpMatElt, GrpMatElt -> BoolElt, GrpElt`

### `ClassicalRewriteNatural({G, type, }{CB, g}): MonStgElt, GrpMatElt, GrpMatElt -> BoolElt, GrpElt`

This is a faster specialized version of the intrinsic `ClassicalRewrite` discussed above; it is designed for classical groups in their **natural representation**.

The argument `type` must be one of the strings “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”. Both `CB` and $g$ are elements of some ${\operatorname{GL}}(d, q)$.

If $g$ is a member of the group generated by `ClassicalStandardGenerators (type, d, q)`$^{{\tt CB}}$ then the function returns `true` and an SLP $w$ such that `Evaluate (w, ClassicalStandardGenerators (type, d, q)`$^{{\tt CB}}) = g$. Otherwise the function returns `false, false`.

If many elements of the same group $G$ are rewritten in terms of standard generators, then the second signature with $G$ as an argument is recommended on efficiency grounds since the results of some necessary precomputations are stored in $G$.

This algorithm, based on that developed by Elliot Costi [[Costi, 2009](../../references.md#cite-costi-phd)], was implemented by Csaba Schneider.

### `ClassicalStandardPresentation(type, d, q : parameters): MonStgElt, RngIntElt, RngIntElt -> SLPGroup, []`

```magma
Projective: BoolElt                    Default: false
```

Given the specification `type, d, q` of a quasisimple group $G$, this intrinsic constructs a presentation on the standard generators for $G$. The string `type` must be one of “SL”, “Sp”, “SU”, “Omega”, “Omega-”, or “Omega+”, while $d$ is the dimension and $q$ is the cardinality of the finite field. The presentations are described in [[Leedham-Green and O'Brien, 2020](../../references.md#cite-lgo-pres)]. The relations are returned as SLPs together with the parent SLPGroup.

If the parameter `Projective` is set to true, the intrinsic constructs a presentation for the corresponding projective group.

### `Example: Classical Constructive Recognition (ex-7ccc3b)`

As our first illustration, we produce standard generators for ${\operatorname{SL}}(6, 5^3)$:

```magma
> E := ClassicalStandardGenerators ("SL", 6, 5^3);
> E;
[
    [      0       1       0       0       0       0]
    [      4       0       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1],

    [      0       0       0       0       0       1]
    [      4       0       0       0       0       0]
    [      0       4       0       0       0       0]
    [      0       0       4       0       0       0]
    [      0       0       0       4       0       0]
    [      0       0       0       0       4       0],

    [      1       1       0       0       0       0]
    [      0       1       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1],

    [    $.1       0       0       0       0       0]
    [      0 $.1^123       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1]
]

```

We now perform constructive recognition on ${\operatorname{SL}}(6, 5^3)$, and so obtain $S$, conjugate to $E$ in ${\operatorname{GL}}(6, 5^3)$. Observe that the change-of-basis matrix returned by `ClassicalChangeOfBasis` performs this conjugation.

```magma
> G := SL (6, 5^3);
> f, S, W := ClassicalConstructiveRecognition (G);
> f;
true
> CB := ClassicalChangeOfBasis (G);
> E^CB eq S;
true

```

Note that $W$ is list of SLPs expressing $S$ in terms of defining generators of $G$.

```magma
> S eq Evaluate (W, [G.i: i in [1..Ngens (G)]]);
true

```

We next express a random element of $G$ as a SLP in $S$ and then check that the standard generators satisfy the standard presentation.

```magma
> g := Random (G);
> f, w := ClassicalRewriteNatural ("SL", CB, g);
> Evaluate (w, S) eq g;
true
>
> P, R := ClassicalStandardPresentation ("SL", 6, 5^3);
> Set (Evaluate (R, S));
{
    [      1       0       0       0       0       0]
    [      0       1       0       0       0       0]
    [      0       0       1       0       0       0]
    [      0       0       0       1       0       0]
    [      0       0       0       0       1       0]
    [      0       0       0       0       0       1]
}

```

We perform constructive recognition on a random conjugate of ${\operatorname{Sp}}(10, 3^6)$ and again check that the standard generators satisfy the standard presentation.

```magma
> G := RandomConjugate (Sp(10, 3^6));
> f, S, W := ClassicalConstructiveRecognition (G);
> f;
true

```

The return variable $W$ is list of SLPs expressing $S$ in terms of defining generators of $G$.

```magma
> S eq Evaluate (W, [G.i: i in [1..Ngens (G)]]);
true
>
> g := Random (G);
> CB := ClassicalChangeOfBasis (G);
> f, w := ClassicalRewriteNatural ("Sp", CB, g);
> Evaluate (w, S) eq g;
true
>
> P, R := ClassicalStandardPresentation ("Sp", 10, 3^6);
> Set (Evaluate (R, S));
{
    [1 0 0 0 0 0 0 0 0 0]
    [0 1 0 0 0 0 0 0 0 0]
    [0 0 1 0 0 0 0 0 0 0]
    [0 0 0 1 0 0 0 0 0 0]
    [0 0 0 0 1 0 0 0 0 0]
    [0 0 0 0 0 1 0 0 0 0]
    [0 0 0 0 0 0 1 0 0 0]
    [0 0 0 0 0 0 0 1 0 0]
    [0 0 0 0 0 0 0 0 1 0]
    [0 0 0 0 0 0 0 0 0 1]
}

```

As another demonstration, we constructively recognise $\Omega^{-}(16, 2^6)$.

```magma
> G := RandomConjugate (OmegaMinus (16, 2^6));
> f, S, W := ClassicalConstructiveRecognition (G);
> f;
true

```

A random element of $G$ is expressed as an SLP in $S$:

```magma
> g := Random (G);
> CB := ClassicalChangeOfBasis (G);
> f, w := ClassicalRewriteNatural ("Omega-", CB, g);
> Evaluate (w, S) eq g;
true

```

Finally, we illustrate using `ClassicalRewrite` to write an element of a classical group in a non-natural representation as an SLP in its standard generators.

```magma
> gens := [ExteriorSquare (x) : x in ClassicalStandardGenerators ("Sp", 6, 25)];
> G := sub<Universe (gens) | gens>;
> x := Random (G);
> f, w := ClassicalRewrite (G, gens, "Sp", 6, 25, x);
> f;
true
> Evaluate (w, gens) eq x;
true
> f, w := ClassicalRewrite (G, gens, "Sp", 6, 25, x : Method := "BB");
> f;
true
> Evaluate (w, gens) eq x;
true

```

## Constructive Recognition for Exceptional Groups

Here we discuss machinery for constructive recognition of most of the finite exceptional groups. For the remainder, see `RecogniseSz`, `RecogniseRee`, and `RecogniseLargeRee`.

### `ExceptionalStandardGenerators(type, rank, q): MonStgElt, RngIntElt, RngIntElt -> []`

Return standard generators for the finite exceptional simple group of specified type `type` and rank `rank` over a field of size $q$. The type is designated by the argument `type` which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. The standard generators, $X$ and $X_m$, are defined in [[Liebeck and O'Brien, 2016](../../references.md#cite-exceptional-lob16)]; they label the positive and negative root groups of the group respectively and satisfy the presentation returned by `ExceptionalStandardPresentation`. The copy of the exceptional group generated by $X$ and $X_m$ is that defined in [[Howlett *et al.*, 2001](../../references.md#cite-howlett-rylands-taylor)]. This function is essentially a wrapper for `CST_Generators` prepared by Don Taylor.

```{.magma
> X, Xm := ExceptionalStandardGenerators ("F", 4, 5^3);
> #X;
8
> #X[1];
3

> X, Xm := ExceptionalStandardGenerators ("2E", 6, 3^4);
> #X;
8
> #X[1];
4

```

### `ExceptionalConstructiveRecognition(G, type, rank, q): GrpMat[FldFin], MonStgElt, RngIntElt, RngIntElt -> BoolElt, Map, Map, Map, Map, SeqEnum, SeqEnum`

The input group $G = \langle Y \rangle$ is a a matrix group defined over a finite field. It must be isomorphic to a central quotient of an exceptional group of specified type `type` and rank `rank` over a field of size $q$. The type is designated by the argument `type` which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. The function constructs standard generators for $G$. If it is successful, then return `true`; four maps $m_1, m_2, m_3, m_4$; the standard generators $E$ for $G$; and their SLPs $W$ in $Y$; otherwise return `false`. The map $m_1$ is from $G$ to the standard copy $S$ of $G$; the map $m_2$ is from $S$ to $G$; the map $m_3$ is from $G$ to `WordGroup(G)`; the map $m_4$ is from `WordGroup(G)` to $G$. Since, in general, $G$ is isomorphic to a central quotient of $S$, the maps $m_1$ and $m_2$ are homomorphisms modulo scalars. The maps $m_1$, $m_2$ and $m_3$ are returned only if $G$ is a defining characteristic absolutely irreducible matrix representation of the exceptional group. The standard generators $E$ are returned as a sequence of length 2: its entries, $X$ and $X_m$, label the positive and negative root groups respectively.

The algorithm used is that of [[Liebeck and O'Brien, 2016](../../references.md#cite-exceptional-lob16)]; the implementation was developed by Eamonn O’Brien. The maps $m_1$, $m_2$ and $m_3$ are provided by `ExceptionalRewrite`, developed and implemented by Don Taylor.

The verbose flag `SetVerbose("Except", 1)` may be used to print information on the progress of the function.

### `Example: Exceptional Constructive Recognition (ex-111a3c)`

We illustrate these functions with two examples.

```magma
> G := MatrixGroup ("G25", 6);
> G: Minimal;
MatrixGroup(27, GF(5)) of order 2^6 * 3^3 * 5^6 * 7 * 31
> f, m1, m2, m3, m4, E, W := ExceptionalConstructiveRecognition( G, "G", 2, 5 );
> Q, R := ExceptionalStandardPresentation ("G", 2, 5);
> X := E[1]; Xm := E[2];
> #Set (Evaluate( R, &cat X cat &cat Xm)) eq 1;
true
> x := Random (G);
> m1;
Mapping from: GL(27, GF(5)) to GL(7, GF(5)) given by a rule [no inverse]
> y := m1 (x);
> m3;
Mapping from: GL(27, GF(5)) to SLPGroup(2) given by a rule [no inverse]
> w := m3 (x);
> Evaluate (w, [G.i: i in [1..Ngens (G)]]) eq x;
true
> &cat X eq Evaluate( &cat W[1], [G.i : i in [ 1 .. Ngens( G )]]);
true
> &cat Xm eq Evaluate( &cat W[2], [G.i : i in [ 1 .. Ngens( G )]]);
true
>
> G := ChevalleyGroup ("3D", 4, 4);
> G := RandomConjugate (G);
> G: Minimal;
MatrixGroup(8, GF(2^6))
> f, m1, m2, m3, m4, E, W := ExceptionalConstructiveRecognition( G, "3D", 4, 4);
> Q, R := ExceptionalStandardPresentation ("3D", 4, 4);
> X := E[1]; Xm := E[2];
> #Set (Evaluate( R, &cat X cat &cat Xm)) eq 1;
true

```

### `ExceptionalRewrite(type, rank, q, X, Xm, g): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum, GrpElt -> BoolElt, GrpElt`

Let $G$ be a finite exceptional group of type `type` and rank `rank` over a field of size $q$. The type is designated by the argument `type` which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. Also $X$ and $X_m$ are generators which satisfy `ExceptionalStandardPresentation (type, rank, q)`. Further, let $g$ be an element of `Generic`$(G)$.

If $g \in G$, then the function returns `true` and an SLP for $g$ in `&cat X cat &cat Xm`; if $g\not\in G$ then the function searches for an SLP $w$ such that $g \cdot$ `Evaluate`(`w, &cat X cat &cat Xm`)$^{-1}$ centralizes $G$; if it is successful, it returns `false` and $w$. Otherwise the function returns `false, false`.

A description of the algorithm used appears in [[Cohen *et al.*, 2004](../../references.md#cite-cohenmurraytaylor), [Cohen and Taylor, 2019](../../references.md#cite-cohen-taylor-preprint)]. This function is essentially a wrapper for `LieTypeRewrite` prepared by Don Taylor.

```{.magma
> g := Random (G);
> f, w := ExceptionalRewrite ("G", 2, 5, X, Xm, g);
> f;
true
> g eq Evaluate (w, &cat X cat &cat Xm);
true

```

### `ExceptionalStandardPresentation(type, rank, q): MonStgElt, RngIntElt, RngIntElt -> SLPGroup, []`

Let $G$ be a finite exceptional group of type `type` and rank `rank` defined over a field of size $q$. The type is designated by the argument `type` which must be one of the strings “E”, “F”, “G”, “2E”, “3D”. This intrinsic constructs a presentation on the standard generators for $G$. The relations are returned as SLPs together with the parent SLPGroup. The standard presentations returned by this function are listed explicitly in [[Liebeck and O'Brien, 2016](../../references.md#cite-exceptional-lob16)]. This function is essentially a wrapper for `CST_Presentation` prepared by Don Taylor.

`ExceptionalStandardGenerators` returns matrices satisfying this presentation. `ExceptionalConstructiveRecognition` constructs such generators in an arbitrary matrix representation $G$.

### `Example: Exp Standard (ex-b84999)`

```magma
> Q, R := ExceptionalStandardPresentation ("G", 2, 5^3);
> X, Xm := ExceptionalStandardGenerators ("G", 2, 5^3);
> #Set (Evaluate (R, &cat X cat &cat Xm));
1
> G := ChevalleyGroup ("G", 2, 5^3);
> G := RandomConjugate (ExteriorSquare (G));
> G:Minimal;
MatrixGroup(21, GF(5^3))
> f, m1, m2, m3, m4, E, W := ExceptionalConstructiveRecognition(G, "G",
>                                                                 2, 5^3);
> X := E[1]; Xm := E[2];
> #Set (Evaluate (R, &cat X cat &cat Xm));
1

```