2023-09-20
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'}. \]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. See also [TG22] for conditions on when $c^{\lambda}_{\mu \nu}$ is positive.
The problem of determining for which $(\lambda, \mu, \nu)$ we have $c^{\lambda}_{\nu\mu} > 0,$ is determined by the Horn inequalities, see [Kly98KT99].
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.
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.$
Semistandard 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.
Semistandard Young tableaux II
In [FG93MS99], the following model us described. $c^{\lambda}_{\mu\nu}$ is the number of semistandard Young tableaux $T$ with shape $\mu,$ with the property that the column index reading word of $T,$ fits the skew shape $\lambda/\mu.$ That is, we take the column reading word of $T,$ reading columns right to left. This gives a word $w.$ For each entry $w_i,$ we put an entry $i$ in row $w_i,$ so that the resulting filling $F=F(T)$ is of shape $\lambda/\mu.$ If this filling is a skew SYT, then we say that $T$ fits $\lambda/\mu.$
Note that the conditions force that $T$ has content $\lambda-\mu.$
Observe that this model is generalized to Littlewood–Richardson coefficiens for shifted Schur functions.
Let us show that $c^{542}_{321,32}=2$ using the Fomin–Greene model. We are counting SSYT with shape $\mu=321,$ which fit $542/32.$
There are two such SSYT (and corresponding SYT obtained from the column reading word):
$1$ | $1$ | $2$ |
$2$ | $3$ | |
$3$ |
$2$ | $4$ | |||
$1$ | $5$ | |||
$3$ | $6$ |
$1$ | $1$ | $3$ |
$2$ | $2$ | |
$3$ |
$2$ | $4$ | |||
$3$ | $5$ | |||
$1$ | $6$ |
Consequently, $c^{542}_{32,321}=2.$
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.
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$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 [BZ92] gave a combinatorial model for the Littlewood–Richardson coefficients that uses certain triangular arrays, reminiscent of Gelfand–Tsetlin patterns. The exact definition is written in an accessible mannar in [Def. A1.3.10, Sta01].
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].
Steinberg's formula
One can express the Littlewood–Richardson coefficients as a signed sum involving the Kostant partition function, by using Steinberg's formula [Ste61].
See the exact formula in the section with the Littlewood–Richardson coefficiens from the Kostant partition function.
Socle tableaux
In [KS], $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
W. Wen 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, see [Wen21].
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 recent papers on these coefficients, see [GOY20aGOY20b].
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 [GOY20a].
In [Thm. 5.1, GOY20a], a polytope description for $N_{\mu,\nu,\lambda}$ is given, and a saturation-type conjecture is stated. See also [Kin21] for more conjectures.
Stretched Littlewood–Richardson coefficients
The Littlewood–Richardson coefficients are in correspondence with lattice points in certain rational polytopes, as proved in [BZ88]. Consequently, it is immediate that this function is a quasi-polynomial, since we can model this as the Ehrhart (quasi)polynomial of a rational polytope. Polynomiality was later proved by H. Derksen and J. Weyman [DW02], and E. Rassart [Ras04a]. A simple proof of polynomiality is given in [Tha22]. The proof uses the Kostant partition function formula due to Steinberg.
The function
\[ t \to c^{t \nu}_{t\lambda,t\mu} \]for fixed partitions, is a polynomial in $t.$ Note that this is the Ehrhart polynomial of the corresponding BZ-polytope (where lattice points are BZ-patterns).
Computer experiments, see [KTT04], suggests that the Ehrhart polynomial above has non-negative coefficients. This conjecture is still open. A special case of this conjecture is to consider the map $t \to K_{t\lambda,t\mu},$ of so called stretched Kostka coefficients. Various aspects of this problem has been considered in [Ale16aAle19b].
Fulton's conjecture stated that $c^{\nu}_{\lambda,\mu}=1$ implies that $c^{t \nu}_{t\lambda,t\mu}=1$ for all $t \geq 1.$ This was later proved in [KTW04]. The next natural case is, $c^{\nu}_{\lambda,\mu}=2$ and it is proved by C. Ikenmenyer [Ike16] and later C. Sherman [She15She17] that
\[ c^{\nu}_{\lambda,\mu}=2 \implies c^{t \nu}_{t\lambda,t\mu}=t+1. \]A nice generalization of this implication is given in [CR22a], where it is proved that
\[ c^{\nu}_{\lambda,\mu}=2 \implies c^{\nu(s,t)}_{\lambda(s,t),\mu(s,t)}=\binom{s+t}{t}, \]with the convention that $\lambda(s,t) \coloneqq s (t \lambda')'$ (i.e., we stretch in both vertical and horizontal direction).
Stretching of Newell–Littlewood coefficients is studied in [Kin21]. This preprint conttains lots of interesting conjectures analogous to results/conjectures about the Littlewood–Richardson coefficients. R. C. King proves that the map $t \to n^{t \nu}_{t\lambda,t\mu}$ is a quasipolynomial with period at most 2.
Identities
Coquereaux–Zuber relation
Let $\mu, \nu \vdash n$ be such that all entries are at most $k.$ In [CZ], it is proved that
\[ \sum_{\lambda \vdash n} c^{\lambda}_{\mu, \nu} = \sum_{\lambda \vdash n} c^{\lambda}_{\mu^{\vee k}, \nu}, \]where $\mu^{\vee k} \coloneqq (k-\lambda_n,\dotsc,k-\lambda_2,k-\lambda_1).$
The Harris–Willenbring identity
See https://link.springer.com/chapter/10.1007/978-1-4939-1590-3_11
\[ \sum_{n \geq 0} \sum_{\lambda,\mu, \nu \vdash n} \left( c^{\lambda}_{\mu\nu} \right)^2 t^{|\mu|}q^{|\nu|} = \prod_{i \geq 1} \frac{1}{1-t^i-q^i} \]Shrivastava's relation with Kostka numbers
In [Shr22], Shrivastava shows how one can compute Littlewood–Richardson coefficients as a signed sum of Kostka coefficients.
It is known that (skew) Kostka coefficients can be obtained as a special case of Littlewood–Richardson coefficients, see e.g. [p. 338, Eq. 7.61, Sta01].
Computing coefficients, and A. Buch's lrcalc
H. Narayanan proved in 2006 that computing Littlewood–Richardson coefficients and Kostka coefficients is in general $\#P$-complete, see [Nar06]. This implies that there are no efficient algorithms for computing these quantities (assuming wildly believed conjectures regarding complexity theory).
Anders Buch has a fast C program, lrcalc, for computing Littlewood–Richardson coefficients.
See also Matthew J. Samuel's python package for computing products of Schubert polynomials which, in particular, can compute Littlewood–Richardson coefficients.
References
- [Ale16a] Per Alexandersson. Gelfand–Tsetlin polytopes and the integer decomposition property. European Journal of Combinatorics, 54:1–20, May 2016.
- [Ale19b] Per Alexandersson. Polytopes and large counterexamples. Experimental Mathematics, 28(1):115–120, 2019.
- [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.
- [BZ92] A. D. Berenstein and A. V. Zelevinsky. Triple multiplicities for $sl(r + 1)$ and the spectrum of the exterior algebra of the adjoint representation. Journal of Algebraic Combinatorics, 1(1):7–22, 1992.
- [CR22a] Pierre-Emmanuel Chaput and Nicolas Ressayre. Bidilatation of small Littlewood–Richardson coefficients. arXiv e-prints, 2022.
- [CZ] Robert Coquereaux and Jean-Bernard Zuber. On sums of tensor and fusion multiplicities. Journal of Physics A: Mathematical and Theoretical, 44(29):295208, June .
- [DW02] Harm Derksen and Jerzy Weyman. On the Littlewood–Richardson polynomials. Journal of Algebra, 255(2):247–257, 2002.
- [FG93] Sergey Fomin and Curtis Greene. A Littlewood–Richardson miscellany. European Journal of Combinatorics, 14(3):191–212, May 1993.
- [GOY20a] Shiliang Gao, Gidon Orelowitz and Alexander Yong. Newell–Littlewood numbers. arXiv e-prints, 2020.
- [GOY20b] Shiliang Gao, Gidon Orelowitz and Alexander Yong. Newell–Littlewood numbers II: extended Horn inequalities. arXiv e-prints, 2020.
- [Ike16] Christian Ikenmeyer. Small Littlewood–Richardson coefficients. Journal of Algebraic Combinatorics, 44(1):1–29, February 2016.
- [Kin21] Ronald C King. Stretched Newell–Littlewood coefficients. arXiv e-prints, 2021.
- [Kly98] A. A. Klyachko. Stable bundles, representation theory and Hermitian operators. Selecta Mathematica, 4(3):419–445, September 1998.
- [KM19] Ryan Kaliszewski and Jennifer Morse. Colorful combinatorics and Macdonald polynomials. European Journal of Combinatorics, 81:354–377, October 2019.
- [KS] Justyna Kosakowska and Markus Schmidmeier. The socle tableau as a dual version of the Littlewood–Richardson tableau. Journal of the London Mathematical Society, May .
- [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.
- [KTT04] R. C. King, C. Tollu and F. Toumazet. Stretched Littlewood–Richardson coefficients and Kostka coefficients. In Symmetry in Physics: In Memory of Robert T. Sharp. AMS / OUP, 2004.
- [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.
- [MS99] Alexander I. Molev and Bruce E. Sagan. A Littlewood–Richardson rule for factorial Schur functions. Transactions of the American Mathematical Society, 351(11):4429–4444, November 1999.
- [Nar06] Hariharan Narayanan. On the complexity of computing Kostka numbers and Littlewood–Richardson coefficients. Journal of Algebraic Combinatorics, 24(3):347–354, July 2006.
- [Ras04a] Etienne Rassart. A polynomiality property for Littlewood–Richardson coefficients. J. Comb. Theory Ser. A, 107(2):161–179, August 2004.
- [She15] Cass Sherman. Geometric proof of a conjecture of King, Tollu, and Toumazet. arXiv e-prints, 2015.
- [She17] Cass Sherman. Quiver generalization of a conjecture of King, Tollu, and Toumazet. Journal of Algebra, 480:487–504, June 2017.
- [Shr22] Sagar Shrivastava. Littlewood–Richardson coefficients as a signed sum of Kostka numbers. arXiv e-prints, 2022.
- [Sta01] Richard P. Stanley. Enumerative Combinatorics: Volume 2. Cambridge University Press, First edition, 2001.
- [Ste61] Robert Steinberg. A general Clebsch–Gordan theorem. Bull. Amer. Math. Soc., 67(4):406–407, July 1961.
- [TG22] Müge Taşkın and R. Bedii Gümüş. Lower bounds for nonzero Littlewood–Richardson coefficients. arXiv e-prints, 2022.
- [Tha22] Warut Thawinrak. Polynomiality of the stretched Littlewood–Richardson coefficients. arXiv e-prints, 2022.
- [Wen21] Xueqing Wen. A closed formula of Littlewood–Richardson coefficients. arXiv e-prints, 2021.