Théorie des représentations, Algèbre, Combinatoire
Breaking down the reduced Kronecker coefficients
[Analyse fine des coefficients de Kronecker réduits]
Comptes Rendus. Mathématique, Tome 358 (2020) no. 4, pp. 463-468.

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

Reçu le : 2020-04-06
Accepté le : 2020-04-25
Accepté après révision le : 2020-05-03
Publié le : 2020-07-28
DOI : https://doi.org/10.5802/crmath.60
@article{CRMATH_2020__358_4_463_0,
author = {Igor Pak and Greta Panova},
title = {Breaking down the reduced Kronecker coefficients},
journal = {Comptes Rendus. Math\'ematique},
publisher = {Acad\'emie des sciences, Paris},
volume = {358},
number = {4},
year = {2020},
pages = {463-468},
doi = {10.5802/crmath.60},
language = {en},
}
Igor Pak; Greta Panova. Breaking down the reduced Kronecker coefficients. Comptes Rendus. Mathématique, Tome 358 (2020) no. 4, pp. 463-468. doi : 10.5802/crmath.60. https://comptes-rendus.academie-sciences.fr/mathematique/item/CRMATH_2020__358_4_463_0/

[1] Christine Bessenrodt; Christiane Behns 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 | Zbl 1073.20004

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

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

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

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

[6] Yoav Dvir On the Kronecker product of ${S}_{n}$ characters, J. Algebra, Volume 154 (1993) no. 1, pp. 125-140 | Zbl 0848.20006

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

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

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

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

[11] Allen Knutson; Terence Tao 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 | Zbl 0944.05097

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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