Littlewood-Richardson polynomials

A. I. Molev

Introduction

is a homomorphism of filtered rings so that we can define the inverse limit ring $\Lambda$ by

In the specialization $a=(0)$ the polynomials $c_{\lambda\mu}^{\nu}(a)$ become the classical Littlewood–Richardson coefficients $c_{\lambda\mu}^{\nu}$ ; see . These are remarkable nonnegative integers which occupy a prominent place in combinatorics, representation theory and geometry; see e.g. Fulton , Macdonald and Sagan .

The main result of this paper is a combinatorial rule for the calculation of the Littlewood–Richardson polynomials which provides a manifestly positive formula in the sense that $c_{\lambda\mu}^{\nu}(a)$ is written as a polynomial in the differences $a_{i}-a_{j}$ , $i<j$ , with positive integer coefficients.

where $d_{\lambda\mu}^{\,\nu}=c_{\lambda\mu}^{\,\nu}(a)$ with the sequence $a$ specialized by

while the remaining parameters $a_{i}$ are set to zero (the $t_{i}$ should be replaced with $y_{i}$ in the notation of ). The coefficients $d_{\lambda\mu}^{\,\nu}$ are given explicitly as polynomials in the $t_{i}-t_{j}$ , $i>j$ , with positive integer coefficients. This positivity property was established by Graham in the general context of the equivariant Schubert calculus. The first manifestly positive formula for the coefficients in the expansion (1.4) was obtained by Knutson and Tao by using combinatorics of puzzles. An earlier rule of Molev and Sagan also calculates $d_{\lambda\mu}^{\,\nu}$ but lacks the explicit positivity property. Our new rule implies a stability property of the coefficients $d_{\lambda\mu}^{\,\nu}$ (see Corollary 3.1 below). Even though this property was not pointed out in , it can be derived directly from the puzzle rule; see also Fulton for its geometrical interpretation and an extension to the equivariant Schubert calculus on the flag variety.

We define the double Schur function $s_{\lambda}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ as the sequence of the double Schur polynomials

which are compatible with respect to the homomorphisms (1.1),

The polynomials (1.6) are closely related to the “factorial” or “double” Schur polynomials $s_{\lambda}(x|u)$ with $x=(x_{1},\dots,x_{n})$ . The latter were introduced by Goulden and Greene and Macdonald as a generalization of the factorial Schur polynomials of Biedenharn and Louck , and they are also a special case of the double Schubert polynomials of Lascoux and Schützenberger; see Lascoux . We follow Chen, Li and Louck and Fulton and use the name “double Schur polynomials” for the related polynomials $s_{\lambda}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ as well.

In a more detail, consider a partition $\lambda$ which is a sequence $\lambda=(\lambda_{1},\dots,\lambda_{n})$ of integers $\lambda_{i}$ such that $\lambda_{1}\geqslant\dots\geqslant\lambda_{n}\geqslant 0$ . We will identify $\lambda$ with its diagram represented graphically as the array of left justified rows of unit boxes with $\lambda_{1}$ boxes in the top row, $\lambda_{2}$ boxes in the second row, etc. The total number of boxes in $\lambda$ will be denoted by $|\lambda|$ . The transposed diagram $\lambda^{\prime}=(\lambda^{\prime}_{1},\dots,\lambda^{\prime}_{p})$ is obtained from $\lambda$ by applying the symmetry with respect to the main diagonal, so that $\lambda^{\prime}_{j}$ is the number of boxes in the $j$ -th column of $\lambda$ .

Let $u=(u_{1},u_{2},\dots)$ be a sequence of variables. The polynomials $s_{\lambda}(x|u)$ can be defined by

where $T$ runs over all semistandard (column-strict) tableaux of shape $\lambda$ with entries in $\{1,\dots,n\}$ , $T(\alpha)$ is the entry of $T$ in the box $\alpha\in\lambda$ and $c(\alpha)=j-i$ is the content of the box $\alpha=(i,j)$ in row $i$ and column $j$ .

By a reverse $\lambda$ -tableau $T$ we will mean the tableau obtained by filling in the boxes of $\lambda$ with the numbers $1,2,\dots,n$ in such a way that the entries weakly decrease along the rows and strictly decrease down the columns. If $\alpha=(i,j)$ is a box of $\lambda$ we let $T(\alpha)=T(i,j)$ denote the entry of $T$ in the box $\alpha$ . We define the double Schur polynomials $s_{\lambda}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ by

summed over the reverse $\lambda$ -tableaux $T$ . Then we have

Note that the stability property (1.7) extends to the double Schubert polynomials (and to the equivariant Schubert calculus on the flag manifold). This follows easily from the Cauchy formula for the Schubert polynomials (e.g., put $x_{1}=y_{1}$ in [15, Formula in 2.5.5]). In a more general context, this was also pointed out in .

The double Schur polynomials $s_{\lambda}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ parameterized by the diagrams $\lambda$ with at most $n$ rows form a basis of the ring $\Lambda_{n}$ . Due to the stability property (1.7), the Littlewood–Richardson polynomials $c_{\lambda\mu}^{\nu}(a)$ can be defined by the expansion (1.3), where $x$ is understood as the set of variables $x=(x_{1},\dots,x_{n})$ for any positive integer $n$ such that the diagrams $\lambda$ , $\mu$ and $\nu$ have at most $n$ rows. This allows us to work with a finite set of variables for the determination of the polynomials $c_{\lambda\mu}^{\nu}(a)$ . For the proof of the main theorem (Theorem 2.1) we follow the general approach of , using the techniques of “barred” tableaux and modify the corresponding arguments in order to obtain manifestly positive polynomials. This is achieved by imposing a boundness condition on the barred tableaux.

It was observed by Goulden and Greene and Macdonald that $s_{\lambda}(x|u)$ , regarded as a formal power series in the infinite sets of variables $x$ and $u$ , admits a “supertableaux” representation. We show that this representation has its “finite” counterpart where $x$ is a finite set of variables. We derive the corresponding formula by choosing a certain specialization of the 9th Variation in . This representation leads to a “supertableau” expression for the Littlewood–Richardson polynomials $c_{\lambda\mu}^{\nu}(a)$ , although that expression is neither manifestly positive, nor stable.

After the first version of this paper was completed we have learned of an independent work of V. Kreiman , where a positive equivariant Littlewood–Richardson rule was given. That rule is equivalent to our Theorem 2.1 although the proof in is different. Moreover, Kreiman’s paper also provides a weight-preserving bijection between the Knutson–Tao puzzles and the barred tableaux used in Theorem 2.1.

This work was inspired by Bill Fulton’s lectures . I am grateful to Bill for stimulating discussions.

Multiplication rule

where $\rho\to\sigma$ means that $\sigma$ is obtained from $\rho$ by adding one box. Let $r_{i}$ denote the row number of the box added to the diagram $\rho^{(i-1)}$ . The sequence $r_{1}r_{2}\dots r_{l}$ is called the Yamanouchi symbol of $R$ . Introduce the ordering on the set of boxes of a diagram $\lambda$ by reading them by columns from left to right and from bottom to top in each column. We call this the column order. We shall write $\alpha\prec\beta$ if $\alpha$ (strictly) precedes $\beta$ with respect to the column order. Given a sequence $R$ , construct the set $\mathcal{T}(\lambda,R)$ of barred reverse $\lambda$ -tableaux $T$ with entries from $\{1,2,\dots\}$ such that $T$ contains boxes $\alpha_{1},\dots,\alpha_{l}$ with

We will distinguish the entries in $\alpha_{1},\dots,\alpha_{l}$ by barring each of them. So, an element of $\mathcal{T}(\lambda,R)$ is a pair consisting of a reverse $\lambda$ -tableau and a chosen sequence of barred entries compatible with $R$ . We shall keep the notation $T$ for such a pair. For example, let $R$ be the sequence

so that the Yamanouchi symbol is $2\,3\,2\,1$ . Then for $\lambda=(5,5,3)$ the following barred $\lambda$ -tableau belongs to $\mathcal{T}(\lambda,R)$ :

. For each box $\alpha$ with $\alpha_{i}\prec\alpha\prec\alpha_{i+1}$ , $0\leqslant i\leqslant l$ , set $\rho(\alpha)=\rho^{(i)}$ . The barred entries $\overline{r}_{1},\dots,\overline{r}_{l}$ divide the tableau into regions marked by the elements of the sequence $R$ , as illustrated:

$\rho^{(0)}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mi>ρ</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></mrow><annotation encoding="application/x-tex">\rho^{(1)}</annotation></semantics></math>ρ(1)\overline{r}_{1}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msub><mover accent="true"><mi>r</mi><mo stretchy="true">‾</mo></mover><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">\overline{r}_{2}</annotation></semantics></math>r2\overline{r}_{l}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mi>ρ</mi><mrow><mo stretchy="false">(</mo><mi>l</mi><mo stretchy="false">)</mo></mrow></msup></mrow><annotation encoding="application/x-tex">\rho^{(l)}</annotation></semantics></math>ρ(l)\cdots$ . Finally, a reverse $\lambda$ -tableau $T$ will be called $\nu$ -bounded if

Note that $\nu$ -bounded $\lambda$ -tableaux exist only if $\lambda\subseteq\nu$ .

We are now in a position to state a rule for the calculation of the Littlewood-Richardson polynomials $c_{\lambda\mu}^{\nu}(a)$ defined by (1.3).

The polynomial $c_{\lambda\mu}^{\nu}(a)$ is zero unless $\mu\subseteq\nu$ . If $\mu\subseteq\nu$ then

summed over all sequences $R$ of the form (2.1) and all $\nu$ -bounded reverse $\lambda$ -tableaux $T\in\mathcal{T}(\lambda,R)$ . Moreover, for each factor occurring in the formula (2.2) we have $\rho(\alpha)_{T(\alpha)}>c(\alpha)$ .

Before proving the theorem, let us point out some properties of the Littlewood-Richardson polynomials which are immediate from the rule and consider some examples. The polynomial $c_{\lambda\mu}^{\nu}(a)$ is zero unless both diagrams $\lambda$ and $\mu$ are contained in $\nu$ and $|\lambda|+|\mu|\geqslant|\nu|$ . In this case $c_{\lambda\mu}^{\nu}(a)$ is a homogeneous polynomial in the $a_{i}$ of degree $|\lambda|+|\mu|-|\nu|$ . If $|\lambda|+|\mu|-|\nu|=0$ then the theorem reproduces a version of the classical Littlewood-Richardson rule; see Corollary 2.9 below. Note also that by the definition, the polynomials have the symmetry $c_{\lambda\mu}^{\nu}(a)=c_{\mu\lambda}^{\nu}(a)$ which is not apparent from the rule.

For the product of the double Schur functions $s_{(2)}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ and $s_{(2,1)}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ we have

For instance, the coefficient of $s_{(3,1)}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ is calculated by the following barred $(2)$ -tableaux

1 $\overline{1}$ $\overline{1}$ 12 $\overline{1}$ compatible with the sequence $(2,1)\to(3,1)$ . They contribute respectively $a_{-1}-a_{1}$ , $a_{-2}-a_{0}$ , $a_{1}-a_{2}$ which sums up to the coefficient $a_{-1}-a_{2}+a_{-2}-a_{0}$ . Alternatively, using the symmetry $c_{\lambda\mu}^{\nu}(a)=c_{\mu\lambda}^{\nu}(a)$ we can calculate the coefficient of $s_{(3,1)}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ by considering the barred $(2,1)$ -tableaux

$\overline{1}$ $\overline{2}$ 11 $\overline{2}$ $\overline{1}$ compatible with the sequences $(2)\to(3)\to(3,1)$ and $(2)\to(2,1)\to(3,1)$ , respectively. Their contributions to the coefficient are $a_{-2}-a_{0}$ and $a_{-1}-a_{2}$ .

For the calculation of $c_{(4,2,1)\hskip 1.0pt(2,2)}^{(5,2,2)}(a)$ take $\lambda=(4,2,1)$ , $\mu=(2,2)$ and $\nu=(5,2,2)$ . We have ten sequences $R$ of the form (2.1) but the set $\mathcal{T}(\lambda,R)$ contains $\nu$ -bounded tableaux only for three of them. For the sequence $R_{1}$ with the Yamanouchi symbol $1\,3\,3\,1\,1$ , the set $\mathcal{T}(\lambda,R_{1})$ contains two bounded barred tableaux

$\overline{1}$ 2 $\overline{3}$ 2 $\overline{3}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>1</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{1}</annotation></semantics></math>1\overline{1}$ $\overline{1}$ 2 $\overline{3}$ 1 $\overline{3}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>1</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{1}</annotation></semantics></math>1\overline{1}$ whose contributions to the Littlewood–Richardson polynomial are $(a_{0}-a_{3})(a_{0}-a_{2})$ and $(a_{0}-a_{3})(a_{-2}-a_{1})$ , respectively. For the sequence $R_{2}$ with the Yamanouchi symbol $1\,3\,1\,3\,1$ , the set $\mathcal{T}(\lambda,R_{2})$ contains the bounded tableaux

$\overline{1}$ 2 $\overline{3}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>1</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{1}</annotation></semantics></math>1\overline{3}$ $\overline{1}$ 1 $\overline{1}$ 2 $\overline{3}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>1</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{1}</annotation></semantics></math>1\overline{3}$ 1 $\overline{1}$ with the respective contributions $(a_{0}-a_{3})(a_{-4}-a_{-2})$ and $(a_{0}-a_{3})(a_{-3}-a_{-1})$ . For the sequence $R_{3}$ with the Yamanouchi symbol $3\,1\,3\,1\,1$ , the set $\mathcal{T}(\lambda,R_{3})$ contains the only bounded tableau

12 $\overline{3}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>1</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{1}</annotation></semantics></math>1\overline{3}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>1</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{1}</annotation></semantics></math>1\overline{1}$ with the contribution $(a_{-1}-a_{3})(a_{0}-a_{3})$ . Hence,

Taking $\lambda=(2,2)$ , $\mu=(4,2,1)$ and $\nu=(5,2,2)$ we get two sequences with the Yamanouchi symbols $1\,3$ and $3\,1$ . The corresponding sets $\mathcal{T}(\lambda,R)$ consist of five and four bounded barred tableaux, respectively, thus leading to a slightly longer calculation. ∎

The coefficient $c_{\lambda\mu}^{\nu}(a,b)$ is zero unless $\mu\subseteq\nu$ . If $\mu\subseteq\nu$ then

summed over all sequences $R$ of the form (2.1) and all reverse $\lambda$ -tableaux $T\in\mathcal{T}(\lambda,R)$ .

This is essentially a reformulation of the main result of (Theorem 3.1). Note that the summation in (2.4) is taken over all barred tableaux $T\in\mathcal{T}(\lambda,R)$ (not just over the $\nu$ -bounded ones as in (2.2)). Rather than repeating the whole argument of , we only sketch the main steps of the proof and indicate the necessary changes to be made. We refer the reader to for the details.

We assume that all diagrams here have at most $n$ rows. If $\rho=(\rho_{1},\dots,\rho_{n})$ is a such diagram, we set

Under the correspondence (1.10) we have $a_{\rho}=u_{\rho}=(u_{\rho_{1}+n},\dots,u_{\rho_{n}+1})$ , the latter notation was used in .

The starting point is the Vanishing Theorem of whose proof was also reproduced in . By that theorem,

The first claim of the lemma follows from the Vanishing Theorem which also implies

This proves (2.4) for the case $\nu=\mu$ . Now we suppose that $|\nu|-|\mu|\geqslant 1$ and proceed by induction on $|\nu|-|\mu|$ . The induction step is based on the recurrence relation

which was proved in [17, Proposition 3.4]; see also . Suppose that the diagram $\nu$ is obtained from $\mu$ by adding one box in row $r$ . Then

Now use the definition (1.9) of the double Schur polynomials. Since the $n$ -tuples $a_{\nu}$ and $a_{\mu}$ only differ at the $r$ -th component, the ratio on the right hand side of (2.6) can be expanded by taking into account the entries $r$ of the reverse $\lambda$ -tableaux $T$ . We need the following formula, where we are thinking of $y=(a_{\nu})_{r}$ , $z=(a_{\mu})_{r}$ and $m_{i}=b_{T(\alpha)-c(\alpha)}$ as $\alpha$ runs over the boxes of $T$ with $T(\alpha)=r$ in column order:

The right hand side of (2.6) can now be interpreted as the right hand side of (2.4), where $R$ is the only sequence $\mu\to\nu$ and the sum is taken over the reverse $\lambda$ -tableaux $T$ with one barred entry $r$ , as illustrated:

We can represent the above calculation of $c_{\lambda\mu}^{\nu}(a)$ by the “diagrammatic” relation

Set $s=r+1$ . Exactly as in the case $|\nu|-|\mu|=1$ , we have the following diagrammatic relations:

$\mu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mi>r</mi><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{r}</annotation></semantics></math>r\overline{s}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>ρ</mi></mrow><annotation encoding="application/x-tex">\rho</annotation></semantics></math>ρ\nu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>=</mo></mrow><annotation encoding="application/x-tex">=</annotation></semantics></math>=\rho<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mi>s</mi><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{s}</annotation></semantics></math>s\nu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>−</mo></mrow><annotation encoding="application/x-tex">-</annotation></semantics></math>−\mu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mi>s</mi><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{s}</annotation></semantics></math>s\nu$ and

$\mu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mi>r</mi><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{r}</annotation></semantics></math>r\overline{s}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>ρ</mi></mrow><annotation encoding="application/x-tex">\rho</annotation></semantics></math>ρ\nu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>=</mo></mrow><annotation encoding="application/x-tex">=</annotation></semantics></math>=\mu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mi>r</mi><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{r}</annotation></semantics></math>r\nu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>−</mo></mrow><annotation encoding="application/x-tex">-</annotation></semantics></math>−\mu<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mi>r</mi><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{r}</annotation></semantics></math>r\rho$ . Hence, the desired formula for $c_{\lambda\mu}^{\nu}(a,b)$ will follow if we prove the relation

the weights of the tableaux are preserved under the map.

Suppose now that the entry in the box $(i-1,j)$ is greater than $r+1$ , or this box is outside the diagram. Consider all entries $r$ in the row $i$ to the left of the box $(i,j)$ and suppose that they occupy the boxes $(i,j-m),\,(i,j-m+1),\dots,(i,j-1)$ . Then the image of the tableau under the map is the tableau obtained by replacing the entries in each of the boxes $(i,j-m),\dots,(i,j)$ with $s=r+1$ and barring the entry in the box $(i,j-m)$ . The weights of the tableaux are again preserved.

The inverse map is described in a similar way. This gives the desired weight-preserving bijection. The general argument uses similar calculations with the barred diagrams and a similar bijection described in . ∎

(i) A cohomological interpretation of the coefficients $c_{\lambda\mu}^{\nu}(a,b)$ and their puzzle computation can be found in .

(ii) The definition (2.3) of the coefficients $c_{\lambda\mu}^{\nu}(a,b)$ can be extended to the case where $\lambda$ is a skew diagram. Lemma 2.4 and its proof remain valid; see .

(iii) In contrast with the Littlewood–Richardson polynomials $c_{\lambda\mu}^{\nu}(a)$ , the coefficients $c_{\lambda\mu}^{\nu}(a,b)$ do not have the stability property as they depend on $n$ . ∎

Lemma 2.4 implies that the Littlewood–Richardson polynomials can be calculated by (2.4) with $b=a$ , that is, $c_{\lambda\mu}^{\nu}(a)=c_{\lambda\mu}^{\nu}(a,a)$ . Our strategy now is to show that (unlike the formula of Theorem 3.1 in ), the formula (2.4) (with $b=a$ ) is “nonnegative” in the sense that all nonzero products which occur in the formula are polynomials in the $a_{i}-a_{j}$ with $i<j$ . Then we demonstrate that the $\nu$ -boundness condition serves to eliminate the unwanted zero terms.

Let $R$ be a sequence of the form (2.1) and let $T\in\mathcal{T}(\lambda,R)$ . Suppose that

Then $\rho(\alpha)_{T(\alpha)}>c(\alpha)$ for all $\alpha\in\lambda$ with unbarred $T(\alpha)$ .

Suppose on the contrary that there exists a box $\alpha=(i,j)$ with an unbarred $T(i,j)$ and the condition $\rho(i,j)_{T(i,j)}<j-i$ ; the equality $\rho(i,j)_{T(i,j)}=j-i$ is excluded since this would violate (2.7). Choose such a box with the minimum possible value of $j$ . If all the entries $T(i,1),\dots,T(i,j-1)$ of $T$ are barred then $\rho(i,j)$ is obtained from $\mu$ by adding boxes in rows $T(i,1)\geqslant\dots\geqslant T(i,j-1)$ and, possibly, by adding other boxes. Since $T(i,j-1)\geqslant T(i,j)$ , we have $\rho(i,j)_{T(i,j)}\geqslant j-1$ , a contradiction. So, at least one of the entries $T(i,1),\dots,T(i,j-1)$ must be unbarred. Take such an unbarred entry $T(i,k)$ which is the closest to $T(i,j)$ , that is, all entries $T(i,k+1),\dots,T(i,j-1)$ are barred. Then $\rho(i,j)$ is obtained from $\rho(i,k)$ by adding boxes in rows $T(i,k+1)\geqslant\dots\geqslant T(i,j-1)$ and, possibly, by adding other boxes. Hence,

which implies $\rho(i,k)_{T(i,k)}<k-i+1$ . However, if $\rho(i,k)_{T(i,k)}=k-i$ then the factor in (2.7) corresponding to $\alpha=(i,k)$ is zero, which is impossible. Therefore $\rho(i,k)_{T(i,k)}<k-i$ which contradicts the choice of $j$ . ∎

Suppose that $R$ is a sequence of the form (2.1) and $T\in\mathcal{T}(\lambda,R)$ . If (2.7) holds then $T$ is $\nu$ -bounded.

By Lemma 2.6, for all unbarred entries $T(1,k)$ of the first row of the tableau $T$ we have $\rho(1,k)_{T(1,k)}\geqslant k$ . This implies $\nu_{T(1,k)}\geqslant k$ . If the entry $T(1,j)$ is barred then $\rho(1,k)_{T(1,k)}\geqslant k$ for the nearest unbarred entry $T(1,k)$ on its left (if it exists). Then $\nu$ is obtained from $\rho(1,k)$ by adding boxes in rows $T(1,k+1)\geqslant\dots\geqslant T(1,j)$ and, possibly, by adding other boxes. This implies $\nu_{T(1,j)}\geqslant j$ . Thus, this inequality holds for all $j=1,\dots,\lambda_{1}$ . This is equivalent to the $\nu$ -boundness of $T$ . ∎

Suppose that $R$ is a sequence of the form (2.1) and $T\in\mathcal{T}(\lambda,R)$ is $\nu$ -bounded. Then $\rho(\alpha)_{T(\alpha)}>c(\alpha)$ for all $\alpha\in\lambda$ with unbarred $T(\alpha)$ .

We argue by contradiction. Taking into account Lemma 2.6, we find that for some $\alpha=(i,j)$ with unbarred $T(\alpha)$ we have $\rho(i,j)_{T(i,j)}=j-i$ . Set $t=T(i,j)$ and consider all barred entries of $T$ (assuming for now they exist) which are equal to $t$ and occur to the right of the column $j$ . Since $T$ is a reverse tableau, these entries $\bar{t}$ can only occur in rows $1,2,\dots,i$ . Let $(r,k)$ be the box with the maximum column number $k$ containing $\bar{t}$ . Then the total number of such entries $\bar{t}$ does not exceed $k-j$ . This implies that the number of boxes $\nu_{t}$ in row $t$ of $\nu$ does not exceed $\rho(i,j)_{t}+k-j=k-i$ . Hence, $\nu^{\prime}_{k}\leqslant t-1$ . On the other hand, by the $\nu$ -boundness of $T$ we have $t=T(r,k)\leqslant T(1,k)\leqslant\nu^{\prime}_{k}$ , a contradiction.

If none of the boxes to the right of the column $j$ contains $\bar{t}$ then $\nu_{t}=\rho(i,j)_{t}=j-i$ . However, by the assumption, $\nu_{t}\geqslant\nu_{T(1,j)}\geqslant j$ , a contradiction. ∎

This completes the proof of the theorem. ∎

By the column word of a tableau $T$ we will mean the sequence of all entries of $T$ written in the column order.

Suppose that $|\nu|=|\lambda|+|\mu|$ . The Littlewood–Richardson coefficient $c_{\lambda\mu}^{\nu}$ equals the number of $\nu$ -bounded reverse $\lambda$ -tableaux $T$ whose column word coincides with the Yamanouchi symbol of a certain sequence $R$ of the form (2.1). ∎

This can be shown to be equivalent to a well-known version of the Littlewood–Richardson rule. Corollary 2.9 also holds with the $\nu$ -boundness condition dropped; see Lemma 2.7. By the corollary, $c_{\lambda\mu}^{\nu}$ counts the cardinality of the intersection of two finite sets: the set of column words of $\nu$ -bounded reverse $\lambda$ -tableaux and the set of Yamanouchi symbols of the sequences of the form (2.1).

Due to (1.10), the multiplication rule for the polynomials $s_{\lambda}(x|u)$ is obtained from Theorem 2.1 by replacing $a_{i}$ with $u_{n-i+1}$ for each $i$ . The corresponding coefficients are polynomials in the $u_{i}-u_{j}$ , $i>j$ , with positive integer coefficients. ∎

Suppose that the polynomials $c_{\lambda\mu}^{\nu}(a)$ are defined by the expansion (1.3) with $x=(x_{1},\dots,x_{n})$ . Then $c_{\lambda\mu}^{\nu}(a)$ is independent of $n$ as soon as $n\geqslant\nu^{\hskip 1.0pt\prime}_{1}$ . Moreover, if $n<\nu^{\hskip 1.0pt\prime}_{1}$ then $c_{\lambda\mu}^{\nu}(a)=0$ .

This follows from the boundness condition on the reverse tableaux. ∎

Applications

Then, due to [6, Lecture 8, Proposition 1.1] (see also ), the equivariant Schubert classes $\sigma_{\lambda}$ can be expressed by

Hence, Theorem 2.1 yields a multiplication rule for the equivariant Schubert classes. The corresponding stability property is implied by Corollary 2.11.

summed over all sequences $R$ of the form (2.1) and all $\nu$ -bounded reverse $\lambda$ -tableaux $T\in\mathcal{T}(\lambda,R)$ . In particular, the $d_{\lambda\mu}^{\,\nu}$ are polynomials in the $t_{i}-t_{j}$ , $i>j$ , with positive integer coefficients. Moreover, the coefficients $d_{\lambda\mu}^{\,\nu}$ , regarded as polynomials in the variables $a_{i}$ defined in (1.5), are independent of $n$ and $m$ , as soon as the inequalities $n\geqslant\lambda^{\prime}_{1}+\mu^{\prime}_{1}$ and $m\geqslant\lambda_{1}+\mu_{1}$ hold. ∎

For any $n\geqslant 3$ and $m\geqslant 4$ we have

The first manifestly positive rule for the expansion of $\sigma_{\lambda}\,\sigma_{\mu}$ was given by Knutson and Tao by using combinatorics of puzzles. Although the stability property was not pointed out in , it can be deduced directly from the puzzle rule or by applying the weight-preserving bijection between the puzzles and the barred tableaux constructed by Kreiman .

2 Quantum immanants and higher Capelli operators

Due to Olshanski , there exist filtration-preserving homomorphisms

which allow one to define the algebra ${\rm Z}$ of the virtual Casimir elements for the Lie algebra $\mathfrak{gl}_{\infty}$ as the inverse limit

The coefficient $f_{\lambda\mu}^{\nu}$ is zero unless $\mu\subseteq\nu$ . If $\mu\subseteq\nu$ then

summed over all sequences $R$ of the form (2.1) and all $\nu$ -bounded reverse $\lambda$ -tableaux $T\in\mathcal{T}(\lambda,R)$ . In particular, the $f^{\nu}_{\lambda\mu}$ are nonnegative integers.

Here we obtain one more rule for the calculation of the Littlewood–Richardson polynomials $c_{\lambda\mu}^{\nu}(a)$ . It relies on a supertableau representation of the double Schur polynomials $s_{\lambda}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ which is implied by the results of . This representation provides a “finite” version of the supertableau formulas of and ; cf. .

Fix a positive integer $n$ . For $r\geqslant 1$ set $u^{(r)}=(u_{1},\dots,u_{r})$ and use the 9th Variation in with the indeterminates $h_{rs}$ specialized by

and otherwise, where $h_{r}$ denotes the $r$ -th complete symmetric polynomial. Let us write $\widehat{s}_{\lambda/\mu}(u)$ for the corresponding Schur functions. Then (8.2) and (9.1) in give

summed over semistandard tableaux $T$ of shape $\lambda/\mu$ , such that the entries of the $i$ -th row do not exceed $n-\lambda_{i}+i$ . Furthermore, using (6.18)This formula in should be corrected by replacing $a^{(\lambda_{j}+n-j)}$ with $a^{(\lambda_{i}+n-i)}$ . and (9.6 ${\hskip 1.0pt}^{\prime}$ ) in we get

Equivalently, this can be interpreted as a combinatorial expression for the polynomials $s_{\lambda}(x|u)$ in terms of “supertableaux”. Identify the indices of $u$ with the symbols $1^{\prime},2^{\prime},\dots$ . A supertableau $T$ is obtained by filling in the diagram of $\lambda$ with the indices $1,\dots,n,1^{\prime},2^{\prime},\dots$ in such a way that in each row (resp. column) each primed index is to the right (resp. below) of each unprimed index; unprimed indices weakly increase along the rows and strictly increase down the columns; primed indices strictly increase along the rows and weakly increase down the columns; primed indices in column $j$ do not exceed $n-\lambda^{\prime}_{j}+j$ . Relation (4.5) implies the following.

summed over all $\lambda$ -supertableaux $T$ . ∎

Using (1.10), we get an analogous representation for the double Schur polynomials $s_{\lambda}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ . A reverse supertableau $T$ is obtained by filling in the diagram of $\lambda$ with the indices $1,\dots,n,n^{\prime},(n-1)^{\prime},\dots$ (including non-positive primed indices) in such a way that in each row (resp. column) each primed index is to the right (resp. below) of each unprimed index; unprimed indices weakly decrease along the rows and strictly decrease down the columns; primed indices strictly decrease along the rows and weakly decrease down the columns; primed indices in column $j$ are not less than $\lambda^{\prime}_{j}-j+1$ . The following supertableau representation of the polynomials $s_{\lambda}(x{\hskip 1.0pt||\hskip 1.0pt}a)$ follows from Proposition 4.1.

summed over all reverse $\lambda$ -supertableaux $T$ . ∎

Let $n=2$ and $\lambda=(2,1)$ . By the definition (1.9),

On the other hand, the reverse $(2,1)$ -supertableaux are

121122 $2^{\hskip 1.0pt\prime}$ 21 $2^{\hskip 1.0pt\prime}$ 22 $2^{\hskip 1.0pt\prime}$ 1112 $0^{\hskip 1.0pt\prime}$ 12 $1^{\hskip 1.0pt\prime}$ 12 $2^{\hskip 1.0pt\prime}$ $2^{\hskip 1.0pt\prime}$ 2 $0^{\hskip 1.0pt\prime}$ $2^{\hskip 1.0pt\prime}$ 2 $1^{\hskip 1.0pt\prime}$ $2^{\hskip 1.0pt\prime}$ 2 $2^{\hskip 1.0pt\prime}$ $2^{\hskip 1.0pt\prime}$ 1 $0^{\hskip 1.0pt\prime}$ $2^{\hskip 1.0pt\prime}$ 1 $1^{\hskip 1.0pt\prime}$ $2^{\hskip 1.0pt\prime}$ 1 $2^{\hskip 1.0pt\prime}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mn>2</mn><mrow><mspace width="0.1em"/><mo mathvariant="normal">′</mo></mrow></msup></mrow><annotation encoding="application/x-tex">2^{\hskip 1.0pt\prime}</annotation></semantics></math>2′2^{\hskip 1.0pt\prime}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mn>0</mn><mrow><mspace width="0.1em"/><mo mathvariant="normal">′</mo></mrow></msup></mrow><annotation encoding="application/x-tex">0^{\hskip 1.0pt\prime}</annotation></semantics></math>0′2^{\hskip 1.0pt\prime}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mn>2</mn><mrow><mspace width="0.1em"/><mo mathvariant="normal">′</mo></mrow></msup></mrow><annotation encoding="application/x-tex">2^{\hskip 1.0pt\prime}</annotation></semantics></math>2′1^{\hskip 1.0pt\prime}$ which yield

Formula (4.5) implies a supertableau representation of the coefficients $c_{\lambda\mu}^{\nu}(a,b)$ and hence, of the Littlewood–Richardson polynomials $c_{\lambda\mu}^{\nu}(a)$ . The representation for the latter is neither manifestly positive, nor stable; it provides an expression for $c_{\lambda\mu}^{\nu}(a)$ as an alternating sum of monomials in the $a_{i}$ . Given a sequence $R$ of the form (2.1), construct the set $\mathcal{S}(\lambda,R)$ of barred reverse $\lambda$ -supertableaux by analogy with $\mathcal{T}(\lambda,R)$ . A tableau $T\in\mathcal{S}(\lambda,R)$ must contain boxes $\alpha_{1},\dots,\alpha_{l}$ occupied by unprimed indices $r_{1},r_{2},\dots,r_{l}$ listed in the column order which is restricted to the subtableau of $T$ formed by the unprimed indices. As before, we distinguish the entries in $\alpha_{1},\dots,\alpha_{l}$ by barring each of them. For each box $\alpha$ with $\alpha_{i}\prec\alpha\prec\alpha_{i+1}$ , $0\leqslant i\leqslant l$ , which is occupied by an unprimed index, set $\rho(\alpha)=\rho^{(i)}$ .

The coefficients $c_{\lambda\mu}^{\nu}(a,b)$ defined in (2.3) can be given by

summed over sequences $R$ of the form (2.1) and reverse supertableaux $T\in\mathcal{S}(\lambda,R)$ .

Applying formula (4.5) we can reduce the calculation of $c^{\nu}_{\lambda\mu}(a,b)$ to the particular case of the sequence $b=(0)$ . Now (4.8) follows from Lemma 2.4. ∎

In order to calculate the Littlewood–Richardson polynomial $c_{(2,1)\,(2)}^{(2,1)}(a)$ we may take $n=2$ ; see Corollary 2.11. The barred reverse supertableaux compatible with the sequence $(2)\to(2,1)$ are

1 $\overline{2}$ 11 $\overline{2}$ 212 $\overline{2}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mn>2</mn><mrow><mspace width="0.1em"/><mo mathvariant="normal">′</mo></mrow></msup></mrow><annotation encoding="application/x-tex">2^{\hskip 1.0pt\prime}</annotation></semantics></math>2′\overline{2}$ 1 $2^{\hskip 1.0pt\prime}$ $\overline{2}$ 2 $2^{\hskip 1.0pt\prime}$ 2 $\overline{2}$ 1 $\overline{2}$ $0^{\hskip 1.0pt\prime}$ 1 $\overline{2}$ $1^{\hskip 1.0pt\prime}$ 1 $\overline{2}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mn>2</mn><mrow><mspace width="0.1em"/><mo mathvariant="normal">′</mo></mrow></msup></mrow><annotation encoding="application/x-tex">2^{\hskip 1.0pt\prime}</annotation></semantics></math>2′2^{\hskip 1.0pt\prime}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>2</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{2}</annotation></semantics></math>20^{\hskip 1.0pt\prime}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mn>2</mn><mrow><mspace width="0.1em"/><mo mathvariant="normal">′</mo></mrow></msup></mrow><annotation encoding="application/x-tex">2^{\hskip 1.0pt\prime}</annotation></semantics></math>2′\overline{2}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mn>1</mn><mrow><mspace width="0.1em"/><mo mathvariant="normal">′</mo></mrow></msup></mrow><annotation encoding="application/x-tex">1^{\hskip 1.0pt\prime}</annotation></semantics></math>1′2^{\hskip 1.0pt\prime}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mover accent="true"><mn>2</mn><mo stretchy="true">‾</mo></mover></mrow><annotation encoding="application/x-tex">\overline{2}</annotation></semantics></math>22^{\hskip 1.0pt\prime}$ so that

Introduction

Multiplication rule

Applications

2 Quantum immanants and higher Capelli operators

References