2021-09-19

## Combinatorial models for Littlewood–Richardson coefficients

The Littlewood–Richardson coefficients are defined as the structure constants $c^{\lambda}_{\mu\nu}$ appearing in the expansion $\schurS_\mu \schurS_\nu = \sum_\lambda c^{\lambda}_{\mu\nu} \schurS_\lambda.$ One can show that $c^{\lambda}_{\mu\nu}=0$ unless $\mu,\nu \subseteq \lambda.$ Furthermore, we have the symmetries

\[ c^{\lambda}_{\mu\nu} = c^{\lambda}_{\nu\mu} = c^{\lambda'}_{\mu'\nu'}. \]Hariharan Narayanan proved in 2006 that it is $\#P$-complete to compute $c^{\lambda}_{\mu\nu}.$

One can express the Littlewood–Richardson coefficients as a signed sum involving the Kostant partition function, by using Steinberg's formula [Ste61].

A simple recursion for computing $c^{\lambda}_{\nu\mu}$ can be obtained from the shifted Schur functions.

In [Aze99], it is proved that for fixed $\lambda$ and $\mu,$ the set

\[ \{ \nu : c^{\lambda}_{\mu \nu}>0 \} \]is a sub-lattice of the partition lattice under domination order.

### Littlewood–Richardson tableaux

The Littlewood–Richardson rule states that $c^{\lambda}_{\mu\nu}$ count the number of skew semi-standard Young tableaux of shape $\lambda/\mu$ with content $\nu,$ with the additional restriction that the concatenation of the reversed rows is a lattice word. A word $w_1,\dotsc,w_\ell$ is a lattice word if every prefix has the property that its content is a partition. That is, the number of times $i$ appears in the prefix is at least as many as $i+1,$ for every $i.$ Tableaux of this type are called Littlewood–Richardson tableaux.

**Example (Littlewood–Richardson tableaux).**

Consider the coefficient of $\schurS_{542}$ in the product $\schurS_{32}\cdot \schurS_{321}.$ We must find all Littlewood–Richardson tableaux of shape $542/32$ with content $321.$ There are two such tableaux:

$1$ | $1$ | |||

$1$ | $2$ | |||

$2$ | $3$ |

$1$ | $1$ | |||

$2$ | $2$ | |||

$1$ | $3$ |

Consequently, $c^{542}_{32,321}=2.$

### Standard Young tableaux

In [Cor. 5.4.8 , Lot02], they give the following characterization of Littlewood–Richardson coefficients: $c^{\lambda}_{\mu\nu}$ is the number of semistandard Young tableaux $T$ with shape $\nu,$ and content $\lambda-\mu$ such that $\rw(t) \cdot \ell^{\mu_\ell} \dotsm 2^{\mu_2}1^{\mu_1}$ is a Yamanouchi word.

By using [Rem. 14 and Cor. 21, KM19], one can show that this is equivalent to the following model.

### Postfix-charge model

In [AU20] we show that

\[ c^{\lambda}_{\mu\nu} = \left| T \in \SSYT(\nu, \lambda - \mu) : \charge( \rw(T) \cdot \ell^{\mu_\ell} \dotsm 2^{\mu_2}1^{\mu_1})=0 \right|. \]That is, $c^{\lambda}_{\mu\nu}$ is equal to the number of semistandard Young tableaux of shape $\nu$ and content $\lambda - \mu$ such that the reading word postfixed with $\ell^{\mu_\ell} \dotsm 2^{\mu_2}1^{\mu_1}$ has charge equal to zero.

**Example (Postfix-charge model).**

Let us compute $c^{33221}_{221,321},$ where $\lambda = 33221,$ $\mu = 221$ and $\nu = 321.$ We are interested in semistandard tableaux with shape $321$ and content $\lambda-\mu = 11121.$ There are eight such tableaux.

$1$ | $4$ | $4$ |

$2$ | $5$ | |

$3$ |

$1$ | $3$ | $5$ |

$2$ | $4$ | |

$4$ |

$1$ | $3$ | $4$ |

$2$ | $5$ | |

$4$ |

$1$ | $3$ | $4$ |

$2$ | $4$ | |

$5$ |

$1$ | $2$ | $5$ |

$3$ | $4$ | |

$4$ |

$1$ | $2$ | $4$ |

$3$ | $5$ | |

$4$ |

$1$ | $2$ | $4$ |

$3$ | $4$ | |

$5$ |

$1$ | $2$ | $3$ |

$4$ | $4$ | |

$5$ |

We take their reading words and concatenate $\ell^{\mu_\ell} \dotsm 2^{\mu_2}1^{\mu_1} = 32211$ at the end.

$\text{Word}$ | $\text{Charge}$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$32514432211$ | $1$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$42413532211$ | $1$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$42513432211$ | $0$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$52413432211$ | $0$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$43412532211$ | $2$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$43512432211$ | $1$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$53412432211$ | $2$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

$54412332211$ | $1$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

**Example (Postfix-charge model II).**

Let us compute $c^{542}_{32,321} = c^{\lambda}_{\mu\nu}.$ We are interested in semistandard tableaux with shape $321$ and content $\lambda-\mu = 222.$ There are two such tableaux.

$1$ | $1$ | $3$ |

$2$ | $2$ | |

$3$ |

$1$ | $1$ | $2$ |

$2$ | $3$ | |

$3$ |

We take their reading words and concatenate $22111$ at the end, $322113\;22111$ and $323112\;22111.$ Both of these words have charge $0,$ so $c^{542}_{32,321}=2.$

### Berenstein–Zelevinsky patterns

Berenstein and Zelevinsky [BZ88] gave a combinatorial model for the Littlewood–Richardson coefficients that uses certain triangular arrays, reminiscent of Gelfand–Tsetlin patterns.

### Knutson–Tao honeycombs

### Knutson–Tao–Woodward puzzles

Knutson–Tao–Woodward puzzles [KT99KTW04] is a different model used for proving the saturation conjecture. A nice overview of the saturation conjecture is given by A. Buch [Buc00].

### Socle tableaux

In https://arxiv.org/pdf/2007.12221.pdf, $c^{\lambda}_{\mu\nu}$
is realized as the number of *socle tableaux* of shape $\lambda/\nu$ and content $\mu.$
Note that the role of $\mu$ and $\nu$ have been interchanged.

A socle tableau is weakly decreasing in rows, strictly decreasing in columns, and for each vertical line and integer $\ell,$ there are at most as many entries $\ell+1$ on the left hand side, as entries $\ell.$

### Evaluating Schur functions at roots of unity

In https://arxiv.org/pdf/2107.09907.pdf, the author gives a fairly explicit formula for Littlewood–Richardson coefficients, as a sum over partitions, where the terms include a product of three Schur functions, evaluated at certain roots of unity.

## Newell–Littlewood numbers

The Newel–Littlewood numbers may be defined as

\[ N_{\mu,\nu,\lambda} = \sum_{\alpha,\beta,\gamma} c^{\mu}_{\alpha\beta} c^{\nu}_{\alpha\gamma} c^{\lambda}_{\beta\gamma}. \]For a recent paper on these coefficients, see [GOY20].

The Littlewood–Richardson coefficients arise as tensor product multiplicities of irreducible representations of $\GL(V).$ The Newel–Littlewood numbers arise in the same manner, where $\GL(V)$ is replaced by a Lie group of type $B,$ $C$ or $D.$

There is a symmetric function basis, the Koike–Terada basis, $\{\schurS_{[\lambda]}\}_\lambda$ for which the $N_{\mu,\nu,\lambda}$ serve as multiplication structure constants. An explicit Jacobi–Trudi type formula for this basis is given in [GOY20].

In [Thm. 5.1, GOY20], a polytope description for $N_{\mu,\nu,\lambda}$ is given, and a saturation-type conjecture is stated.

## A. Buch's lrcalc

Anders Buch has a fast C program, lrcalc, for computing Littlewood–Richardson coefficients.

## References

- [AU20] Per Alexandersson and Joakim Uhlin. Cyclic sieving, skew Macdonald polynomials and Schur positivity. Algebraic Combinatorics, 3(4):913-939, 2020.
- [Aze99] Olga Azenhas. The admissible interval for the invariant factors of a product of matrices. Linear and Multilinear Algebra, 46(1-2):51–99, July 1999.
- [Buc00] Anders Skovsted Buch. The saturation conjecture (after A. Knutson and T. Tao), with an appendix by William Fulton. Enseign. Math. (2), 46:43–60, 2000.
- [BZ88] A. D. Berenstein and A. V. Zelevinsky. Tensor product multiplicities and convex polytopes in partition space. Journal of Geometry and Physics, 5(3):453–472, 1988.
- [GOY20] Shiliang Gao, Gidon Orelowitz and Alexander Yong. Newell–Littlewood numbers. arXiv e-prints, 2020.
- [KM19] Ryan Kaliszewski and Jennifer Morse. Colorful combinatorics and Macdonald polynomials. European Journal of Combinatorics, 81:354–377, October 2019.
- [KT99] Allen Knutson and Terence Tao. The honeycomb model of $GL_n(C)$ tensor products I: proof of the saturation conjecture. Journal of the American Mathematical Society, 12(04):1055–1091, October 1999.
- [KTW04] Allen Knutson, Terence Tao and Christopher Woodward. The honeycomb model of $GL_n(C)$ tensor products II: puzzles determine facets of the Littlewood–Richardson cone. Journal of the American Mathematical Society, 17(1):19–49, January 2004.
- [Lot02] M. Lothaire. Algebraic combinatorics on words. Cambridge University Press, 2002.
- [Ste61] Robert Steinberg. A general Clebsch–Gordan theorem. Bull. Amer. Math. Soc., 67(4):406–407, July 1961.