Kronecker coefficient explained

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.

Definition

Given a partition λ of n, write V_λ for the Specht module associated to λ. Then the Kronecker coefficients g^λ_μν are given by the rule

V _{\mu} ⊗ V _{\nu} = o plus _{λ} g ^{λ} _{\mu \nu} V _{λ.}

One can interpret this on the level of symmetric functions, giving a formula for the Kronecker product of two Schur polynomials:

s _{\mu} \star s _{\nu} = \sum _{λ} g ^{λ} _{\mu \nu} s _{λ.}

This is to be compared with Littlewood–Richardson coefficients, where one instead considers the induced representation

\uparrow ^{S _{|λ|}} _{S _{|\mu|} x S _{|\nu|}} \left ( V _{\mu} ⊗ V _{\nu} \right ) = o plus _{λ} c ^{λ} _{\mu \nu} V _{λ,}

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 GL_n, i.e. if we write W_λ for the irreducible representation corresponding to λ (where λ has at most n parts), one gets that

W _{\mu} ⊗ W _{\nu} = o plus _{λ} c ^{λ} _{\mu \nu} W _{λ.}

Properties

showed that computing Kronecker coefficients is

1. P-hard

and contained in GapP. A recent work by shows that deciding whether a given Kronecker coefficient is non-zero is NP-hard.^[1] 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.^[2] 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$$g(\backslash lambda,\; \backslash mu,\; \backslash nu)\; =\; \backslash frac\; \backslash sum\_\; \backslash chi^(\backslash sigma)\backslash chi^(\backslash sigma)\backslash chi^(\backslash sigma),$$where

\chi ^{λ} (\sigma) is the character value of the irreducible representation corresponding to integer partition λ on a permutation \sigma \in S _{n} .

The Kronecker coefficients also appear in the generalized Cauchy identity$$\backslash sum\_\; g(\backslash lambda,\; \backslash mu,\; \backslash nu)\; s\_\backslash lambda(x)s\_\backslash mu(y)s\_\backslash nu(z)\; =\; \backslash prod\_\; \backslash frac.$$

See also

• Littlewood–Richardson coefficient

Notes and References

1. Ikenmeyer. Christian. Mulmuley. Ketan D.. Walter. Michael. 2017-12-01. On vanishing of Kronecker coefficients. Computational Complexity. en. 26. 4. 949–992. 10.1007/s00037-017-0158-y. 1420-8954. 1507.02955. 1126187.
2. Murnaghan. D.. The Analysis of the Direct Product of Irreducible Representations of the Symmetric Groups. Amer. J. Math.. 1938. 60. 9. 44–65. 10.2307/2371542. 16577800. 1076971. 2371542.