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 finite-dimensional representations of general linear 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.
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.
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).
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.
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.
A Littlewood–Richardson tableau is a skew semistandard tableau with the additional property that the sequence obtained by concatenating its reversed rows is a lattice word (or lattice permutation), which means that in every initial part of the sequence any number
Many other combinatorial notions have been found that turn out to be in bijection with Littlewood–Richardson tableaux, and can therefore also be used to define the Littlewood–Richardson coefficients.
Indeed, since the last box on the first nonempty line of the skew diagram can only contain an entry 1, the entire first line must be filled with entries 1 (this is true for any Littlewood–Richardson tableau); in the last box of the second row we can only place a 2 by column strictness and the fact that our lattice word cannot contain any larger entry before it contains a 2.
Once that entry is chosen, the third row must contain the remaining entries to make the weight (3,2,1), in a weakly increasing order, so we have no choice left any more; in both case it turns out that we do find a Littlewood–Richardson tableau.
The condition that the sequence of entries read from the tableau in a somewhat peculiar order form a lattice word can be replaced by a more local and geometrical condition.
Since in a semistandard tableau equal entries never occur in the same column, one can number the copies of any value from right to left, which is their order of occurrence in the sequence that should be a lattice word.
If the weight of the Littlewood–Richardson tableau is fixed beforehand, then one can form a fixed collection of indexed entries, and if these are placed in a way respecting those geometric restrictions, in addition to those of semistandard tableaux and the condition that indexed copies of the same entries should respect right-to-left ordering of the indexes, then the resulting tableaux are guaranteed to be Littlewood–Richardson tableaux.
The Littlewood–Richardson as stated above gives a combinatorial expression for individual Littlewood–Richardson coefficients, but gives no indication of a practical method to enumerate the Littlewood–Richardson tableaux in order to find the values of these coefficients.
); therefore it seems inevitable that in some cases one has to go through an elaborate search, only to find that no solutions exist.
Since the weight is known, the set of indexed entries in the geometric description is fixed.
Now for successive indexed entries, all possible positions allowed by the geometric restrictions can be tried in a backtracking search.
The latter point is the key to efficiency of the search procedure: the entry i[j] is then restricted to be in a column to the right of
; thus every placement of an entry will give rise to at least one complete Littlewood–Richardson tableau, and the search tree contains no dead ends.
The Littlewood–Richardson coefficients cνλμ appear in the following interrelated ways: 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 Sn 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.
If both partitions are rectangular in shape, the sum is also multiplicity free (Okada 1998).
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.
Newell-Littlewood numbers are defined from Littlewood–Richardson coefficients by the cubic expression[1] Newell-Littlewood numbers give some of the tensor product multiplicities of finite-dimensional representations of classical Lie groups of the types
leads to Newell-Littlewood numbers are generalizations of Littlewood–Richardson coefficients in the sense that Newell-Littlewood numbers that involve a Young diagram with only one row obey a Pieri-type rule:
[1] Newell-Littlewood numbers are the structure constants of an associative and commutative algebra whose basis elements are partitions, with the product
at most 4 are given by: 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.
For example, 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) with 26 terms coming from the following 34 tableaux: Calculating skew Schur functions is similar.
