Geodesic
All Kronecker coefficients are reduced Kronecker coefficients
Forum of Mathematics, Pi, Tome 12 (2024)

Voir la notice de l'article provenant de la source Cambridge University Press

We settle the question of where exactly do the reduced Kronecker coefficients lie on the spectrum between the Littlewood-Richardson and Kronecker coefficients by showing that every Kronecker coefficient of the symmetric group is equal to a reduced Kronecker coefficient by an explicit construction. This implies the equivalence of an open problem by Stanley from 2000 and an open problem by Kirillov from 2004 about combinatorial interpretations of these two families of coefficients. Moreover, as a corollary, we deduce that deciding the positivity of reduced Kronecker coefficients is ${\textsf {NP}}$-hard, and computing them is ${{{\textsf {#P}}}}$-hard under parsimonious many-one reductions. Our proof also provides an explicit isomorphism of the corresponding highest weight vector spaces. 
@article{10_1017_fmp_2024_23,
     author = {Christian Ikenmeyer and Greta Panova},
     title = {All {Kronecker} coefficients are reduced {Kronecker} coefficients},
     journal = {Forum of Mathematics, Pi},
     publisher = {mathdoc},
     volume = {12},
     year = {2024},
     doi = {10.1017/fmp.2024.23},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2024.23/}
}
TY  - JOUR
AU  - Christian Ikenmeyer
AU  - Greta Panova
TI  - All Kronecker coefficients are reduced Kronecker coefficients
JO  - Forum of Mathematics, Pi
PY  - 2024
VL  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2024.23/
DO  - 10.1017/fmp.2024.23
LA  - en
ID  - 10_1017_fmp_2024_23
ER  - 
%0 Journal Article
%A Christian Ikenmeyer
%A Greta Panova
%T All Kronecker coefficients are reduced Kronecker coefficients
%J Forum of Mathematics, Pi
%D 2024
%V 12
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2024.23/
%R 10.1017/fmp.2024.23
%G en
%F 10_1017_fmp_2024_23
Christian Ikenmeyer; Greta Panova. All Kronecker coefficients are reduced Kronecker coefficients. Forum of Mathematics, Pi, Tome 12 (2024). doi: 10.1017/fmp.2024.23

[BB17] Bessenrodt, C. and Bowman, C., ‘Multiplicity-free Kronecker products of characters of the symmetric groups’, Adv. Math. 322 (2017), 473–529.Google Scholar | DOI

[BCG+23] Bravyi, S., Chowdhury, A., Gosset, D., Havlícĕk, V. and Zhu, G., ‘Quantum complexity of the Kronecker coefficients’, Preprint, 2023, .Google Scholar | arXiv | DOI

[BCMW17] Bürgisser, P., Christandl, M., Mulmuley, K. and Walter, M., ‘Membership in moment polytopes is in NP and coNP’, SIAM J. Comput. 46(3) (2017), 972–991.Google Scholar | DOI

[BDVO15] Bowman, C., De Visscher, M. and Orellana, R., ‘The partition algebra and the Kronecker coefficients’, Trans. Am. Math. Soc. 367(5) (2015), 3647–3667.Google Scholar | DOI

[BL18] Blasiak, J. and Liu, R. I., ‘Kronecker coefficients and noncommutative super Schur functions’, J. Comb. Theory, Ser. A 158 (2018), 315–361.Google Scholar | DOI

[Bla17] Blasiak, J., ‘Kronecker coefficients for one hook shape’, Sém. Lothar. Combin. 77 (2017), 2016–2017.Google Scholar

[BMS15] Blasiak, J., Mulmuley, K. and Sohoni, M., ‘Geometric complexity theory IV: Nonstandard quantum group for the Kronecker problem’, in Memoirs of the American Mathematical Society, volume 235 (American Mathematical Society, Providence, RI, 2015), 1–165.Google Scholar

[BO05] Ballantine, C. and Orellana, R., ‘On the Kronecker product ’, Electron. J. Comb. 12 (2005), R28.Google Scholar

[BO06] Ballantine, C. and Orellana, R., ‘A combinatorial interpretation for the coefficients in the Kronecker product ’, Sém. Lothar. Combin. A 54A (2006), B54Af.Google Scholar

[BOR09] Briand, E., Orellana, R. and Rosas, M., ‘Reduced Kronecker coefficients and counter–examples to Mulmuley’s strong saturation conjecture SH’, Comput. Complex. 18 (2009), 577–600. With an appendix by Ketan Mulmuley.Google Scholar | DOI

[BOR11] Briand, E., Orellana, R. and Rosas, M., ‘The stability of the Kronecker product of Schur functions’, J. Algebra 331(1) (2011), 11–27.Google Scholar | DOI

[Bri93] Brion, M., ‘Stable properties of plethysm: On two conjectures of Foulkes’, Manuscripta Math. 80 (1993), 347–371.Google Scholar | DOI

[CDW12] Christandl, M., Doran, B. and Walter, M., ‘Computing multiplicities of Lie group representations’, in 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (IEEE Computer Society, US, 2012), 639–648.Google Scholar | DOI

[Chr06] Christandl, M., ‘The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography’, PhD thesis, 2006, .Google Scholar | arXiv

[CR15] Colmenarejo, L. and Rosas, M., ‘Combinatorics on a family of reduced Kronecker coefficients’, Comptes Rendus Math. 353 (2015), 865–869.Google Scholar | DOI

[CŞW18] Christandl, M., Şahinoğlu, M. B. and Walter, M., ‘Recoupling coefficients and quantum entropies’, Ann. Henri Poincaré 19 (2018), 385–410.Google Scholar | DOI

[DLM06] De Loera, J. and Mcallister, T., ‘On the computation of Clebsch–Gordan coefficients and the dilation effect’, Exp. Math. 15(1) (2006), 7–19.Google Scholar | DOI

[Dvi93] Dvir, Y., ‘On the Kronecker product of characters’, J. Algebra 154(1) (1993), 125–140.Google Scholar | DOI

[Ful97] Fulton, W., Young Tableaux, Number 35 (Cambridge University Press, Cambridge, 1997), i–260. With applications to representation theory and geometry.Google Scholar

[GR85] Garsia, A. and Remmel, J., ‘Shuffles of permutations and the Kronecker product’, Graphs Comb. 1 (1985), 217–263.Google Scholar | DOI

[Ike12] Ikenmeyer, C., ‘Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients’, PhD thesis, Paderborn, Universität Paderborn, 2012.Google Scholar

[IMW17] Ikenmeyer, C., Mulmuley, K. and Walter, M., ‘On vanishing of Kronecker coefficients’, Comput. Complex. 26 (2017), 949–992.Google Scholar | DOI

[IP17] Ikenmeyer, C. and Panova, G., ‘Rectangular Kronecker coefficients and plethysms in geometric complexity theory’, Adv. Math. 319 (2017), 40–66.Google Scholar | DOI

[IP22] Ikenmeyer, C. and Pak, I., ‘What is in #P and what is not?’, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, Denver, CO, 2022), 860–871.Google Scholar | DOI

[JK84] James, G. and Kerber, A., ‘The representation theory of the symmetric group’, in Encyclopedia of Mathematics and its Applications (Cambridge University Press, Cambridge, 1984), i–510.Google Scholar

[Kir04] Kirillov, A. N., ‘An invitation to the generalized saturation conjecture’, Publ. Res. Inst. Math. Sci. 40(4) (2004), 1147–1239.Google Scholar | DOI

[Kly04] Klyachko, A., ‘Quantum marginal problem and representations of the symmetric group’, Preprint, 2004, .Google Scholar | arXiv

[KT99] Knutson, A. and Tao, T., ‘The honeycomb model of tensor products I: Proof of the saturation conjecture’, J. Am. Math. Soc. 12(4) (1999), 1055–1090.Google Scholar | DOI

[Las79] Lascoux, A., ‘Produit de Kronecker des représentations du groupe symétrique’, in Séminaire d’Algèbre Paul Dubreil et Marie-Paule Malliavin: Proceedings, Paris 1979 (32ème Année), Lecture Notes in Mathematics, 795 (Springer, Berlin, 1979), 319–329.Google Scholar | DOI

[Lit58] Littlewood, D. E., ‘Products and plethysms of characters with orthogonal, symplectic and symmetric groups’, Can. J. Math. 10 (1958), 17–32.Google Scholar | DOI

[Liu17] Liu, R. I., ‘A simplified Kronecker rule for one hook shape’, Proc. Am. Math. Soc. 145(9) (2017), 3657–3664.Google Scholar | DOI

[Mac98] Macdonald, I. G., Symmetric Functions and Hall Polynomials, second edn (Oxford University Press, Oxford, 1998), 1–474.Google Scholar

[Man15] Manivel, L., ‘On the asymptotics of Kronecker coefficients’, J. Algebr. Comb. 42(4) (2015), 999–1025.Google Scholar | DOI

[MNS12] Mulmuley, K., Narayanan, H. and Sohoni, M., ‘Geometric complexity theory III: On deciding nonvanishing of a Littlewood–Richardson coefficient’, J. Algebr. Comb. 36(1) (2012), 103–110.Google Scholar | DOI

[Mur38] Murnaghan, F. D., ‘The analysis of the Kronecker product of irreducible representations of the symmetric group’, Am. J. Math. 60(3) (1938), 761–784.Google Scholar | DOI

[Mur56] Murnaghan, F. D., ‘On the Kronecker product of irreducible representations of the symmetric group’, Proc. Nat. Acad. Sci. 42(2) (1956), 95–98.Google ScholarPubMed | DOI

[OZ19] Orellana, R. and Zabrocki, M., ‘Products of symmetric group characters’, J. Comb. Theory, Ser. A 165 (2019), 299–324.Google Scholar | DOI

[OZ21] Orellana, R. and Zabrocki, M., ‘Symmetric group characters as symmetric functions’, Adv. Math. 390 (2021), 107943.Google Scholar | DOI

[Pak22] Pak, I., ‘What is a combinatorial interpretation?’, Preprint, 2022, . To appear in Proc. Sym. Pure Math. OPAC 2022.Google Scholar | arXiv

[Pan15] Panova, G., ‘Kronecker coefficients: Combinatorics, complexity and beyond’, 2015, https://drive.google.com/file/d/1T2bVbLa4Bozy2_VBzT_Z0aezw8Y7ysrX/view. Presentation slides.Google Scholar

[Pan23] Panova, G., ‘Complexity and asymptotics of structure constants’, OPAC 2023, Google Scholar | arXiv

[PP14] Pak, I. and Panova, G., ‘Unimodality via Kronecker products’, J. Algebr. Comb. 40 (2014), 1103–1120.Google Scholar | DOI

[PP17a] Pak, I. and Panova, G., ‘Bounds on certain classes of Kronecker and q-binomial coefficients’, J. Combin. Theory, Ser. A 147 (2017), 1–17.Google Scholar | DOI

[PP17b] Pak, I. and Panova, G., ‘On the complexity of computing Kronecker coefficients’, Comput. Complex. 26 (2017), 1–36.Google Scholar | DOI

[PP20a] Pak, I. and Panova, G., ‘Bounds on Kronecker coefficients via contingency tables’, Linear Algebra Appl. 602 (2020), 157–178.Google Scholar | DOI

[PP20b] Pak, I. and Panova, G., ‘Breaking down the reduced Kronecker coefficients’, Comptes Rendus Math. 358(4) (2020), 463–468.Google Scholar | DOI

[Rem89] Remmel, J., ‘A formula for the Kronecker products of Schur functions of hook shapes’, J. Algebra 120(1) (1989), 100–118.Google Scholar | DOI

[RW94] Remmel, J. and Whitehead, T., ‘On the Kronecker product of Schur functions of two row shapes’, Bull. Belg. Math. Soc. Simon Stevin 1(5) (1994), 649–683.Google Scholar | DOI

[Sag13] Sagan, B. E., ‘The symmetric group: Representations, combinatorial algorithms, and symmetric functions’, in Graduate Texts in Mathematics, volume 203 (Springer, NY, 2013), i–241.Google Scholar

[SS16] Sam, S. and Snowden, A., ‘Proof of Stembridge’s conjecture on stability of Kronecker coefficients’, J. Algebr. Comb. 43(1) (2016), 1–10.Google Scholar | DOI

[Sta99] Stanley, R., Enumerative Combinatorics, volume 2, first edn (Cambridge University Press, Cambridge, 1999), i–585.Google Scholar | DOI

[Sta00] Stanley, R., ‘Positivity problems and conjectures in algebraic combinatorics’, in Mathematics: Frontiers and Perspectives (American Mathematical Society, Providence, RI, 2000), 295–319.Google Scholar

[Ste] Stembridge, J., ‘Generalized stability of Kronecker coefficients’, 2014, http://www.math.lsa.umich.edu/~jrs.Google Scholar

[Tew15] Tewari, V., ‘Kronecker coefficients for some near-rectangular partitions’, J. Algebra 429 (2015), 287–317.Google Scholar | DOI

[Val99] Vallejo, E., ‘Stability of Kronecker products of irreducible characters of the symmetric group’, Electron. J. Comb. 6 (1999), R39.Google Scholar | DOI

[Val09] Vallejo, E., ‘A stability property for coefficients in Kronecker products of complex characters’, Electron. J. Comb. 16(22) (2009), 1.Google Scholar

[Val20] Vallejo, E., ‘Stability of Kronecker coefficients via discrete tomography’, Discrete Math. 343(5) (2020), 111817.Google Scholar | DOI

Cité par Sources :