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). 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].

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 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{split}\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}\end{split}\]

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). However, if GS is true, the root order and signs used by Gilkey and Seitz [Gilkey and 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

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.

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

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

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.

> 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

Run in calculatorCopy input

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

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.

> 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

Run in calculatorCopy input

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

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

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, 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)\).

> 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

Run in calculatorCopy input

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

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

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

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] 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. This uses the “row reduction” algorithms for twisted [Cohen and Taylor, n.d.] and untwisted [Cohen et al., 2004] groups (a generalisation of Gaussian row reduction of matrices to groups of Lie type).

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

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.

> 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

Run in calculatorCopy input

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

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

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.

> 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

Run in calculatorCopy input

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.