40.03.05 · combinatorics / symmetric-functions-rsk

The Littlewood-Richardson Rule, Skew Schur Functions, and Jeu de Taquin

shipped3 tiersLean: none

Anchor (Master): Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e (Oxford) Ch. I §5 and §9 (skew Schur functions, the Littlewood-Richardson rule, the $c^\lambda_{\mu\nu}$ as structure constants and skew expansion coefficients); Stanley 1999 *Enumerative Combinatorics, Volume 2* Ch. 7 Appendix A1 (jeu de taquin, the fundamental theorem of rectification, the proof of the LR rule); Fulton 1997 *Young Tableaux* (the plactic-monoid proof and the cohomology of the Grassmannian); Littlewood-Richardson 1934 *Phil. Trans. R. Soc. A* 233 (the original statement); Schützenberger 1977 (jeu de taquin and the plactic monoid); Knutson-Tao 1999 (honeycombs and the saturation theorem)

Intuition Beginner

In the previous unit, each Young diagram came with a symmetric expression, its Schur function. A natural question follows at once: if you multiply two of these expressions together, the answer is again symmetric, so it must be a combination of Schur functions. Which ones, and how many of each? The numbers that answer this are the Littlewood-Richardson coefficients, and they turn out to count something you can draw with boxes.

The pictures involved are skew shapes: take a big staircase of boxes and remove a smaller staircase from its top-left corner. What is left is a crooked band of boxes. You fill it by the same two house rules as before — values do not decrease across a row, and strictly increase down a column. The question of how Schur functions multiply becomes the question of how many such fillings have a special, balanced pattern as you read them off.

The tool that tames all of this is a sliding game called jeu de taquin (French for the teasing or fifteen-puzzle game). You start with a crooked filled band, find an empty corner, and slide boxes into the hole one move at a time, the way you slide tiles in a sliding puzzle. Keep sliding until the band is straightened into an ordinary staircase. The astonishing fact is that no matter which empty corner you start from or which order you slide, you always arrive at the same straightened filling. That stability is what makes the whole theory work, and it is the same idea that drives Schubert calculus in geometry later on.

Visual Beginner

A jeu de taquin slide. The skew band has an empty inner corner marked with a dot. A slide compares the box to the right of the hole and the box below it, and moves the smaller of the two into the hole; the hole travels outward. Repeat until no inner empty corner remains, and the crooked band has become a straight staircase.

stage	the band (• is the empty corner being filled)	what just happened
start	row 1: `• 2`, row 2: `1 3`	hole at top-left; neighbours are $2$ (right) and $1$ (below)
slide 1	row 1: `1 2`, row 2: `• 3`	the smaller neighbour $1$ moved up; hole dropped down
slide 2	row 1: `1 2`, row 2: `3 •`	the only neighbour $3$ moved left; hole exits
result	row 1: `1 2`, row 2: `3`	a straight tableau of shape (2,1)

Each slide picks the empty inner corner, looks at its right and lower neighbours, and pulls the smaller value into the hole; ties are broken by pulling the value from below. The hole migrates outward step by step until it leaves the diagram. Doing this repeatedly converts any crooked filled band into one ordinary staircase filling, called its rectification. The promise of the theory is that the straightened result never depends on the choices made along the way.

Worked example Beginner

Let us rectify the skew band of shape $(2, 2) / (1)$ : the missing box is the top-left, so the top row has a single box (to the right) and the bottom row has two boxes. Fill it with the top box holding $1$ , and the bottom row holding $1$ and $2$ . Drawn with a dot for the missing top-left box, it reads top row • 1 and bottom row 1 2.

Step 1. Find the empty inner corner. It is the dotted box at top-left. Its right neighbour holds $1$ ; its lower neighbour holds $1$ .

Step 2. Slide the smaller of the two into the hole. The two neighbours tie at $1$ , and the rule breaks ties by pulling the value from below. The lower $1$ moves up into the dotted box. Now the top row reads 1 1 and the hole has dropped to the lower-left, so the bottom row reads • 2.

Step 3. Find the new empty corner. It is the dotted box at bottom-left, whose only neighbour inside the band is the $2$ to its right.

Step 4. Slide that neighbour in. The $2$ moves left into the hole, and the hole exits the diagram. The bottom row now reads 2 in a single box at the left.

Step 5. Read the result. The straightened filling is top row 1 1 and bottom row a single 2. This is a legal staircase of shape rows $2$ and $1$ : the top row $11$ does not decrease, and the left column reads $1$ over $2$ , which strictly increases. The filling is legal.

What this tells us: sliding turned a crooked band into a clean staircase, and the rule that decides each move is purely local — compare two neighbours, pull the smaller (lower one on a tie). The same straightened picture is the bookkeeping key to multiplying Schur functions.

Check your understanding Beginner

Formal definition Intermediate+

Work in the ring $Λ$ of symmetric functions and with the Schur basis ${s_{λ}}$ of 40.03.02; partitions, Young diagrams, conjugates $λ^{'}$ , the dominance order, the involution $ω$ with $ω (s_{λ}) = s_{λ^{'}}$ , and the Hall inner product $⟨ s_{λ}, s_{μ} ⟩ = δ_{λ μ}$ are inherited from there. For partitions $μ \subseteq λ$ (containment of diagrams) the skew shape $λ / μ$ is the set of cells of $λ$ not in $μ$ .

Definition (skew Schur function). A semistandard tableau of skew shape $λ / μ$ is a filling of the cells of $λ / μ$ with entries in ${1, 2, \dots}$ , weakly increasing along rows and strictly increasing down columns. The skew Schur function is the weight generating function $$ s_{\lambda/\mu} ;=; \sum_{T \in \mathrm{SSYT}(\lambda/\mu)} x^{\mathrm{wt}(T)} ;\in; \Lambda, $$ homogeneous of degree $∣ λ ∣ - ∣ μ ∣$ . The skew Jacobi-Trudi determinant of 40.03.02 extends to $s_{λ / μ} = det (h_{λ_{i} - μ_{j} - i + j})$ , so $s_{λ / μ}$ is symmetric and Schur-positive. When $μ = \emptyset$ this is the ordinary $s_{λ}$ .

Definition (Littlewood-Richardson coefficients). The Schur basis is closed under multiplication, so there are unique integers $c_{μν}^{λ}$ with $$ s_\mu, s_\nu ;=; \sum_\lambda c^\lambda_{\mu\nu}, s_\lambda . $$ These are the Littlewood-Richardson coefficients. By the self-duality of the Schur basis, $c_{μν}^{λ} = ⟨ s_{μ} s_{ν}, s_{λ} ⟩ = ⟨ s_{ν}, s_{λ / μ} ⟩$ , so equivalently the skew Schur function expands as $$ s_{\lambda/\mu} ;=; \sum_\nu c^\lambda_{\mu\nu}, s_\nu . $$ The coefficient $c_{μν}^{λ}$ vanishes unless $μ, ν \subseteq λ$ , $∣ μ ∣ + ∣ ν ∣ = ∣ λ ∣$ , and (from dominance) $μ \cup ν$ -type constraints hold. Commutativity of the product gives $c_{μν}^{λ} = c_{ν μ}^{λ}$ ; applying $ω$ gives the conjugation symmetry $c_{μν}^{λ} = c_{μ^{'} ν^{'}}^{λ^{'}}$ .

Definition (reading word, lattice word, LR tableau). The reverse reading word of a tableau $T$ reads its entries right-to-left across each row, top row first. A word $w = w_{1} w_{2} \dots w_{N}$ in the alphabet ${1, 2, \dots}$ is a lattice word (or Yamanouchi/ballot word) if in every prefix $w_{1} \dots w_{k}$ the number of $i$ 's is at least the number of $(i + 1)$ 's, for every $i$ . A semistandard skew tableau is a Littlewood-Richardson tableau if its reverse reading word is a lattice word.

Definition (jeu de taquin). Given a skew tableau of shape $λ / μ$ , an inner corner is a cell of $μ$ with no cell of $μ$ to its right or below within $λ$ . A forward slide into an inner corner $c$ proceeds: among the cells of $λ / μ$ immediately to the right of and below $c$ , move the one with the smaller entry into $c$ (ties broken by moving the lower entry), creating a new hole at the vacated cell; repeat until the hole reaches an outer corner and exits. Iterating slides until no inner corner remains yields a straight-shape tableau $Rect (T)$ , the rectification of $T$ .

Counterexamples to common slips Intermediate+

"The reading word, not its reverse, should be a lattice word." The conventions are linked: with the reverse reading word (right-to-left, top-to-bottom) the lattice condition is the standard one for LR tableaux. Reading left-to-right instead requires reversing the lattice condition. Mixing the two miscounts $c_{μν}^{λ}$ .
" $c_{μν}^{λ}$ is always $0$ or $1$ ." It is for the Pieri cases $ν = (r)$ or $(1^{r})$ and for many small partitions, but in general it is an arbitrary non-negative integer. The smallest example with $c_{μν}^{λ} = 2$ has $μ = ν = (2, 1)$ and $λ = (3, 2, 1)$ : there are two LR tableaux of shape $(3, 2, 1) / (2, 1)$ and content $(2, 1)$ .
"Jeu de taquin's result depends on which corner you slide from." The content is conserved and the rules are local, but the depth of the theory is precisely that $Rect (T)$ does not depend on the slide order — this is the fundamental theorem (confluence), and without it the LR rule would be ill-posed.

Key theorem with proof Intermediate+

The signature theorem is the Littlewood-Richardson rule: the structure constants of the Schur basis are counts of explicit combinatorial objects.

Theorem (Littlewood-Richardson rule). For partitions $μ, ν, λ$ , $$ c^\lambda_{\mu\nu} ;=; #\big{,T : T \text{ is an LR tableau of skew shape } \lambda/\mu \text{ and content } \nu ,\big}, $$ the number of semistandard skew tableaux of shape $λ / μ$ and content $ν$ whose reverse reading word is a lattice word. Equivalently, $c_{μν}^{λ}$ is the number of semistandard tableaux of shape $λ / μ$ and content $ν$ that rectify under jeu de taquin to the unique superstandard tableau $U_{ν}$ (the straight-shape tableau of shape $ν$ with row $i$ filled entirely by $i$ ). In particular all $c_{μν}^{λ}$ are non-negative integers. ^{[Stanley §7.18, Appendix A1]}

Proof. The argument has two halves: jeu de taquin is well-defined (the fundamental theorem of rectification), and rectification computes the coefficients.

(i) Rectification is well-defined. Encode a tableau by its reading word and use Knuth equivalence (the plactic monoid of 40.03.04). Two words are Knuth-equivalent if related by the elementary relations $y z x \equiv y x z$ for $x \leq y < z$ and $x z y \equiv z x y$ for $x < y \leq z$ . A forward (or reverse) jeu de taquin slide changes the reading word only by a sequence of Knuth relations: each elementary move past one cell is one elementary Knuth transformation, as a direct check of the four local configurations shows. Hence $T$ and any slide of $T$ have Knuth-equivalent reading words. Knuth's theorem states that each Knuth-equivalence class of words contains exactly one tableau reading word, namely that of $P (w)$ , the insertion tableau of 40.03.04. Therefore every sequence of slides emptying $μ$ produces the same straight tableau, namely the one whose reading word is the canonical representative; this is $Rect (T)$ , independent of the slide order.

(ii) Rectification computes $c_{μν}^{λ}$ . Fix $ν$ . By the definition $s_{λ / μ} = \sum_{ν} c_{μν}^{λ} s_{ν}$ and the SSYT expansion of each side, the coefficient $c_{μν}^{λ}$ equals the number of SSYT $T$ of shape $λ / μ$ in any fixed Knuth class corresponding to $ν$ . Because rectification is a content-preserving bijection from SSYT of shape $λ / μ$ to pairs (straight tableau $Rect (T)$ , recording data) compatible with the Hall inner product, $⟨ s_{λ / μ}, s_{ν} ⟩$ counts those $T$ with $Rect (T) = U_{ν}$ , the lexicographically least tableau of shape $ν$ . The LR (lattice-word) condition on the reverse reading word is exactly the condition $Rect (T) = U_{ν}$ : a skew semistandard tableau rectifies to $U_{ν}$ if and only if its reverse reading word is a lattice word of content $ν$ , since $U_{ν}$ is the unique tableau whose own reading word is the lattice word $ν_{ℓ}^{ν_{ℓ}} \dots 1^{ν_{1}}$ read appropriately, and Knuth equivalence preserves the lattice property of the canonical representative. Counting gives the two stated forms of $c_{μν}^{λ}$ . $□$

Bridge. This theorem is the foundational reason the Schur basis is computationally tractable: it builds toward the entire structure theory of $Λ$ by turning an algebraic question — how Schur functions multiply — into a finite count of pictures, and the same count appears again in the cohomology of the Grassmannian, where the $c_{μν}^{λ}$ are Schubert intersection numbers. This is exactly the statement that the Schur structure constants are non-negative, which generalises the Pieri rules of 40.03.02 (the cases $ν = (r)$ and $ν = (1^{r})$ ) and is dual to the skew expansion through the Hall inner product of 40.03.03. The central insight is that jeu de taquin and Knuth equivalence are one phenomenon: putting these together, the well-definedness of rectification (a sliding-puzzle confluence) and the bijective proof of the Cauchy identity by RSK in 40.03.04 are two readings of the plactic monoid, and the bridge is that the lattice-word condition records precisely which skew fillings carry the canonical representative of their Knuth class.

Exercises Intermediate+

Exercise 2 (easy, symbolic).

Rectify the skew tableau of shape $(3, 2) / (2)$ : the top row has a single box (after the two missing boxes) holding $2$ , and the bottom row holds $13$ . Give the straight shape and filling.

Hint

The inner corner is the rightmost missing cell of the top row. Slide the smaller of its right/below neighbours in, and repeat.

Answer

The band is top row • 2 (with one earlier missing cell off to the left), bottom row 1 3 sitting under the missing region. Working the inner corner adjacent to the entries: the corner's neighbours are $2$ (right) and $1$ (below); the smaller is $1$ , which slides up. The top then reads 1 2 and the hole drops, after which $3$ slides left. Result: shape $(2, 1)$ with top row $12$ and bottom row $3$ . The top row does not decrease and the left column $1$ over $3$ strictly increases. Rubric: full credit for the correct slides and the final straight tableau $Rect = 132$ .

Exercise 3 (medium, numeric).

Use the LR rule to compute $c_{(1), (1, 1)}^{(2, 1)}$ by counting LR tableaux of shape $(2, 1) / (1)$ and content $(1, 1)$ .

Hint

The skew shape $(2, 1) / (1)$ has two cells: the top-right cell and the bottom-left cell. Fill with content $(1, 1)$ (one $1$ , one $2$ ) so columns strictly increase and the reverse reading word is a lattice word.

Answer

$1$ . The cells are the top-right and the bottom-left; they share no row or column, so the column rule is automatic. Content $(1, 1)$ forces a $1$ and a $2$ . The reverse reading word reads the top row (just the top-right cell) then the bottom row. For a lattice word the first letter must be $1$ , so the top-right cell holds $1$ and the bottom-left holds $2$ ; word $= 1, 2$ , a lattice word. The other assignment gives word $2, 1$ , not lattice. Hence one LR tableau, $c = 1$ . This matches $s_{(2, 1) / (1)} = s_{(2)} + s_{(1, 1)}$ , so the $s_{(1, 1)}$ coefficient is $1$ . Rubric: full credit for the single valid filling and the lattice check.

Exercise 5 (medium, numeric).

Compute $c_{(2, 1), (2, 1)}^{(3, 2, 1)}$ by counting LR tableaux of shape $(3, 2, 1) / (2, 1)$ and content $(2, 1)$ .

Hint

The skew shape $(3, 2, 1) / (2, 1)$ has three cells: the rightmost cell of row $1$ , the rightmost cell of row $2$ , and the cell of row $3$ . Fill with two $1$ 's and one $2$ , column-strict, with a lattice reverse reading word.

Answer

$2$ . Cells: $(1, 3)$ , $(2, 2)$ , $(3, 1)$ — pairwise in distinct rows and columns, so column-strictness is automatic. Content $(2, 1)$ means two $1$ 's and one $2$ . The reverse reading word reads $(1, 3)$ , then $(2, 2)$ , then $(3, 1)$ . For a lattice word the first letter is $1$ , so $(1, 3) = 1$ . The remaining cells $(2, 2), (3, 1)$ get one $1$ and one $2$ in either order: words $1, 1, 2$ and $1, 2, 1$ are both lattice. Hence two LR tableaux, $c_{(2, 1), (2, 1)}^{(3, 2, 1)} = 2$ — the smallest LR coefficient exceeding $1$ . Rubric: full credit for both valid fillings and the lattice verification.

Exercise 6 (hard, symbolic).

Prove that a jeu de taquin forward slide changes the reading word of a tableau only by Knuth relations, for the local configuration where the hole at cell $c$ has right neighbour $b$ and lower neighbour $a$ with $a \leq b$ (so $a$ slides up).

Hint

Write the relevant fragment of the reading word before and after the slide and identify the elementary Knuth move $y z x \equiv y x z$ or $x z y \equiv z x y$ .

Answer

Before the slide, the lower neighbour $a$ precedes the entry above-right of it in the reading order, and the right neighbour $b$ sits in the row above. The semistandard conditions give the inequalities $a \leq b$ (slide hypothesis) and, with the cell $d$ above $b$ in $b$ 's column, $d < b$ . Reading the affected three entries in the reverse reading word produces a fragment $d b a$ (or its row-local analogue) which, under $a \leq d < b$ , is an instance of $x z y \equiv z x y$ with $x = a, y = d, z = b$ after the slide reorders them to $d a b$ ; one checks the inequality pattern $x < y \leq z$ matches. Each elementary slide step thus realises exactly one Knuth relation, and concatenating over the path of the hole shows the whole slide is a Knuth equivalence. Rubric: full credit for exhibiting the three-letter fragment, the matching inequalities, and the identification with the elementary relation. (Either Knuth relation, correctly matched to the local inequalities, earns full credit.)

Exercise 7 (hard, symbolic).

Derive the symmetry $c_{μν}^{λ} = c_{ν μ}^{λ}$ from the associativity and commutativity of the product on $Λ$ , and explain why the LR rule's combinatorial description (which treats $μ$ and $ν$ asymmetrically) nonetheless produces a symmetric number.

Hint

$c_{μν}^{λ}$ is the coefficient of $s_{λ}$ in $s_{μ} s_{ν}$ . The ring $Λ$ is commutative.

Answer

Since $Λ$ is a commutative ring, $s_{μ} s_{ν} = s_{ν} s_{μ}$ ; equating Schur expansions, $\sum_{λ} c_{μν}^{λ} s_{λ} = \sum_{λ} c_{ν μ}^{λ} s_{λ}$ , and as ${s_{λ}}$ is a basis, $c_{μν}^{λ} = c_{ν μ}^{λ}$ for all $λ$ . The LR rule counts LR tableaux of shape $λ / μ$ and content $ν$ — visibly asymmetric in $μ$ (the removed inner shape) and $ν$ (the content). That the count is symmetric is a non-obvious combinatorial fact, proved bijectively by the commutativity of jeu de taquin / Knuth equivalence (or by symmetry-establishing maps such as those of Hahn, Schützenberger's involution, or the hive/honeycomb model). The algebraic symmetry is immediate; the combinatorial symmetry is a theorem requiring an explicit bijection. Rubric: full credit for the commutativity derivation and for articulating the asymmetry-of-description versus symmetry-of-count distinction.

Advanced results Master

The Littlewood-Richardson coefficients are simultaneously algebraic structure constants, geometric intersection numbers, and representation-theoretic multiplicities, and the same numbers obey deep positivity and saturation laws.

Theorem 1 (the three interpretations). The integer $c_{μν}^{λ}$ equals: (a) the structure constant $s_{μ} s_{ν} = \sum_{λ} c_{μν}^{λ} s_{λ}$ in $Λ$ and the skew expansion coefficient $s_{λ / μ} = \sum_{ν} c_{μν}^{λ} s_{ν}$ ; (b) the multiplicity of the irreducible $GL_{n} (C)$ -representation $V_{λ}$ of highest weight $λ$ in the tensor product $V_{μ} \otimes V_{ν}$ (a Clebsch-Gordan number), cross-referenced to 07.05.04; (c) the multiplicity of the irreducible $S_{∣ λ ∣}$ -module $S^{λ}$ in the induction $Ind_{S_{∣ μ ∣} \times S_{∣ ν ∣}}^{S_{∣ λ ∣}} (S^{μ} ⊠ S^{ν})$ , via the Frobenius characteristic of the co-produced 40.03.06. The equivalence of (a)-(c) is the statement that the characteristic map is a ring isomorphism carrying induction product to the symmetric-function product ^{[Macdonald §5, §9]}.

Theorem 2 (jeu de taquin, the plactic monoid, and rectification). Knuth equivalence is the congruence on words generated by the elementary relations $y z x \equiv y x z$ ( $x \leq y < z$ ) and $x z y \equiv z x y$ ( $x < y \leq z$ ); the quotient is the plactic monoid. Every word is Knuth-equivalent to the reading word of a unique tableau $P (w)$ , and two skew tableaux have the same rectification if and only if their reading words are Knuth-equivalent. Jeu de taquin slides preserve the Knuth class, so $Rect (T) = P (read (T))$ is independent of slide order — the confluence / fundamental theorem of rectification. The LR coefficient $c_{μν}^{λ}$ is the number of skew tableaux of shape $λ / μ$ and content $ν$ rectifying to $U_{ν}$ , equivalently the number with lattice reverse reading word ^{[Fulton Ch. 2-5]}.

Theorem 3 (Schubert calculus on the Grassmannian). In the cohomology ring $H^{*} (Gr (k, n); Z)$ of the Grassmannian of $k$ -planes in $C^{n}$ , the Schubert classes $σ_{λ}$ (indexed by partitions $λ$ in the $k \times (n - k)$ box) form an additive basis, and $$ \sigma_\mu \cdot \sigma_\nu ;=; \sum_\lambda c^\lambda_{\mu\nu}, \sigma_\lambda , $$ so the Littlewood-Richardson coefficients are the Schubert intersection numbers — the number of $k$ -planes meeting fixed flags in prescribed Schubert conditions, when the count is finite. This identifies $H^{*} (Gr)$ with a quotient of $Λ$ by the Schur functions leaving the box, cross-referenced to the algebraic geometry of intersection theory.

Theorem 4 (saturation). The saturation theorem of Knutson and Tao states: for all $N \geq 1$ , $$ c^{N\lambda}{N\mu,,N\nu} > 0 \quad\Longleftrightarrow\quad c^\lambda{\mu\nu} > 0 . $$ The proof models $c_{μν}^{λ}$ as the number of integer points of the hive polytope (equivalently the count of honeycombs with boundary $(μ, ν, λ)$ ); non-emptiness of the polytope is scale-invariant, while a polytope with rational vertices that contains a point at scale $N$ contains an integer point at scale $1$ because the hive polytope has integral vertices. A corollary is Horn's conjecture, characterising the possible spectra $(μ, ν, λ)$ of triples of Hermitian matrices $A + B = C$ by a recursive system of LR-positivity inequalities ^{[Macdonald §5]}.

Synthesis. Putting these together, the Littlewood-Richardson coefficient is the point at which algebra, geometry, and representation theory coincide: the foundational reason is that the Frobenius characteristic of the co-produced 40.03.06 is a ring isomorphism, so the multiplication in $Λ$ is at once the tensor product of $GL_{n}$ -modules of 07.05.04, the induction product of symmetric-group modules of 07.05.02, and the cup product in the cohomology of the Grassmannian. This is exactly why a single non-negative integer governs all three, and why the Pieri rules of 40.03.02 are the universal special cases $ν = (r), (1^{r})$ that generalise to the full rule. The central insight is that jeu de taquin and the RSK correspondence of the co-produced 40.03.04 are two windows on the plactic monoid: rectification computes the Knuth class, and the bridge is that the Cauchy identity proved by RSK and the well-definedness of rectification are the same statement about that monoid, dual to each other through the Hall inner product of the co-produced 40.03.03. The saturation theorem then shows the positivity of these numbers is governed by a polytope with integral vertices, so the discrete count and the continuous (honeycomb) model carry the same information — the combinatorics of sliding boxes is dual to the convex geometry of hives, and both compute the geometry of intersecting Schubert cycles.

Full proof set Master

Proposition 1 (skew Schur functions are Schur-positive). For $μ \subseteq λ$ , $s_{λ / μ} = \sum_{ν} c_{μν}^{λ} s_{ν}$ with each $c_{μν}^{λ} \in Z_{\geq 0}$ .

Proof. By definition $s_{λ / μ} \in Λ$ is symmetric (the skew Jacobi-Trudi determinant exhibits it as a polynomial in the $h_{k}$ ), hence a $Z$ -linear combination $\sum_{ν} a_{ν} s_{ν}$ of Schur functions. Pairing with $s_{ν}$ under the Hall inner product of 40.03.03, $a_{ν} = ⟨ s_{λ / μ}, s_{ν} ⟩$ . The defining adjunction of skewing is $⟨ s_{λ / μ}, s_{ν} ⟩ = ⟨ s_{λ}, s_{μ} s_{ν} ⟩ = c_{μν}^{λ}$ , using that multiplication by $s_{μ}$ and skewing by $s_{μ}$ are adjoint and that ${s_{λ}}$ is orthonormal. Thus $a_{ν} = c_{μν}^{λ}$ . Non-negativity follows from the Littlewood-Richardson rule (Proposition 3): $c_{μν}^{λ}$ is a cardinality of a set of tableaux. $□$

Proposition 2 (well-definedness of rectification). For a skew tableau $T$ , every sequence of jeu de taquin slides emptying the inner shape produces the same straight-shape tableau, equal to $P (read (T))$ .

Proof. It suffices that each elementary slide step preserves the Knuth-equivalence class of the reading word, since by Knuth's theorem (the plactic monoid of 40.03.04) each class contains exactly one tableau reading word, namely $read (P (w))$ . Consider one step of a forward slide: the hole at cell $c$ has right neighbour $b$ and lower neighbour $a$ . If only one neighbour exists, the entry slides with no reordering of the reading word beyond a transposition of a letter past the (un-read) hole, leaving the word unchanged as a word. If both exist, semistandardness gives $a$ in the column below $c$ with the entry $b$ to the right; the slide moves $min (a, b)$ (lower on tie) into $c$ . Tracking the three local entries through the reverse reading word, the reordering is precisely one of the elementary Knuth relations $y z x \equiv y x z$ ( $x \leq y < z$ ) or $x z y \equiv z x y$ ( $x < y \leq z$ ), the inequalities supplied by the row-weak/column-strict conditions; a case check over the four sign patterns confirms each step is a single Knuth move. Composing along the hole's outward path, the slide is a Knuth equivalence. Two slide orders therefore yield Knuth-equivalent reading words, hence the same canonical tableau. $□$

Proposition 3 (Littlewood-Richardson rule). $c_{μν}^{λ}$ equals the number of LR tableaux of shape $λ / μ$ and content $ν$ .

Proof. By Proposition 1, $c_{μν}^{λ} = ⟨ s_{λ / μ}, s_{ν} ⟩$ counts, with the orthonormality of the Schur basis, the SSYT of shape $λ / μ$ in the Knuth class of $s_{ν}$ . A skew SSYT $T$ contributes to the $s_{ν}$ -component precisely when $Rect (T) = U_{ν}$ , the superstandard tableau of shape $ν$ (row $i$ all $i$ 's), since $U_{ν}$ is the unique straight tableau of content $ν$ that is its own rectification and whose reading word is the canonical lattice representative. It remains to identify ${T : Rect (T) = U_{ν}}$ with the LR tableaux. The reading word of $U_{ν}$ is the lattice (ballot) word in which, reading $U_{ν}$ by reverse reading order, every prefix has at least as many $i$ 's as $(i + 1)$ 's. Knuth equivalence preserves the property of being Knuth-equivalent to a lattice word; and a skew SSYT $T$ has reverse reading word Knuth-equivalent to that of $U_{ν}$ if and only if its own reverse reading word is itself a lattice word of content $ν$ — because among all words in a Knuth class, the reverse reading words that are lattice are exactly those whose insertion tableau is superstandard. Hence $Rect (T) = U_{ν} ⟺ T$ is an LR tableau of content $ν$ , and the two counts coincide. $□$

Proposition 4 (Pieri as a special case). $c_{μ, (r)}^{λ} = 1$ if $λ / μ$ is a horizontal $r$ -strip and $0$ otherwise; $c_{μ, (1^{r})}^{λ} = 1$ if $λ / μ$ is a vertical $r$ -strip and $0$ otherwise.

Proof. Take $ν = (r)$ . An LR tableau of shape $λ / μ$ and content $(r)$ has all entries equal to $1$ (content $(r)$ means $r$ ones). Column-strictness forbids two $1$ 's in a column, so $λ / μ$ has at most one cell per column: it is a horizontal strip. The reverse reading word is $1^{r}$ , automatically lattice. There is exactly one such filling when $λ / μ$ is a horizontal $r$ -strip, and none otherwise, giving $c_{μ, (r)}^{λ} \in {0, 1}$ as stated — the Pieri rule $s_{μ} h_{r} = \sum s_{λ}$ of 40.03.02. Dually $ν = (1^{r})$ forces content $(1, 1, \dots, 1)$ with entries $1, \dots, r$ ; column-strictness and the lattice condition force each value once with the $i$ 's weakly left of the $(i + 1)$ 's and no two in a row, so $λ / μ$ is a vertical $r$ -strip, giving the conjugate Pieri rule. Equivalently, apply $ω$ to the horizontal case. $□$

Proposition 5 (conjugation symmetry). $c_{μν}^{λ} = c_{μ^{'} ν^{'}}^{λ^{'}}$ .

Proof. The involution $ω$ of 40.03.02 is a ring automorphism of $Λ$ with $ω (s_{κ}) = s_{κ^{'}}$ for every partition $κ$ . Apply $ω$ to $s_{μ} s_{ν} = \sum_{λ} c_{μν}^{λ} s_{λ}$ : since $ω$ is multiplicative, $ω (s_{μ}) ω (s_{ν}) = \sum_{λ} c_{μν}^{λ} ω (s_{λ})$ , i.e. $s_{μ^{'}} s_{ν^{'}} = \sum_{λ} c_{μν}^{λ} s_{λ^{'}}$ . Re-indexing by $κ = λ^{'}$ (a bijection on partitions, since conjugation is involutive) gives $s_{μ^{'}} s_{ν^{'}} = \sum_{κ} c_{μν}^{κ^{'}} s_{κ}$ . Comparing with the definition $s_{μ^{'}} s_{ν^{'}} = \sum_{κ} c_{μ^{'} ν^{'}}^{κ} s_{κ}$ and using that ${s_{κ}}$ is a basis, $c_{μ^{'} ν^{'}}^{κ} = c_{μν}^{κ^{'}}$ for all $κ$ , which is the claim with $λ = κ^{'}$ . $□$

Connections Master

This unit is built directly on the Schur functions of 40.03.02: the skew Schur function $s_{λ / μ}$ extends the SSYT and Jacobi-Trudi definitions there, the Pieri rules proved there ( $s_{μ} h_{r}$ , $s_{μ} e_{r}$ ) are the special cases $ν = (r), (1^{r})$ of the Littlewood-Richardson rule, and the involution $ω$ with $ω (s_{λ}) = s_{λ^{'}}$ of 40.03.01 supplies the conjugation symmetry $c_{μν}^{λ} = c_{μ^{'} ν^{'}}^{λ^{'}}$ . The orthonormality and Hall inner product of the co-produced 40.03.03 are what make $c_{μν}^{λ} = ⟨ s_{μ} s_{ν}, s_{λ} ⟩ = ⟨ s_{ν}, s_{λ / μ} ⟩$ , identifying the structure constants with the skew expansion coefficients.
Jeu de taquin is the sliding cousin of the RSK insertion of the co-produced 40.03.04: both are governed by the plactic monoid (Knuth equivalence), and the well-definedness of rectification is the same theorem about that monoid that underlies the bijectivity of RSK and the combinatorial proof of the Cauchy identity. The Frobenius characteristic of the co-produced 40.03.06 carries the LR coefficients to the induction multiplicities $Ind (S^{μ} ⊠ S^{ν}) \supseteq S^{λ}$ of the symmetric groups, turning the multiplication rule into a character-theoretic branching law.
The Littlewood-Richardson coefficients are the structure constants of the cohomology of the Grassmannian, where they are the Schubert intersection numbers, linking this unit to algebraic geometry and intersection theory; the same numbers are the tensor-product (Clebsch-Gordan) multiplicities for $GL_{n}$ of 07.05.04 and the symmetric-group induction multiplicities of 07.05.02. The saturation theorem connects them to the convex geometry of hive/honeycomb polytopes and, through Horn's problem, to the eigenvalues of sums of Hermitian matrices, cross-referencing the spectral theory of self-adjoint operators.

Historical & philosophical context Master

The multiplication rule for Schur functions was first stated by Dudley Littlewood and Archibald Richardson in their 1934 paper Group characters and algebra in the Philosophical Transactions of the Royal Society ^{[Littlewood-Richardson 1934]}, in the language of $S_{n}$ -character products; their formulation was correct but their proof had gaps, and a complete proof did not appear for several decades. The combinatorial machinery that finally settled it — jeu de taquin and the plactic monoid — is due to Marcel-Paul Schützenberger, whose 1977 work on the plactic monoid and the sliding algorithm established the confluence of rectification and with it the rule ^{[Schützenberger 1977]}; complete proofs in the modern style are given by Thomas, Macdonald, Fulton, and Stanley.

The identification of the $c_{μν}^{λ}$ with Schubert intersection numbers on the Grassmannian descends from the nineteenth-century enumerative geometry of Hermann Schubert, made rigorous in the twentieth century and reorganised by the Schur-function dictionary. The saturation theorem was proved by Allen Knutson and Terence Tao in 1999 via the honeycomb model ^{[Knutson-Tao 1999]}, resolving the long-standing saturation conjecture and, in combination with work of Klyachko, settling Horn's 1962 conjecture on the spectra of sums of Hermitian matrices. The honeycomb and hive models recast a count of tableaux as the lattice-point enumeration of an integral polytope, a translation between the discrete combinatorics of sliding boxes and the convex geometry of moment polytopes.

Bibliography Master

@article{littlewoodrichardson1934,
  author  = {Littlewood, Dudley E. and Richardson, Archibald R.},
  title   = {Group characters and algebra},
  journal = {Philosophical Transactions of the Royal Society A},
  volume  = {233},
  pages   = {99--141},
  year    = {1934}
}

@article{schutzenberger1977,
  author  = {Sch\"{u}tzenberger, Marcel-Paul},
  title   = {La correspondance de Robinson},
  journal = {Combinatoire et repr\'{e}sentation du groupe sym\'{e}trique (Lecture Notes in Mathematics)},
  volume  = {579},
  pages   = {59--113},
  publisher = {Springer},
  year    = {1977}
}

@article{knutsontao1999,
  author  = {Knutson, Allen and Tao, Terence},
  title   = {The honeycomb model of $GL_n(\mathbb{C})$ tensor products I: Proof of the saturation conjecture},
  journal = {Journal of the American Mathematical Society},
  volume  = {12},
  number  = {4},
  pages   = {1055--1090},
  year    = {1999}
}

@book{fulton1997young,
  author    = {Fulton, William},
  title     = {Young Tableaux: With Applications to Representation Theory and Geometry},
  series    = {London Mathematical Society Student Texts},
  volume    = {35},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@book{stanley1999ec2,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 2},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {62},
  publisher = {Cambridge University Press},
  year      = {1999}
}

@book{macdonald1995symmetric,
  author    = {Macdonald, Ian G.},
  title     = {Symmetric Functions and Hall Polynomials},
  series    = {Oxford Mathematical Monographs},
  edition   = {2},
  publisher = {Oxford University Press},
  year      = {1995}
}

Prerequisites

40.03.02

Tier anchors

beginner: Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) §7.10-7.15 opening (skew shapes and the product of Schur functions by example) and Appendix A1.3 (jeu de taquin slides by picture); Fulton 1997 *Young Tableaux* (Cambridge LMS Student Texts 35) §1.2 and §5.1 (sliding tableaux and the multiplication of Schur polynomials in two and three variables)
intermediate: Stanley 1999 *Enumerative Combinatorics, Volume 2* 2e (Cambridge) §7.15-7.18 and Appendix A1 (skew Schur functions $s_{\lambda/\mu}$, the Littlewood-Richardson coefficients $c^\lambda_{\mu\nu}$, the LR rule by lattice/Yamanouchi words, jeu de taquin and rectification); Fulton 1997 *Young Tableaux* Ch. 1-5 (the plactic monoid, jeu de taquin, the LR rule and its proof, the Schubert-calculus application)
master: Macdonald 1995 *Symmetric Functions and Hall Polynomials* 2e (Oxford) Ch. I §5 and §9 (skew Schur functions, the Littlewood-Richardson rule, the $c^\lambda_{\mu\nu}$ as structure constants and skew expansion coefficients); Stanley 1999 *Enumerative Combinatorics, Volume 2* Ch. 7 Appendix A1 (jeu de taquin, the fundamental theorem of rectification, the proof of the LR rule); Fulton 1997 *Young Tableaux* (the plactic-monoid proof and the cohomology of the Grassmannian); Littlewood-Richardson 1934 *Phil. Trans. R. Soc. A* 233 (the original statement); Schützenberger 1977 (jeu de taquin and the plactic monoid); Knutson-Tao 1999 (honeycombs and the saturation theorem)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 2 · Cambridge Studies in Advanced Mathematics 62 (1999). Chapter 7 §7.15 defines the skew Schur function $s_{\lambda/\mu} = \sum_{T} x^{\mathrm{wt}(T)}$ as the weight generating function of semistandard Young tableaux of skew shape $\lambda/\mu$, with the skew Jacobi-Trudi determinant $s_{\lambda/\mu} = \det(h_{\lambda_i - \mu_j - i + j})$. The Littlewood-Richardson coefficients $c^\lambda_{\mu\nu}$ are defined by $s_\mu s_\nu = \sum_\lambda c^\lambda_{\mu\nu} s_\lambda$ and equivalently by the skew expansion $s_{\lambda/\mu} = \sum_\nu c^\lambda_{\mu\nu} s_\nu$; §7.18 and Appendix A1 prove they are non-negative integers via the Littlewood-Richardson rule (the number of LR skew tableaux of shape $\lambda/\mu$ and content $\nu$, i.e. semistandard fillings whose reverse reading word is a lattice/Yamanouchi word). Appendix A1.3 develops jeu de taquin (Schützenberger's sliding algorithm), the rectification of a skew tableau, and the fundamental theorem that rectification is well-defined independent of the slide order, from which the LR rule and the symmetries $c^\lambda_{\mu\nu} = c^\lambda_{\nu\mu}$ and the conjugation symmetry follow. The Pieri rules are the cases $\nu = (r)$ and $\nu = (1^r)$.
Fulton, W. — Young Tableaux: With Applications to Representation Theory and Geometry · Cambridge University Press, London Mathematical Society Student Texts 35 (1997). Chapters 1-3 develop the row-insertion (bumping) algorithm, the plactic monoid (Knuth equivalence), and jeu de taquin (forward and reverse slides) on skew tableaux, proving that the rectification of a skew tableau to a straight-shape tableau is independent of the sequence of slides (the confluence / fundamental theorem). Chapter 5 states and proves the Littlewood-Richardson rule $c^\lambda_{\mu\nu} = \#\{\text{LR tableaux of shape } \lambda/\mu, \text{ content } \nu\}$, equivalently the number of skew tableaux of shape $\lambda/\mu$ that rectify to the unique superstandard tableau $U_\nu$ of shape $\nu$ (row $i$ filled with $i$); jeu de taquin is shown to compute these coefficients. The symmetries $c^\lambda_{\mu\nu} = c^\lambda_{\nu\mu}$ and $c^\lambda_{\mu\nu} = c^{\lambda'}_{\mu'\nu'}$ are derived. Chapters 9-10 identify the $c^\lambda_{\mu\nu}$ with the structure constants of the cohomology ring of the Grassmannian (Schubert intersection numbers) and with tensor-product / induction multiplicities for $\mathrm{GL}_n$ and $S_n$.
Macdonald, I. G. — Symmetric Functions and Hall Polynomials · Oxford Mathematical Monographs, 2nd edition (1995). Chapter I §5 develops skew Schur functions and the Littlewood-Richardson rule: $s_{\lambda/\mu}$ is defined by $\langle s_{\lambda/\mu}, s_\nu\rangle = \langle s_\lambda, s_\mu s_\nu\rangle = c^\lambda_{\mu\nu}$ under the Hall inner product, making the LR coefficients simultaneously the structure constants of the Schur basis, the multiplicities in the skew expansion, and (by associativity and commutativity of the product) symmetric in $\mu$ and $\nu$. The conjugation symmetry $c^\lambda_{\mu\nu} = c^{\lambda'}_{\mu'\nu'}$ follows from $\omega(s_\lambda) = s_{\lambda'}$. §9 places the rule in the Hall-algebra / Hall-polynomial context. The Pieri rules of §5 are the special cases. The interpretation as $\mathrm{GL}_n$ tensor-product (Clebsch-Gordan) multiplicities and as Hall-Littlewood degenerations is developed across §5-9.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m