Littlewood–Richardson rule

Littlewood–Richardson rule

In mathematics, the Littlewood–Richardson rule is a combinatorial description of the coefficients that arise when decomposing a product of two Schur functions as a linear combination of other Schur functions. These coefficients are natural numbers, which the Littlewood–Richardson rule describes as counting certain skew tableaux. They occur in many other mathematical contexts, for instance as multiplicity in the decomposition of tensor products of irreducible representations of general linear groups (or related groups like the special linear and special unitary groups), or in the decomposition of certain induced representations in the representation theory of the symmetric group, or in the area of algebraic combinatorics dealing with Young tableaux and symmetric polynomials.
History
Unfortunately the Littlewood–Richardson rule is much harder to prove than was at first suspected. The author was once told that the Littlewood–Richardson rule helped to get men on the moon but was not proved until after they got there. Gordon James (1987)
The Littlewood–Richardson rule was first stated by D. E. Littlewood and A. R. Richardson (1934, theorem III p. 119) but though they claimed it as a theorem they only proved it in some fairly simple special cases. Robinson (1938) claimed to complete their proof, but his argument had gaps, though it was so obscurely written that these gaps were not noticed for some time, and his argument is reproduced in the book (Littlewood 1950). Some of the gaps were later filled by Macdonald (1995). The first rigorous proofs of the rule were given four decades after it was found, by Schützenberger (1977) and Thomas (1974), after the necessary combinatorial theory was developed by C. Schensted (1961), Schützenberger (1963), and Knuth (1970) in their work on the Robinson–Schensted correspondence. There are now several short proofs of the rule, such as (Gasharov 1998), and (Stembridge 2002) using Bender-Knuth involutions. Littelmann (1994) used the Littelmann path model to generalize the Littlewood–Richardson rule to other semisimple Lie groups.
The Littlewood–Richardson rule is notorious for the number of errors that appeared prior to its complete, published proof. Several published attempts to prove it are incomplete, and it is particularly difficult to avoid errors when doing hand calculations with it: even the original example in D. E. Littlewood and A. R. Richardson (1934) contains an error.
Littlewood–Richardson tableaux
Example
A more geometrical description
An algorithmic form of the rule
Littlewood–Richardson coefficients
The Littlewood–Richardson coefficients cνλμ appear in the following interrelated ways:
They are the structure constants for the product in the ring of symmetric functions with respect to the basis of Schur functions
λμ is the inner product of sνand sλsμ.
They express skew Schur functions in terms of Schur functions
The cνλμ appear as intersection numbers on a Grassmannian:
cνλμ is the number of times the irreducible representation V**λ ⊗ V**μ of the product of symmetric groups S|λ| × S|μ| appears in the restriction of the representation V**ν of S|ν| to S|λ| × S|μ|. By Frobenius reciprocity this is also the number of times that V**ν occurs in the representation of S|ν| induced from V**λ ⊗ V**μ.
The cνλμ appear in the decomposition of the tensor product (Fulton 1997) of two Schur modules (irreducible representations of special linear groups)
cνλμ is the number of standard Young tableaux of shape ν/μ that are jeu de taquin equivalent to some fixed standard Young tableau of shape λ.
cνλμ is the number of Littlewood–Richardson tableaux of shape ν/λ and of weight μ.
cνλμ is the number of pictures between μ and ν/λ.
Generalizations and special cases
Zelevinsky (1981) extended the Littlewood–Richardson rule to skew Schur functions as follows:
where the sum is over all tableaux T on μ/ν such that for all j, the sequence of integers λ+ω(T≥j) is non-increasing, and ω is the weight.
Pieri's formula, which is the special case of the Littlewood–Richardson rule in the case when one of the partitions has only one part, states that
where S**n is the Schur function of a partition with one row and the sum is over all partitions λ obtained from μ by adding n elements to its Ferrers diagram, no two in the same column.
For example,
.
Examples
The examples of Littlewood-Richardson coefficients below are given in terms of products of Schur polynomials Sπ, indexed by partitions π, using the formula
All coefficients with ν at most 4 are given by:
S0Sπ = Sπ for any π. where S0=1 is the Schur polynomial of the empty partition
S1S1 = S2 + S11
S2S1 = S3 + S21
S11S1 = S111 + S21
S3S1 = S4 + S31
S21S1 = S31 + S22 + S211
S2S2 = S4 + S31 + S22
S2S11 = S31 + S211
S111S1 = S1111 + S211
S11S11 = S1111 + S211 + S22
Most of the coefficients for small partitions are 0 or 1, which happens in particular whenever one of the factors is of the form Sn or S11...1, because of Pieri's formula and its transposed counterpart. The simplest example with a coefficient larger than 1 happens when neither of the factors has this form:
S21S21 = S42 + S411 + S33 + 2S321 + S3111 + S222 + S2211.
For larger partitions the coefficients become more complicated. For example,
S321S321 = S642 +S6411 +S633 +2S6321 +S63111 +S6222 +S62211 +S552 +S5511 +2S543 +4S5421 +2S54111 +3S5331 +3S5322 +4S53211 +S531111 +2S52221 +S522111 +S444 +3S4431 +2S4422 +3S44211 +S441111 +3S4332 +3S43311 +4S43221 +2S432111 +S42222 +S422211 +S3333 +2S33321 +S333111 +S33222 +S332211 with 34 terms and total multiplicity 62, and the largest coefficient is 4
S4321S4321 is a sum of 206 terms with total multiplicity is 930, and the largest coefficient is 18.
S54321S54321 is a sum of 1433 terms with total multiplicity 26704, and the largest coefficient (that of S86543211) is 176.
S654321S654321 is a sum of 10873 terms with total multiplicity is 1458444 (so the average value of the coefficients is more than 100, and they can be as large as 2064).
The original example given by Littlewood & Richardson (1934, p. 122-124) was (after correcting for 3 tableaux they found but forgot to include in the final sum)
S431S221 = S652 + S6511 + S643 + 2S6421 + S64111 + S6331 + S6322 + S63211 + S553 + 2S5521 + S55111 + 2S5431 + 2S5422 + 3S54211 + S541111 + S5332 + S53311 + 2S53221 + S532111 + S4432 + S44311 + 2S44221 + S442111 + S43321 + S43222 + S432211
with 26 terms coming from the following 34 tableaux:
Calculating skew Schur functions is similar. For example, the 15 Littlewood–Richardson tableaux for ν=5432 and λ=331 are
so S5432/331 = Σcνλμ Sμ = S52 + S511 + S4111 + S2221 + 2S43 + 2S3211 + 2S322 + 2S331 + 3S421 (Fulton 1997, p. 64).