The positive formula

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last update: 28 September 2012

The positive formula

In the type A case Lascoux and Schützenberger [LaS1978] have used the theory of column strict tableaux to give a positive formula for the Kostka-Foulkes polynomial. In this section we give a proof of this formula. Versions of this proof have appeared previously in [Sch1978] and in [But1994].

The starting point is the formula for Kλμ(t) in Theorem 3.4(b). To match the setup in [Mac1995] we shall work in a slightly different setting (corresponding to the Weyl group W and the weight lattice of the reductive group GLn()). In this case the vector space 𝔥*=n has orthonormal basis ε1,,εn, where εi=(0,,0,1,0,,0) with the 1 in the ith coordinate, the Weyl group is the symmetric group Sn acting on n by permuting the coordinates, the weight lattice P is replaced by the lattice

n= { (γ1,,γn) γi } andδ= ( n-1,n-2, ,2,1,0 ) (4.1)

replaces the element ρ. The positive roots are given by R+= { εi-εj 1i<jn } and the Schur functions (defined as in (2.6)) are viewed as (Laurent) polynomials in the variables x1,,xn, where xi=xεi and the symmetric group Sn acts by permuting the variables. If wSn then (-1)(w)= det(w) is the sign of the permutation w and the straightening law for Schur functions (see (2.7) and [Mac1995, I paragraph after (3.1)]) is

sμ= (-1)(w) swμ,where wμ=w (μ+δ)-δ, (4.2)

for wSn and μn. The set of partitions

𝒫= { (λ1,,λn) n λ1λn0 } (4.3)

takes the role played by the set P+. Conforming to the conventions in [Mac1995] so that gravity goes up and to the left, each partition μ=(μ1,,μn) 𝒫 is identified with the collection of boxes in a corner which has μi boxes in row i, where, as for matrices, the rows and columns of μ are indexed from top to bottom and left to right, respectively. For example, with n=7,

(5,5,3,3,1,1,0) = .

For each pair 1i<jn define the raising operator Rij:nn (see (3.13) and [Mac1995, I § (1.14)]) by

Rijμ=μ+εi -εjand define ( Ri1j1 Riljl ) sμ= s Ri1j1 Riljl μ , (4.4)

for a sequence of pairs i1<j1,, il<jl. Using the straightening law (4.2) any Schur function sμ indexed by μn with μ1++μn0 is either equal to 0 or to ±sλ for some λ𝒫. Composing the action of raising operators on Schur functions sλ should be avoided. For example, if n=2 and s1 denotes the transposition in the symmetric group S2 then, by the straightening law, s(0,1)=- s s1 ((0,1)+(1,0)) -(1,0) =- s (1,1)- (1,0) =-s(0,1) giving that s(0,1)=0 and so

R12 ( R12s(-1,2) ) =R12s(0,1)= R12·0=0,whereas (R122) s(-1,2)= s(1,0)= x1+x2.

With notation as in (4.2) and (4.4) we may define the Hall-Littlewood polynomials for this type A case by (see Theorem 3.4(b) and [Mac1995, III (4.6)])

Qμ= ( 1i<jn 11-tRij ) sμ,for all μn, (4.5)

and the Kostka-Foulkes polynomials Kλμ(t), λ,μ𝒫, by

Qμ=λ𝒫 Kλμ(t)sλ. (4.6)

Insertion and Pieri rules

Let λ,μn be partitions. A column strict tableaux of shape λ and weight μ is a filling of the boxes of λ with μ1 1s, μ2 2s, , μn ns, such that

  1. the rows are weakly increasing from left to right,
  2. the columns are strictly increasing from top to bottom.

If t is a column strict tableaux write shp(T) and wt(T) for the shape and the weight of T so that

shp(T)= (λ1,,λn), whereλi= number of boxes in rowiofT, and wt(T)= (μ1,,μn), whereμi= number of is inT.

For example,

T= 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 4 3 3 3 4 4 4 5 4 5 5 6 6 7 7 hasshp(T) = ( 9,7,7,4, 2,1,0 ) andwt(T) = ( 7,6,5,5, 3,2,2 ) .

For partitions λ and μ and, more generally, for any two sets 𝒮,𝒲𝒫 write

B(λ) = { column strict tableauxT shp(T)=λ } , B(λ)μ = { column strict tableauxT shp(T)=λ, wt(T)=μ } , B(𝒮)𝒲 = { column strict tableauxT shp(T)𝒮, wt(T)𝒲 } . (4.7)

Let λ and γ be partitions such that γλ (as collections of boxes in a corner, that is γiλi for 1in). The skew shape λ/γ is the collection of boxes of λ which are not in γ. The jeu de taquin reduces a column strict filling of a skew shape λ/γ to a column strict tableau of partition shape. At each step "gravity" moves one box up or to the left without violating the column strict condition (weakly increasing in rows, strictly increasing in columns). Once an empty box on the northwest side of the skew shape starts to move it must continue and exit the southeast border of the skew shape before another empty box can start its exit. The jeu de taquin is most easily illustrated by example:

1 1 2 2 1 2 3 3 4 4 2 1 1 2 2 1 2 3 2 3 4 4 1 1 2 2 1 2 3 2 3 4 4 1 1 2 2 1 2 3 2 3 4 4 1 1 2 2 1 2 3 2 3 4 4 1 1 2 2 1 2 3 4 2 3 4 1 1 2 2 1 2 3 4 2 3 4 1 1 2 2 1 2 3 4 2 3 4 1 1 2 2 1 2 3 4 2 3 4 1 1 2 2 1 2 3 4 2 3 4 1 1 1 2 2 2 3 4 2 3 4 1 1 1 2 2 2 2 3 4 3 4 1 1 1 2 2 2 2 3 4 3 4 1 1 1 2 2 2 2 3 4 3 4

In this example λ=(6,4,4,1), γ=(2,1,1) and the resulting column strict tableau is of shape (5,4,2). The result of the jeu de taquin is independent of the choice of order of the moves ([Ful1997, §1.2, Claim 2] which is proved in [Ful1997, §2 and §3]).

The plactic monoid is the set B(𝒫) of column strict tableaux with product given by

T1*T2=jeu de taquin reduction of T1 T2

Because the result of the jeu de taquin is independent of the choice of the order of the moves this is an associative monoid.

If x is a “letter”, that is, a column strict tableau of shape (1)=, then

x*Tis the column insertionofx intoT,and T*xis the row insertionofx intoT. (4.8)

The shape λ of P=T*x differs from the shape γ of T by single box and so if γ and P are given then the pair (T,x) can be recovered by “uninserting” the box λ/γ from P. The tableaux P and T differ by at most one entry in each row. The entries where P and T differ form the bumping path of x. The bumping path begins with x in the first row of P and ends at the entry in the box λ/γ. For example,

1 1 1 1 2 2 2 3 3 4 4 4 4 5 6 * 1 = 1 1 1 1 1 2 2 2 3 4 3 4 4 5 4 6 ,

where the bold face entries form the bumping path.

The monoid of words is the free monoid B* generated by {1,2,,n}. The weight wt(w) of a word w=w1wn is

wt(w)= wt(w1wn)= (μ1,,μn) whereμiis the number of i's inw.

For example, w=3214566532211 is a word of weight wt(w)=(3,3,2,1,2,2). The insertion map

B* B(𝒫) w1wn w1**wn (4.9)

is a weight preserving homomorphism of monoids.

A horizontal strip is a skew shape which contains at most one box in each column. The length of a horizontal strip λ/γ is the number of boxes in λ/γ. The boxes containing × in the picture

λ= γ × × × × × × × × × × × form a horizontal strip λ/γ of length 11.

For partitions μ and γ and a nonnegative integer r let

γ(r)= (r)γ = { partitionsλ λ/γis a horizontal strip of length r } , ( B(r) B(γ) ) μ = { pairsvT vB(r),T B(γ) such that wt(v)+ wt(T)=μ } , ( B(γ) B(r) ) μ = { pairsTv vB(r),T B(γ) such that wt(v)+ wt(T)=μ } , (4.10)

The following lemma gives tableau versions of the Pieri rule [Mac1995, I (5.16)]. The second bijection of the lemma is proved in [Fil1997, §1.1 Proposition], and the proof of the first bijection is similar (see also [But1994, Propositions 2.3.4 and 2.3.11]).

Let γ,μ,τ𝒫 be partitions and let r,s0. There are bijections

( B(r) B(γ) ) μ B(γ(r))μ vTv*T and ( B(γ) B(s) ) τ B(γ(s))τ TuT*u .


Let B(𝒫)= 1in B(𝒫)i, where

B(𝒫)i= { column strict tableauxb wt(b)= (μ1,,μn) has μ1== μi-1=0and μiμn 0 } .

Let ik= i i i be the unique column strict tableau of shape (k) and weight ( 0,,k,0 ,,0 ) , where the k appears in the ith entry. Charge is the function ch:B(𝒫) 0 such that

  1. ch()=0,
  2. if TB(𝒫)(i+1) and T*iμiB (𝒫)i then ch(T*iμi) =ch(T),
  3. if TB(𝒫)i and x is a letter not equal to i then ch(x*T)= ch(T*x)+1.

The proof of the existence and uniqueness of the function ch is presented beautifully in [Kil2000].

(Lascoux-Schützenberger [LaS1978], [Sch1978]) For partitions λ and μ,

Kλμ(t)= bB(λ)μ tch(b),

where the sum is over all column strict tableaux b of shape λ and weight μ.


The proof is by induction on n. Assume that the statement of the theorem holds for all partitions μ=(μ1,,μn). We shall prove that, for all partitions (μ0,μ)= (μ0,μ1,,μn) , Q(μ0,μ) has an expansion

Q(μ0,μ)= pB(ν)(μ0,μ) tch(p) sν, (4.11)

Beginning with the expression (4.5),

Q(μ0,μ) = ( 0i<jn 11-tRij ) s(μ0,μ) = ( j=1n 11-tR0j ) ( 1i<jn 11-tRij ) s(μ0,μ)

Proposition 3.5 shows that this particular product of raising operators can be composed and so, by applying the definition of the Kostka–Foulkes polynomials (4.6),

Q(μ0,μ) = ( j=1n 11-tR0j ) λ𝒫 Kλμ(t) s(μ0,λ) = λ𝒫 Kλμ(t) r0 tr k1,,kn 0 k1++kn=r R01k1 R0nkn s(μ0,λ) = λ𝒫 Kλμ(t) r0 tr k1,,kn 0 k1++kn=r s ( μ0+r,λ- (k1,,kn) )

Let γ=λ-(k1,,kn) be such that λ/γ is not a horizontal strip (usually γ isn’t even a partition). Let m be the first place a violation to being a horizontal strip occurs, that is,

letmbe minimal such that λm-km< λm+1.

For example, in the following picture, γ=λ- (3,1,2,2,1,0) and m=3.

λ= γ × × × × × × × × × m

Let sm be the simple transposition in the symmetric group which switches m and m+1 and define

γ=smγ, so that s(μ0+r,γ) =-s(μ0+r,γ)

Then γ=λ- (k1,,kn) with λi-ki= λi-ki, for im, m+1, and

λm-km= λm+1- km+1-1,and λm+1- km+1=λm -km+1.

Thus γm=λm+1 -km+1-1< λm+1 and so λ/γ is not a horizontal strip. This pairing γγ provides a cancellation in the expression for Q(μ0,μ) and thus

Q(μ0,μ) = λ𝒫 r0 trKλμ(t) γ𝒫λγ(r) s(μ0+r,γ) = γ,r λ𝒫λγ(r) trKλμ(t) s(μ0+r,γ),

where γ(r) is as defined in (4.10). Then, by the induction assumption,

Q(μ0,μ) = γ,r λ𝒫λγ(r) bB(λ)μ trtch(b) s(μ0+r,γ) = γ,r bB(γ(r))μ tr+ch(b) s(μ0+r,γ),

with B(γ(r))μ as in (4.10). By the first bijection in Lemma 4.1 this can be rewritten as

Q(μ0,μ) = γ,r vT (B(r)B(γ))μ tr+ch(v*T) s(μ0+r,γ) = γ,r vT (B(r)B(γ))μ tr+ch(v*T*0μ0) s(μ0+r,γ) = γ,r vT (B(r)B(γ))μ tch(T*0μ0*v) s(μ0+r,γ), (4.12)

where the last two equalities come from the defining properties of the charge function ch.

Let vT(B(r)B(γ))μ and let

p=T*0μ0*vand ν=shp (T*0μ0*v).

Let d be such that

μ0+r+d>νd andμ0+r+d-1 νd-1,

where, by convention, ν0=μ0+r. If d>1 define γ and r by

γ= ( γ1,,γd-2 ,μ0+r+d-1,γd ,,γn ) andμ0+r +d-1=γd-1,

so that, if si denotes the transposition (i,i+1) in the symmetric group, then (μ0+r,γ)= ( s0sd-3 sd-2sd-3 s0 ) (μ0+r,γ), and

s(μ0+r,γ)= (-1)2(d-3)+1 s(μ0+r,γ) =-s(μ0+r,γ) . (4.13) ν = γ × × × × × × × × × × d μ0+r = γ × × × × × × × × × d μ0+r

Note that γ=γ and r=r.

Case 1: d>1 and (μ0+r,γ)= (μ0+r,γ) . In this case (4.13) implies s(μ0+r,γ).

Case 2: d>1 and (μ0+r,γ) (μ0+r,γ) . Then

νγ(μ0+r) andνγ (μ0+r).

Row uninserting the horizontal strips ν/γ and ν/γ from p, by using the second bijection in Lemma 4.1, produces pairs

Tu=T (0μ0*v) ( B(γ)B (μ0+r) ) (μ0,μ)


Tu ( B(γ)B (μ0+r) ) (μ0,μ) ,

respectively. Consider the =μ0+r bumping paths in the tableau p which arise from T*u. These begin with the letters u1u of u and end at the boxes of the horizontal strip ν/γ. Similarly, there are =μ0+r bumping paths in p arising from T*u. Note that

  1. since u=0μ0*v begins with μ0 0s the leftmost μ0 bumping paths in T*u travel vertically, directly down the first μ0 columns of p, and
  2. in rows numbered d the bumping paths for T*u coincide exactly with the bumping paths for T*u, since the horizontal strips ν/γ and ν/γ coincide exactly in rows d and these paths are obtained by uninserting the boxes in this portion of the horizontal strip.
p = × × × × × × × × × × rowd-1 0 0 bumping paths inT*u p = × × × × × × × × × rowd-1 u1 u2 bumping paths inT*u

Suppose there are k bumping paths which end in rows d. The picture above has k=6 and corresponds to Case 2b below.

Case 2a: If μ0+r> μ0+r then the k bumping paths which end in rows d are the same or slightly “more left” in T*u than in T*u. Since the first μ0 bumping paths cannot be any “more left” than vertical, this forces the first μ0 entries of u to be 0 so that u=0μ0*v for some vB(r).

Case 2b: If μ0+r< μ0+r then the k bumping paths which end in rows d are the same or slightly “more right” in T*u than in T*u. We shall analyze how these k paths pass through row d-1 in T*u and in T*u. Divide row d-1 into four disjoint regions, left to right:

Region 1: the leftmost μ0 boxes of row d-1,
Region 2: the boxes which do not have a cross in them in T*u (and are not in Region 1),
Region 3: the boxes which have a cross in them in T*u but not in T*u,
Region 4: the boxes which have a cross in them in both T*u and T*u.

Of the k bumping paths of T*u which end in rows d the first μ0 of these pass through Region 1 in T*u, and the others (k-μ0 of them) pass through Region 2. Since the total number of bumping paths (the number of crosses) in T*u is μ0+r and there are some bumping paths of T*u which end in row d-1 (r-r of these), k<μ0+r. Thus

k-μ0<μ0+r -μ0<μ0+r+ (d-1)-μ0=Card (Region 2),

since Card(Region 1)=μ0 and Card(Region 1)+Card(Region 2)=μ0+r +d-1. Thus there must be a box in Region 2 of T*u that does not have a bumping path passing through it. All the bumping paths of T*u which pass through row d-1 to the left of this box remain the same as bumping paths for T*u and the first μ0 of these begin at an entry 0 in the first row of p. Thus, as in Case 2a, the first μ0 entries of u are 0 so that u=0μ0*v for some vB(r).


Tu=T (0μ0*v) ,withvT (B(r)B(γ))μ,

and the terms in the last line of (4.12) corresponding to the pairs vT and vT cancel each other

T*0μ0*v=T *0μ0*v and s(μ0+r,γ)=- s(μ0+r,γ).

Case 3: d=1. Since μ0+r+1>ν1 and νγ(μ0+r) the horizontal strip ν/γ has its boxes in each of the first μ0+r columns and

ν= (ν0,ν1,,νn)= ( μ0+r,γ1 ,,γn ) =(μ0+r,γ).

Row uninsertion of the horizontal strip ν/γ from the column strict tableau p, i.e. using the second bijection in Lemma 4.1, recovers the pair T(0μ0*v) and shows that 0μ0*v is the first row of p.

In conclusion, in the last line of (4.12) the terms corresponding to Case 1 vanish, the terms corresponding to Case 2 cancel, and the remaining Case 3 terms give formula (4.11), as desired.


The research of A. Ram was partially supported by the National Science Foundation (DMS-0097977), the National Security Agency (MDA904-01-1-0032) and by EPSRC Grant GR K99015 at the Newton Institute for Mathematical Sciences. The research of K. Nelsen was partially supported by the National Science Foundation (DMS-0097977 and a VIGRE grant) and the National Security Agency (MDA904-01-1-0032).

page history