Last update: 28 September 2012
In the type 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 in Theorem 3.4(b). To match the setup in [Mac1995] we shall work in a slightly different setting (corresponding to the Weyl group and the weight lattice of the reductive group In this case the vector space has orthonormal basis where with the 1 in the coordinate, the Weyl group is the symmetric group acting on by permuting the coordinates, the weight lattice is replaced by the lattice
replaces the element The positive roots are given by and the Schur functions (defined as in (2.6)) are viewed as (Laurent) polynomials in the variables where and the symmetric group acts by permuting the variables. If then is the sign of the permutation and the straightening law for Schur functions (see (2.7) and [Mac1995, I paragraph after (3.1)]) is
for and The set of partitions
takes the role played by the set Conforming to the conventions in [Mac1995] so that gravity goes up and to the left, each partition is identified with the collection of boxes in a corner which has boxes in row where, as for matrices, the rows and columns of are indexed from top to bottom and left to right, respectively. For example, with
For each pair define the raising operator (see (3.13) and [Mac1995, I § (1.14)]) by
for a sequence of pairs Using the straightening law (4.2) any Schur function indexed by with is either equal to 0 or to for some Composing the action of raising operators on Schur functions should be avoided. For example, if and denotes the transposition in the symmetric group then, by the straightening law, giving that and so
With notation as in (4.2) and (4.4) we may define the Hall-Littlewood polynomials for this type case by (see Theorem 3.4(b) and [Mac1995, III (4.6)])
and the Kostka-Foulkes polynomials by
Let be partitions. A column strict tableaux of shape and weight is a filling of the boxes of with 1s, 2s, s, such that
If is a column strict tableaux write and for the shape and the weight of so that
For partitions and and, more generally, for any two sets write
Let and be partitions such that (as collections of boxes in a corner, that is for 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:
In this example and the resulting column strict tableau is of shape 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 of column strict tableaux with product given by
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 is a “letter”, that is, a column strict tableau of shape then
The shape of differs from the shape of by single box and so if and are given then the pair can be recovered by “uninserting” the box from The tableaux and differ by at most one entry in each row. The entries where and differ form the bumping path of The bumping path begins with in the first row of and ends at the entry in the box For example,
where the bold face entries form the bumping path.
The monoid of words is the free monoid generated by The weight of a word is
For example, is a word of weight The insertion map
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
For partitions and and a nonnegative integer let
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 There are bijections
Let be the unique column strict tableau of shape and weight where the appears in the th entry. Charge is the function such that
The proof of the existence and uniqueness of the function ch is presented beautifully in [Kil2000].
(Lascoux-Schützenberger [LaS1978], [Sch1978]) For partitions and
where the sum is over all column strict tableaux of shape and weight
The proof is by induction on Assume that the statement of the theorem holds for all partitions We shall prove that, for all partitions has an expansion
Beginning with the expression (4.5),
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),
Let be such that is not a horizontal strip (usually isn’t even a partition). Let be the first place a violation to being a horizontal strip occurs, that is,
For example, in the following picture, and
Let be the simple transposition in the symmetric group which switches and and define
Then with for and
Thus and so is not a horizontal strip. This pairing provides a cancellation in the expression for and thus
where is as defined in (4.10). Then, by the induction assumption,
with as in (4.10). By the first bijection in Lemma 4.1 this can be rewritten as
where the last two equalities come from the defining properties of the charge function ch.
Let and let
Let be such that
where, by convention, If define and by
so that, if denotes the transposition in the symmetric group, then and
Note that and
Case 1: and In this case (4.13) implies
Case 2: and Then
Row uninserting the horizontal strips and from by using the second bijection in Lemma 4.1, produces pairs
respectively. Consider the bumping paths in the tableau which arise from These begin with the letters of and end at the boxes of the horizontal strip Similarly, there are bumping paths in arising from Note that
Suppose there are bumping paths which end in rows The picture above has and corresponds to Case 2b below.
Case 2a: If then the bumping paths which end in rows are the same or slightly “more left” in than in Since the first bumping paths cannot be any “more left” than vertical, this forces the first entries of to be 0 so that for some
Case 2b: If then the bumping paths which end in rows are the same or slightly “more right” in than in We shall analyze how these paths pass through row in and in Divide row into four disjoint regions, left to right:
Of the bumping paths of which end in rows the first of these pass through Region 1 in and the others of them) pass through Region 2. Since the total number of bumping paths (the number of crosses) in is and there are some bumping paths of which end in row of these), Thus
since and Thus there must be a box in Region 2 of that does not have a bumping path passing through it. All the bumping paths of which pass through row to the left of this box remain the same as bumping paths for and the first of these begin at an entry 0 in the first row of Thus, as in Case 2a, the first entries of are 0 so that for some
and the terms in the last line of (4.12) corresponding to the pairs and cancel each other
Case 3: Since and the horizontal strip has its boxes in each of the first columns and
Row uninsertion of the horizontal strip from the column strict tableau i.e. using the second bijection in Lemma 4.1, recovers the pair and shows that is the first row of
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).