In mathematics, Kronecker coefficients gλμν describe the decomposition of the tensor product (= Kronecker product) of two irreducible representations of a symmetric group into irreducible representations. They play an important role algebraic combinatorics and geometric complexity theory. They were introduced by Murnaghan in 1938.
Given a partition λ of n, write Vλ for the Specht module associated to λ. Then the Kronecker coefficients gλμν are given by the rule
This is to be compared with Littlewood–Richardson coefficients, where one instead considers the induced representation
and the corresponding operation of symmetric functions is the usual product. Also note that the Littlewood–Richardson coefficients are the analogue of the Kronecker coefficients for representations of GLn, i.e. if we write Wλ for the irreducible representation corresponding to λ (where λ has at most n parts), one gets that
Bürgisser & Ikenmeyer (2008) showed that computing Kronecker coefficients is #P-hard and contained in GapP. A recent work by Ikenmeyer, Mulmuley & Walter (2017) shows that deciding whether a given Kronecker coefficient is non-zero is NP-hard. This recent interest in computational complexity of these coefficients arises from its relevance in the Geometric Complexity Theory program.
A major unsolved problem in representation theory and combinatorics is to give a combinatorial description of the Kronecker coefficients. It has been open since 1938, when Murnaghan asked for such a combinatorial description. A combinatorial description would also imply that the problem is # P-complete in light of the above result.
The Kronecker coefficients can be computed as
The Kronecker coefficients also appear in the generalized Cauchy identity
- Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael (2017-12-01). "On vanishing of Kronecker coefficients". Computational Complexity. 26 (4): 949–992. arXiv:1507.02955. doi:10.1007/s00037-017-0158-y. ISSN 1420-8954. S2CID 1126187.
- Murnaghan, D. (1938). "The Analysis of the Direct Product of Irreducible Representations of the Symmetric Groups". Amer. J. Math. 60 (9): 44–65. doi:10.2307/2371542. JSTOR 2371542. PMC 1076971. PMID 16577800.
- Bürgisser, Peter; Ikenmeyer, Christian (2008), "The complexity of computing Kronecker coefficients", 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), Discrete Math. Theor. Comput. Sci. Proc., AJ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 357–368, MR 2721467