The positive formula

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

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_{\lambda \mu }\left(t\right)$ 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 $G{L}_n\left(ℂ\right)\text{).}$ In this case the vector space ${𝔥}_{ℝ}^{*}={ℝ}^n$ has orthonormal basis ${\epsilon }_1,\dots ,{\epsilon }_n,$ where ${\epsilon }_i=(0,\dots ,0,1,0,\dots ,0)$ with the 1 in the $i\text{th}$ coordinate, the Weyl group is the symmetric group $S_n$ acting on ${ℝ}^n$ by permuting the coordinates, the weight lattice $P$ is replaced by the lattice

$$\begin{array}{cc}{\mathbb{Z}}^n=\{({\gamma }_1,\dots ,{\gamma }_n)\mid {\gamma }_i\in \mathbb{Z}\}\text{and}\delta =(n-1,n-2,\dots ,2,1,0)& \text{(4.1)}\end{array}$$

replaces the element $\rho \text{.}$ The positive roots are given by $R^{+}=\{{\epsilon }_i-{\epsilon }_j\mid 1\le i<j\le n\}$ and the Schur functions (defined as in (2.6)) are viewed as (Laurent) polynomials in the variables $x_1,\dots ,x_n,$ where $x_i=x^{{\epsilon }_i}$ and the symmetric group $S_n$ acts by permuting the variables. If $w\in S_n$ then ${(-1)}^{\ell \left(w\right)}=\text{det}\left(w\right)$ 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

$$\begin{array}{cc}{s}_{\mu }={(-1)}^{\ell \left(w\right)}{s}_{w\circ \mu },\text{where}w\circ \mu =w(\mu +\delta )-\delta ,& \text{(4.2)}\end{array}$$

for $w\in S_n$ and $\mu \in {\mathbb{Z}}^n\text{.}$ The set of partitions

$$\begin{array}{cc}𝒫=\{({\lambda }_1,\dots ,{\lambda }_n)\in {\mathbb{Z}}^n\mid {\lambda }_1\ge \dots \ge {\lambda }_n\ge 0\}& \text{(4.3)}\end{array}$$

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

$$\begin{array}{ccc}(5,5,3,3,1,1,0)=& & \text{.}\end{array}$$

For each pair $1\le i<j\le n$ define the raising operator $R_{ij}:{\mathbb{Z}}^n\to {\mathbb{Z}}^n$ (see (3.13) and [Mac1995, I § (1.14)]) by

$$\begin{array}{cc}{R}_{ij}\mu =\mu +{\epsilon }_i-{\epsilon }_j\text{and define}\left(R_{i_1{j}_1}\dots R_{i_l{j}_l}\right)s_{\mu }=s_{R_{i_1{j}_1}\dots R_{i_l{j}_l}\mu },& \text{(4.4)}\end{array}$$

for a sequence of pairs $i_1<j_1,\dots ,i_l<j_l\text{.}$ Using the straightening law (4.2) any Schur function $s_{\mu }$ indexed by $\mu \in {\mathbb{Z}}^n$ with ${\mu }_1+\dots +{\mu }_n\ge 0$ is either equal to 0 or to $\pm s_{\lambda }$ for some $\lambda \in 𝒫\text{.}$ Composing the action of raising operators on Schur functions $s_{\lambda }$ should be avoided. For example, if $n=2$ and $s_1$ denotes the transposition in the symmetric group $S_2$ then, by the straightening law, $s_{(0,1)}=-s_{s_1((0,1)+(1,0))-(1,0)}=-s_{(1,1)-(1,0)}=-s_{(0,1)}$ giving that $s_{(0,1)}=0$ and so

$$\begin{array}{c}{R}_{12}\left(R_{12}{s}_{(-1,2)}\right)=R_{12}{s}_{(0,1)}=R_{12}·0=0,\text{whereas}\\ \left(R_{12}^2\right)s_{(-1,2)}=s_{(1,0)}=x_1+x_2\text{.}\end{array}$$

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)])

$$\begin{array}{cc}{Q}_{\mu }=\left(\prod _{1\le i<j\le n}\frac{1}{1-t{R}_{ij}}\right)s_{\mu },\text{for all}\mu \in {\mathbb{Z}}^n,& \text{(4.5)}\end{array}$$

and the Kostka-Foulkes polynomials $K_{\lambda \mu }\left(t\right),$ $\lambda ,\mu \in 𝒫,$ by

$$\begin{array}{cc}{Q}_{\mu }=\sum _{\lambda \in 𝒫}{K}_{\lambda \mu }\left(t\right)s_{\lambda }\text{.}& \text{(4.6)}\end{array}$$

Insertion and Pieri rules

Let $\lambda ,\mu \in {\mathbb{Z}}^n$ be partitions. A column strict tableaux of shape $\lambda$ and weight $\mu$ is a filling of the boxes of $\lambda$ with ${\mu }_1$ 1s, ${\mu }_2$ 2s, $\dots ,$ ${\mu }_n$ $n$s, 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 $\text{shp}\left(T\right)$ and $\text{wt}\left(T\right)$ for the shape and the weight of $T$ so that

$$\begin{array}{cc}\text{shp}\left(T\right)=({\lambda }_1,\dots ,{\lambda }_n),& \text{where}{\lambda }_i=\text{number of boxes in row}i\text{of}T,\text{and}\\ \text{wt}\left(T\right)=({\mu }_1,\dots ,{\mu }_n),& \text{where}{\mu }_i=\text{number of}i\text{s in}T\text{.}\end{array}$$

For example,

$$\begin{array}{ccc}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 & \begin{array}{ccc}\text{has}\text{shp}\left(T\right)& =& (9,7,7,4,2,1,0)\\ \text{and}\text{wt}\left(T\right)& =& (7,6,5,5,3,2,2)\text{.}\end{array}\end{array}$$

For partitions $\lambda$ and $\mu$ and, more generally, for any two sets $𝒮,𝒲\subseteq 𝒫$ write

$$\begin{array}{cc}\begin{array}{ccc}B\left(\lambda \right)& =& \{\text{column strict tableaux}T\mid \text{shp}\left(T\right)=\lambda \},\\ B{\left(\lambda \right)}_{\mu }& =& \{\text{column strict tableaux}T\mid \text{shp}\left(T\right)=\lambda ,\text{wt}\left(T\right)=\mu \},\\ B{\left(𝒮\right)}_{𝒲}& =& \{\text{column strict tableaux}T\mid \text{shp}\left(T\right)\in 𝒮,\text{wt}\left(T\right)\in 𝒲\}\text{.}\end{array}& \text{(4.7)}\end{array}$$

Let $\lambda$ and $\gamma$ be partitions such that $\gamma \subseteq \lambda$ (as collections of boxes in a corner, that is ${\gamma }_i\le {\lambda }_i$ for $1\le i\le n\text{).}$ The skew shape $\lambda /\gamma$ is the collection of boxes of $\lambda$ which are not in $\gamma \text{.}$ The jeu de taquin reduces a column strict filling of a skew shape $\lambda /\gamma$ 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:

$$\begin{array}{cccc}& 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 \end{array}$$

In this example $\lambda =(6,4,4,1),$ $\gamma =(2,1,1)$ and the resulting column strict tableau is of shape $(5,4,2)\text{.}$ 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\left(𝒫\right)$ of column strict tableaux with product given by

$$\begin{array}{cc}{T}_1*T_2=\text{jeu de taquin reduction of}& T1 T2 \end{array}$$

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 $\left(1\right)=\square ,$ then

$$\begin{array}{cc}\begin{array}{c}x*T\text{is the}\text{column insertion}\text{of}x\text{into}T,\text{and}\\ T*x\text{is the}\text{row insertion}\text{of}x\text{into}T\text{.}\end{array}& \text{(4.8)}\end{array}$$

The shape $\lambda$ of $P=T*x$ differs from the shape $\gamma$ of $T$ by single box and so if $\gamma$ and $P$ are given then the pair $(T,x)$ can be recovered by “uninserting” the box $\lambda /\gamma$ from $P\text{.}$ 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\text{.}$ The bumping path begins with $x$ in the first row of $P$ and ends at the entry in the box $\lambda /\gamma \text{.}$ For example,

$$\begin{array}{cccccc} 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 & ,\end{array}$$

where the bold face entries form the bumping path.

The monoid of words is the free monoid $B^{*}$ generated by $\{1,2,\dots ,n\}\text{.}$ The weight $\text{wt}\left(w\right)$ of a word $w=w_1\dots w_n$ is

$$\text{wt}\left(w\right)=\text{wt}\left(w_1\dots w_n\right)=({\mu }_1,\dots ,{\mu }_n)\text{where}{\mu }_i\text{is the number of}i\text{'s in}w\text{.}$$

For example, $w=3214566532211$ is a word of weight $\text{wt}\left(w\right)=(3,3,2,1,2,2)\text{.}$ The insertion map

$$\begin{array}{cc}\begin{array}{ccc}{B}^{*}& ⟶& B\left(𝒫\right)\\ w_1\dots w_n& ⟼& w_1*\dots *w_n\end{array}& \text{(4.9)}\end{array}$$

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 $\lambda /\gamma$ is the number of boxes in $\lambda /\gamma \text{.}$ The boxes containing $\times$ in the picture

$$\begin{array}{ccc}\lambda =& γ × × × × × × × × × × × & \text{form a horizontal strip}\lambda /\gamma \text{of length 11.}\end{array}$$

For partitions $\mu$ and $\gamma$ and a nonnegative integer $r$ let

$$\begin{array}{cc}\begin{array}{ccc}\gamma \otimes \left(r\right)=\left(r\right)\otimes \gamma & =& \{\text{partitions}\lambda \mid \lambda /\gamma \text{is a horizontal strip of length}r\},\\ {(B\left(r\right)\otimes B\left(\gamma \right))}_{\mu }& =& \{\text{pairs}v\otimes T\mid \begin{array}{c}v\in B\left(r\right),T\in B\left(\gamma \right)\\ \text{such that wt}\left(v\right)+\text{wt}\left(T\right)=\mu \end{array}\},\\ {(B\left(\gamma \right)\otimes B\left(r\right))}_{\mu }& =& \{\text{pairs}T\otimes v\mid \begin{array}{c}v\in B\left(r\right),T\in B\left(\gamma \right)\\ \text{such that wt}\left(v\right)+\text{wt}\left(T\right)=\mu \end{array}\},\end{array}& \text{(4.10)}\end{array}$$

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 $\gamma ,\mu ,\tau \in 𝒫$ be partitions and let $r,s\in {\mathbb{Z}}_{\ge 0}\text{.}$ There are bijections

$$\begin{array}{ccc}\begin{array}{ccc}{(B\left(r\right)\otimes B\left(\gamma \right))}_{\mu }& ⟷& B{(\gamma \otimes \left(r\right))}_{\mu }\\ v\otimes T& ⟶& v*T\end{array}& \text{and}& \begin{array}{ccc}{(B\left(\gamma \right)\otimes B\left(s\right))}_{\tau }& ⟷& B{(\gamma \otimes \left(s\right))}_{\tau }\\ T\otimes u& ⟶& T*u\end{array}\text{.}\end{array}$$

Charge

Let $B{\left(𝒫\right)}_{\ge }={\displaystyle \bigcup _{1\le i\le n}}B{\left(𝒫\right)}_{\ge i},$ where

$$B{\left(𝒫\right)}_{\ge i}=\{\text{column strict tableaux}b\mid \begin{array}{c}\text{wt}\left(b\right)=({\mu }_1,\dots ,{\mu }_n)\text{has}\\ {\mu }_1=\dots ={\mu }_{i-1}=0\text{and}\\ {\mu }_i\ge \dots \ge {\mu }_n\ge 0\end{array}\}\text{.}$$

Let $\begin{array}{cc}{i}^k=& i i … i \end{array}$ be the unique column strict tableau of shape $\left(k\right)$ and weight $(0,\dots ,k,0,\dots ,0),$ where the $k$ appears in the $i$th entry. Charge is the function $\text{ch}:B{\left(𝒫\right)}_{\ge }⟶{\mathbb{Z}}_{\ge 0}$ such that

1. $\text{ch}(\varnothing )=0,$
2. if $T\in B{\left(𝒫\right)}_{\ge (i+1)}$ and $T*i^{{\mu }_i}\in B{\left(𝒫\right)}_{\ge i}$ then $\text{ch}(T*i^{{\mu }_i})=\text{ch}\left(T\right),$
3. if $T\in B{\left(𝒫\right)}_{\ge i}$ and $x$ is a letter not equal to $i$ then $\text{ch}(x*T)=\text{ch}(T*x)+1\text{.}$

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

(Lascoux-Schützenberger [LaS1978], [Sch1978]) For partitions $\lambda$ and $\mu ,$

$$K_{\lambda \mu }\left(t\right)=\sum _{b\in B{\left(\lambda \right)}_{\mu }}{t}^{\text{ch}\left(b\right)},$$

where the sum is over all column strict tableaux $b$ of shape $\lambda$ and weight $\mu \text{.}$

		Proof.
	The proof is by induction on $n\text{.}$ Assume that the statement of the theorem holds for all partitions $\mu =({\mu }_1,\dots ,{\mu }_n)\text{.}$ We shall prove that, for all partitions $({\mu }_0,\mu )=({\mu }_0,{\mu }_1,\dots ,{\mu }_n),$ $Q_{({\mu }_0,\mu )}$ has an expansion $$\begin{array}{cc}{Q}_{({\mu }_0,\mu )}=\sum _{p\in B{\left(\nu \right)}_{({\mu }_0,\mu )}}{t}^{\text{ch}\left(p\right)}{s}_{\nu },& \text{(4.11)}\end{array}$$ Beginning with the expression (4.5), $$\begin{array}{ccc}{Q}_{({\mu }_0,\mu )}& =& \left(\prod _{0\le i<j\le n}\frac{1}{1-t{R}_{ij}}\right)s_{({\mu }_0,\mu )}\\ & =& \left(\prod _{j=1}^n\frac{1}{1-t{R}_{0j}}\right)\left(\prod _{1\le i<j\le n}\frac{1}{1-t{R}_{ij}}\right)s_{({\mu }_0,\mu )}\end{array}$$ 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), $$\begin{array}{ccc}{Q}_{({\mu }_0,\mu )}& =& \left(\prod _{j=1}^n\frac{1}{1-t{R}_{0j}}\right)\sum _{\lambda \in 𝒫}{K}_{\lambda \mu }\left(t\right)s_{({\mu }_0,\lambda )}\\ & =& \sum _{\lambda \in 𝒫}{K}_{\lambda \mu }\left(t\right)\sum _{r\in {\mathbb{Z}}_{\ge 0}}{t}^r\sum _{\underset{k_1+\dots +k_n=r}{k_1,\dots ,k_n\in {\mathbb{Z}}_{\ge 0}}}{R}_{01}^{k_1}\dots R_{0n}^{k_n}{s}_{({\mu }_0,\lambda )}\\ & =& \sum _{\lambda \in 𝒫}{K}_{\lambda \mu }\left(t\right)\sum _{r\in {\mathbb{Z}}_{\ge 0}}{t}^r\sum _{\underset{k_1+\dots +k_n=r}{k_1,\dots ,k_n\in {\mathbb{Z}}_{\ge 0}}}{s}_{({\mu }_0+r,\lambda -(k_1,\dots ,k_n))}\end{array}$$ Let $\gamma =\lambda -(k_1,\dots ,k_n)$ be such that $\lambda /\gamma$ is not a horizontal strip (usually $\gamma$ isn’t even a partition). Let $m$ be the first place a violation to being a horizontal strip occurs, that is, $$\text{let}m\text{be minimal such that}{\lambda }_m-k_m<{\lambda }_{m+1}\text{.}$$ For example, in the following picture, $\gamma =\lambda -(3,1,2,2,1,0)$ and $m=3\text{.}$ $$\begin{array}{cc}\lambda =& γ × × × × × × × × × ↑ m ↓ \end{array}$$ Let $s_m$ be the simple transposition in the symmetric group which switches $m$ and $m+1$ and define $$\stackrel{\sim }{\gamma }=s_m\circ \gamma ,\text{so that}{s}_{({\mu }_0+r,\gamma )}=-s_{({\mu }_0+r,\stackrel{\sim }{\gamma })}$$ Then $\stackrel{\sim }{\gamma }=\lambda -({\stackrel{\sim }{k}}_1,\dots ,{\stackrel{\sim }{k}}_n)$ with ${\lambda }_i-{\stackrel{\sim }{k}}_i={\lambda }_i-k_i,$ for $i\ne m,$ $m+1,$ and $${\lambda }_m-{\stackrel{\sim }{k}}_m={\lambda }_{m+1}-k_{m+1}-1,\text{and}{\lambda }_{m+1}-{\stackrel{\sim }{k}}_{m+1}={\lambda }_m-k_m+1\text{.}$$ Thus ${\stackrel{\sim }{\gamma }}_m={\lambda }_{m+1}-k_{m+1}-1<{\lambda }_{m+1}$ and so $\lambda /\stackrel{\sim }{\gamma }$ is not a horizontal strip. This pairing $\gamma \leftrightarrow \stackrel{\sim }{\gamma }$ provides a cancellation in the expression for $Q_{({\mu }_0,\mu )}$ and thus $$\begin{array}{ccc}{Q}_{({\mu }_0,\mu )}& =& \sum _{\lambda \in 𝒫}\sum _{r\in {\mathbb{Z}}_{\ge 0}}{t}^r{K}_{\lambda \mu }\left(t\right)\sum _{\underset{\lambda \in \gamma \otimes \left(r\right)}{\gamma \in 𝒫}}{s}_{({\mu }_0+r,\gamma )}\\ & =& \sum _{\gamma ,r}\sum _{\underset{\lambda \in \gamma \otimes \left(r\right)}{\lambda \in 𝒫}}{t}^r{K}_{\lambda \mu }\left(t\right)s_{({\mu }_0+r,\gamma )},\end{array}$$ where $\gamma \otimes \left(r\right)$ is as defined in (4.10). Then, by the induction assumption, $$\begin{array}{ccc}{Q}_{({\mu }_0,\mu )}& =& \sum _{\gamma ,r}\sum _{\underset{\lambda \in \gamma \otimes \left(r\right)}{\lambda \in 𝒫}}\sum _{b\in B{\left(\lambda \right)}_{\mu }}{t}^r{t}^{\text{ch}\left(b\right)}{s}_{({\mu }_0+r,\gamma )}\\ & =& \sum _{\gamma ,r}\sum _{b\in B{(\gamma \vee \left(r\right))}_{\mu }}{t}^{r+\text{ch}\left(b\right)}{s}_{({\mu }_0+r,\gamma )},\end{array}$$ with $B{(\gamma \otimes \left(r\right))}_{\mu }$ as in (4.10). By the first bijection in Lemma 4.1 this can be rewritten as $$\begin{array}{cc}\begin{array}{ccc}{Q}_{({\mu }_0,\mu )}& =& \sum _{\gamma ,r}\sum _{v\otimes T\in {(B\left(r\right)\otimes B\left(\gamma \right))}_{\mu }}{t}^{r+\text{ch}(v*T)}{s}_{({\mu }_0+r,\gamma )}\\ & =& \sum _{\gamma ,r}\sum _{v\otimes T\in {(B\left(r\right)\otimes B\left(\gamma \right))}_{\mu }}{t}^{r+\text{ch}(v*T*0^{{\mu }_0})}{s}_{({\mu }_0+r,\gamma )}\\ & =& \sum _{\gamma ,r}\sum _{v\otimes T\in {(B\left(r\right)\otimes B\left(\gamma \right))}_{\mu }}{t}^{\text{ch}(T*0^{{\mu }_0}*v)}{s}_{({\mu }_0+r,\gamma )},\end{array}& \text{(4.12)}\end{array}$$ where the last two equalities come from the defining properties of the charge function ch. Let $v\otimes T\in {(B\left(r\right)\otimes B\left(\gamma \right))}_{\mu }$ and let $$p=T*0^{{\mu }_0}*v\text{and}\nu =\text{shp}(T*0^{{\mu }_0}*v)\text{.}$$ Let $d$ be such that $${\mu }_0+r+d>{\nu }_d\text{and}{\mu }_0+r+d-1\le {\nu }_{d-1},$$ where, by convention, ${\nu }_0={\mu }_0+r\text{.}$ If $d>1$ define $\stackrel{\sim }{\gamma }$ and $\stackrel{\sim }{r}$ by $$\stackrel{\sim }{\gamma }=({\gamma }_1,\dots ,{\gamma }_{d-2},{\mu }_0+r+d-1,{\gamma }_d,\dots ,{\gamma }_n)\text{and}{\mu }_0+\stackrel{\sim }{r}+d-1={\gamma }_{d-1},$$ so that, if $s_i$ denotes the transposition $(i,i+1)$ in the symmetric group, then $({\mu }_0+\stackrel{\sim }{r},\stackrel{\sim }{\gamma })=\left(s_0\dots s_{d-3}{s}_{d-2}{s}_{d-3}\dots s_0\right)\circ ({\mu }_0+r,\gamma ),$ and $$\begin{array}{cc}{s}_{({\mu }_0+r,\gamma )}={(-1)}^{2(d-3)+1}{s}_{({\mu }_0+\stackrel{\sim }{r},\stackrel{\sim }{\gamma })}=-s_{({\mu }_0+\stackrel{\sim }{r},\stackrel{\sim }{\gamma })}\text{.}& \text{(4.13)}\end{array}$$ $$\begin{array}{ccc}\nu & =& γ × × × × × × × × × × ↑ d ↓ μ0+r \\ & =& γ∼ × × × × × × × × × ↑ d ↓ μ0+r∼ \end{array}$$ Note that $\stackrel{\stackrel{\sim }{\sim }}{\gamma }=\gamma$ and $\stackrel{\stackrel{\sim }{\sim }}{r}=r\text{.}$ Case 1: $d>1$ and $({\mu }_0+r,\gamma )=({\mu }_0+\stackrel{\sim }{r},\stackrel{\sim }{\gamma })\text{.}$ In this case (4.13) implies $s_{({\mu }_0+r,\gamma )}\text{.}$ Case 2: $d>1$ and $({\mu }_0+r,\gamma )\ne ({\mu }_0+\stackrel{\sim }{r},\stackrel{\sim }{\gamma })\text{.}$ Then $$\nu \in \gamma \otimes ({\mu }_0+r)\text{and}\nu \in \stackrel{\sim }{\gamma }\otimes ({\mu }_0+\stackrel{\sim }{r})\text{.}$$ Row uninserting the horizontal strips $\nu /\gamma$ and $\nu /\stackrel{\sim }{\gamma }$ from $p,$ by using the second bijection in Lemma 4.1, produces pairs $$T\otimes u=T\otimes (0^{{\mu }_0}*v)\in {(B\left(\gamma \right)\otimes B({\mu }_0+r))}_{({\mu }_0,\mu )}$$ and $$\stackrel{\sim }{T}\otimes \stackrel{\sim }{u}\in {(B\left(\stackrel{\sim }{\gamma }\right)\otimes B({\mu }_0+\stackrel{\sim }{r}))}_{({\mu }_0,\mu )},$$ respectively. Consider the $\ell ={\mu }_0+r$ bumping paths in the tableau $p$ which arise from $T*u\text{.}$ These begin with the letters $u_1\le \dots \le u_{\ell }$ of $u$ and end at the boxes of the horizontal strip $\nu /\gamma \text{.}$ Similarly, there are $\stackrel{\sim }{\ell }={\mu }_0+\stackrel{\sim }{r}$ bumping paths in $p$ arising from $\stackrel{\sim }{T}*\stackrel{\sim }{u}\text{.}$ Note that since $u=0^{{\mu }_0}*v$ begins with ${\mu }_0$ 0s the leftmost ${\mu }_0$ bumping paths in $T*u$ travel vertically, directly down the first ${\mu }_0$ columns of $p,$ and in rows numbered $\ge d$ the bumping paths for $\stackrel{\sim }{T}*\stackrel{\sim }{u}$ coincide exactly with the bumping paths for $T*u,$ since the horizontal strips $\nu /\gamma$ and $\nu /\stackrel{\sim }{\gamma }$ coincide exactly in rows $\ge d$ and these paths are obtained by uninserting the boxes in this portion of the horizontal strip. $$\begin{array}{ccc}p& =& × × × × × × × × × × ⟵rowd-1 0 0 \\ & & \text{bumping paths in}T*u\\ p& =& × × × × × × × × × ⟵rowd-1 u∼1 u∼2 \\ & & \text{bumping paths in}\stackrel{\sim }{T}*\stackrel{\sim }{u}\end{array}$$ Suppose there are $k$ bumping paths which end in rows $\ge d\text{.}$ The picture above has $k=6$ and corresponds to Case 2b below. Case 2a: If ${\mu }_0+\stackrel{\sim }{r}>{\mu }_0+r$ then the $k$ bumping paths which end in rows $\ge d$ are the same or slightly “more left” in $\stackrel{\sim }{T}*\stackrel{\sim }{u}$ than in $T*u\text{.}$ Since the first ${\mu }_0$ bumping paths cannot be any “more left” than vertical, this forces the first ${\mu }_0$ entries of $\stackrel{\sim }{u}$ to be 0 so that $\stackrel{\sim }{u}=0^{{\mu }_0}*\stackrel{\sim }{v}$ for some $v\in B\left(\stackrel{\sim }{r}\right)\text{.}$ Case 2b: If ${\mu }_0+\stackrel{\sim }{r}<{\mu }_0+r$ then the $k$ bumping paths which end in rows $\ge d$ are the same or slightly “more right” in $\stackrel{\sim }{T}*\stackrel{\sim }{u}$ than in $T*u\text{.}$ We shall analyze how these $k$ paths pass through row $d-1$ in $T*u$ and in $\stackrel{\sim }{T}*\stackrel{\sim }{u}\text{.}$ Divide row $d-1$ into four disjoint regions, left to right: Region 1: the leftmost ${\mu }_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 $\stackrel{\sim }{T}*\stackrel{\sim }{u},$ Region 4: the boxes which have a cross in them in both $T*u$ and $\stackrel{\sim }{T}*\stackrel{\sim }{u}\text{.}$ Of the $k$ bumping paths of $T*u$ which end in rows $\ge d$ the first ${\mu }_0$ of these pass through Region 1 in $T*u,$ and the others $(k-{\mu }_0$ of them) pass through Region 2. Since the total number of bumping paths (the number of crosses) in $\stackrel{\sim }{T}*\stackrel{\sim }{u}$ is ${\mu }_0+\stackrel{\sim }{r}$ and there are some bumping paths of $\stackrel{\sim }{T}*\stackrel{\sim }{u}$ which end in row $d-1$ $(r-\stackrel{\sim }{r}$ of these), $k<{\mu }_0+\stackrel{\sim }{r}\text{.}$ Thus $$k-{\mu }_0<{\mu }_0+\stackrel{\sim }{r}-{\mu }_0<{\mu }_0+\stackrel{\sim }{r}+(d-1)-{\mu }_0=\text{Card}\left(\text{Region 2}\right),$$ since $\text{Card(Region 1)}={\mu }_0$ and $\text{Card(Region 1)}+\text{Card(Region 2)}={\mu }_0+\stackrel{\sim }{r}+d-1\text{.}$ 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 $\stackrel{\sim }{T}*\stackrel{\sim }{u}$ and the first ${\mu }_0$ of these begin at an entry 0 in the first row of $p\text{.}$ Thus, as in Case 2a, the first ${\mu }_0$ entries of $\stackrel{\sim }{u}$ are 0 so that $\stackrel{\sim }{u}=0^{{\mu }_0}*\stackrel{\sim }{v}$ for some $v\in B\left(\stackrel{\sim }{r}\right)\text{.}$ So, $$\stackrel{\sim }{T}\otimes \stackrel{\sim }{u}=\stackrel{\sim }{T}\otimes (0^{{\mu }_0}*\stackrel{\sim }{v}),\text{with}\stackrel{\sim }{v}\otimes \stackrel{\sim }{T}\in {(B\left(\stackrel{\sim }{r}\right)\otimes B\left(\stackrel{\sim }{\gamma }\right))}_{\mu },$$ and the terms in the last line of (4.12) corresponding to the pairs $v\otimes T$ and $\stackrel{\sim }{v}\otimes \stackrel{\sim }{T}$ cancel each other $$T*0^{{\mu }_0}*v=\stackrel{\sim }{T}*0^{{\mu }_0}*\stackrel{\sim }{v}\text{and}{s}_{({\mu }_0+r,\gamma )}=-s_{({\mu }_0+\stackrel{\sim }{r},\stackrel{\sim }{\gamma })}\text{.}$$ Case 3: $d=1\text{.}$ Since ${\mu }_0+r+1>{\nu }_1$ and $\nu \in \gamma \otimes ({\mu }_0+r)$ the horizontal strip $\nu /\gamma$ has its boxes in each of the first ${\mu }_0+r$ columns and $$\nu =({\nu }_0,{\nu }_1,\dots ,{\nu }_n)=({\mu }_0+r,{\gamma }_1,\dots ,{\gamma }_n)=({\mu }_0+r,\gamma )\text{.}$$ Row uninsertion of the horizontal strip $\nu /\gamma$ from the column strict tableau $p,$ i.e. using the second bijection in Lemma 4.1, recovers the pair $T\otimes (0^{{\mu }_0}*v)$ and shows that $0^{{\mu }_0}*v$ is the first row of $p\text{.}$ 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. $\square$

Acknowledgements

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