Breaking down the reduced Kronecker coefficients

Pak, Igor; Panova, Greta

Comptes Rendus. Mathématique, Tome 358 (2020) no. 4, pp. 463-468.

We resolve three interrelated problems on reduced Kronecker coefficients $\overline{g}(\alpha ,\beta ,\gamma )$. First, we disprove the saturation property which states that $\overline{g}(N\alpha ,N\beta ,N\gamma )>0$ implies $\overline{g}(\alpha ,\beta ,\gamma )>0$ for all $N>1$. Second, we esimate the maximal $\overline{g}(\alpha ,\beta ,\gamma )$, over all $\left|\alpha \right|+\left|\beta \right|+\left|\gamma \right|=n$. Finally, we show that computing $\overline{g}(\lambda ,\mu ,\nu )$ is strongly $\mathrm{\#P}$-hard, i.e. $\mathrm{\#P}$-hard when the input $(\lambda ,\mu ,\nu )$ is in unary.

[1] Bessenrodt, Christine; Behns, Christiane On the Durfee size of Kronecker products of characters of the symmetric group and its double covers, J. Algebra, Volume 280 (2004) no. 1, pp. 132-144 | DOI | MR | Zbl

[2] Bowman, Christopher; De Visscher, Maud; Orellana, Rosa The partition algebra and the Kronecker coefficients, Trans. Am. Math. Soc., Volume 367 (2015) no. 5, pp. 3647-3667 | DOI | MR | Zbl

[3] Briand, Emmanuel; Orellana, Rosa; Rosas, Mercedes The stability of the Kronecker product of Schur functions, J. Algebra, Volume 331 (2011) no. 1, pp. 11-27 | DOI | MR | Zbl

[4] Christandl, Matthias; Harrow, Aram W.; Mitchison, Graeme Nonzero Kronecker coefficients and what they tell us about spectra, Commun. Math. Phys., Volume 270 (2007) no. 3, pp. 575-585 | DOI | MR | Zbl

[5] Colmenarejo, Laura; Rosas, Mercedes Combinatorics on a family of reduced Kronecker coefficients, C. R. Math. Acad. Sci. Paris, Volume 353 (2015) no. 10, pp. 865-869 | DOI | MR | Zbl

[6] Dvir, Yoav On the Kronecker product of $S_n$ characters, J. Algebra, Volume 154 (1993) no. 1, pp. 125-140 | DOI | MR | Zbl

[7] Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael On vanishing of Kronecker coefficients, Comput. Complexity, Volume 26 (2017) no. 4, pp. 949-992 | DOI | MR | Zbl

[8] Ikenmeyer, Christian; Panova, Greta Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Adv. Math., Volume 319 (2017), pp. 40-66 | DOI | MR | Zbl

[9] Kirillov, Anatol N. An invitation to the generalized saturation conjecture, Publ. Res. Inst. Math. Sci., Volume 40 (2004) no. 4, pp. 1147-1239 | DOI | MR | Zbl

[10] Klyachko, Alexander Quantum marginal problem and representations of the symmetric group (2004) (https://arxiv.org/abs/quant-ph/0409113)

[11] Knutson, Allen; Tao, Terence The honeycomb model of ${\mathrm{GL}}_n\left(ℂ\right)$ tensor products. I: Proof of the saturation conjecture, J. Am. Math. Soc., Volume 12 (1999) no. 4, pp. 1055-1090 | DOI | MR | Zbl

[12] Littlewood, Dudley E. Products and plethysms of characters with orthogonal, symplectic and symmetric groups, Can. J. Math., Volume 10 (1958), pp. 17-32 | DOI | MR | Zbl

[13] Manivel, Laurent On the asymptotics of Kronecker coefficients, J. Algebr. Comb., Volume 42 (2015) no. 4, pp. 999-1025 | DOI | MR | Zbl

[14] Mulmuley, Ketan D.; Narayanan, Hariharan; Sohoni, Milind Geometric complexity theory III: On deciding nonvanishing of a Littlewood–Richardson coefficient, J. Algebr. Comb., Volume 36 (2012), pp. 103-110 | DOI | MR | Zbl

[15] Murnaghan, Francis D. The analysis of the Kronecker product of irreducible representations of the symmetric group, Am. J. Math., Volume 60 (1938), pp. 761-784 | DOI | MR | Zbl

[16] Murnaghan, Francis D. On the Kronecker product of irreducible representations of the symmetric group, Proc. Natl. Acad. Sci. USA, Volume 42 (1956), pp. 95-98 | DOI | MR | Zbl

[17] Narayanan, Hariharan On the complexity of computing Kostka numbers and Littlewood–Richardson coefficients, J. Algebr. Comb., Volume 24 (2006) no. 3, pp. 347-354 | DOI | MR | Zbl

[18] Orellana, Rosa; Zabrocki, Mike Products of symmetric group characters, J. Comb. Theory, Ser. A, Volume 165 (2019), pp. 299-324 | DOI | MR | Zbl

[19] Pak, Igor; Panova, Greta On the complexity of computing Kronecker coefficients, Comput. Complexity, Volume 26 (2017) no. 1, pp. 1-36 | MR | Zbl

[20] Pak, Igor; Panova, Greta Upper bounds on Kronecker coefficients with few rows (2020) (https://arxiv.org/abs/2002.10956)

[21] Pak, Igor; Panova, Greta; Yeliussizov, Damir On the largest Kronecker and Littlewood–Richardson coefficients, J. Comb. Theory, Ser. A, Volume 165 (2019), pp. 44-77 | MR | Zbl

[22] Sam, Steven V.; Snowden, Andrew Proof of Stembridge’s conjecture on stability of Kronecker, J. Algebr. Comb., Volume 43 (2016) no. 1, pp. 1-10 | MR | Zbl

[23] Stanley, Richard P. Enumerative Combinatorics. Volume 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, 1999 | Zbl

[24] Stanley, Richard P. Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives, American Mathematical Society, 2000, pp. 295-319 | Zbl

[25] Stanley, Richard P. Supplementary Excercies to [23, Ch. 7], 2011 (http://www-math.mit.edu/~rstan/ec)

[26] Stanley, Richard P. Plethysm and Kronecker Products, 2016 (talk slides, http://www-math.mit.edu/~rstan/transparencies/plethysm.pdf)

[27] Vallejo, Ernesto Stability of Kronecker products of irreducible characters of the symmetric group, Electron. J. Comb., Volume 6 (1999) no. 1, R39, 7 pages | MR | Zbl