Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ah

THE HIVE MODEL AND THE FACTORISATION OF KOSTKA COEFFICIENTS

R.C. KING, C. TOLLU, AND F. TOUMAZET

Abstract. The hive model is used to explore the properties of both Kostka coefficients and stretched Kostka coefficient polynomials. It is shown that both of these may factorise, and that they can then be expressed as products of certain primitive coefficients and polynomials, respectively. It is further shown how to determine a sequence of linear factors (t + m) of the primitive polynomials, where t is the stretching parameter, as well as a bound on their degree in the form of a simple formula which is conjectured to be exact. Résumé. Nous utilisons le modèle des ruches pour étudier les propriétés des cœfficients de Kostka et des polynômes associés aux cœfficients de Kostka dilatés. Nous montrons que les uns et les autres peuvent se factoriser : ils s’écrivent comme des produits de cœfficients (respectivement polynômes) primitifs. En outre, nous montrons comment établir une suite de facteurs linéaires (t + m) des polynômes primitifs (t est le paramètre de dilatation), et proposons une formule simple donnant une borne supérieure de leur degré.

1. Introduction

There is no doubt that Kostka coefficients, K_{λμ} are interesting combinatorial objects. They are indexed by pairs of partitions λ and μ, and are non-zero if and only if these partitions have the same weight and λ precedes μ with respect to the dominance partial order on partitions [JK]. They count the number of semistandard Young tableaux of shape determined by λ and of weight determined by μ, see for example [L, M, S2]. They also count Gelfand-Tsetlin patterns, as described for example in [GT, S2]. These patterns are in bijective correspondence with semistandard Young tableaux and also with certain K-hives, introduced comparatively recently [KTT1] as a variation on the hives used to calculate Littlewood-Richardson coefficients [KT, KTW, B]. These K-hives are triangular arrays of non-negative integers with borders of length n labelled by the parts of the partitions 0, λ and μ, where 0 = (0, 0, …, 0). Counting such K-hives gives K_{λμ}.

Multiplying all the parts of the partitions λ and μ by a stretching parameter t, with t a positive integer, gives new partitions tλ and tμ. Since the weights of tλ and tμ are simply those of λ and μ multiplied by t, and this scaling preserves dominance partial ordering, it follows that K_{tλ,tμ} is non-zero if and only if K_{λμ} is non-zero.

By way of a non-trivial example, for n = 9, λ = (9, 5, 2, 2, 2, 2, 1) and μ = (5, 5, 5, 3, 1, 1, 1, 1, 1) it is found quite typically that

(1.1)  K_{tλ,tμ} = \frac{1}{24}(t + 1)^{2}(t + 2)(5t + 2)(t^{2} + 3t + 6)

These functions K_{tλ,tμ} are necessarily quasi-polynomials in t since they enumerate integer points of rational polytopes subject to a scaling by t [E, S1]. However, contrary to initial expectations [BK], these rational polytopes may, and indeed sometimes do, possess nonintegral vertices [KTT1, DeLM]. Despite this, it has been proved [KR, K1, BGR] that P_{λμ}(t) = K_{tλ,tμ} is always a polynomial in t.

A study of such K-polynomials has revealed a number of interesting features that are illustrated in the above example. In particular, it appears that the coefficients in the expansion of P_{λμ}(t) are all positive rational numbers. This remains a conjecture [KTT1].

Secondly, P_{λμ}(t) often contains a sequence of factors (t + m) for m = 1, 2, …, M, with M some non-negative integer. In the above example M = 2. More generally, both the value of M and the degree, d of the K-polynomial appear to be difficult to predict from a knowledge of n, λ and μ. Although the hive model does give an immediate bound, d ≤ (n − 1)(n − 2)/2, on the degree, it can be seen in the above n = 9 example that we have d = 6, so that the bound is far from being saturated.

It is also found that under certain circumstances there exists a factorisation of the form

(1.2)  P_{λμ}(t) = P_{σζ}(t) P_{τη}(t)

for some σ, τ, ζ and η such that λ = (σ, τ) and μ = (ζ, η), where the notation is intended to signify that the list of parts of λ are simply those of σ followed by those of τ, and similarly for μ. In the above example we have P_{9522221,555311111}(t) = P_{9522,5553}(t) P_{221,11111}(t) with

(1.3) P_{9522,5553}(t) = \frac{1}{2}(t + 1)(5t + 2) and P_{221,11111}(t) = \frac{1}{12}(t + 1)(t + 2)(t^{2} + 3t + 6).

In this presentation, our intention is to exploit the hive model to study the properties of stretched Kostka coefficient polynomials. We first derive combinatorially the precise conditions under which such K-polynomials factorise as products of certain primitive Kpolynomials. In the case of any primitive K-polynomial we then show how to determine the precise range of values, 1 ≤ m ≤ M, such that the K-polynomial contains a factor (t + m). This is done by giving an interpretation of P_{λμ}(t) for negative integer values of t. Finally, we obtain a formula for an explicit bound on the degree d of a primitive K-polynomial which we conjecture is always saturated.

Our analysis covers not only the Kostka coefficients K_{λμ} and the K-polynomials P_{λμ}(t) in which μ is a partition, but also K_{λβ} and P_{λβ}(t) in which β is, more generally, a weight. The combinatorial proof of the factorisation theorem in this case is presented in an Appendix.

2. Kostka coefficients

Let n be a fixed positive integer. For any α = (α_{1}, …, α_{n}) ∈ ℤ^{n} let |α| = α_{1} + ⋯ + α_{n} be the weight of α, let #α = n be the number of components of α and let the symmetric group S_{n} act naturally on the components of α. Let λ = (λ_{1}, …, λ_{n}) be a partition of length ℓ(λ) ≤ n and weight |λ| with λ_{1} ≥ ⋯ ≥ λ_{n} ≥ 0. Then |λ| = λ_{1} + ⋯ + λ_{n} with λ_{i} > 0 for i ≤ ℓ(λ) and λ_{i} = 0 for i > ℓ(λ). It is sometimes convenient to write λ in terms of its distinct parts, that is to set λ = (κ_{1}^{v_{1}}, …, κ_{m}^{v_{m}}) with κ_{1} > ⋯ > κ_{m} ≥ 0 and v_{j} > 0 for j = 1, …, m. Then |λ| = v_{1}κ_{1} + ⋯ + v_{m}κ_{m} with v_{1} + ⋯ + v_{m} = n, and ℓ(λ) = n if κ_{m} > 0 and ℓ(λ) = n − v_{m} if κ_{m} = 0.

Definition 2.1. Let x = (x_{1}, …, x_{n}). Then to each partition λ with ℓ(λ) ≤ n there corresponds a Schur function s_{λ}(x) defined by

(2.1)  s_{λ}(x) = \begin{matrix}|x_{i}^{n+λ_{j}−j}| & 1≤i,j≤n \\ |x_{i}^{n−j}| & 1≤i,j≤n \end{matrix} .

Since s_{λ}(x) is a ratio of two alternants, it is a symmetric polynomial in the components x_{1}, …, x_{n} of x. Indeed, the Schur functions {s_{λ}(x) | ℓ(λ) ≤ n} constitute a linear basis of the algebra of symmetric polynomials in the set of variables {x_{1}, …, x_{n}}.

Definition 2.2. The expansion of each Schur function in terms of monomials takes the form

(2.2)  s_{λ}(x) = ∑_{β} K_{λβ}x^{β},

where the summation is over all β = (β_{1}, …, β_{n}) and x^{β} = x_{1}^{β_{1}} ⋯ x_{n}^{β_{n}}. The coefficients K_{λβ} are known as Kostka coefficients.

The Schur functions defined by (2.1) also have a combinatorial interpretation from which it is possible to evaluate the Kostka coefficients.

Each partition λ with ℓ(λ) ≤ n specifies a corresponding Young diagram F^{λ} of shape λ. This consists of |λ| boxes arranged in ℓ(λ) left-adjusted rows of lengths λ_{1}, λ_{2}, …, λ_{ℓ(λ)}. Furthermore, there exists a set, T^{λ}(n), of semistandard tableaux T. Each such T is a numbering of the boxes of F^{λ} with entries from {1, 2, …, n} such that they are weakly increasing across rows and strictly increasing down columns. Any such T ∈ T^{λ}(n) is said to have weight wgt (T) = (#1′s ∈ T, #2′s ∈ T, …, #n′s ∈ T) where #k′s ∈ T is the number of entries k in T for k = 1, 2, …, n.

Typically, for n = 3 and λ = (3, 2, 0) we have

F^{32} =  T^{32}(3) ∋ T = 1 1 3 2 3

with wgt (T) = (2, 1, 2).

It can be shown from the definition (2.1) that

(2.3)  s_{λ}(x) = ∑_{T ∈T^{λ}(n)} x^{wgt (T)}.

It then follows that we have: Property 2.3. (see for example [L, p. 191], [M, p. 101].) K_{λβ} is the number of distinctly labelled semistandard tableaux T ∈ T^{λ}(n) of shape F^{λ} and weight wgt (T) = β, that is to say with β_{k} entries k for k = 1, 2, …, n.

The fact that s_{λ}(x) is symmetric implies that the coefficients K_{λβ} are insensitive to the permutations of the components of β, that is they possess:

Property 2.4. For all w ∈ S_{n} we have K_{λ,w(β)} = K_{λβ}, and there must exist a partition μ such that w(β) = μ for some w ∈ S_{n}, in which case K_{λβ} = K_{λμ}.

To specify those partitions λ and weights β for which K_{λβ} is non-zero it is convenient to introduce the notion of partial sums of the parts of partitions and weights, and the dominance partial order.

Definition 2.5. For any partition ν = (ν_{1}, ν_{2}, …, ν_{n}) and any weight α = (α_{1}, α_{2}, …, α_{n}), their partial sums are defined by

(2.4) ps(ν)_{i} = ν_{1} + ν_{2} + ⋯ + ν_{i} and ps(α)_{i} = α_{1} + α_{2} + ⋯ + α_{i} for all i = 1, 2, …, n.

More generally, for any subset I = {i_{1}, i_{2}, …, i_{r}} of N = {1, 2, …, n} of cardinality #I = r with 1 ≤ r ≤ n let

(2.5)  ps(ν)_{I} = ν_{i_{1}} + ν_{i_{2}} + ⋯ + ν_{i_{r}} and ps(α)_{I} = α_{i_{1}} + α_{i_{2}} + ⋯ + α_{i_{r}}.

Definition 2.6. Given partitions λ and μ of lengths ℓ(λ), ℓ(μ) ≤ n, then λ is said to dominate μ, and we write λ ⪰ μ, or more precisely λ ⪰_{n} μ, if

(2.6)  ps(λ)_{i} ≥ ps(μ)_{i} for all i = 1, 2, …, n and |λ| = |μ|.

Moreover, λ is said to strongly dominate μ, and we write λ ≻ μ, or more precisely λ ≻_{n} μ, if

(2.7)  ps(λ)_{i} > ps(μ)_{i} for all i = 1, 2, …, n − 1 and |λ| = |μ|.

We now have the following important condition for the non-vanishing of Kostka coefficients:

Theorem 2.7. Let λ and μ be partitions of lengths ℓ(λ), ℓ(μ) ≤ n, and let N = {1, 2, …, n}. Then

(2.8)  K_{λμ} > 0 ⟺ λ ⪰_{n} μ

More generally, let λ be a partition of length ℓ(λ) ≤ n and let β be a weight with #β = n. Then

(2.9) K_{λβ} > 0 ⟺ |λ| = |β| and ps(λ)_{i} ≥ ps(β)_{I} for all I ⊆ N with i = #I > 0.

The first set of conditions (2.8) is well-known (see for example [JK, p. 44]), and the second set of conditions (2.9) is a simple corollary following from the fact that if μ = w(β) for some w ∈ S_{n} then ps(μ)_{i} = ps(β)_{I} for some I ⊆ N with i = #I, and ps(μ)_{i} ≥ ps(β)_{J} for all J ⊆ N with i = #J.

3. The hive model

An n-hive is an array of numbers a_{ij} with 0 ≤ i, j, i + j ≤ n placed at the vertices of an equilateral triangular graph. Typically, for n = 4 their arrangement is as shown below:

a_{13} a_{22} a_{00}  a_{10}  a_{20}  a_{30}  a_{40} a_{31} a_{03} a_{02} a_{01}  a_{04} a_{12} a_{11}  a_{21}

Such an n-hive is said to be an integer hive if all of its entries are non-negative integers. Neighbouring entries define three distinct types of rhombus, each with its own constraint condition.

α  δ b a  α c δγ  β  b  d cδ γ γ  d R1:  R2:  R3:a a  β α β  b  d c

In each case, with the labelling as shown, the hive condition takes the form:

(3.1)  b + c ≥ a + d

In what follows we make use of edge labels more often than vertex labels. Each edge in the hive is labelled by means of the difference, ϵ = q − p, between the labels, p and q, on the two vertices connected by this edge, with q always to the right of p. In all the above cases, with this convention, we have α + δ = β + γ, and the hive conditions take the form:

(3.2)  α ≥ γ and β ≥ δ,

where, of course, either one of the conditions α ≥ γ or β ≥ δ is sufficient to imply the other.

Although, for completeness, we have included hive conditions for all three types of rhombus that appear in a general hive, it is only the type R1 and R2 hive conditions that apply to what we call K-hives. For such K-hives the type R3 hive conditions will, in general, be violated.

Definition 3.1. A K-hive is an integer hive satisfying the hive conditions (3.1), or equivalently (3.2) for all its constituent rhombi of type R1 and R2 (but not R3), with border labels determined by the zero partition or weight 0 = (0, 0, …, 0) with #0 = n, a partition λ with ℓ(λ) ≤ n and a weight β with #β = n, satisfying the constraint |λ| = |β|, in such a way that a_{0i} = 0 for i = 0, 1, …, n, a_{j,n−j} = ps(λ)_{j} = λ_{1} + λ_{2} + ⋯ + λ_{j} for j = 1, 2, …, n, a_{k,0} = ps(β)_{k} = β_{1} + β_{2} + ⋯ + β_{k} for k = 1, 2, …, n.

Schematically, we have

0 0 0 0  |β| = |λ| · · · · · ·  β^{1}  β^{1} + β^{2}  λ_{1} + λ_{2} λ_{1}

Alternatively, in terms of edge labels we have:

⋯ 0  0  0  β^{n} ⋯ β^{2} β^{1}  λ_{1} λ_{2}  ⋯ λ_{n}

With this definition, we then have:

Proposition 3.2. [KTT1] The Kostka coefficient K_{λβ} is the number of K-hives with border labels determined as above by λ and β.

Proof. Thanks to Property 2.3, it is only necessary to establish a bijection between the set of all semistandard tableaux T ∈ T^{λ}(n) of weight wgt (T) = β and the set of all Khives with boundary specified as in Definition 3.1. This bijection comes about through the existence of a sequence of maps exemplified as shown below.

T = 1 1 3 2 3 ⟺ G = 3  2  0 2  1 2

⟺ Z = 0  3  5  5 0  2  3 0  2 0  ⟺ H = 0 0  3 0  2  5 0  2  3  5

Each step from the semistandard tableau T to the K-hive H is a bijection. G is just the Gelfand-Tsetlin pattern corresponding to T whose top row is the partition specifying the shape of T, and whose successive rows thereafter are the partitions specifying the shape of the sub-diagrams obtained from T by deleting all boxes containing the entries n, then n − 1, and so on. The array Z is then formed by adding a diagonal of 0’s and forming the cumulative rows sums of the entries in G. Finally, H is just a re-orientation of Z, and corresponds to a K-hive, with all edges removed for the sake of clarity.

The upshot, quite generally, is that for all (i, j) with 0 ≤ i, j, i + j ≤ n the entries of the K-hive H are given by

(3.3)  a_{ij} = # of entries ≤ (i + j) in first i rows of T .

The fact that a_{0j} = 0 follows immediately. Since the entries of T are strictly increasing down each column, it follows that no entry i may lie below the ith row, and thus (3.3) implies that a_{i0} = ps (β)_{i} with β_{i} = wgt (T)_{i} = #i′s ∈ T, as required. Similarly, since all entries of T are no larger than n, it follows that (3.3) implies that a_{i,n−i} = ps (λ)_{i} where λ is the shape of T.

Again using (3.3), the hive decrements Δ = b + c − a − d = α − γ = β − δ arising from rhombi of type R1 and R2 with a in the position (i, j) are given by:

R1 : Δ = # of entries ≤ (i + j) in row i + 1 − # of entries ≤ (i + j + 1) in row i + 2 ;
R2 : Δ = # of entries equal to (i + j) in row i + 1 .

The fact that numbers of entries k in each row r of T are non-negative, ensures that Δ ≥ 0 in the R2 case, while the fact that they are weakly increasing across rows and strictly increasing down columns ensures that Δ ≥ 0 in the R1 case. Thus if T is semistandard, then the map to H yields a K-hive.

Conversely, the map from any K-hive H to a tableau T always yields a semistandard tableau, as can be seen by reversing the above arguments. The fact that Δ ≥ 0 in the R2 case ensures that each row of T contains non-negative numbers of each distinct entry. If these are arranged in weakly decreasing order across each row, then the fact that Δ ≥ 0 in the R1 case implies that all the entries in row i + 1 immediately above the k’s in row i + 2 are less than k, that is the entries are strictly increasing down columns.

Thus the maps described above are bijective, and the Proposition 3.2 follows. □

As an example of the application of this Proposition, if n = 3, λ = (3, 2, 0) and β = (2, 1, 2) then the corresponding K-hives take the form:

(3.4)  \begin{aligned}& & & 0 \\ & & 0 & & 3 \\ & 0 & & a & & 5 \\ 0 & & 2 & & 3 & & 5 \end{aligned}

where once again for the sake of clarity all the hive edges have been omitted. Since the only integer values of a satisfying the hive conditions (3.1) for all the constituent rhombi of type R1 and R2 are a = 3 and a = 2, it follows that K_{32,212} = 2. The corresponding semistandard tableaux are, of course, given by:

(3.5)  1 1 2 3 3  1 1 3 2 3

It might be pointed out that when expressed in terms of edge labels, the hive conditions (3.2) for all constituent rhombi of types R1 and R2 imply that in every K-hive the edge labels along any line parallel to the right-hand edge of the hive are weakly decreasing from top left to bottom right. This can be seen from the following 5-vertex sub-diagram.

β  α  γ

The edge conditions on the rhombi of type R1 and R2 in the above diagram give β ≥ γ and α ≥ β, respectively, so that α ≥ γ, as claimed. This is of course consistent with the edges of the right-hand boundary of each K-hive being specified by a partition λ.

4. Stretched coefficients

4.1. Polynomial conjectures. Now we are in a position to define and evaluate stretched Kostka coefficients. The partition obtained from λ = (λ_{1}, λ_{2}, …, λ_{p}) by multiplying all of its parts by the same positive integer, t, is denoted by tλ = (tλ_{1}, tλ_{2}, …, tλ_{p}). With this notation, we refer to K_{tλ,tβ} as stretched Kostka coefficients, where t is said to be the stretching parameter. It is not difficult to evaluate these stretched coefficients, particularly through the use of the hive model, for a range of positive integer values of t.

For example, for λ = (3, 2) and μ = (1, 1, 1, 1, 1) the corresponding stretched Kostka coefficients are given by

(4.1)  K_{tλ,tμ} = \frac{1}{2}(t + 1)(t^{2} + 2t + 2).

The generating function for these coefficients takes the form:

(4.2)  F_{λμ}(z) = ∑_{t=0}^{∞} K_{tλ,tμ} z^{t} = \frac{1 + z + z^{2}}{(1 − z)^{4}} .

On the basis of this and many other examples we were led to the following: Conjecture 4.1. [KTT1] For all partitions λ and μ such that K_{λμ} > 0 there exists a polynomial P_{λμ}(t) in t with positive rational coefficients such that P_{λμ}(0) = 1 and P_{λμ}(t) = K_{tλ,tμ} for all positive integers t. Conjecture 4.2. [KTT1] Given that the degree of the polynomial K_{tλ,tμ} is d, the generating function for K_{tλ,tμ} takes the form F_{λμ}(z) = G_{λμ}(z)/(1−z)^{d+1}, with G_{λμ}(z) a polynomial of degree ≤ d having non-negative integer coefficients.

Much of these conjectures has now been proved. In particular the fact that P_{λμ}(t) is polynomial appears to have been proved first by Kirillov and Reshetikhin [KR], with a more recent proof provided by Billey, Guillemin and Rassart [BGR]. In fact all that remains to be answered are the questions of the positivity of the coefficients in P_{λμ}(t) and G_{λμ}(z).

Before looking in more detail at the nature of the polynomials P_{λμ}(t) we note: Saturation Condition 4.3. [KTT1]

(4.3)  K_{tλ,tμ} > 0 ⟺ K_{λμ} > 0.

Proof. This can be seen immediately from Theorem 2.7 by noting that |tλ| = t |λ| and ps(tλ)_{r} = t ps(λ)_{r} for all partitions λ and all r. It follows that

(4.4) K_{λμ} > 0 ⟺ |λ| = |μ| and λ ⪰ μ ⟺ |tλ| = |tμ| and tλ ⪰ tμ ⟺ K_{tλ,tμ} > 0,

as required. □

Turning to the Conjecture 4.1 itself, the following key component has been established: Theorem 4.4. [K1, BGR] Let λ and μ be partitions of lengths ℓ(λ), ℓ(μ) ≤ n such that K_{λμ} > 0. Then P_{λμ}(t) = K_{tλ,tμ} is a polynomial of degree at most (n − 1)(n − 2)/2 in t.

Clearly, Property 2.4 then implies as a corollary of Theorem 4.4 that if K_{λβ} > 0 then P_{λβ}(t) = K_{tλ,tβ} is also a polynomial in t with the same upper bound on its degree.

5. Factorisation

Berenstein and Zelevinsky [BZ] introduced the notion of primitive Kostka coefficients and pointed out that every Kostka coefficient may be expressed as a product of primitive Kostka coefficients. First we deal with the case K_{λμ} where λ and μ are both partitions. Following Berenstein and Zelevinsky, we make the following definition.

Definition 5.1. Let λ and μ be partitions such that |λ| = |μ|, ℓ(λ), ℓ(μ) ≤ n and λ ⪰_{n} μ, so that K_{λμ} > 0. Then K_{λμ} is said to be primitive if λ ≻_{n} μ, that is ps (λ)_{r} > ps (μ)_{r} for all r = 1, 2, …, n − 1. Conversely, if K_{λμ} is not primitive then there exists at least one value of r, with 1 ≤ r < n, such that ps (λ)_{r} = ps(μ)_{r}.

If K_{λμ} > 0 but K_{λμ} is not primitive then K_{λμ} factorises in accordance with the following theorem.

Theorem 5.2. Let λ, μ be partitions such that |λ| = |μ| and ℓ(λ), ℓ(μ) ≤ n, with λ ⪰_{n} μ and ps(λ)_{r} = ps(μ)_{r} for some r such that 1 ≤ r < n. Let λ = (σ, τ) and μ = (ζ, η), with σ = (λ_{1}, λ_{2}, …, λ_{r}), τ = (λ_{r+1}, λ_{r+2}, …, λ_{n}), ζ = (μ_{1}, μ_{2}, …, μ_{r}) and η = (μ_{r+1}, μ_{r+2}, …, μ_{n}), then

(5.1)  K_{λμ} = K_{σζ} K_{τη}.

We first give a combinatorial proof based on the use of semistandard tableaux, and then a second combinatorial proof based on the use of K-hives.

Proof 1. It follows from the definition of semistandard tableaux that no entry k of T ∈ T^{λ}(n) may appear lower than the kth row of T. If ps (λ)_{r} = ps (μ)_{r} then all entries 1, 2, …, r completely fill the first r rows of T. This means that all the remaining entries r+1, r+2, …, n must fill the rows of T below the rth. Thus the top r rows of T constitute a semistandard tableau T_{r} ∈ T^{σ}(r) of shape F^{σ} with entries taken from the set {1, 2, …, r}, while the bottom (n−r) rows of T constitute a second semistandard tableau T ∈ T^{τ}(n−r) of shape F^{τ} with entries taken from the set {r + 1, r + 2, …, n}. Moreover, if any such semistandard tableaux T_{r} of shape F^{σ} and T_{n−r} of shape F^{τ} are joined together to create a tableau T of shape F^{λ} with λ = (σ, τ), then T is itself semistandard since all the entries in the bottom row of T_{r}, which are necessarily ≤ r, are strictly less than all the entries in the top row of T_{n−r}, which are necessarily ≥ (r + 1).

Setting, x = y z with y = (x_{1}, x_{2}, …, x_{r}) and z = (x_{r+1}, x_{r+2}, …, x_{n}) it follows from (2.3) that

s_{λ}(x) = ∑_{T ∈T^{λ}(n)} x^{wgt (T)} = ∑_{T_{r}∈T^{σ}(r)} ∑_{T_{n−r}∈T^{τ} (n−r)} y^{wgt (T_{r})} z^{wgt (T_{n−r})}.

It then follows from Property 2.3 that

K_{λμ} = #T ∈ T^{λ}(n) with wgt (T) = μ

= (#T_{r} ∈ T^{σ}(r) with wgt (T_{r}) = ζ) · (#T_{n−r} ∈ T^{τ}(n − r) with wgt (T_{n−r}) = η)

= K_{σζ} K_{τη} ,

as required. □

Proof 2. First it should be noted that the hypothesis λ ⪰_{n} μ implies that K_{λμ} > 0. Moreover, we have ps(σ)_{i} = ps(λ)_{i} ≥ ps(μ)_{i} = ps(ζ)_{i} for i = 1, 2, …, r − 1 and |σ| = ps(σ)_{r} = ps(λ)_{r} = ps(μ)_{r} = ps(ζ)_{r} = |ζ|. Thus σ ⪰_{r} ζ and hence K_{σζ} > 0. In addition we have ps(τ)_{i} = ps(λ)_{r+i}−ps(λ)_{r} = ps(λ)_{r+i}−|σ| ≥ ps(μ)_{r+i}−|ζ| = ps(μ)_{r+i}−ps(μ)_{r} = ps(η)_{i} for i = 1, 2, …, n − r, and |τ| = |λ| − |σ| = |μ| − |ζ| = |η|. Thus τ ⪰_{n−r} η and hence K_{τ,η} > 0.

Now consider the K-hive with boundary determined by λ = (σ, τ)

X  A 0 0 0 ζ  η  τ T  σ 0 0  ρ

The rules about edge sums are such that on the boundary of the triangular region T we have |ζ| = |0| + |ρ| = |ρ|. Since |ζ| = |σ| we have |ρ| = |σ|. The same rules applied to the parallelogram X then imply that the sum of the edge lengths on the boundary between X and A must be |0| + |σ| − |ρ| = 0. Since X can be viewed as a collection of rhombi of type R2, applying the hive condition β ≥ δ to each of these rhombi implies that the edge lengths on the lower right boundary of X must be non-negative. Since their sum is zero, they must all be zero, as indicated in the diagram. The α ≥ γ hive condition for R2 may then be applied to these same rhombi constituting X, yielding the constraints ρ_{i} ≤ σ_{i} for i = 1, 2, …, r. Since |ρ| = |σ|, we must have ρ_{i} = σ_{i} for i = 1, 2, …, r, that is ρ = σ.

Thus each K-hive H with boundary λ and μ consists of a parallelogram X in which all edge lengths are fixed, together with a K-hive T with boundary σ and ζ, and a second K-hive A with boundary τ and η. The hive conditions for H imply those appropriate to T and A.

In order to prove the required factorisation (5.1) it only remains to show that combining all possible hives T and A with a parallelogram X of the appropriate boundary gives a hive H in which all the hive conditions corresponding to rhombi crossing the boundaries of T with X, and A with X, are automatically satisfied. Since, for K-hives we only use the rhombi of type R1 and R2, it is clear that no such rhombus crosses the boundary between T and X, while only rhombi of type R1 cross the boundary between A and X. One such rhombus has been shown above.

We may look in more detail at such a rhombus by means of the following diagram which shows a strip one edge length wide on either side of the A − X boundary.

0  0  0  0 α β  δ γ  σ_{r} ρ_{r}  A X  τ_{1}

With the edge labels as shown, the R2 rhombus condition applied in the region A just below the A − X boundary gives δ ≤ τ_{1}, while the same rhombus condition applied in the region X just above the A − X boundary gives ρ_{r} ≤ β ≤ σ_{r}. Since ρ_{r} = σ_{r} and τ_{1} = λ_{r+1} ≤ λ_{r} = σ_{r}, we have δ ≤ τ_{1} ≤ σ_{r} = β. However, this is just what is required to satisfy the R1 condition (3.2).

This completes the proof of the K-hive factorisation theorem. □

Repeated use of this theorem allows any non-primitive Kostka coefficient K_{λμ} to be expressed as a unique product of primitive Kostka coefficients K_{σζ}. It is only necessary at each stage to factor out the term meeting the hypotheses of the above Theorem 5.2 with the smallest possible value of r.

Applying the above argument to stretched Kostka coefficients immediately gives the following:

Theorem 5.3. Let λ, μ be partitions such that |λ| = |μ| and ℓ(λ), ℓ(μ) ≤ n, with λ ⪰_{n} μ and ps(λ)_{r} = ps(μ)_{r} for some r for which 1 ≤ r < n. Let λ = (σ, τ) and μ = (ζ, η), with σ = (λ_{1}, λ_{2}, …, λ_{r}), τ = (λ_{r+1}, λ_{r+2}, …, λ_{n}), ζ = (μ_{1}, μ_{2}, …, μ_{r}) and η = (μ_{r+1}, μ_{r+2}, …, μ_{n}), then for all positive integers t we have

(5.2)  P_{λμ}(t) = P_{σζ}(t) P_{τ,η}(t).

An example of this type of factorisation has been provided in the introduction in (1.3). It is quite instructive from a combinatorial point of view, although not strictly necessary

by virtue of Property 2.4, to extend the above analysis to the case of Kostka coefficients K_{λβ} for which the weight β is not necessarily a partition. In this case K_{λβ} is said to be primitive if |λ| = |β| and ps(λ)_{r} ≥ ps(β)_{I} for any proper subset I of N = {1, 2, …, n} with r = #I.

In the non-primitive case, we have:

Theorem 5.4. Let λ be a partition with ℓ(λ) ≤ n, and let β = (β_{1}, β_{2}, …, β_{n}) be a weight such that |λ| = |β| and ps(λ)_{i} ≥ ps(β)_{I} for any I ⊂ N, with i = #I. Then K_{λβ} is not primitive if there exists a proper subset I = {i_{1}, i_{2}, …, i_{r}} of N such that ps(λ)_{r} = ps(β)_{I} with r = #I for some r for which 1 ≤ r < n. Let the complement of I in N be denoted by \overline{I} = \{j_{1}, j_{2}, …, j_{n−r}\}. In such a case let σ = (λ_{1}, λ_{2}, …, λ_{r}), τ = (λ_{r+1}, λ_{r+2}, …, λ_{n}), ζ = (β_{i_{1}}, β_{i_{2}}, …, β_{i_{r}}) and η = (β_{j_{1}}, β_{j_{2}}, …, β_{j_{n−r}}), so that λ = (σ, τ), with σ and τ partitions, and β = ζ ∪ η, with ζ and η weights, not necessarily partitions, satisfying the partial sum constraints |ζ| = |σ| and |η| = |τ|. Then

(5.3)  K_{λβ} = K_{σζ} K_{τη}.

A complete combinatorial proof of this theorem, based on the use of hives, is presented in an Appendix below.

Once again scaling everything by t is straightforward. If K_{λβ} is primitive then so is K_{tλ,tβ} since all the partial sum conditions are scaled by the same factor t. By the same token the factorisation occurs in the stretched non-primitive case just as it does in the unstretched non-primitive case – all boundary edges are simply scaled by t, and as we have shown, it is these boundary edges that completely determine the factorisation. Thus under the hypotheses of Theorem 5.4 we have

(5.4)  P_{λβ}(t) = P_{σζ}(t) P_{τη}(t).

This is illustrated for n = 6 and r = 3 by λ = (9, 6, 4, 4, 2, 0) and β = (2, 6, 3, 7, 6, 1), for which ps(λ)_{3} = 19 = ps(β)_{I} with I = {2, 4, 5}. In this case σ = (9, 6, 4), τ = (4, 2, 0), ζ = (6, 7, 6) and η = (2, 3, 1). Correspondingly we find

(5.5)  P_{96442,263761} = (t + 1)(2t + 1), P_{964,676} = (2t + 1), P_{42,231} = (t + 1),

thereby exemplifying the factorisation (5.4).

It is interesting to note that the above factorisation of Kostka coefficients can be extended to the case of q-dependent Kostka–Foulkes polynomials, K_{λμ}(q). These have a combinatorial definition in terms of the charge statistic on semistandard Young tableaux [M, p. 242]. By way of illustration, in the case of the above example we find

K_{t(96442),t(766321)}(q) = q^{3t} \frac{q^{t+1} − 1}{q − 1} \frac{q^{2t+1} − 1}{q − 1}
K_{t(964),t(766)}(q) = q^{2t} \frac{q^{2t+1} − 1}{q − 1}
K_{t(42),t(321)}(q) = q^{t} \frac{q^{t+1} − 1}{q − 1}.

6. The zeros of stretched Kostka polynomials

As has been noted the stretched Kostka polynomials P_{λμ}(t) contain factors (t + m) for some sequence of values m = 1, 2, …, M for some positive integer M. This is no accident. In this section we describe a method of determining M for stretched Kostka polynomials. It will be recalled that the Kostka coefficients are defined in terms of Schur functions by (2.2). It then follows from (2.1) that P_{λμ}(t) = K_{tλ,tμ} is the coefficient of x_{1}^{tμ_{1}}x_{2}^{tμ_{2}} ⋯ x_{n}^{tμ_{n}} in the expansion of

(6.1)  s_{tλ}(x) = \frac{|x_{i}^{tλ_{j}+n−j}|}{|x_{i}^{n−j}|}

This may be readily extended to the case t = −m with m a positive integer. Then P_{λμ}(−m) = K_{−mλ,−mμ} is the coefficient of x_{1}^{−mμ_{1}}x_{2}^{−mμ_{2}} ⋯ x_{n}^{−mμ_{n}} in the expansion of s_{−mλ}(x). However

(6.2)  s_{−mλ}(x) = \frac{|x_{i}^{−mλ_{j}+n−j}|}{|x_{i}^{n−j}|} = \frac{|x_{i}^{−mλ_{n−k+1}−n+k}|}{|x_{i}^{−n+k}|},

where first x_{i}^{n−1} has been extracted as a common factor from the ith row of each determinant for i = 1, 2, …, n and cancelled from numerator and denominator, and then j replaced by k = n − j + 1 with an appropriate reversal of order of the columns in both determinants. If we now set \overline{x}_{i} = x_{i}^{−1} for i = 1, 2, …, n and \overline{x} = (\overline{x}_{1}, \overline{x}_{2}, …, \overline{x}_{n}), this gives

(6.3)  s_{−mλ}(x_{1}, x_{2}, …, x_{n}) = \begin{matrix}| & \overline{x} & {mλ_{n−k+1}+n−k \atop i} & | \\ | & \overline{x} & {n−k \atop i} & | \end{matrix} = s_{mλ_{n},...,mλ_{2},mλ_{1}}(\overline{x}).

Since x_{1}^{−mμ_{1}}x_{2}^{−mμ_{2}} ⋯ x_{n}^{−mμ_{n}} = \overline{x}_{1}^{mμ_{1}} \overline{x}_{2}^{mμ_{2}} ⋯ \overline{x}_{n}^{mμ_{n}} it follows that P_{λμ}(−m) = K_{−mλ,−mμ} is the coefficient of \overline{x}_{1}^{mμ_{1}} \overline{x}_{2}^{mμ_{2}} ⋯ \overline{x}_{n}^{mμ_{n}} in the expansion of the right hand side. It then follows, replacing the dummy variables \overline{x}_{i} by x_{i} for i = 1, 2, …, n, that P_{λμ}(−m) = K_{−mλ,−mμ} is the coefficient of x_{1}^{mμ_{1}}x_{2}^{mμ_{2}} ⋯ x_{n}^{mμ_{n}} in the expansion of s_{mλ̃}(x), where λ̃ = (λ_{n}, …, λ_{2}, λ_{1}) is the weight obtained by reversing the order of the parts of λ, including any trailing zeros. Then to exploit the above it is only necessary to standardise

(6.4)  s_{mλ̃}(x) = s_{mλ_{n},...,mλ_{2},mλ_{1}}(x_{1}, x_{2}, …, x_{n}) = \frac{|x_{i}^{mλ_{n−k+1}+n−k}|}{|x_{i}^{n−k}|}.

This is carried out in the usual way [L] by reordering the columns of the numerator determinant. However there are two quite different possible outcomes:

(6.5)  s_{mλ̃}(x) = \begin{cases}0 & case (i); \\ η_{ρ} s_{ρ}(x) with η_{ρ} = ±1 & case (ii). \end{cases}

For example, in the case n = 5 and λ = (4, 2, 1, 0, 0) we have λ̃ = (0, 0, 1, 2, 4). For m = 1 this gives s_{mλ̃}(x) = s_{0,0,1,2,4}(x) = 0. Similarly for m = 2 we have s_{mλ̃}(x) = s_{0,0,2,4,8}(x) = 0. However, for m = 3 we obtain s_{mλ̃}(x) = s_{0,0,3,6,12}(x) = −s_{8,4,3,3,3}(x), while for m = 5 we have s_{mλ̃}(x) = s_{0,0,4,8,16}(x) = −s_{12,6,4,3,3}(x).

More generally, the case (i) result 0 arises if and only if

(6.6)  m λ_{n−k+1} + n − k = m λ_{n−l+1} + n − l

for some k and l such that 1 ≤ l < k ≤ n. In all other cases the formula given in case (ii) applies for some partition ρ of length at most n and weight m|λ|, and η_{ρ} = ±1 is a sign factor recording the number of transpositions of columns of the numerator determinant of (6.4) required to standardise the Schur function.

It follows that we can expect there to be a possibility of two types of zero of P_{λμ}(t) for t = −m: type (i) associated with case (i) of (6.5), and type (ii) associated under certain conditions on ρ and m μ with case (ii). Indeed adopting the notation of (6.5) we have the following:

Proposition 6.1. Let λ and μ be such that K_{λμ} is primitive. Then P_{λμ}(t) = K_{tλ,tμ} contains a factor (t + m) if and only if either case (i) applies and

(6.7)  m = (j − i)/(λ_{i} − λ_{j})

for some i and j such that 1 ≤ i < j ≤ n, or case (ii) applies and

(6.8)  ps(ρ)_{k} < m ps(μ)_{k}

for some k such that 1 ≤ k < n.

Proof. We have already noted that P_{λμ}(−m) = K_{−mλ,−mμ} is the coefficient of x_{1}^{mμ_{1}}x_{2}^{mμ_{2}} ⋯ x_{n}^{mμ_{n}} in s_{mλ̃}(x) = s_{mλ_{n},...,mλ_{2},mλ_{1}}(x_{1}, x_{2}, …, x_{n}). Thus if case (i) of (6.5) applies then P_{λμ}(−m) = 0, while if case (ii) applies then P_{λμ}(−m) = η_{ρ}K_{ρ,mμ}. The conditions for case (i) to apply are given in (6.6). However, setting i = n − k + 1 and j = n − l + 1 leads immediately to the required case (i) conditions (6.7) for P_{λμ}(−m) = 0. Turning to case (ii) of (6.5) P_{λμ}(−m) = η_{ρ} K_{ρ,mμ} will be zero by virtue of Theorem 2.7 if any one of the partial sum conditions ps(ρ)_{k} ≥ m ps(μ)_{k} for all k = 1, 2, …, n is violated. Since |ρ| = m |μ| this leaves precisely the required case (ii) conditions (6.8) for P_{λμ}(−m) = 0. □

We may extend our earlier example with n = 5 and λ = (4, 2, 1, 0, 0) by taking μ = (3, 1, 1, 1, 1) for illustrative purposes. We have already seen that there are type (i) zeros, independent of μ that arise for m = 1 and m = 2. These arise from (6.7) for the pairs (i, j) = (3, 4) and (3, 5), respectively, leading to (j − i)/(λ_{i} − λ_{j}) = (4 − 3)/(1 − 0) = 1 and (5 − 3)/(1 − 0) = 2. For m = 3 we have a type (ii) zero since P_{λμ}(−3) = η_{ρ}K_{ρ,mμ} = −K_{84333,93333} = 0 by virtue of the fact that ps(ρ)_{1} = 8 < 9 = ps(mμ)_{1}. On the other hand for m = 4 we have P_{λμ}(−4) = η_{ρ}K_{ρ,mμ} = −K_{12 6433,12 4444} = −3 which is non-zero, and the same will be true for all m ≥ 4.

In view of our earlier remarks about the sequence of zeros of P_{λμ}(t) for t = −m with m = 1, 2, …, M, it comes as no surprise that we are able to elaborate on the above and establish that the zeros are indeed consecutive and that for any primitive K_{λμ} we can always find a finite M > 0 such that P_{λμ}(−m) = 0 for all m = 1, 2, …, M, but thereafter P_{λμ}(−m) ≠ 0 for all m > M.

All this is borne out in our example with n = 5, λ = (4, 2, 1, 0, 0) and μ = (3, 1, 1, 1, 1) for which

(6.9)  P_{λμ}(t) = K_{tλ,tμ} = \frac{1}{60}(t + 1)(t + 2)(t + 3)(3t^{2} + 7t + 10),

for which M = 3 and we have consecutive zeros at t = −m with m = 1, 2, 3. Of these, as we have seen, the first two are type (i) and the third is type (ii). The first non-zero case occurs with t = −4 and we obtain from the explicit formula (6.9) the result P_{λμ}(−4) = −3 that we had found earlier. In fact for t = −m it is clear that (6.9) gives P_{λμ}(−m) < 0 for all m > M = 3.

7. The degrees of stretched Kostka polynomials

As we have seen the calculation of stretched Kostka polynomials may be reduced to that of calculating these polynomials in primitive cases only. Even so the task may be combinatorially formidable. In any given case a knowledge of the degree of the polynomial would be extremely advantageous. Here we establish an upper bound on this degree by means of the following rather innocuous looking result. Let the edge labelling of a particular 5-vertex subset of a K-hive be as shown below in the left hand diagram, with two identical labels α.

β  α  α

This diagram contains rhombi of type R1 and R2. The hive conditions (3.2) for the former imply α ≤ β, while those for the latter give β ≤ α. It follows that β = α. This result is displayed more simply by deleting all the edges except those sharing the same label α, and suppressing the label itself. This gives the right hand diagram where the equality of a pair of edge labels in a linear sequence forces an identical edge label in a neighbouring line.

Applying these notions to the case of K-hives with boundaries of length n and with border labels determined by 0, λ and μ, it follows from the above that any equalities of successive parts of λ propagate as equalities of edge labels within each possible K-hive. To be more precise let all the λ-boundary edges be labelled by the parts of λ. If any sequence of parts of λ share the same value, say α, then we can identify an equilateral sub-hive having the sequence of equally labelled edges as one boundary, with its other boundaries parallel to the 0 and μ-boundaries of the original hive. Within this sub-hive all the vertices along lines parallel to the λ-boundary are to be connected by edges indicating that in any K-hive the differences in values between neighbouring entries along these lines are all α.

This process is to be repeated for all sequences of equal edge labels along the λ-boundary. Finally, all neighbouring vertices on all three boundaries are to be connected by edges. In this way we arrive at a graph G_{n;λ} that depends only upon n and λ.

For example, for n = 6 and λ = (4, 2, 2, 0, 0, 0) the graph G_{n;λ} takes the form:

4  2  2  0  0  0

With this notation we have:

Proposition 7.1. Let λ and μ be partitions of lengths ℓ(λ), ℓ(μ) ≤ n such that K_{λμ} > 0. Let deg(P_{λμ}(t)) be the degree of the corresponding stretched K-polynomial P_{λμ}(t) = K_{tλ,tμ}. Let d(G_{n;λ}) be the number of connected components of the graph G_{n;λ} that are not connected to the boundary. Then

(7.1)  deg(P_{λμ}(t)) ≤ d(G_{n;λ}).

Moreover, if λ = (w_{1}^{v_{1}}, w_{2}^{v_{2}}, …, w_{r}^{v_{r}}), with w_{1} > w_{2} > ⋯ > w_{r} ≥ 0, v_{s} ≥ 1 for all s = 1, 2 …, r, with r ≥ 2, and v_{1} + v_{2} + ⋯ + v_{r} = n, then

(7.2)  d(G_{n;λ}) = \frac{1}{2}(n − 1)(n − 2) − ∑_{s=1}^{r} \frac{1}{2}v_{s}(v_{s} − 1).

Proof. Any labelling of the vertices of the hive must be such that the difference α in values along each interior edge of the graph G_{n;λ} is, by construction of those edges, equal to a corresponding edge value on the parallel λ-boundary, that is α = λ_{i} = w_{s} for some i and a corresponding s. For each connected component this fixes the values of all vertex labels in terms of that of any one vertex of that component. In the case of a component connected to the boundary, the value at the boundary vertex fixes all the others in that component.

The maximum number of degrees of freedom in assigning entries to the corresponding set of K-hives with given boundary is then d(G_{n;λ}).

The application of the stretching parameter t leaves G_{n;λ} unaltered, that is G_{n;tλ} = G_{n;λ}, so that the number of degrees of freedom in assigning entries to the stretched K-hives is still d(G_{n;λ}). For each connected component of G_{n;λ} that is not connected to the boundary we may select any one convenient vertex. The values of its label are not fixed by the hive constraints. They must satisfy a set of linear inequalities that are all scaled by t as both the boundary vertex and edge labels are scaled by the stretching parameter t. It follows that the range of allowed values of the label must be either independent of t or linear in t, thereby giving rise to a corresponding contribution to P_{λμ}(t) that is at most linear in t. The number of degrees of freedom, d(G_{n;λ}), that we have identified therefore gives an upper bound on the degree of the corresponding stretched K-polynomial in t.

The number of internal vertices of G_{n;λ} is (n − 1)(n − 2)/2. For given n and arbitrary λ this provides a preliminary upper bound on the degree of P_{λμ}(t). However, for λ = (w_{1}^{v_{1}}, w_{2}^{v_{2}}, …, w_{r}^{v_{r}}), each s such that v_{s} > 1 specifies a sequence of components of λ having the same value, namely w_{s}. There is a corresponding set of v_{s}(v_{s} − 1)/2 interior edges within G_{n;λ}. Whether or not these interior edges reach the boundary, as they do in the two cases s = 1 and s = r, their introduction reduces the number of connected components not linked to the boundary by v_{s}(v_{s} − 1)/2. The result (7.2) then follows by noting that for different s the sets of vertices linked by the interior edges are disjoint, so that their contributions to the reduction of d(G_{n;λ}) are independent. □

In the case of our example with n = 6 and λ = (4, 2, 2, 0, 0, 0) = (4, 2^{2}, 0^{3}) we can see from the graph of G_{n;λ} that d(G_{n;λ}) = 6, in agreement with the formula (7.2) that gives d(G_{n;λ}) = 5 · 4/2 − 2 · 1/2 − 3 · 2/2 = 6. Hence for all μ the degree of the corresponding stretched Kostka coefficient polynomial P_{λμ}(t) must satisfy

(7.3)  deg(P_{λμ}(t)) ≤ 6.

By way of example, for μ = (3, 1, 1, 1, 1, 1) we find

(7.4) P_{λμ}(t) = \frac{1}{72}(t + 1)(t + 2)(t + 3)(t + 4)(t^{2} + 2t + 3) so that F_{λμ}(z) = \frac{1 + 3z + 6z^{2}}{(1 − z)^{7}} ,

while for μ = (2, 2, 1, 1, 1, 1) we have (7.5)

P_{λμ}(t) = \frac{1}{60}(t+1)(t+2)(t+3)(3t+5)(t^{2} +2t+2) so that F_{λμ}(z) = \frac{1 + 9z + 19z^{2} + 7z^{3}}{(1 − z)^{7}} .

On the other hand if μ = (3, 2, 1, 1, 1, 0) we find

(7.6)  P_{λμ}(t) = \frac{1}{24}(t + 1)(t + 2)(t + 3)(t + 4) so that F_{λμ}(z) = \frac{1}{(1 − z)^{5}} .

The third case in which deg(P_{λμ}(t)) = 4 < 6 is one for which K_{λμ} is not primitive. In both the other cases K_{λμ} is primitive, and we have deg(P_{λμ}(t)) = 6 so that the bound (7.1) is saturated.

On the basis of very many calculations of this type we are led to the following:

Conjecture 7.2. Let λ and μ be partitions of lengths ℓ(λ), ℓ(μ) ≤ n such that K_{λμ} > 0. Let P_{λμ}(t) = K_{tλ,tμ}, then deg(P_{λμ}(t)) = d(G_{n;λ}) for all μ such that K_{λμ} is primitive.

We might point out that a formula for the dimension d = dim G(λ, μ) of the convex Gelfand-Tsetlin polytope G(λ, μ), which is nothing other than our deg(P_{λμ}(t)), has been given in Section 7 Exercise 3.a. of [K1], and also quoted in Section 5.4 of [K2]. With the summation upper limit extended appropriately, this formula coincides with our d(G_{n;λ}) if we choose n = s = ℓ(μ). Thus if K_{λμ} is primitive, in which case it is necessarily true that n = ℓ(μ), the above conjecture is equivalent to the claim made regarding the formula given in [K1]. However, in non-primitive cases such as that exemplified in (1.1), the cited formula in [K1] does not yield the correct value, 6, of deg(P_{λμ}(t)). Instead, the formula yields the value d(G_{9;λ}) = 21. To obtain the correct result one must first factorise the non-primitive K-polynomial and then apply the above conjecture to each of the primitive factors to give deg(P_{λμ}(t)) = 2 + 4 = 6, in accordance with (1.3).

Finally, we should note that the work of Kirillov [K2] includes a wealth of conjectures concerning not just Kostka coefficients and polynomials, but also what he calls parabolic Kostka polynomials and Littlewood-Richardson polynomials. The latter are also discussed in [KTT2].

Note added in proof. The validity of the above Conjecture 7.2, including its restriction to the primitive case, has recently been proved by McAllister [McA].

References

[BK] A.D. Berenstein and A.N. Kirillov, Groups generated by involutions, Gelfand-Tsetlin patterns and combinatorics of Young tableaux, St Petersburg Math. J. 7 (1966), 77–127.

[BZ] A.D. Berenstein and A.V. Zelevinsky, When is the multiplicity of a weight equal to 1?, Funct. Anal. Appl. 24 (1990), 259–269.

[BGR] S. Billey, V. Guillemin and E. Rassart, A vector partition function for the multiplicities of sl_{k}(ℂ), J. Algebra 278 (2004), 251–293.

[B] A.S. Buch, The saturation conjecture (after A. Knutson and T. Tao). With an appendix by W. Fulton, Enseign. Math. 46 (2000), 43–60.

[DeLM] J.A. De Loera and T.B. McAllister, Vertices of Gelfand-Tsetlin polytopes, Discr. Comput. Geom. 32 (2004), 459–470.

[E] E. Ehrhart, Polynômes arithmétiques et méthode des polyèdres en combinatoire, Internat. Ser. Numer. Math., Vol. 35, Birkhäuser–Verlag, Basel, 1977.

[GT] I.M. Gel’fand and M.L. Tsetlin, Finite-dimensional representations of the group of unimodular matrices, Dokl. Akad. Nauk. SSSR 77 (1950), 825–828.

[JK] G. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of mathematics and its applications 16, Addison–Wesley, Reading, 1981.

[KTT1] R.C. King, C. Tollu and F. Toumazet, Stretched Littlewood-Richardson and Kostka coefficients, CRM Proceedings and Lecture Notes, Vol. 34, Amer. Math. Soc, 2004, pp. 99–112.

[KTT2] R.C. King, C. Tollu and F. Toumazet, The hive model and the polynomial nature of stretched Littlewood-Richardson coefficients, Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ad, 19 pp.

[K1] A.N. Kirillov, Ubiquity of Kostka polynomials, in Physics and Combinatorics 1999, World Scientific, Singapore, 2001, pp. 85–200.

[K2] A.N. Kirillov, An invitation to the generalized saturation conjecture, RIMS Publ. Kyoto Univ. 40 (2004), 1147–1239.

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

[KT] A. Knutson and T. Tao, The honeycomb model of GL_{n}(ℂ) tensor products. I: Proof of the saturation conjecture, J. Amer. Math. Soc. 12 (1999), 1055–1090.

[KTW] A. Knutson, T. Tao and C. Woodward, The honeycomb model of GL_{n}(ℂ) tensor products. II: Puzzles determine facets of the Littlewood-Richardson cone, J. Amer. Math. Soc. 17 (2004), 19– 48.

[L] D.E. Littlewood, The theory of group characters and matrix representations of groups, 2nd ed., Clarendon Press, Oxford, 1950.

[M] I.G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford University Press, Oxford, 1995.

[McA] T.B. McAllister, Degrees of stretched Kostka coefficients, arχiv:math.RT/0603173, (2006).

[S1] R.P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, Cambridge, 1997.

[S2] R.P. Stanley, Enumerative Combinatorics, Vol. II, Cambridge University Press, Cambridge, 1999.

Appendix

Here we present a proof of the following factorisation theorem for K_{λβ} in the case where β is any weight, not necessarily a partition, such that K_{λβ} is not primitive. The approach is instructive since it is indicative of the way in which our factorisation result may be extended to the case of Littlewood-Richardson coefficients. An account of this is presented elsewhere [KTT2].

Theorem 5.4. Let λ be a partition with ℓ(λ) ≤ n, and let β = (β_{1}, β_{2}, …, β_{n}) be a weight such that |λ| = |β| and ps(λ)_{i} ≥ ps(β)_{I} for any I ⊂ N = {1, 2, …, n}, with i = #I. Then K_{λβ} is not primitive if there exists a proper subset I = {i_{1}, i_{2}, …, i_{r}} of N such that ps(λ)_{r} = ps(β)_{I} with r = #I for some r for which 1 ≤ r < n. Let the complement of I in N be denoted by \overline{I} = \{j_{1}, j_{2}, …, j_{n−r}\}. In such a case let σ = (λ_{1}, λ_{2}, …, λ_{r}), τ = (λ_{r+1}, λ_{r+2}, …, λ_{n}), ζ = (β_{i_{1}}, β_{i_{2}}, …, β_{i_{r}}) and η = (β_{j_{1}}, β_{j_{2}}, …, β_{j_{n−r}}), so that λ = (σ, τ), with σ and τ partitions, and β = ζ ∪ η, with ζ and η weights, not necessarily partitions, satisfying the partial sum constraints |ζ| = |σ| and |η| = |τ|. Then

(5.3)  K_{λβ} = K_{σζ} K_{τη}.

Proof Consider first the special case for which β = (θ, ζ, ϕ) and η = (θ, ϕ) with #ζ = r and #θ + #ϕ = n − r. The hives H whose enumeration gives K_{λβ} are illustrated schematically in the following diagram.

T A  Y  B X 0  0  0 θ  ζ  σ  τ 0 0 0 ρ  ϕ κ  ω ξ  χ  ψ

As in our proof of (5.1), covering the parallelograms Y and X with rhombi of type R1 and R2, respectively, and applying the γ ≤ α hive conditions gives |ζ| ≤ |ξ| + |χ| + |ψ| ≤ |0| + |ρ| ≤ |σ|. Since |ζ| = |σ| the intervening inequalities must be equalities. Then as before the constraint |ρ| = |σ| coupled with the R2 hive conditions ρ_{i} ≤ σ_{i} for i = 1, 2, …, r implies that ρ = σ. In exactly the same way the constraint |ζ| = |ξ| + |χ| + |ψ| coupled to the R1 hive conditions of the form ζ_{j} ≤ ξ_{j}, χ_{k}, ψ_{l}, as appropriate, gives ζ = (ξ, χ, ψ). Since |ρ| = |σ| and the edge labels along the upper left boundary of X are all 0, it follows, as indicated, that the same is true of the lower right boundary edges of X. We note also that |κ| + |ζ| = |ξ| + |χ| + |ψ| + |ω|, so that |κ| = |ω|. Finally, it follows by using the β ≥ δ hive condition for R1 that κ_{j} ≥ ω_{j} for all j. Hence κ = ω so that the right-hand boundary of A matches up exactly with the left-hand boundary of B. All this shows that each hive H contributing to K_{λβ} consists of a subhive T contributing to K_{σζ} and a subhive formed from the union of A and B contributing to K_{τη} with η = (θ, ϕ). The remaining portions X and Y are completely constrained by the equality of edge labels across each of these parallelograms in each direction.

In order to prove the validity of (5.3) it only remains to show that all cross boundary hive conditions are automatically satisfied once the hives T and A ∪ B are specified. The only cases of concern are R1 hives crossing the X − B boundary and the R2 hives crossing the T −Y boundary. The former are covered by the argument used in the proof of Theorem 5.2. The latter are dealt with in a precisely analogous way, through the consideration of a subdiagram following the T − Y and X − B boundary of width equal to two edge lengths, as shown below.

τ_{1} ρ_{r} κ_{1} ξ  χ  ψ α δγ  β  σ_{r} ω_{1}  B X T Y

First of all in the portions of the strips overlapping the regions X and Y, we have ρ_{r} = σ_{r} and κ_{1} ≥ γ ≥ ω_{1}. However κ_{1} = ω_{1}. In B and T the R2 and R1 hive conditions imply ω_{1} ≤ τ_{1} and ρ_{r} ≤ α. Combining these we have γ = ω_{1} ≤ τ_{1} = λ_{r+1} ≤ λ_{r} = σ_{r} = ρ_{r} ≤ α. Hence the R2 hive condition γ ≤ α is automatically satisfied everywhere on the T − Y boundary.

This completes the proof of (5.3) for one class of non-primitive cases. Generalising to the case of any weight β such that K_{λβ} is not primitive, is now rather straightforward. The most general type of case is illustrated below:

A_{2}  A_{3} X_{1} Y_{1}  Y_{2}  Y_{3} α^{1}  γ^{1}  α^{2}  γ^{2} 0  0  γ^{3} T_{2}  X_{2}  T_{3} A_{1}  0 0 0 0  σ  τ T_{1}  γ_{2}  γ_{3} γ_{1}  α_{3}

Here, the pattern is clear. We have λ = (σ, τ) and β = ζ ∪ η with ζ = ∪_{i}γ_{i} and η = ∪_{j}α_{j}, where in general α_{i} and γ_{j} are themselves weights with many parts, as are ζ and η. The regions X_{i} and Y_{i} are all parallelograms composed of rhombi if type R2 and R1, respectively. The total number of edges specified by γ_{i} for all i is r, and the total number of edges specified by α_{i} for all i is n − r, thereby matching the number of parts of the partitions σ and τ, including any trailing zeros. All edges along the X_{i} − A_{i+1} boundaries are 0, and all along the Y_{i} − T_{i} boundaries are specified by the parts of γ_{i}. The right and left-hand edges of A_{i} and A_{i+1} match. The same is true of T_{i} and T_{i+1}. Juxtaposing these edges creates subhives T = ∪_{i}T_{i} and A = ∪_{i}A_{i} appropriate to K_{σζ} and K_{τη}. All the hive conditions are satisfied.

Conversely, reconstituting H by inserting fixed edge parallelograms X_{i} and Y_{i} between the various T_{i} and A_{i} corresponding to K-hives T and A, always gives rise to a K-hive, as required. This is because the necessary hive conditions for all hives of type R1 and R2 crossing X_{i} − A_{i+1} and T_{i} − Y_{i} boundaries, respectively, are once again automatically satisfied. The argument is precisely the same as that given previously.

This completes the proof of Theorem 5.4. □

School of Mathematics, University of Southampton, Southampton SO17 1BJ, U.K.

E-mail address: R.C.King@maths.soton.ac.uk

Laboratoire d’Informatique de Paris-Nord, CNRS UMR 7030, Université Paris 13, 93430 Villetaneuse, France

E-mail address: ct@lipn.univ-paris13.fr

Laboratoire d’Informatique de Paris-Nord, CNRS UMR 7030, Université Paris 13, 93430 Villetaneuse, France

E-mail address: ft@lipn.univ-paris13.fr