# Curtis–Steinberg–Tits Presentations

In Magma a group of Lie type over a field is defined by generators which satisfy Steinberg relations (see section [The Steinberg Presentation](introduction.md#subsectgrpliesteinberg)). In particular the unipotent elements $x_\alpha(a)$ are parametrised by the field and the torus elements are parametrised by the non-zero elements of the field. However, the number of generators and relations can be reduced considerably using a form of the Curtis–Steinberg–Tits (CST) presentation [[Babai *et al.*, 1997](../../references.md#cite-babai-etal-1997)].

This section describes basic functions to compute with highest weight representations of finite groups of Lie type defined by CST presentations: see the previous section and Chapter [Representations of Lie Groups and Algebras](../RepresentationsOfLieGroupsAndAlgebras/index-representations-of-lie-groups-and-algebras.md#chapliereps) for more functions for highest weight representations.

Currently this functionality is available only for algebraically simple finite reductive groups with a simply connected root datum: all untwisted types and the twisted groups of types ${}^2\hbox{A}_n$ ($n$ odd), ${}^2\hbox{D}_n$, ${}^3\hbox{D}_4$ and ${}^2\hbox{E}_6$.

Let $G(q)$ be a simply connected group defined over the field ${\mathbb{F}}_q$, let $\Delta = \{\alpha_1,\dots,\alpha_d\}$ be a base of simple roots and let $B$ be a basis for ${\mathbb{F}}_q$ regarded as a vector space over its prime field. The CST presentation can be described as follows.

For $i < j$, let $\Phi_{ij}$ be the subsystem spanned by $\alpha_i$ and $\alpha_j$, put $\Psi = \bigcup_{i,j}\Phi_{ij}$ and $\Upsilon = \bigcup_{i,j}\{\,(\alpha,\beta) \in \Phi_{ij}\times \Phi_{ij} \mid \alpha\ne \pm \beta\,\}$. Then $G(q)$ has a presentation with generators $x_\alpha(a)$ for $\alpha \in \Psi$ and $a\in B$. It is enough to require relations $x_\alpha(a)x_\alpha(b) = x_\alpha(a+b)$ for $\alpha\in \Psi$ and relations

$$
[x_\alpha(a),x_\beta(b)] =
    \prod_{i,j > 0}  x_{i\alpha+j\beta}(C_{ij\alpha\beta}a^ib^j)
$$

for $(\alpha,\beta)\in\Upsilon$ and $a,b\in B$. (If $G(q)$ were not simply connected we would need additional generators for the torus.)

In Magma, the CST generators are represented by a pair of sequences $X$, $Y$

$$
\begin{aligned}X &= [[x_\alpha(a) \mid a \in B] \mid \alpha \in \Psi ]\quad\hbox{and}\\
  Y &= [[x_{-\alpha}(a) \mid a \in B] \mid \alpha \in \Psi],\end{aligned}
$$

where $X$ (resp. $Y$) may be regarded as a matrix whose rows are indexed by positive (resp. negative) roots and whose columns are indexed by basis elements of ${\mathbb{F}}_q$.

For many functions there are optional parameters `OnlySimple` and `GS`. If `OnlySimple` is `true`, only the CST generators $x_\alpha(a)$ where $\pm\alpha$ is a simple root are used. (The function `ExtendGeneratorList` can be used to extend the simple generators to the full collection of CST generators.)

The functions generally use the default signs for the extraspecial pairs (Section [Constructing Root Data](../RootData/create-root-datum.md#sectrdconstr)). However, if `GS` is `true`, the root order and signs used by Gilkey and Seitz [[Gilkey and Seitz, 1988](../../references.md#cite-gilkey-seitz-1988)] are used; this only applies to groups of types $\hbox{F}_4$ and $\hbox{G}_2$.

## `CST_Generators(t, r, q, w): MonStgElt, RngIntElt, RngIntElt, SeqEnum -> SeqEnum, SeqEnum`

```magma
GS        : BoolElt                    Default: false
OnlySimple: BoolElt                    Default: false
Weyl      : BoolElt                    Default: false
Signs     : Any                        Default: 1
```

The Curtis–Steinberg–Tits generators for the group of Lie type $t$ and rank $r$ over the field ${\mathbb{F}}_q$ in the irreducible representation with highest weight $w$. If `OnlySimple` is `true`, only generators for the simple roots are returned. If `Weyl` is `true`, the Weyl representation of highest weight $w$ is returned. If $w$ is the empty sequence, the standard representation is used.

The parameter `Signs` can take the values described in Section [Constructing Root Data](../RootData/create-root-datum.md#sectrdconstr).

## `CST_Presentation(t, r, q): MonStgElt, RngIntElt, RngIntElt -> GrpSLP, SeqEnum`

```magma
GS: BoolElt                    Default: false
```

The Curtis–Steinberg–Tits relations for the simply connected group of Lie type $t$ and rank $r$ over the field ${\mathbb{F}}_q$. The function returns an SLP-group $G$ and a sequence containing the relations as straight-line programs in $G$.

If `GS` is `true`, the Gilkey–Seitz structure constants are used and the simple roots for groups of type $\hbox{G}_2$ are swapped.

## `CST_VerifyPresentation(t, r, q, X, Y): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum -> BoolElt, RngIntElt`

```magma
GS: BoolElt                    Default: false
```

Given Curtis–Steinberg–Tits generators $X$, $Y$ for a simply connected group of Lie type $t$ and rank $r$ over the field ${\mathbb{F}}_q$, verify that the generators satisfy the relations. Set `GS` to `true` if the Gilkey–Seitz conventions hold for $X$ and $Y$.

## `Example: CST Pres (ex-edd24d)`

Verify that the CST generators for the 273-dimensional representation of ${\rm F}_4(5)$ satisfy the CST relations but not the relations for ${\rm F}_4(5)$. When the relations are not satisfied, the index of the first relation which fails is returned.

```magma
> X,Y := CST_Generators("F",4,5,[0,0,1,0]);
> CST_VerifyPresentation("F",4,5,X,Y);
true
> CST_VerifyPresentation("F",4,3,X,Y);
false 1
> G, rels := CST_Presentation("F",4,3);
> rels[1];
function(G)
    w1 := G.1^3; return w1;
end function

```

## `CSTtoChev(t, r, q, X, Y): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum -> Map`

```magma
GS    : BoolElt                    Default: false
UseMap: BoolElt                    Default: false
```

Given Curtis–Steinberg–Tits generators $X$, $Y$ which satisfy the presentation for a group of Lie type $t$ and rank $r$ over the field of $q$ elements, return a function $f$ from the group they generate to the standard Magma copy obtained from `ChevalleyGroup(t,r,q)`. The function $f$ will be a homomorphism up to a scalar multiple.

Set `GS` to `true` if the Gilkey–Seitz conventions hold for $X$ and $Y$. If `UseMap` is `true`, the function $f$ is returned as a Magma `Map`, otherwise the type is `UserProgram`.

## `Example: CS Tto Chev (ex-430d2a)`

Construct a map from the 28-dimensional representation of the simply connected version of the twisted group ${}^3{\rm D}_4(3)$ to its standard 8-dimensional representation.

```magma
> X,Y := CST_Generators("3D",4,3,[0,1,0,0]);
> f := CSTtoChev("3D",4,3,X,Y : UseMap);
> G := Domain(f); G:Minimal;
MatrixGroup(28, GF(5^3))
> L := Codomain(f); L;
GL(8, GF(5, 3))
> C := ChevalleyGroup("3D",4,3);
> Order(C);
20560831566912
> forall{ x : x in Generators(G) | f(x) in C };
true

```

## `ExtendGeneratorList(t, r, X, Y): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum -> SeqEnum, SeqEnum`

```magma
GS: BoolElt                    Default: false
```

Given matrix generators (for the simple roots and their negatives) for a simply connected group of Lie type $t$ and rank $k$ over the field of $q$ elements, return the Curtis–Steinberg–Tits generators.

## `IrreducibleHighestWeightRepresentation(G, w): GrpLie, SeqEnum -> Map`

The function `CST_Generators` returns the Curti–Steinberg–Tits generators either for a Weyl module of weight $w$ or its irreducible quotient. This function returns the corresponding irreducible representation as a `Map`.

## `IrreducibleHighestWeightGenerators(G, w): GrpLie, SeqEnum -> SeqEnum, SeqEnum`

```magma
OnlySimple: BoolElt                    Default: false
```

For a simply connected finite group $G$ over the field of $q$ elements and a $q$-restricted weight $w$ return Curtis–Steinberg–Tits generators $X$, $Y$ for the irreducible $G$-module of weight $w$ for the group $G$. If `OnlySimple` is `true`, return generators for just the simple roots.

If $\varpi_1$, $\varpi_2$,…,$\varpi_k$ are the fundamental weights, then $w = a_1\varpi_n + a_2\varpi_2 + \cdots + a_k \varpi_k$ is $q$-restricted if $0\le a_i < q$ for $1 \le i\le k$.

## `IrreducibleHighestWeightFunction(G, w): GrpLie, SeqEnum -> UserProgram`

This is a version of `IrreducibleHighestWeightGenerators` which returns the homomorphism from $G$ to the matrix representation of weight $w$.

## `VermaModule(G, w): GrpLie, SeqEnum -> ModGrp`

For a finite group $G$ of Lie type and a weight $w$ this function returns a module $M$ of highest weight $w$ such that every highest weight module of weight $w$ is a quotient of $M$.

## `UniversalHighWeightRepresentation(G, w): GrpLie, SeqEnum -> Map, SeqEnum, SeqEnum`

This function returns a homomorphism from $G$ into ${\operatorname{GL}}(M)$ and Curtis-Steinberg–Tits generators for the image, where $M$ is the module returned by the previous function.

## Chevalley Groups

Let $\cal L$ be a complex semisimple Lie algebra with root system $\Phi$, simple roots $\Delta$, Cartan subalgebra $H$, one-dimensional root spaces ${\cal L}_\alpha$ and Cartan decomposition ${\cal L} = H\oplus \bigoplus_{\alpha \in \Phi}{\cal L}_\alpha$.

We choose basis vectors $e_\alpha\in{\cal L}_\alpha$ such that $[e_\alpha,e_\beta] = c_{\alpha,\beta}$, and the *structure constants* $c_{\alpha,\beta}$ are integers $\pm (r+1)$, where $r$ is the greatest integer such that $\beta-r\alpha$ is a root.

For all $\alpha\in\Delta$, we have $h_\alpha = [e_{-\alpha},e_\alpha]\in H$ and the *Chevalley basis* of $\cal L$ is the set $\{e_\alpha\}_{\alpha\in\Phi}\cup\{h_\alpha\}_{\alpha\in\Delta}$. The ${\mathbb{Z}}$-span of the Chevalley basis is the Lie algebra ${\cal L}_{\mathbb{Z}}$.

Given a field ${\mathbb{F}}$, define ${\cal L}_{\mathbb{F}}= {\cal L}_{\mathbb{Z}}\otimes {\mathbb{F}}$. For all roots $\alpha$ there is a homomorphism $x_\alpha$ from the additive group of ${\mathbb{F}}$ to ${\operatorname{GL}}({\cal L}_{\mathbb{F}})$ given by

$$
x_\alpha(\xi) = 1 + \xi\,\hbox{ad}\, e_\alpha +
  {\xi^2\over 2!}(\hbox{ad}\, e_\alpha)^2 + \cdots\ .
$$

Then

$$
G_{\hbox{\egtrm ad}}({\mathbb{F}}) = \langle\;x_\alpha(\xi)\mid \xi\in{\mathbb{F}},
  \ \alpha\in \Phi\;\rangle.
$$

is the *adjoint Chevalley group*. Other than a few exceptions of rank 1 or 2 over fields of at most 3 elements these groups are simple. However, $G_{\hbox{\egtrm ad}}({\mathbb{F}})$ is generally **not** the adjoint group of Lie type in the sense of linear algebraic groups (see [[Carter, 1993](../../references.md#cite-carter-big), p. 39]).

More generally, given a representation $\varphi : {\cal L}_{\mathbb{Z}}\to {\operatorname{GL}}(M)$, where $M$ is a ${\mathbb{Z}}$-module, we may define *root elements*

$$
x_\alpha(\xi) = 1 + \xi\varphi(e_\alpha) +
  {\xi^2\over 2!}\varphi(e_\alpha)^2 + \cdots\ .
$$

and set

$$
G_\varphi({\mathbb{F}}) = \langle\;x_\alpha(\xi)\mid \xi\in{\mathbb{F}},\ \alpha\in \Phi\;\rangle.
$$

This is also called a *Chevalley group*.

Suppose that $\Delta = \{\alpha_1,\dots,\alpha_n\}$ and that $\Phi'$ is a root subsystem of $\Phi$ with simple roots $\Delta'\subset\Delta$ such that $\Delta\setminus\Delta' = \{\alpha_i\}$ for some $i$. The restriction of the adjoint action of ${\cal L}_{\mathbb{Z}}$ to the Lie subalgebra ${\cal L}_{\mathbb{Z}}'$ corresponding to $\Phi'$ preserves the ${\mathbb{Z}}$-submodule $V$ of ${\cal L}_{\mathbb{Z}}$ whose basis is the set $X$ of elements $e_\beta$ such that the coefficient of $\alpha_i$ is $1$ when $\beta$ is expressed as a sum of simple roots.

For root data of types A, B, C, D and rank $n$ and types ${\rm E}_6$ and ${\rm E}_7$, the embedding in the root datum of rank $n+1$ adds an extra node to the Dynkin diagram and the construction of the previous paragraph produces the “standard module” for the corresponding Chevalley group. For groups of type ${\rm E}_8$ the “standard module” is the adjoint representation.

The construction of the “standard modules” for groups of types ${\rm F}_4$ and ${\rm G}_2$ is more complicated. In order to defined them we identify the Lie algebra of type ${\rm F}_4$ with the algebra of fixed points of the graph automorphism order 2 of ${\rm E}_6$ and identify the Lie algebra of type ${\rm G}_2$ with the fixed points of a graph automorphism of order 3 of ${\rm D}_4$.

### `StandardLieRepresentation(t, r): MonStgElt, RngIntElt -> SeqEnum, SeqEnum`

This function returns two sequences of lower triangular integer matrices defining the action of the ${\mathbb{Z}}$-form ${\cal L}_{\mathbb{Z}}$ of the simple Lie algebra of type $t$ and rank $r$ on its “standard module”. The first sequence represents the simple roots and the second sequence represents the negatives of the simple roots.

### `AdjointChevalleyGroup(t, r, q): MonStgElt, RngIntElt, RngIntElt -> GrpMat`

This function returns the adjoint Chevalley group of type $t$ and rank $r$ over the field of $q$ elements as a matrix group. The generators are Curtis–Steinberg–Tits generators.

### `Example: Adjoint Chev (ex-1c5530)`

The adjoint Chevalley group of type ${\rm B}_n(q)$ is isomorphic to the permutation group ${\rm P}\Omega(2n+1,q)$.

```magma
> n := 2;
> q := 5;
> G := AdjointChevalleyGroup("B",n,q);
> Type(G),Dimension(G);
GrpMat 10
> H := POmega(2*n+1,q);
> Type(H), Degree(H);
GrpPerm 156
> flag, _ := IsIsomorphic(G,H);
> flag;
true

```

### `LieRootMatrix(R, α, B): RootDtm, ModTupFldElt, SetIndx -> AlgMatElt`

The matrix of $\hbox{ad}\,(e_\alpha)$ acting (on the right) on the module with basis $B$, where $B$ must be a subset of the positive or the negative roots of the root datum $R$, as outlined in the construction above. The argument $\alpha$ is a vector representing a root in the root basis.

### `LieRootMatrix(R, r, X): RootDtm, RngIntElt, SeqEnum -> AlgMatElt`

```magma
Negative: BoolElt                    Default: false
```

The matrix of $\hbox{ad}\,(e_\alpha)$ where $\alpha$ is the $r$-th root acting (on the right) on the subspace of the Lie algebra of $R$ spanned by the roots indexed by $X$. The elements of $X$ are indices of positive roots unless `Negative` is `true`, in which case they they are indices of negative roots.

### `LieTypeGenerators(t, k, q): MonStgElt, RngIntElt, RngIntElt -> SeqEnum, SeqEnum`

### `LieTypeGenerators(t, k, K): MonStgElt, RngIntElt, FldFin -> SeqEnum, SeqEnum`

### `LieTypeGenerators(G): GrpLie -> SeqEnum, SeqEnum`

```magma
GS: BoolElt                    Default: false
```

The Curtis–Steinberg–Tits generators of a simply connected group $G$ of Lie type or the simply connected group of Lie type $t$ and rank $r$ over the finite field $K$ or ${\mathbb{F}}_q$. This function is available for both twisted and untwisted groups. If `GS` is `true`, the Gilkey–Seitz structure constants and root order are used.

### `SLPGeneratorList(t, r, q): MonStgElt, RngIntElt, RngIntElt -> SeqEnum, SeqEnum`

```magma
GS: BoolElt                    Default: false
```

The Curtis–Steinberg–Tits generators of the simply connected group of Lie type $t$ and rank $r$ over the field of $q$ elements, returned as straight-line programs. If `GS` is `true`, the Gilkey–Seitz structure constants and root order are used.

## Morphisms and the Row Reduction Algorithm

From an irreducible quasisimple matrix group $H$ of known Lie type $t$ and rank $r$ over the field of $q$ elements, the work of [[Liebeck and O'Brien, 2016](../../references.md#cite-exceptional-lob16)] produces Curtis–Steinberg–Tits generators $X$, $Y$ as part of the constructive recognition algorithm. This section describes some functions to construct homomorphisms $\rho : G \to H$ and their inverses from such generators, where $G$ is the simply connected group of Lie type $t$, rank $r$ over ${\mathbb{F}}_q$.

From the homomorphism $\rho : G\to H$ and a matrix $A\in H$, an element $g\in G$ such that $\rho(g) = A$ can be constructed using the Chevalley normal form of the Bruhat decomposition of $A$. That is, we write $g = uh\dot{w}u'$, where $u$, $h$, $\dot{w}$ and $u'$ have the properties described in Subsection [Bruhat Normalisation](introduction.md#subsectgrpliebruhat). This uses the “row reduction” algorithms for twisted [[Cohen and Taylor, n.d.](../../references.md#cite-cohen-taylor)] and untwisted [[Cohen *et al.*, 2004](../../references.md#cite-cohenmurraytaylor)] groups (a generalisation of Gaussian row reduction of matrices to groups of Lie type).

### `Morphism(G, X, Y): GrpLie, SeqEnum, SeqEnum -> Map`

```magma
OnlySimple: BoolElt                    Default: false
GS        : BoolElt                    Default: false
Verify    : BoolElt                    Default: false
```

Given an algebraically simple, simply connected group $G$ of Lie type and Curtis–Steinberg–Tits generators for a representation, return the homomorphism from $G$ to the group generated by $X$ and $Y$. If generators $X$ and $Y$ are available only for the simple roots and their negatives, set `OnlySimple` to `true`. If the generators follow the Gilkey–Seitz conventions, set `GS` to `true`. If `Verify` is true, the function first checks that $X$ and $Y$ satisfy the appropriate CST presentation. This function applies to both twisted and untwisted groups.

### `ChevalleyForm(ρ, A): Map[GrpLie,GrpMat], GrpMatElt -> SeqEnum, FldFinElt`

Given a homomorphism $\rho : G \to H$ from a simply connected group $G$ of Lie type to a matrix group $H$ and a matrix $A$, this function returns a sequence $s$ and a field element $z$. If $A$ is not in the image of $\rho$ (modulo scalars) then $s = [\ ]$, otherwise the elements of $s = [u, h, \dot{w},u']$ are the components of the Chevalley normal form of an element $g = uh\dot{w}u'$ such that $A = z\rho(g)$.

### `Example: Chev Form (ex-6fae1c)`

Choose a random element in a twisted group of Lie type, get a scalar multiple of its image in an irreducible highest weight representation and then check the Chevalley normal form.

```magma
> G := TwistedGroupOfLieType("2E",6,3);
> RootDatum(G);
Twisted simply connected root datum of dimension 6 of type 2E6,4
> Dimension(G);
78
> X,Y := CST_Generators("2E",6,3,[0,1,0,0,0,0]);
> rho := Morphism(G,X,Y);
> L := Codomain(rho);
> Dimension(L);
77
> F<t> := BaseRing(L);
> I := sub<L | &cat X, &cat Y>;
> g := Random(G);
> A := L!ScalarMatrix(77,t)*rho(g);
> s,z := ChevalleyForm(rho,A);
> z;
t
> &* s eq g;
true

```

### `PrepareRewrite(t, r, q, X, Y): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum -> UserProgram, Map`

### `TwistedPrepareRewrite(t, r, q, X, Y): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum -> UserProgram, Map`

```magma
OnlySimple: BoolElt                    Default: false
GS        : BoolElt                    Default: false
```

This function constructs the group $G$ of Lie type $t$ and rank $r$ over the field of $q$ elements and the homomorphism $f : G \to H$, where $H$ is the matrix group generated by the CST generators $X$ and $Y$. In addition to $f$ this function returns a map $\varphi : H \to G$ such that $f\circ \varphi = \hbox{id}_H$.

If generators $X$ and $Y$ are available only for the simple roots and their negatives, set `OnlySimple` to `true`. If the generators follow the Gilkey–Seitz conventions, set `GS` to `true`.

### `LieTypeRewrite(t, r, q, X, Y, g): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum, GrpMatElt -> BoolElt, GrpSLPElt`

### `TwistedLieTypeRewrite(t, r, q, X, Y, g): MonStgElt, RngIntElt, RngIntElt, SeqEnum, SeqEnum, GrpMatElt -> BoolElt, GrpSLPElt`

```magma
OnlySimple: BoolElt                    Default: false
GS        : BoolElt                    Default: false
```

Given a finite (untwisted or twisted) matrix group $H$ with generators $X$, $Y$ in CST format and an element $g\in H$, return a boolean flag $b$ and, if $b$ is `true`, an SLP $\pi$ that expresses $g$ as a word in the given generators.

If the parameter `OnlySimple` is `true`, the return value $\pi$ is an SLP in the generators corresponding to the simple roots and their negatives. Set `GS` to `true` if the generators follow the Gilkey–Seitz conventions.

### `Example: Lie Rewrite (ex-22cf73)`

Check that the SLP returned by `TwistedLieTypeRewrite` evaluates to the correct matrix when evaluated on the CST generators.

```magma
> X,Y := CST_Generators("3D",4,5,[]);
> H := sub< Parent(X[1,1]) | &cat X, &cat Y>;
> g := Random(H);
> flag, s := TwistedLieTypeRewrite("3D",4,5,X,Y,g);
> flag;
true
> gens := &cat X cat &cat Y;
> g eq Evaluate(s,gens);
true

```

### `RowReductionMap(ρ): Map[GrpLie,GrpMat] -> UserProgram`

### `TwistedRowReductionMap(ρ): Map[GrpLie,GrpMat] -> UserProgram`

Given an irreducible representation $\rho : G(q)\to {\operatorname{GL}}(M)$ of an untwisted (respectively twisted) finite group $G$ of Lie type, this function returns a function $f$ such that $\rho(f(A)) = A$ for all $A$ in the image of $A$.

More precisely, given $A$ in the codomain of $\rho$, the application of $f$ to $A$ returns two values: a sequence $w$ of length 0 or 1, and an element $z$. If $A$ is a scalar multiple of an element of the image of $\rho$, then $w[1]$ is a Steinberg word in the domain of $\rho$ and $z$ is a field element such that $z\rho(w[1]) = A$; otherwise $w$ is empty and $z$ is a message indicating the reason for failure. In particular, if $A$ is in the image of $\rho$, then $z$ is 1.