VARIOUS REPRESENTATIONS OF THE GENERALIZED KOSTKA POLYNOMIALS

ANATOL N. KIRILLOV, ANNE SCHILLING^{∗}, AND MARK SHIMOZONO^{†}

Dedicated to George Andrews on the occasion of his sixtieth birthday

Abstract. The generalized Kostka polynomials K_{λR}(q) are labeled by a partition λ and a sequence of rectangles R. They are q-analogues of multiplicities of the finite-dimensional irreducible representation W (λ) of 𝔤𝔩_{n} with highest weight λ in the tensor product W (R_{1}) ⊗ ⋯ ⊗ W (R_{L}). We review several representations of the generalized Kostka polynomials, such as the charge, path space, quasi-particle and bosonic representation. In addition we describe a bijection between Littlewood–Richardson tableaux and rigged configurations, and sketch a proof that it preserves the appropriate statistics. This proves in particular the equality of the quasi-particle and charge representation of the generalized Kostka polynomials.

1. Introduction

The Kostka number K_{λμ} labeled by two partitions λ = (λ_{1}, …, λ_{n}) and μ = (μ_{1}, …, μ_{L}) is the multiplicity of the finite-dimensional irreducible representation W (λ) of 𝔤𝔩_{n} with highest weight λ in the tensor product W (μ_{1}) ⊗ ⋯ ⊗ W (μ_{L}), that is

K_{λμ} = [W (λ) : W (μ_{1}) ⊗ ⋯ ⊗ W (μ_{L})].

This multiplicity is equal to the cardinality of the set of column-strict Young tableaux of shape λ and content μ. There is a natural qdeformation of the Kostka numbers given by the Kostka polynomials which are formally defined as the connection coefficients between the Schur and the Hall–Littlewood polynomials [24].

Date: December 1998. 1991 Mathematics Subject Classification. Primary 05A19, 05A15; Secondary

81R50, 82B23.

Key words and phrases. Generalized Kostka polynomials, charge, path space, Littlewood–Richardson tableaux, rigged configurations.

∗ Supported by the “Stichting Fundamenteel Onderzoek der Materie”. † Partially supported by NSF grant DMS-9800941.

There are several explicit expressions for the Kostka polynomials. Lascoux and Schützenberger [20] express them as the generating function of column-strict Young tableaux with a charge statistic. They show that the set of column-strict Young tableaux of fixed content has the structure of a graded poset with the covering relation given by the cocyclage. In their study of the XXX model using Bethe Ansatz techniques, Kirillov and Reshetikhin [16] obtained an expression for the Kostka polynomials in terms of rigged configurations. Rigged configurations index the solutions of the Bethe Ansatz equations; they are sequences of partitions obeying certain conditions together with quantum numbers or riggings labeling the parts of the partitions. This representation is of interest from the physics perspective as it reflects the quasiparticle content of the underlying statistical mechanical model [13, 14]. A third representation in terms of path spaces was given by Nakayashiki and Yamada [25], and in a slightly different formulation using the plactic monoid by Lascoux, Leclerc and Thibon [22]. Path spaces first occurred in the corner transfer matrix study of exactly solvable lattice models (see for example [1]) and are closely related to the crystal theory of Kashiwara [10]. The statistic in this case is given by the energy function on paths. We will refer to these three representations as charge, quasi-particle and path space representation, respectively.

Recently certain generalizations of the Kostka polynomials were introduced and studied [18, 28, 30, 31, 32, 33]. These generalized Kostka polynomials K_{λR}(q) are labeled by a partition λ and a sequence of rectangles R = (R_{1}, …, R_{L}), that is, each R_{i} = (η_{i}^{μ_{i}}) is a partition of rectangular shape. They are q-analogues of the multiplicity

K_{λR}(1) = [W (λ) : W (R_{1}) ⊗ ⋯ ⊗ W (R_{L})], (1)

and when all R_{i} are single rows (in which case R_{i} = (η_{i})), the generalized Kostka polynomial reduces to the Kostka polynomial K_{λη}(q). The multiplicity K_{λR}(1) is equal to the cardinality of the set of Littlewood– Richardson tableaux [5].

Akin to the Kostka polynomials, the generalized Kostka polynomials have a charge, path space and quasi-particle representation. We will discuss these representations in Sections 2, 3 and 5, respectively. A fourth representation as the sum of q-supernomials over the A_{n} Weyl group is given in Section 4. q-Supernomials extend the q-binomial coefficients and correspond to the generating function of unrestricted paths. Because most formulas of the form of this fourth representation can be interpreted as (finitizations of) characters or branching functions of bosonic algebras, they are referred to as bosonic representations.

The generalized Kostka polynomials also arise as Poincaré polynomials of isotypic components of graded GL(n)-modules supported in the closure of a nilpotent conjugacy class [33]. This yields in particular another tableau formula for the generalized Kostka polynomials in terms of catabolizable tableaux [31, Proposition 19]. These connections are however beyond the scope of this paper.

The relations between the different representations of the generalized Kostka polynomials discussed here have been established in various papers. The equality between the bosonic and path space representation was shown in [28], the equality between the path space and the charge representation was established in [28, 32], and finally the equivalence of the charge and quasi-particle representation was recently proven in [17]. In [17] a bijection between the set of Littlewood–Richardson tableaux and rigged configurations is given, which is reviewed in Section 6. This bijection preserves the statistics. A sketch of the proof of this property is given in Section 7. The equality between the quasi-particle and the bosonic representation can be viewed as a Rogers–Ramanujantype identity. We conclude in Section 8 with a discussion of some open problems related to the generalized Kostka polynomials.

2. Charge representation

The multiplicity K_{λR}(1) as defined in (1) is equal to the cardinality of the set of Littlewood–Richardson tableaux. There are several ways to define LR tableaux. Here we define the set CLR(λ; R) where “C” indicates a column labeling. Later we will also need the set of row LR tableaux denoted by RLR(λ; R). For a given sequence of rectangles R = (R_{1}, …, R_{L}) define the standard tableaux Z_{i} (1 ≤ i ≤ L) of shape R_{i} = (η_{i}^{μ_{i}}) by inserting the numbers

(c − 1)μ_{i} + ∑_{j=1}^{i−1} |R_{i}| < k ≤ cμ_{i} + ∑_{j=1}^{i−1} |R_{i}|

into the c-th column of R_{i}. For example, for R = ((2, 2), (3, 3)) we have, using the English convention for tableaux,

Z_{1} = 1 3 2 4 and Z_{2} = 5 7 9 6 8 10.

This means that Z_{i} is a standard tableau over the alphabet B_{i} = {|R_{1}|+ ⋯ + |R_{i−1}| + 1 < ⋯ < |R_{1}| + ⋯ + |R_{i}|}. For a tableau T denote by T |_{B} the restriction of T to the alphabet B. The row-reading word of a skew tableau T is given by word(T) = ⋯ w_{2}w_{1} where w_{i} is the word of the i-th row of T. Denote by P (w) the Schensted P -tableau of the word w and define P (T) := P (word(T)). Finally denote the set of all standard tableaux of shape λ by ST(λ). Then the set CLR(λ; R) is defined as

CLR(λ; R) = {T ∈ ST(λ)|P (T |_{B_{i}}) = Z_{i}}.

Example 1. Let λ = (3, 2) and R = ((1), (2, 2)). Then

T = 1 2 4 3 5

is in CLR(λ; R) since P (T |_{B_{1}}) = 1 and P (T |_{B_{2}}) = 2 4 3 5. On the

other hand T = 1 3 5 2 4 is not an LR tableau with respect to R since

P (T |_{B_{2}}) = 2 3 5 4.

It was shown in [28, Section 6] and [30] that the set CLR(R) = ∪_{λ}CLR(λ; R) has the structure of a graded poset with covering relation given by the R-cocyclage and grading function given by the generalized charge, denoted c_{R}. The generalized Kostka polynomial is the generating function of LR tableaux with the charge statistic [28, 30]

K_{λR}(q) = ∑_{T ∈CLR(λ;R)} q^{c_{R}(T)}. (2)

This extends the charge representation of the Kostka polynomial K_{λη}(q) of Lascoux and Schützenberger [20, 21].

The charge of an LR tableau can be given explicitly. To this end we need to introduce bijections on the set of LR tableaux which correspond to a permutation of the rectangles in R. Define by s_{p}R the sequence of rectangles obtained from R by exchanging R_{p} and R_{p+1}. Furthermore, denote by ev : ST(λ) → ST(λ) Schützenberger’s evacuation involution [29]. This involution restricts to a bijection ev : CLR(λ; R) → CLR(λ; R^{ev}) where R^{ev} = (R_{L}, …, R_{1}).

Definition-Proposition 1. For 1 ≤ p ≤ L − 1 there are unique bijections σ_{p} : CLR(λ; R) → CLR(λ; s_{p}R) satisfying the following properties:

1. If p < L−1 then σ_{p} commutes with restriction to the initial interval B_{1} ∪⋯∪B_{L−1} where B_{i} are as in the definition of CLR(λ; R).

2. For p = L − 1 the following diagram commutes:

CLR(λ; R) ⟶^{σ_{p}} CLR(λ; s_{p}R)
ev↓  ↓^{ev}
CLR(λ; R^{ev}) ⟶_{σ_{1}} CLR(λ; s_{1}(R^{ev}))

Proof. One may reduce to the case p = L − 1 using 1, then to the case p = 1 using 2, and then to the case p = 1 and L = 2 using 1 again. In this case the sets of tableaux are all empty or all singletons by [30, Prop. 33] and the result holds trivially.

Then the generalized charge on CLR(R) is given by [30, 28]

c_{R}(T) = \frac{1}{L!} ∑_{σ∈S_{L}} ∑_{i=1}^{L−1}(L − i)d_{i,σR}(σT). (3)

Here σ = σ_{p_{1}} ∘⋯∘σ_{p_{k}} is an element of the symmetric group, d_{i,R}(T) = d_{R_{i},R_{i+1}}(word(T)|_{B_{i}∪B_{i+1}}) where B_{i} is the alphabet corresponding to R_{i} in the definition of CLR(λ; R) and d_{R_{1},R_{2}}(w) is the number of cells of the shape P (w) that lie in columns strictly to the right of the max(η_{1}, η_{2})-th column.

3. Path space representation

It was shown in [28, 32] that the generalized Kostka polynomials have a path space representation. Denote by B_{λ} the set of columnstrict Young tableaux of shape λ over the alphabet {1, 2, …, n}. Let us restrict here to partitions with at most n − 1 parts. The partition λ can be identified with a weight Λ = Λ_{λ_{1}^{t}} + Λ_{λ_{2}^{t}} + ⋯ where λ^{t} denotes the transpose of λ and Λ_{i} are the fundamental weights of A_{n−1}. Then the set B_{λ} is the crystal base of the irreducible integral highest weight module of highest weight Λ over the quantized universal enveloping algebra U_{q}(A_{n−1}) [11]. The action of the raising and lowering operators e_{i} and f_{i} on B_{λ} for i ∈ I = {1, 2, …, n} are also given in [11] which are compatible with the tensor product structure. There is an inclusion U_{q}(A_{n−1}) ⊂ U′_{q}(A_{n−1}^{(1)}) where U′_{q}(A_{n−1}^{(1)}) is the universal enveloping algebra of the derived algebra A′_{n−1}^{(1)} [9]. The weight lattice of A′_{n−1}^{(1)} is the ℤ-span of the fundamental weights {Λ_{0}, Λ_{1}, …, Λ_{n−1}}. In ref. [12] the actions of e_{i} and f_{i} for i ∈ J = {0, 1, …, n} were defined, and it was shown that for rectangular shapes λ the crystal B_{λ} is perfect.

Write ϕ_{i}(b) (resp. ϵ_{i}(b)) for the maximum index m such that f_{i}^{m}(b) ≠ 0 (resp. e_{i}^{m}(b) ≠ 0). Given crystals B_{1} and B_{2} define the following crystal structure on the tensor product B_{2} ⊗ B_{1} (which differs from the literature, but is consistent with the Robinson–Schensted–Knuth correspondence). For b_{2} ⊗ b_{1} ∈ B_{2} ⊗ B_{1} one defines

\begin{aligned}ϕ_{i}(b_{2} ⊗ b_{1}) & = ϕ_{i}(b_{2}) + max(0, ϕ_{i}(b_{1}) − ϵ_{i}(b_{2})) \\ ϵ_{i}(b_{2} ⊗ b_{1}) & = ϵ_{i}(b_{1}) + max(0, −ϕ_{i}(b_{1}) + ϵ_{i}(b_{2})). \end{aligned}

When ϕ_{i}(b_{2} ⊗ b_{1}) > 0 (resp. ϵ_{i}(b_{2} ⊗ b_{1}) > 0) one defines

f_{i}(b_{2} ⊗ b_{1}) = \begin{cases}b_{2} ⊗ f_{i}(b_{1}) & if ϕ_{i}(b_{1}) > ϵ_{i}(b_{2}) \\ f_{i}(b_{2}) ⊗ b_{1} & if ϕ_{i}(b_{1}) ≤ ϵ_{i}(b_{2}) \end{cases}

and respectively

e_{i}(b_{2} ⊗ b_{1}) = \begin{cases}b_{2} ⊗ e_{i}(b_{1}) & if ϕ_{i}(b_{1}) ≥ ϵ_{i}(b_{2}) \\ e_{i}(b_{2}) ⊗ b_{1} & if ϕ_{i}(b_{1}) < ϵ_{i}(b_{2}). \end{cases}

For a partition λ and a sequence of rectangles R define the set of unrestricted paths

P_{λR} = {b_{L} ⊗ ⋯ ⊗ b_{1}|b_{i} ∈ B_{R_{i}} and ∑_{i=1}^{L} content(b_{i}) = λ}.

Say that b ∈ P_{λR} is classically restricted if e_{i}(b) = 0 for all i ∈ I. The set of classically restricted paths is defined as

P_{λR}^{r} = {b ∈ P_{λR}|b is classically restricted}.

There exists an energy function on the set of paths. The definitions here follow [25]. Suppose that B_{1} and B_{2} are perfect crystals of finitedimensional U_{q}(A_{n−1})-modules; then B_{2} ⊗ B_{1} is connected. There is an isomorphism B_{2} ⊗ B_{1} ≅ B_{1} ⊗ B_{2}. This is called the local isomorphism. Let the image of b_{2} ⊗ b_{1} ∈ B_{2} ⊗ B_{1} under this isomorphism be denoted b′_{1} ⊗ b′_{2}. Then there is a unique (up to global additive constant) map H : B_{2} ⊗ B_{1} → ℤ such that

H(e_{i}(b_{2} ⊗ b_{1})) = H(b_{2} ⊗ b_{1}) + \begin{cases}−1 & if i = 0, e_{0}(b_{2} ⊗ b_{1}) = e_{0}b_{2} ⊗ b_{1} \\ & and e_{0}(b′_{1} ⊗ b′_{2}) = e_{0}b′_{1} ⊗ b′_{2} \\ 1 & if i = 0, e_{0}(b_{2} ⊗ b_{1}) = b_{2} ⊗ e_{0}b_{1} \\ & and e_{0}(b′_{1} ⊗ b′_{2}) = b′_{1} ⊗ e_{0}b′_{2} \\ 0 & otherwise. \end{cases}

This map is called the local energy function.

Let R be a sequence of rectangles. Given b = b_{L} ⊗ ⋯ ⊗ b_{1} with b_{i} ∈ B_{R_{i}}, denote by b_{j}^{(i+1)} the (i + 1)-th tensor factor in the image of b under the composition of local isomorphisms that switch B_{R_{j}} with B_{R_{k}} as k goes from j − 1 down to i + 1. Then define the energy function

E(b) = ∑_{1≤i<j≤L} H(b_{j}^{(i+1)} ⊗ b_{i}).

It was shown in [32] that the generalized Kostka polynomial can be expressed as

K_{λR}(q) = ∑_{b∈P_{λR}^{r}} q^{E(b)}. (4)

This representation extends the path space representation of the Kostka polynomials of Nakayashiki and Yamada [25]. A slightly different energy function, more in the spirit of (3), was given in [28, 32] extending the representation of [22] in the Kostka case.

4. Bosonic representation

Similar to (4) of the previous section one may define the generating function of unrestricted paths as

S_{λR}(q) = ∑_{b∈P_{λR}} q^{E(b)}. (5)

For R a sequence of single rows or single columns these polynomials were studied in [3, 4, 7, 15]. For an arbitrary sequence of rectangles the polynomials (5) were introduced in [28] where they were called supernomials. The supernomials can be expressed in terms of the generalized Kostka polynomials and the Kostka numbers [28, Theorem 7.2]

S_{λR}(q) = ∑_{η} K_{ηλ}K_{ηR}(q),

where the sum is over all partitions η of |λ|. The inverse of this relation yields the bosonic representation of the generalized Kostka polynomials [28, Corollary 7.3]

K_{λR}(q) = ∑_{τ∈S_{n}} ϵ(τ)S_{(λ_{1}+τ_{1}−1,... ,λ_{n}+τ_{n}−n)R}(q).

5. Quasi-particle representation

This section follows [17, Section 2.2].

Recall that R = (R_{1}, …, R_{L}) such that R_{j} has μ_{j} rows and η_{j} columns for 1 ≤ j ≤ L. For a partition λ denote by λ^{t} its transpose and set R^{t} = (R_{1}^{t}, …, R_{L}^{t}). A (λ^{t}; R^{t})-configuration is a sequence of partitions ν = (ν^{(1)}, ν^{(2)}, …) with the size constraints

|ν^{(k)}| = ∑_{j>k} λ_{j}^{t} − ∑_{a=1}^{L} μ_{a} max(η_{a} − k, 0) (6)

for k ≥ 0 where by convention ν^{(0)} is the empty partition. For a partition ρ, define m_{n}(ρ) as the number of parts equal to n and Q_{n}(ρ) = ρ_{1}^{t} +ρ_{2}^{t} +⋯+ρ_{n}^{t}, the size of the first n columns of ρ. Let ξ^{(k)}(R) be the partition whose parts are the heights of the rectangles in R of width k. The vacancy numbers for the (λ^{t}; R^{t})-configuration ν are the numbers (indexed by k ≥ 1 and n ≥ 0) defined by

P_{n}^{(k)}(ν) = Q_{n}(ν^{(k−1)}) − 2Q_{n}(ν^{(k)}) + Q_{n}(ν^{(k+1)}) + Q_{n}(ξ^{(k)}(R)). (7)

In particular P_{0}^{(k)}(ν) = 0 for all k ≥ 1. The (λ^{t}; R^{t})-configuration ν is admissible if P_{n}^{(k)}(ν) ≥ 0 for all k, n ≥ 1, and the set of admissible (λ^{t}; R^{t})-configurations is denoted by C(λ^{t}; R^{t}). Set

cc(ν) = ∑_{k,n≥1} α_{n}^{(k)}(α_{n}^{(k)} − α_{n}^{(k+1)})

where α_{n}^{(k)} is the size of the n-th column in ν^{(k)}.

Example 2. Let λ = (4, 3, 1) and R = ((2), (2, 2), (1, 1)). Then ν = ((2), (2, 1), (1)) is a (λ^{t}; R^{t})-configuration. We have ξ^{(1)}(R) = (2) and ξ^{(2)}(R) = (2, 1). The configuration ν may be represented as

1  {0 \atop 0}  0

where the vacancy numbers are indicated to the left of each part.

Define the q-binomial as

\left[{m + n \atop m}\right] = \frac{(q)_{m+n}}{(q)_{m}(q)_{n}}

for m, n ∈ ℤ_{≥0} and zero otherwise where (q)_{m} = (1 − q)(1 − q^{2}) ⋯ (1 − q^{m}). Then the quasi-particle expression of the generalized Kostka polynomials can be stated as follows.

Theorem 2 (Theorem 2.10, [17]). For λ a partition and R a sequence of rectangles

K_{λR}(q) = ∑_{ν∈C(λ^{t};R^{t})} q^{cc(ν)} ∏_{k,n≥1} \left[{P_{n}^{(k)}(ν) + m_{n}(ν^{(k)}) \atop m_{n}(ν^{(k)})}\right]. (8)

Expression (8) can be reformulated as the generating function over rigged configurations. To this end we need to define certain labelings of the rows of the partitions in a configuration. For this purpose one should view a partition as a multiset of positive integers. A rigged partition is by definition a finite multiset of pairs (n, x) where n is a positive integer and x is a nonnegative integer. The pairs (n, x) are referred to as strings; n is referred to as the length or size of the string and x as the label or quantum number of the string. A rigged partition is said to be a rigging of the partition ρ if the multiset consisting of the sizes of the strings, is the partition ρ. So a rigging of ρ is a labeling of the parts of ρ by nonnegative integers, where one identifies labelings that differ only by permuting labels among equal-sized parts of ρ.

A rigging J of the (λ^{t}; R^{t})-configuration ν is a sequence of riggings of the partitions ν^{(k)} such that every label x of a part of ν^{(k)} of size n, satisfies the inequalities

0 ≤ x ≤ P_{n}^{(k)}(ν). (9)

The pair (ν, J) is called a rigged configuration. The set of riggings of admissible (λ^{t}; R^{t})-configurations is denoted by RC(λ^{t}; R^{t}). Let (ν, J)^{(k)} be the k-th rigged partition of (ν, J). A string (n, x) ∈ (ν, J)^{(k)} is said to be singular if x = P_{n}^{(k)}(ν), that is, its label takes on the maximum value.

Observe that the definition of the set RC(λ^{t}; R^{t}) is completely insensitive to the order of the rectangles in the sequence R. However the notation involving the sequence R is useful when discussing the bijection \overline{ϕ}_{R} : CLR(λ; R) → RC(λ^{t}; R^{t}) between LR tableaux and rigged configurations as defined in the next section, since the ordering on R is essential in the definition of CLR(λ; R).

The set of rigged configurations is endowed with a natural statistic cc [18, (3.2)] defined by

cc(ν, J) = cc(ν) + ∑_{k,n≥1} |J_{n}^{(k)}|

for (ν, J) ∈ RC(λ^{t}; R^{t}). Here |ρ| is the size of the partition ρ and J_{n}^{(k)} denotes the partition inside the rectangle of height m_{n}(ν^{(k)}) and width P_{n}^{(k)}(ν) given by the labels of the parts of ν^{(k)} of size n. Since the q-binomial \left[{P +m \atop m}\right] is the generating function of partitions with at most m parts each not exceeding P, Theorem 2 is equivalent to the following theorem.

Theorem 2′ (Theorem 2.12, [17]). For λ a partition and R a sequence of rectangles

K_{λR}(q) = ∑_{(ν,J)∈RC(λ^{t};R^{t})} q^{cc(ν,J)}. (10)

A detailed proof of this Theorem is given in [17]. In the following section we describe the bijection ϕ_{R} : CLR(λ; R) → RC(λ^{t}; R^{t}) of [17] and sketch the proof in section 7 that this bijection preserves the statistics, that is c_{R}(T) = cc(ϕ_{R}(T)).

6. The bijection between LR tableaux and rigged configurations

In this section we define the bijection \overline{ϕ}_{R} : CLR(λ; R) → RC(λ^{t}; R^{t}) between LR tableaux and rigged configurations. The bijection which preserves the statistics is

ϕ_{R} = comp ∘ \overline{ϕ}_{R}

where comp : RC(λ; R) → RC(λ; R) complements the rigging labels. That is, for (ν, J) ∈ RC(λ; R) a string (n, x) ∈ (ν, J)^{(k)} is mapped to (n, P_{n}^{(k)}(ν) − x).

The bijection \overline{ϕ}_{R} is defined recursively based on the following two operations on sequences of rectangles R = (R_{1}, …, R_{L}):

I. Let R^{∧} be the sequence of rectangles obtained from R by splitting off the last column of R_{L}; formally, R_{j}^{∧} = R_{j} for 1 ≤ j ≤ L − 1, R_{L}^{∧} = ((η_{L} − 1)^{μ_{L}}) and R_{L+1}^{∧} = (1^{μ_{L}}).

II. If the last rectangle of R is a single column, let \overline{R} be given by removing one cell from the column R_{L}; \overline{R}_{j} = R_{j} for 1 ≤ j ≤ L−1 and \overline{R}_{L} = (1^{μ_{L}−1}).

Remark 1. Given any sequence of rectangles, there is a unique sequence of transformations of the form R → R^{∧} or R → \overline{R} resulting in the empty sequence, where R → R^{∧} is only used when the last rectangle of R has more than one column.

For both transformations on sequences of rectangles, there are natural (injective) maps on the corresponding sets of LR tableaux and rigged configurations. The analogue of transformation I on LR tableaux is the inclusion

ı^{∧} : CLR(λ; R) → CLR(λ; R^{∧}).

When the last rectangle of R is a single column define

CLR(λ^{−}; \overline{R}) = ⋃_{ρ⋖λ}CLR(ρ; \overline{R})

where ρ ⋖ λ means that ρ ⊂ λ and λ/ρ is a single cell. Define the injective map

\begin{matrix}CLR(λ; R) & → CLR(λ^{−}; \overline{R}) \\ T & ↦ T^{−} \end{matrix}

where T^{−} is the LR tableau obtained by removing the maximum letter from T. This corresponds to transform II.

The analogue of transform I for rigged configurations is given by the map

ȷ^{∧} : RC(λ^{t}; R^{t}) → RC(λ^{t}; (R^{∧})^{t})

by declaring that ȷ^{∧}(ν, J) is obtained from (ν, J) ∈ RC(λ^{t}; R^{t}) by adding a singular string of length μ_{L} to each of the first η_{L} − 1 rigged partitions. Note that ȷ^{∧} is the identity map if R_{L} is a single column. It is shown in [17, Lemma 3.9] that ȷ^{∧} is a well-defined injection that preserves the vacancy numbers of the underlying configurations. An example of the map ȷ^{∧} is the first transformation of Table 1 in Appendix A.

Suppose the last rectangle of R is a single column. Define the set

RC(λ^{−t}; \overline{R}^{t}) = ⋃_{ρ⋖λ}RC(ρ^{t}; \overline{R}^{t}).

The key algorithm on rigged configurations is given by the map

\overline{δ} : RC(λ^{t}; R^{t}) → RC(λ^{−t}; \overline{R}^{t}),

defined as follows. Let (ν, J) ∈ RC(λ^{t}; R^{t}). Define \overline{ℓ}^{(0)} = μ_{L}. By induction select the singular string in (ν, J)^{(k)} whose length \overline{ℓ}^{(k)} is minimal such that \overline{ℓ}^{(k−1)} ≤ \overline{ℓ}^{(k)}. Let \overline{rk}(ν, J) denote the smallest k for which no such string exists, and set \overline{ℓ}^{(k)} = ∞ for k ≥ \overline{rk}(ν, J). Then \overline{δ}(ν, J) is obtained from (ν, J) by shortening each of the selected singular strings by one, changing their labels so that they remain singular, and leaving the other strings unchanged. It is shown in [17, Proposition 3.12] that the map \overline{δ} is a well-defined injection such that \overline{δ}(ν, J) ∈ RC(ρ^{t}; \overline{R}^{t}) where ρ is obtained from λ by removing the corner cell in the column of index \overline{rk}(ν, J).

Example 3. We continue Example 2 and consider the rigged configuration (ν, J)

1  1  0  0 0 0  0 0

where the vacancy numbers are indicated to the left and the riggings to the right of each part. By definition \overline{ℓ}^{(0)} = μ_{2} = 2. Now we need to pick a singular string in ν^{(1)} of length \overline{ℓ}^{(1)} minimal such that \overline{ℓ}^{(1)} ≥ 2. The part of length two in ν^{(1)} is singular; hence \overline{ℓ}^{(1)} = 2. Next select a singular string in ν^{(2)} of length \overline{ℓ}^{(2)} minimal such that \overline{ℓ}^{(2)} ≥ \overline{ℓ}^{(1)}. The part of length two in ν^{(2)} is singular; hence \overline{ℓ}^{(2)} = 2. There is no singular string of length greater or equal to two in ν^{(3)}. This implies \overline{rk}(ν, J) = 3. The selected strings are indicated by ∗ in the following diagram

1 ∗ 1  \begin{matrix}0 & ∗ & 0 \\ 0 & 0 \end{matrix}  0 0 .

Now \overline{δ}(ν, J) is obtained by shortening the selected strings keeping them singular so that \overline{δ}(ν, J) is represented by

1 1  0 0 0 0  0 0

which is indeed a (\overline{λ}^{t}; \overline{R}^{t})-configuration with \overline{λ} = (4, 2, 1) and \overline{R} = ((2), (2, 2), (1)).

The bijection \overline{ϕ}_{R} : CLR(λ; R) → RC(λ^{t}; R^{t}) is defined inductively based on Remark 1.

Definition-Proposition 3. There is a unique family of bijections \overline{ϕ}_{R} : CLR(λ; R) → RC(λ^{t}; R^{t}) indexed by R, such that:

1. If the last rectangle of R is a single column, then the following diagram commutes:

CLR(λ; R) ⟶^{−} CLR(λ^{−}; \overline{R})
\overline{ϕ}_{R}↓  ↓\overline{ϕ}\overline{R}
RC(λ^{t}; R^{t}) ⟶_{\overline{δ}} RC(λ^{−t}; \overline{R}^{t}).

2. The following diagram commutes:

CLR(λ; R) ⟶^{ı^{∧}} CLR(λ; R^{∧})
\overline{ϕ}_{R}↓  ↓\overline{ϕ}_{R^{∧}}
RC(λ^{t}; R^{t}) ⟶_{ȷ^{∧}} RC(λ^{t}; R^{∧}^{t}).

The proof of this Definition-Proposition is given in [17]. An example illustrating this bijection is given in Appendix A.

7. Sketch of the proof of theorem 2′

For the proof of Theorem 2′ it remains to show that the bijection ϕ_{R} preserves the statistics.

Lemma 4. Let T ∈ CLR(λ; R). Then c_{R}(T) = cc(ϕ_{R}(T)).

The proof of this lemma is given in full length in [17]. Here we only sketch the main ideas.

There are further important maps on the sets of LR tableaux and rigged configurations. The maps which play a central rôle in the proof are the transposition maps on LR tableaux and rigged configurations and a statistic preserving embedding on LR tableaux. Let us briefly review their definitions and some of their properties.

Denote by tr : ST(λ) → ST(λ^{t}) the ordinary transposition of standard tableaux. Analogous to the definition of CLR(λ; R) let us define the set

RLR(λ; R) = {T ∈ ST(λ)|P (T |_{B_{i}}) = Z′_{i}}

where Z′_{i} is the standard tableau of shape R_{i} = (η_{i}^{μ_{i}}) obtained by inserting the numbers

(r − 1)η_{i} + ∑_{j=1}^{i−1} |R_{i}| < k ≤ rη_{i} + ∑_{j=1}^{i−1} |R_{i}|

into the r-th row of R_{i}. There is a bijection γ_{R} : CLR(λ; R) → RLR(λ; R) given by relabeling as follows. Suppose the letter j occurs in Z_{i} in cell s. Then, to obtain γ_{R}(T) from T ∈ CLR(λ; R), replace the letter j in T by the letter occurring in cell s of Z′_{i} for all letters j. The transpose map tr restricts to a bijection tr : CLR(λ; R) → RLR(λ^{t}; R^{t}). Then the LR-transpose

tr_{LR} : CLR(λ; R) → CLR(λ^{t}; R^{t})

is defined as tr_{LR} := tr ∘ γ_{R}.

An analogous RC-transpose bijection exists for the set of rigged configurations denoted by tr_{RC} : RC(λ^{t}; R^{t}) → RC(λ; R), which was described in [18, Section 9]. Let (ν, J) ∈ RC(λ^{t}; R^{t}) and let ν have the associated matrix m with entries m_{ij} as in [18, (9.2)]

m_{ij} = α_{j}^{(i−1)} − α_{j}^{(i)}

for i, j ≥ 1, where α_{j}^{(i)} is the size of the j-th column of the partition ν^{(i)}, recalling that ν^{(0)} is defined to be the empty partition. The configuration ν^{t} in (ν^{t}, J^{t}) = tr_{RC}(ν, J) is defined by its associated matrix m^{t} given by

m_{ij}^{t} = −m_{ji} + χ((i, j) ∈ λ) − ∑_{a=1}^{L} χ((i, j) ∈ R_{a})

for all i, j ≥ 1. Here (i, j) ∈ λ means that the cell (i, j) is in the Ferrers diagram of the partition λ with i specifying the row and j the column, and χ(true) = 1 and χ(false) = 0. Recall that the rigging J is determined by partitions J_{n}^{(k)} inside the rectangle of height m_{n}(ν^{(k)}) and width P_{n}^{(k)}(ν) given by the labels of the parts of ν^{(k)} of size n. The partition J_{k}^{t(n)} corresponding to (ν^{t}, J^{t}) = tr_{RC}(ν, J) is defined as the transpose of the complementary partition to J_{n}^{(k)} in the rectangle of height m_{n}(ν^{(k)}) and width P_{n}^{(k)}(ν).

It is shown in [17, Theorem 7.1] that the diagram

CLR(λ; R) ⟶^{tr_{LR}} CLR(λ^{t}; R^{t})
ϕ_{R}↓  ↓^{ϕ_{R^{t}}}
RC(λ^{t}; R^{t}) ⟶_{tr_{RC}} RC(λ; R)

(11)

commutes.

Let rows(R) be obtained from the sequence of rectangles R by slicing all the rectangles of R into single rows. In refs. [30, 28] an embedding

θ_{R} : CLR(λ; R) → CLR(λ; rows(R))

was defined and it was shown that θ_{R} preserves the charge c_{R} of LR tableaux. This embedding stems from an analogous embedding on column-strict tableaux given by Lascoux and Schützenberger [19, 21]. For rigged configurations, it follows immediately from the definitions that there is an inclusion RC(λ^{t}; R^{t}) ⊆ RC(λ^{t}; rows(R)^{t}). It is shown in [17, Theorem 8.3] that the diagram

CLR(λ; R) ⟶^{θ_{R}} CLR(λ; rows(R))
ϕ_{R}↓  ↓^{ϕ_{rows(R)}}
RC(λ^{t}; R^{t}) ⟶_{inclusion} RC(λ^{t}; rows(R)^{t})

(12)

commutes.

Now the proof of Lemma 4 follows directly from (11) and (12). Since the embedding θ_{R} preserves the statistics one can reduce the proof of Lemma 4 to the case that all rectangles in R are single rows using (12). By (11) it may be assumed that R consists of single columns only. Finally applying (12) again, it is sufficient to establish Lemma 4 for R a sequence of single boxes only. In this case the lemma is verified explicitly [17].

8. Outlook

Let us take this opportunity to discuss some open problems regarding the generalized Kostka polynomials.

It was conjectured in [15, 18] that the generalized Kostka polynomials coincide with special cases of the spin generating functions over ribbon tableaux of Lascoux, Leclerc and Thibon [23]. A proof of this conjecture would add yet another representation of the generalized Kostka polynomials to the list. The spin generating functions over ribbon tableaux are defined for an arbitrary sequence of partitions R, not just a sequence of rectangles.

The algebraic structure underlying the generalized Kostka polynomials is determined by the affine Kac–Moody algebras of type A (compare with Section 3). The crystal theory can be formulated very generally for any affine Kac–Moody algebra. Recently Hatayama et al. [8] conjectured quasi-particle representations for all untwisted affine algebras. It would be interesting to find proofs of these conjectures.

In addition to the sets of unrestricted and classically restricted paths one can also define the set of level-restricted paths by imposing additional conditions using the raising operator e_{0}. Quasi-particle representations for the generating functions of level-restricted paths have been conjectured (see e.g. [8, 28]). However, proofs only exist in isolated cases (see e.g. [2, 6, 27]). A bosonic representation for level-restricted paths was recently proven in [26].

Finally, it would be interesting to find explicit expressions for the supernomial coefficients as introduced in Section 4. So far, explicit

(ν, J)^{(1)}  (ν, J)^{(2)}  R  \overline{rk}(ν, J)

0 0  0 0
↓ȷ^{∧}  ↓^{∧}
\begin{matrix}0 & ∗ & 0 \\ 0 & 0 \end{matrix} 0 0  2
\sqrt{δ}  ↓−
\begin{aligned}0 & ∗ & 0 \\ & & 0 \end{aligned}  0 ∗ 0  3
\sqrt{δ}  ↓−
0 0  ∅  1
\sqrt{δ}  ↓−
0 ∗ 0  ∅  2
\sqrt{δ}  ↓−
∅  ∅  1
\sqrt{δ}  ↓−
∅  ∅  ∅

Table 1. Example of the bijection

formulas for the supernomials are only known for type A when R is either a sequence of single rows or single columns.

Appendix A. An example of the bijection

Here we give an example illustrating the bijection of Definition-Proposition 1. Set λ = (3, 2) and R = ((1), (2, 2)). Then (ν, J) with ν = ((1), (1)) and J = ((0), (0)) is a (λ^{t}; R^{t})-configuration. In Table 1 the sequence of steps under ȷ^{∧} and \overline{δ} is given. The vacancy numbers are indicated to the left of the corresponding part of the partition and the riggings are given on the right. The selected singular strings in each step are indicated by ∗. The LR tableau which corresponds to (ν, J) under the bijection \overline{ϕ}_{R} can be obtained as follows. First insert |λ| = 5 into column \overline{rk}(ν, J) = 2 of the shape λ. This yields

5 .

Next insert 4,3,2,1 into columns 3,1,2,1, respectively, where the second set of numbers are those of the last column in Table 1. This yields the LR tableau

1 2 4 3 5 .

References

[1] R. J. Baxter, Exactly solved models in statistical mechanics, Academic Press, London (1982).

[2] A. Berkovich, Fermionic counting of RSOS-states and Virasoro character formulas for the unitary minimal series M(ν, ν + 1). Exact results, Nucl. Phys. B 431 (1994) 315–348.

[3] L. M. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc. 101 (1987) 771–775.

[4] L. M. Butler, Generalized flags in finite abelian p-groups, Discrete Appl. Math. 34 (1991), 67–81.

[5] S. Fomin and C. Greene, A Littlewood–Richardson miscellany, European J. Combin. 14 (1993) 191–212.

[6] O. Foda, M. Okado and S. O. Warnaar, A proof of polynomial identities of type { \atop sl(n)}_{1} ⊗ { \atop sl(n)}_{1}/{ \atop sl(n)}_{2}, J. Math. Phys. 37 (1996) 965–986.

[7] G. Hatayama, A. N. Kirillov, A. Kuniba, M. Okado, T. Takagi and Y. Yamada, Character formulae of ŝl_{n}-modules and inhomogeneous paths, Nucl. Phys. B536 [PM] (1998) 575–616.

[8] G. Hatayama, A. Kuniba, M. Okado, T. Takagi and Y. Yamada, Remarks on fermionic formula, preprint math.QA/9812022.

[9] V. Kac, Infinite dimensional Lie algebras, 3rd ed., Cambridge Univ. Press, 1990.

[10] M. Kashiwara, On crystal bases of the q-analogue of universal enveloping algebras, Duke Math. J. 63 (1991) 465–516.

[11] M. Kashiwara and T. Nakashima, Crystal graphs of representations of the qanalogue of classical Lie algebras, J. Alg. 165 (1994) 295–345.

[12] S.-J. Kang, M. Kashiwara, K. Misra, T. Miwa, T. Nakashima, and A. Nakayashiki, Perfect crystals of quantum affine Lie algebras, Duke Math. J. 68 (1992) 499–607.

[13] R. Kedem, T.R. Klassen, B.M. McCoy and E. Melzer, Fermionic quasi-particle representations for characters of (G^{(1)})_{1} × (G^{(1)})_{1}/(G^{(1)})_{2}, Phys. Lett. B 304 (1993) 263–270.

[14] R. Kedem, T.R. Klassen, B.M. McCoy and E. Melzer, Fermionic sum representations for conformal field theory characters, Phys. Lett. B 307 (1993) 68–76.

[15] A. N. Kirillov, New combinatorial formula for modified Hall–Littlewood polynomials, preprint math.QA/9803006.

[16] A. N. Kirillov and N. Y. Reshetikhin, The Bethe Ansatz and the combinatorics of Young tableaux, J. Soviet Math. 41 (1988) 925–955.

[17] A.N. Kirillov, A. Schilling and M. Shimozono, A bijection between Littlewood– Richardson tableaux and rigged configurations, preprint math.CO/9901037.

[18] A. N. Kirillov and M. Shimozono, A generalization of the Kostka–Foulkes polynomials, preprint math.QA/9803062.

[19] A. Lascoux, Cyclic permutations on words, tableaux and harmonic polynomials, Proc. Hyderabad Conference on Algebraic Groups 1989, Manoj Prakashan, Madras (1991) 323–347.

[20] A. Lascoux and M.P. Schützenberger, Sur une conjecture de H.O. Foulkes, CR Acad. Sci. Paris 286A (1978) 323–324.

[21] A. Lascoux, M. P. Schützenberger, Le monoïde plaxique, in Noncommutative structures in algebra and geometric combinatorics (Naples, 1978), 129–156, A. de Luca Ed., Quaderni della Ricerca Scientifica, 109, CNR, Roma, 1981.

[22] A. Lascoux, B. Leclerc and J.-Y. Thibon, Crystal graphs and q-analogues of weight multiplicities for the root system A_{n}, Lett. Math. Phys. 35 (1995) 359– 374.

[23] A. Lascoux, B. Leclerc and J.-Y. Thibon, Ribbon tableaux, Hall–Littlewood functions, quantum affine algebras, and unipotent varieties, J. Math. Phys. 38 (1997) 1041–1068.

[24] I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, Oxford, second edition, 1995.

[25] A. Nakayashiki and Y. Yamada, Kostka polynomials and energy functions in solvable lattice models, Selecta Math. (N.S.) 3 (1997) 547–599.

[26] A. Schilling and M. Shimozono, Bosonic formula for level-restricted paths, preprint math.QA/9812106.

[27] A. Schilling and S. O. Warnaar Supernomial coefficients, polynomial identities and q-series, The Ramanujan Journal 2 (1998) 459–494.

[28] A. Schilling and S. O. Warnaar, Inhomogeneous lattice paths, generalized Kostka polynomials and A_{n−1}-supernomials, to appear in Commun. Math. Phys., preprint math.QA/9802111.

[29] M. P. Schützenberger, Quelques remarques sur une construction de Schensted, Math. Scand. 12 (1963) 117–128.

[30] M. Shimozono, A cyclage poset structure for Littlewood-Richardson tableaux, preprint math.QA/9804037.

[31] M. Shimozono, Multi-atoms and monotonicity of generalized Kostka polynomials, preprint math.QA/9804038.

[32] M. Shimozono, Affine type A crystal structure on tensor products of rectangles, Demazure characters, and nilpotent varieties, preprint math.QA/9804039.

[33] M. Shimozono and J. Weyman, Graded characters of modules supported in the closure of a nilpotent conjugacy class, preprint math.QA/9804036.

Division of Mathematics, Graduate School of Science, Hokkaido University, Sapporo, 060-0810, Japan

E-mail address: kirillov@math.sci.hokudai.ac.jp

Instituut voor Theoretische Fysica, Universiteit van Amsterdam, Valckenierstraat 65, 1018 XE Amsterdam, The Netherlands

E-mail address: schillin@wins.uva.nl

Department of Mathematics, Virginia Tech, Blacksburg, VA 24061-0123, U.S.A.

E-mail address: mshimo@math.vt.edu