In mathematics, Kronecker coefficients ''g''^λ_''μν'' describe the decomposition of the

tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same Field (mathematics), field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an e ...

Kronecker product In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation Operation or Operations may refer to: Arts, entertainment and media * ''Operation'' (game), a battery-operated board game that challenges dexterity * Oper ...

) of two irreducible representations of a

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...

into irreducible representations. They play an important role

algebraic combinatorics Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in alg ...

and geometric complexity theory. They were introduced by Murnaghan in 1938.

Definition

Given a partition λ of ''n'', write ''V''_λ for the

Specht module In mathematics, a Specht module is one of the representations of symmetric groups studied by . They are indexed by partitions, and in characteristic 0 the Specht modules of partitions of ''n'' form a complete set of irreducible representations of t ...

associated to λ. Then the Kronecker coefficients ''g''^λ_''μν'' are given by the rule :

V_\mu \otimes V_\nu = \bigoplus_\lambda g_^ V_\lambda.

One can interpret this on the level of

symmetric function In mathematics, a function of n variables is symmetric if its value is the same no matter the order of its arguments. For example, a function f\left(x_1,x_2\right) of two arguments is a symmetric function if and only if f\left(x_1,x_2\right) = f ...

s, giving a formula for the Kronecker product of two

Schur polynomial In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in ''n'' variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. ...

s: :

s_\mu \star s_\nu = \sum_ g_^ s_\lambda.

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

\uparrow_^ \left ( V_\mu \otimes V_\nu \right ) = \bigoplus_\lambda c_^ V_\lambda,

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 \otimes W_\nu = \bigoplus_\lambda c_^ W_\lambda.

Properties

showed that computing Kronecker coefficients is #P-hard and contained in GapP. A recent work by shows that deciding whether a given Kronecker coefficient is non-zero is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

. 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 computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction. The notion of P-complete decision problems is usef ...

in light of the above result. The Kronecker coefficients can be computed as :

g(\lambda, \mu, \nu) = \frac \sum_ \chi^(\sigma)\chi^(\sigma)\chi^(\sigma),

where

\chi^(\sigma)

is the character value of the irreducible representation corresponding to partition

\lambda

on a permutation

\sigma \in S_n

. The Kronecker coefficients also appear in the generalized Cauchy identity :

\sum_ g(\lambda, \mu , \nu) s_\lambda(x)s_\mu(y)s_\nu(z) = \prod_ \frac.

References

* {{DEFAULTSORT:Kronecker coefficient Algebraic combinatorics Representation theory Symmetric functions

Definition

Properties

See also

References