Let v be an indeterminate over Q. For a positive integer n we set [n]v = vn - 1 + vn - 3 + ... + v - n + 3 + v - n + 1. We say that [n]v is the Gaussian integer corresponding to n. The Gaussian factorial [n]v! is defined by [0]v! = 1, [n]v! = [n]v[n - 1]v ... [1]v (for ) n >0. Finally, the Gaussian binomial is (n choose k)v = ([n]! /[k]![n - k]!).
Let L be a semisimple Lie algebra with root system Φ. By Δ={α1, ..., αl } we denote a fixed set of simple roots of Φ. Let C=(Cij) be the Cartan matrix of Φ (with respect to Δ, i.e., Cij = < αi, αjv >). Let d1, ..., dl be the unique sequence of positive integers with greatest common divisor 1, such that di Cji = dj Cij , and set (αi, αj) = dj Cij . (We note that this implies that (αi, αi) is divisible by 2.) By P we denote the weight lattice, and we extend the form ( , ) to P by bilinearity.
By W(Φ) we denote the Weyl group of Φ. It is generated by the simple reflections si=sαi for 1≤i≤l (where sα is defined by sα(β) = β - < β, αv > α).
We work over the field Q(q). For α∈Φ we set qα = q^(((α, α)/2)), and for a non-negative integer n, [n]α= [n]_(v=qα); [n]α! and (n choose k )α are defined analogously.
The quantized enveloping algebra Uq(L) is the associative
algebra (with one) over Q(q) generated by Fα,
Kα, Kα - 1, Eα for α∈Δ,
subject to the following relations
eqalign(
KαKα - 1 &= Kα - 1Kα = 1,
KαKβ = KβKα
Eβ Kα &= q - (α, β)Kα Eβ
Kα Fβ &= q - (α, β)FβKα
Eα Fβ &= FβEα + δα, β
(Kα - Kα - 1 /qα - qα - 1)
)
together with, for α != β∈Δ,
eqalign(
∑k=0^(1 - < β, αv > )
( - 1)k (1 - < β, αv > choose k)α
Eα^(1 - < β, αv > - k)
Eβ Eαk =0 &
∑k=0^(1 - < β, αv > ) ( - 1)k
(1 - < β, αv > choose k)α
Fα^(1 - < β, αv > - k)
Fβ Fαk =0 &.
)
The quantized enveloping algebra has an automorphism ω defined by ω(Fα) = Eα, ω(Eα)= Fα and ω(Kα)=Kα - 1. Also there is an anti-automorphism τ defined by τ(Fα)=Fα, τ(Eα)= Eα and τ(Kα)=Kα - 1. We have ω2=1 and τ2=1.
If the Dynkin diagram of Φ admits a diagram automorphism π, then π induces an automorphism of Uq(L) in the obvious way (π is a permutation of the simple roots; we permute the Fα, Eα, Kα∓ 1 accordingly).
Now we view Uq(L) as an algebra over Q, and we let /line((A)) : Uq(L)to Uq(L) be the automorphism defined by /line(Fα)=Fα, /line(Kα)= Kα - 1, /line(Eα)=Eα, /line(q)=q - 1. This map is called the bar-automorphism.
Let λ∈P be a dominant weight. Then there is a unique irreducible highest-weight module over Uq(L) with highest weight λ. We denote it by V(λ). It has the same character as the irreducible highest-weight module over L with highest weight λ. Furthermore, every finite-dimensional Uq(L)-module is a direct sum of irreducible highest-weight modules. In [Gra04] a few algorithms for constructing V(λ) are given. In the Magma implementation the algorithm based on Gröbner bases is used.
It is well-known that Uq(L) is a Hopf algebra. The
comultiplication Δ : Uq(L)to Uq(L) tensor Uq(L) is defined by
eqalign(
Δ(Eα) &= Eα tensor 1 + Kα tensor Eα
Δ(Fα) &= Fα tensor Kα - 1 +
1 tensor Fα
Δ(Kα) &= Kα tensor Kα.)
(Note that we use the same symbol (Δ) to denote a set of simple roots of Φ;
of course this does not cause confusion.) The counit ε :
Uq(L) to Q(q) is a homomorphism defined by
ε(Eα)=ε(Fα)=0,
ε(Kα) =1. Finally, the antipode
S: Uq(L)to Uq(L) is an anti-automorphism given
by S(Eα)= - Kα - 1Eα, S(Fα)= - Fα
Kα, S(Kα)=Kα - 1.
Using Δ we can make the tensor product V tensor W of two Uq(L)-modules V, W into a Uq(L)-module. The counit ε yields a trivial 1-dimensional Uq(L)-module. And with S we can define a Uq(L)-module structure on the dual V * of a Uq(L)-module V, by (u.f)(v) = f(S(u).v).
The Hopf algebra structure given above is not the only one possible. For example, we can twist Δ, ε, S by an automorphism, or an anti-automorphism f. The twisted comultiplication is given by Δf = f tensor f Δ f - 1, the twisted antipode by Sf = f S f - 1, if f is an automorphism, and Sf = f S - 1 f - 1, if f is an anti-automorphism. The twisted counit is given by εf = ε f - 1.
The first problem one has to deal with when working with Uq(L) is finding a basis of it, along with an algorithm for expressing the product of two basis elements as a linear combination of basis elements. First of all we have that Uq(L) isomorphic to U^ - tensor U0 tensor U^ + (as vector spaces), where U^ - is the subalgebra generated by the Fα, U0 is the subalgebra generated by the Kα, and U^ + is generated by the Eα. So a basis of Uq(L) is formed by all elements FKE, where F, K, E run through bases of U^ -, U0, U^ + respectively.
Finding a basis of U0 is easy: it is spanned by all Kα1r1 ... Kαlrl, where ri∈Z. For U^ - and U^ + we
use the so-called PBW-type bases. They are defined as follows.
For α, β∈Δ we set rβ, α = - < β,
αv >. Then for α∈Δ we have the automorphism
Tα : Uq(L)to Uq(L) defined by
eqalign(
Tα(Eα) &= - FαKα
Tα(Eβ) &= ∑i=0rβ, α
( - 1)i qα - i Eα(rβ, α - i)Eβ
Eα(i), (α != β)
Tα(Kβ) &= KβKαrβ, α
Tα(Fα) &= - Kα - 1 Eα
Tα(Fβ) &= ∑i=0rβ, α
( - 1)i qαi Fα(i)FβFα^
((rβ, α - i)), (α != β)
)
(where Eα(k) = Eαk/[k]α!, and likewise for
Fα(k)).
Let w0=si1 ... sit be a reduced expression for the longest element in the Weyl group W(Φ). For 1≤k≤t set Fk = T_(αi1) ... T_(α_(ik - 1))(F_(αik)), and Ek = T_(αi1) ... T_(α_(ik - 1))(E_(αik)). Then Fk∈U^ -, and Ek∈U^ +. Furthermore, the elements F1m1 ... Ftmt, E1n1 ... Etnt (where the mi, ni are non-negative integers) form bases of U^ - and U^ + respectively.
The elements Fα and Eα are said to have weight -α and α respectively, where α is a simple root. Furthermore, the weight of a product ab is the sum of the weights of a and b. Now elements of U^ -, U^ + that are linear combinations of elements of the same weight are said to be homogeneous. It can be shown that the elements Fk, and Ek are homogeneous of weight -β and β respectively, where β=si1 ... s_(ik - 1)(αik).
In the following we use the notation Fk(m) = Fkm/[m]_(αik)!, and Ek(n) = Ekn/[n]_(αik)!.
We refer to [Gra01] for an account of algorithms for expressing the product of two elements of a PBW-type basis as a linear combination of such elements. These algorithms are implemented in Magma.
For α∈Δ set (Kα choose n ) = ∏i=1n (qα - i + 1Kα - qαi - 1 Kα - 1/qαi - qα - i). Then according to [Lus90], Theorem 6.7 the elements F1(k1) ... Ft(kt) Kα1δ1 (Kα1 choose m1 ) ... Kαlδl (Kαl choose ml ) E1(n1) ... Et(nt), (where ki, mi, ni≥0, δi=0, 1) form a basis of Uq(L), such that the product of any two basis elements is a linear combination of basis elements with coefficients in Z[q, q - 1]. The quantized enveloping algebra over Z[q, q - 1] with this basis is called the Z-form of Uq(L), and denoted by UZ. Since UZ is defined over Z[q, q - 1] we can specialize q to any nonzero element ε of a field F, and obtain an algebra Uε over F. In particular, if we take ε = 1, then we obtain an algebra U1 over Q. Let I be the ideal of U1 generated by Kα1 - 1, ..., Kαl - 1. Then U1/I is isomorphic to the universal enveloping algebra U(L) of L. Also, the homomorphism Uq(L) to U(L) maps the basis above onto an integral basis of U(L) ([Lus90]).
We call q∈Q(q), and ε ∈F the quantum parameter of Uq(L) and Uε respectively.
As in Section PBW-type Bases we let U^ - be the subalgebra of Uq(L) generated by the Fα for α∈Δ. Kashiwara and Lusztig have (independently) given constructions of a basis of U^ - with very nice properties, called the canonical basis.
Let w0=si1 ... sit, and the elements Fk be as in Section PBW-type Bases. Then, in order to stress the dependency of the monomial F1(n1) ... Ft(nt) on the choice of reduced expression for the longest element in W(Φ) we say that it is a w0-monomial. The integer n1 is called its first exponent.
Now we let /line((a)) be the automorphism of U^ - defined in Section Quantized Enveloping Algebras. Elements that are invariant under /line((a)) are said to be bar-invariant.
By results of Lusztig ([Lus93], Theorem 42.1.10, [Lus96], Proposition 8.2), there is a unique basis (B) of U^ - with the following properties. Firstly, all elements of (B) are bar-invariant. Secondly, for any choice of reduced expression w0 for the longest element in the Weyl group, and any element X∈(B) we have that X = x + ∑i ζi xi, where x, xi are w0-monomials, x != xi for all i, and ζi∈qZ[q]. The basis (B) is called the canonical basis. If we work with a fixed reduced expression for the longest element in W(Φ), and write X∈(B) as above, then we say that x is the principal monomial of X.
Let (L) be the Z[q]-lattice in U^ - spanned by B. Then (L) is also spanned by all w0-monomials (where w0 is a fixed reduced expression for the longest element in W(Φ)).
Now let widetilde(w)0 be a second reduced expression for the longest element in W(Φ). Let x be a w0-monomial, and let X be the element of B with principal monomial x. Write X as a linear combination of widetilde(w)0-monomials, and let widetilde(x) be the principal monomial of that expression. Then we write widetilde(x) = Rw0^(tilde(w)0)(x). Note that x = widetilde(x) mod q(L).
Now let (B) be the set of all x mod q(L), where x runs through the set of w0-monomials. Then (B) is a basis of the Z-module (L)/q(L). Moreover, (B) is independent of the choice of w0. Let α∈Δ, and let widetilde(w)0 be a reduced expression for the longest element in W(Φ), starting with sα. The Kashiwara operators widetilde(F) α : (B)to (B) and widetilde(E)α : (B)to (B)∪{0} are defined as follows. Let b∈(B) and let x be the w0-monomial such that b = x mod q(L). Set widetilde(x) = Rw0^ (tilde(w)0)(x). Let widetilde(x)' be the widetilde(w)0-monomial constructed from widetilde(x) by increasing its first exponent by 1. Then widetilde(F) α(b) = R_(tilde(w)0)w0(widetilde(x)') mod q(L). For widetilde(E)α we let widetilde(x)' be the widetilde(w)0-monomial constructed from widetilde(x) by decreasing its first exponent by 1, if this exponent is ≥1. Then widetilde(E)α(b) = R_(tilde(w)0)w0(widetilde(x)') mod q(L). Furthermore, widetilde(E)α(b) =0 if the first exponent of widetilde(x) is 0. It can be shown that this definition does not depend on the choice of w0, widetilde(w)0. Furthermore we have widetilde(F)αwidetilde(E)α(b)=b, if widetilde(E)α(b) != 0, and widetilde(E)α widetilde(F)_ (α)(b)=b for all b∈(B).
Now let V(λ) be a highest-weight module over Uq(L), with highest weight λ. Let vλ be a fixed highest weight vector. Then (B)λ = { X.vλ | X∈(B)} - {0} is a basis of V(λ), called the canonical basis of V(λ). Let (L)(λ) be the Z[q]-lattice in V(λ) spanned by (B)λ. We let (B)((λ)) be the set of all x.vλ mod q(L)(λ), where x runs through all w0-monomials, such that X.vλ != 0, where X∈(B) is the element with principal monomial x. Then the Kashiwara operators are also viewed as maps (B)(λ)to (B)(λ)∪{0}, in the following way. Let b=x.vλ mod q(L)(λ) be an element of (B)(λ), and let b'=x mod q(L) be the corresponding element of (B). Let y be the w0-monomial such that widetilde(F)α(b')=y mod q(L). Then widetilde(F) α(b) = y.vλ mod q(L)(λ). The description of widetilde(E)α is analogous. (In [Jan96], Chapter 9 a different definition is given; however, by [Jan96], Proposition 10.9, Lemma 10.13, the two definitions agree).
The set (B)(λ) has dim V(λ) elements. We let Γ be the coloured directed graph defined as follows. The points of Γ are the elements of (B)(λ), and there is an arrow with colour α∈Δ connecting b, b'∈(B), if widetilde(F)α(b)=b'. The graph Γ is called the crystal graph of V(λ).
In [Gra02] algorithms are given for computing the action of the Kashiwara operators on (B) (without computing B first), and for computing elements of B.
In this section we recall some basic facts on Littelmann's path model.
From Section Quantized Enveloping Algebras we recall that P denotes the weight lattice. Let PR be the vector space over R spanned by P. Let Π be the set of all piecewise linear paths ξ : [0, 1]to PR, such that ξ(0)=0. For α∈Δ Littelmann defined path operators fα, eα : Π to Π∪{0}. Let λ be a dominant weight and let ξλ be the path joining λ and the origin by a straight line. Let Πλ be the set of all nonzero f_(αi1) ... f_(αim)(ξλ) for m≥0. Then ξ(1)∈P for all ξ∈Πλ. Let μ∈P be a weight, and let V(λ) be the highest-weight module over Uq(L) of highest weight λ. A theorem of Littelmann states that the number of paths ξ∈Πλ such that ξ(1)=μ is equal to the dimension of the weight space of weight μ in V(λ) ([Lit95], Theorem 9.1).
All paths appearing in Πλ are so-called Lakshmibai--Seshadri paths (LS-paths for short). They are defined as follows. Let ≤ denote the Bruhat order on W(Φ). For μ, ν∈W(Φ).λ (the orbit of λ under the action of W(Φ)), write μ≤ν if τ≤σ, where τ, σ∈W(Φ) are the unique elements of minimal length such that τ(λ)=μ, σ(λ)= ν. Now a rational path of shape λ is a pair π=(ν, a), where ν=(ν1, ..., νs) is a sequence of elements of W(Φ).λ, such that νi> νi + 1 and a=(a0=0, a1, ... , as=1) is a sequence of rationals such that ai < ai + 1. The path π corresponding to these sequences is given by π(t) =∑j=1r - 1 (aj - aj - 1)νj + νr(t - ar - 1) for ar - 1≤t≤ar. Now an LS-path of shape λ is a rational path satisfying a certain integrality condition (see [Lit94], [Lit95]). We note that the path ξλ = ((λ), (0, 1)) joining the origin and λ by a straight line is an LS-path of shape λ. Furthermore, all paths obtained from ξλ by applying the path operators are LS-paths of shape λ.
From [Lit94], [Lit95]) we transcribe the following: