Background

Gaussian Binomials

Let v be an indeterminate over Q. For a positive integer n we set [n]_v = v^{n - 1} + v^{n - 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]!).

Quantized Enveloping Algebras

Let L be a semisimple Lie algebra with root system Φ. By Δ={α₁, ..., α_l } we denote a fixed set of simple roots of Φ. Let C=(C_ij) be the Cartan matrix of Φ (with respect to Δ, i.e., C_ij = < α_i, α_j^v >). Let d₁, ..., d_l be the unique sequence of positive integers with greatest common divisor 1, such that d_i C_ji = d_j C_ij , and set (α_i, α_j) = d_j C_ij . (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 s_i=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 U_q(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_α ^{- 1}K_α = 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 ω²=1 and τ²=1.

If the Dynkin diagram of Φ admits a diagram automorphism π, then π induces an automorphism of U_q(L) in the obvious way (π is a permutation of the simple roots; we permute the F_α, E_α, K_α^{∓ 1} accordingly).

Now we view U_q(L) as an algebra over Q, and we let /line((A)) : U_q(L)to U_q(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.

Representations of U_q(L)

Let λ∈P be a dominant weight. Then there is a unique irreducible highest-weight module over U_q(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 U_q(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 U_q(L) is a Hopf algebra. The comultiplication Δ : U_q(L)to U_q(L) tensor U_q(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 ε : U_q(L) to Q(q) is a homomorphism defined by ε(E_α)=ε(F_α)=0, ε(K_α) =1. Finally, the antipode S: U_q(L)to U_q(L) is an anti-automorphism given by S(E_α)= - K_α ^{- 1}E_α, S(F_α)= - F_α K_α, S(K_α)=K_α ^{- 1}.

Using Δ we can make the tensor product V tensor W of two U_q(L)-modules V, W into a U_q(L)-module. The counit ε yields a trivial 1-dimensional U_q(L)-module. And with S we can define a U_q(L)-module structure on the dual V ^* of a U_q(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 S^f = f S f ^{- 1}, if f is an automorphism, and S^f = f S ^{- 1} f ^{- 1}, if f is an anti-automorphism. The twisted counit is given by ε^f = ε f ^{- 1}.

PBW-type Bases

The first problem one has to deal with when working with U_q(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 U_q(L) isomorphic to U^ - tensor U⁰ tensor U^ + (as vector spaces), where U^ - is the subalgebra generated by the F_α, U⁰ is the subalgebra generated by the K_α, and U^ + is generated by the E_α. So a basis of U_q(L) is formed by all elements FKE, where F, K, E run through bases of U^ -, U⁰, U^ + respectively.

Finding a basis of U⁰ is easy: it is spanned by all K_α1^r₁ ... K_αl^r_l, where r_i∈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_α : U_q(L)to U_q(L) defined by eqalign( T_α(E_α) &= - F_αK_α
T_α(E_β) &= ∑_i=0^{r_{β, α}} ( - 1)ⁱ q_α ^{- i} E_α^{(r_{β, α} - i)}E_β E_α⁽ⁱ⁾, (α != β)
T_α(K_β) &= K_βK_α^{r_{β, α}}
T_α(F_α) &= - K_α ^{- 1} E_α
T_α(F_β) &= ∑_i=0^{r_{β, α}} ( - 1)ⁱ q_αⁱ F_α⁽ⁱ⁾F_βF_α^ ((r_{β, α} - i)), (α != β)
) (where E_α^(k) = E_α^k/[k]_α!, and likewise for F_α^(k)).

Let w₀=s_i1 ... s_it be a reduced expression for the longest element in the Weyl group W(Φ). For 1≤k≤t set F_k = T_(α_i1) ... T_(α_(i_{k - 1}))(F_(α_ik)), and E_k = T_(α_i1) ... T_(α_(i_{k - 1}))(E_(α_ik)). Then F_k∈U^ -, and E_k∈U^ +. Furthermore, the elements F₁^m₁ ... F_t^m_t, E₁^n₁ ... E_t^n_t (where the m_i, n_i 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 F_k, and E_k are homogeneous of weight -β and β respectively, where β=s_i1 ... s_(i_{k - 1})(α_ik).

In the following we use the notation F_k^(m) = F_k^m/[m]_(α_ik)!, and E_k⁽ⁿ⁾ = E_kⁿ/[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.

The Z-form of U_q(L)

For α∈Δ set (K_α choose n ) = ∏_i=1ⁿ (q_α ^{- i + 1}K_α - q_α^{i - 1} K_α ^{- 1}/q_αⁱ - q_α ^{- i}). Then according to [Lus90], Theorem 6.7 the elements F₁^(k₁) ... F_t^(k_t) K_α1^δ₁ (K_α1 choose m₁ ) ... K_αl^δ_l (K_αl choose m_l ) E₁^(n₁) ... E_t^(n_t), (where k_i, m_i, n_i≥0, δ_i=0, 1) form a basis of U_q(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 U_q(L), and denoted by U_Z. Since U_Z 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 U₁ over Q. Let I be the ideal of U₁ generated by K_α1 - 1, ..., K_αl - 1. Then U₁/I is isomorphic to the universal enveloping algebra U(L) of L. Also, the homomorphism U_q(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 U_q(L) and U_ε respectively.

The Canonical Basis

As in Section PBW-type Bases we let U^ - be the subalgebra of U_q(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 w₀=s_i1 ... s_it, and the elements F_k be as in Section PBW-type Bases. Then, in order to stress the dependency of the monomial F₁^(n₁) ... F_t^(n_t) on the choice of reduced expression for the longest element in W(Φ) we say that it is a w₀-monomial. The integer n₁ 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 w₀ for the longest element in the Weyl group, and any element X∈(B) we have that X = x + ∑_i ζ_i x_i, where x, x_i are w₀-monomials, x != x_i 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 w₀-monomials (where w₀ is a fixed reduced expression for the longest element in W(Φ)).

Now let widetilde(w)₀ be a second reduced expression for the longest element in W(Φ). Let x be a w₀-monomial, and let X be the element of B with principal monomial x. Write X as a linear combination of widetilde(w)₀-monomials, and let widetilde(x) be the principal monomial of that expression. Then we write widetilde(x) = R_w0^(tilde(w)₀)(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 w₀-monomials. Then (B) is a basis of the Z-module (L)/q(L). Moreover, (B) is independent of the choice of w₀. Let α∈Δ, and let widetilde(w)₀ 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 w₀-monomial such that b = x mod q(L). Set widetilde(x) = R_w0^ (tilde(w)₀)(x). Let widetilde(x)' be the widetilde(w)₀-monomial constructed from widetilde(x) by increasing its first exponent by 1. Then widetilde(F) _α(b) = R_(tilde(w)₀)^w₀(widetilde(x)') mod q(L). For widetilde(E)_α we let widetilde(x)' be the widetilde(w)₀-monomial constructed from widetilde(x) by decreasing its first exponent by 1, if this exponent is ≥1. Then widetilde(E)_α(b) = R_(tilde(w)₀)^w₀(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 w₀, widetilde(w)₀. 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 U_q(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 w₀-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 w₀-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.

The Path Model

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 P_R be the vector space over R spanned by P. Let Π be the set of all piecewise linear paths ξ : [0, 1]to P_R, 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 U_q(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 ν=(ν₁, ..., ν_s) is a sequence of elements of W(Φ).λ, such that ν_i> ν_{i + 1} and a=(a₀=0, a₁, ... , a_s=1) is a sequence of rationals such that a_i < a_{i + 1}. The path π corresponding to these sequences is given by π(t) =∑_j=1^{r - 1} (a_j - a_{j - 1})ν_j + ν_r(t - a_{r - 1}) for a_{r - 1}≤t≤a_r. 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:

(a)

Let π be an LS-path. Then f_απ is an LS-path or 0; and the same holds for e_απ.

(b)

The action of f_α, e_α can easily be described combinatorially (see [Lit94]).

(c)

The endpoint of an LS-path is an integral weight.

(d)

Let π=(ν, a) be an LS-path. Then by φ(π) we denote the unique element σ of W(Φ) of shortest length such that σ(λ)=ν₁.