Combinatorial interpretation of Kronecker coefficients

Combinatorial interpretation of Kronecker coefficients

Definitions and mathematical statement

A partition $\lambda\vdash n$ is a nonincreasing sequence of positive integers summing to $n$, and $S^\lambda$ denotes the corresponding irreducible complex representation of the symmetric group $S_n$. The Kronecker coefficients are defined by \[ S^\lambda\otimes S^\mu\cong \bigoplus_{\nu\vdash n}(S^\nu)^{\oplus g_{\lambda,\mu,\nu}}, \qquad g_{\lambda,\mu,\nu}=\dim\operatorname{Hom}_{S_n} (S^\nu,S^\lambda\otimes S^\mu). \] Find a uniform positive combinatorial rule, for example explicit finite combinatorial sets $\mathcal C_{\lambda,\mu,\nu}$ whose cardinalities give these coefficients without cancellation. The catalogue does not impose a runtime bound or a formal class of allowed combinatorial rules. Merely naming a basis of the above Hom space, or declaring a set of that unknown cardinality, is a tautology rather than the intended interpretation.

Formulation and concept references: [S1].

Short English statement

Can every Kronecker coefficient be computed by directly counting explicitly described combinatorial objects, without subtracting cancelling contributions?

Research attempt

Status: UNRESOLVED. A uniform positive rule for arbitrary triples of partitions is not obtained. This attempt gives an explicit positive rule when one partition is $(n-1,1)$, derives the usual signed character calculation to locate the cancellation problem, and supplies a small exact obstruction to importing the saturation argument from Littlewood--Richardson coefficients. The rules and examples below are special cases, not a claimed general solution.

Source audit and meaning of a rule.

The abstract of [S1], checked on 27 September 2026, describes general alternating-sum expressions and positive expressions for specified families involving hooks and certain further shapes. An alternating expression for every coefficient and a positive expression for some coefficients do not together give a positive expression for every coefficient. The catalogue also correctly leaves the formal class and running time of an admissible rule unspecified. In this attempt, a positive rule means a finite collection of combinatorial objects with membership conditions stated directly from the three diagrams, together with a proof that its cardinality equals the coefficient. Evaluating a signed character sum first and subsequently declaring that many objects is not such a construction.

1. The character formula and its exact source of cancellation.

Let $\chi^\lambda$ be the character of $S^\lambda$. Complex irreducible representations of $S_n$ are self-dual, so \[ g_{\lambda,\mu,\nu} =\dim (S^\lambda\otimes S^\mu\otimes S^\nu)^{S_n}. \] For any finite-group representation $V$, the averaging operator \[ P=\frac1{|G|}\sum_{\sigma\in G}\rho_V(\sigma) \] satisfies $P^2=P$, and its image is precisely the invariant subspace: group multiplication permutes its summands, and it fixes invariant vectors. An idempotent has eigenvalues zero and one, hence its trace equals its rank. Applying this to the tensor product and grouping permutations by cycle type gives \[ g_{\lambda,\mu,\nu} =\sum_{\rho\vdash n} \frac{\chi^\lambda(\rho)\chi^\mu(\rho)\chi^\nu(\rho)}{z_\rho}, \qquad z_\rho=\prod_{i\ge1}i^{m_i}m_i!, \] where $m_i$ is the number of parts of $\rho$ equal to $i$. Indeed a permutation with those cycle multiplicities has centralizer order $z_\rho$, so its conjugacy class has size $n!/z_\rho$.

This argument proves that the final rational sum is a nonnegative integer, and also proves symmetry in all three partitions. It does not make the individual summands nonnegative. For example, on $S_3$ the standard character has values $2,0,-1$ on cycle types $1^3,21,3$. Its triple product therefore has a negative contribution from the 3-cycles: \[ g_{(2,1),(2,1),(2,1)} =\frac{2^3}{6}+\frac{0^3}{2}+\frac{(-1)^3}{3}=1. \] Averaging has explained integrality through linear algebra, not furnished a cancellation-free description of the single surviving object.

2. Two elementary positive families.

The trivial representation is $S^{(n)}$, so Schur's lemma gives \[ g_{\lambda,(n),\mu}=\begin{cases}1&\lambda=\mu,\\0&\lambda\ne\mu.\end{cases} \] The sign twist sends $S^\lambda$ to $S^{\lambda'}$, where $\lambda'$ is the conjugate partition. Thus \[ g_{\lambda,(1^n),\mu}=\begin{cases}1&\lambda'=\mu,\\0&\lambda'\ne\mu.\end{cases} \] A singleton when the indicated equality holds and the empty set otherwise are literal positive rules. By the symmetry already proved, any position in the triple may contain the trivial or sign partition. These formulas also check normalization: in particular, a proposed rule must reproduce the conjugation imposed by a sign factor, rather than confusing it with the trivial factor.

The representation-theoretic inputs here are the classical parametrization by Specht modules, self-duality, and the sign-twist identity. They are being used as established results, not proved from scratch or counted as progress on the unrestricted question.

3. An explicit rule with one standard representation.

Assume $n\ge2$, and write $D(\lambda)$ for the set of partitions of $n-1$ obtained by deleting a removable corner from $\lambda$. Each resulting diagram occurs once. We will prove \[ g_{\lambda,(n-1,1),\mu} =|D(\lambda)\cap D(\mu)|-\mathbf 1_{\lambda=\mu}. \] Although this display contains a subtraction, it immediately gives the following positive objects. If $\lambda\ne\mu$, take the common predecessor diagrams. If $\lambda=\mu$, take all removable corners of $\lambda$ except a specified distinguished corner, for example the rightmost cell of the last row. Every nonempty partition has that removable corner, so the exclusion is defined even for a rectangle with only one removable corner. The resulting set has the displayed cardinality without evaluating any signed sum.

Here is the proof. Let $P_n$ be the permutation representation on $n$ letters. Its invariant line is spanned by the sum of the coordinate vectors, and its complementary sum-zero subspace is the standard representation. Hence \[ P_n\cong S^{(n)}\oplus S^{(n-1,1)}. \] Also $P_n=\operatorname{Ind}_{S_{n-1}}^{S_n}\mathbf1$. The tensor-induction identity gives \[ S^\lambda\otimes P_n \cong\operatorname{Ind}_{S_{n-1}}^{S_n} \operatorname{Res}_{S_{n-1}}^{S_n}S^\lambda. \] One can verify this identity directly: for a subgroup $H\le G$ and a $G$-module $V$, the map from the induced module sends $g\otimes v$ to $gv\otimes[gH]$; the relation $gh\otimes v=g\otimes hv$ makes it well-defined, and the inverse is read on each coset summand.

By Frobenius reciprocity, the multiplicity of $S^\mu$ on the right is the inner product of the restrictions of $S^\lambda$ and $S^\mu$. The classical multiplicity-free branching rule says \[ \operatorname{Res}_{S_{n-1}}^{S_n}S^\lambda \cong\bigoplus_{\eta\in D(\lambda)}S^\eta. \] The inner product is therefore $|D(\lambda)\cap D(\mu)|$. The trivial summand in $P_n$ contributes exactly $\mathbf1_{\lambda=\mu}$, leaving the claimed coefficient for its standard summand. The only substantial imported combinatorial theorem in this proof is the branching rule; the tensor-induction and multiplicity calculations have been made explicit.

For example, for $n=4$ the predecessors of $(3,1)$ are $(3)$ and $(2,1)$. The rule gives \[ S^{(3,1)}\otimes S^{(3,1)} \cong S^{(4)}\oplus S^{(3,1)}\oplus S^{(2,2)}\oplus S^{(2,1,1)}. \] The dimensions $1+3+2+3=9$ agree with $3^2$. The absent sign summand also follows from the sign rule, since $(3,1)'=(2,1,1)\ne(3,1)$. This is a useful example where the distinguished-corner exclusion makes the diagonal coefficient one instead of the uncorrected count two.

4. A concrete failure of saturation.

For partitions, let $N\lambda$ mean multiplying every row length by $N$, not repeating each row $N$ times. At size two, \[ g_{(1,1),(1,1),(1,1)}=0, \] because sign tensor sign is trivial. At size four, however, \[ g_{(2,2),(2,2),(2,2)}=1. \] For completeness, this latter calculation needs only a five-entry character. Act on the three partitions of four letters into two unordered pairs. The permutation module splits as a trivial line and the irreducible two-dimensional module $S^{(2,2)}$. Its character on cycle types $1^4,21^2,2^2,31,4$ is \[ (2,0,2,-1,0). \] These entries come by subtracting one from the respective numbers $3,1,3,0,1$ of fixed pairings. Its squared character norm is \[ \frac{1\cdot4+6\cdot0+3\cdot4+8\cdot1+6\cdot0}{24}=1, \] confirming irreducibility; the usual Specht labeling identifies this two-dimensional representation with $(2,2)$. Cubing the character and weighting by those same class sizes gives \[ \frac{8+3\cdot8-8}{24}=1. \] Thus positivity at twice a triple of partitions need not descend to positivity at that triple. This directly rules out a naive transfer of the Littlewood--Richardson saturation conclusion to Kronecker coefficients. It does not rule out polyhedral rules with additional congruence conditions, nor a positive rule of a quite different sort.

5. Why several apparently positive algorithms miss the target.

A basis of the invariant subspace can be computed by solving a finite linear system in matrix realizations of the three Specht modules. Its dimension is certainly a nonnegative integer. However, describing the desired combinatorial objects as the pivot columns selected after elimination merely hides the invariant-space computation inside a membership test. It does not provide the diagrammatic counting rule sought here. Similarly, a list of the integers from one to the value obtained by the character formula is a re-encoding of the answer, not an explanation of it.

The Murnaghan--Nakayama recursion does give a completely finite combinatorial computation of each character: remove successive rim hooks of specified cycle lengths, weight each by $(-1)^{h-1}$, and sum. Substitution into the character formula still introduces signs and rational class weights. Any proposal to erase the signs must explain why the deleted terms pair with equal absolute weights and opposite signs, and characterize the unpaired objects independently. Nonnegativity of the final representation multiplicity does not supply such a pairing.

A possible direction is to begin with a suitably integral signed model and construct a sign-reversing involution with an explicit fixed-point set. To make this a proof, one needs a precise finite signed set, an involution defined on every non-fixed element, proof that it preserves the relevant triple and reverses sign, and a positive characterization of every survivor. No such general involution is defined in this attempt. The corner rule above succeeds because restriction to $S_{n-1}$ is multiplicity-free and the only subtraction is one known trivial summand; that mechanism does not automatically persist for an arbitrary factor $S^\mu$.

6. Exact checks and the remaining gap.

The offline computation enumerates partitions through size seven, evaluates characters by rim-hook removal using exact integers, and checks character orthogonality. It then calculates all triple coefficients by exact rational arithmetic, verifies their nonnegative integrality, and compares the trivial, sign, and standard-factor formulas with every applicable triple. The size-two and size-four saturation example is checked independently from the displayed small character tables. These tests help detect a wrong hook sign, a confused partition conjugation, or an incorrect distinguished-corner count. They cannot establish a formula in arbitrary size.

The substantive output is a positive family with one standard factor and an explicit explanation of the obstruction to two natural shortcuts. The uniform arbitrary-shape rule is still absent. In particular, the external alternating expressions of [S1], the invariant-space projector, and exhaustive finite character computations remain methods with cancellation or linear algebra; none is being presented as the requested resolution.

Sources

• S1 John M. Campbell, Kronecker coefficients via the Giambelli identity for Schur functions, arXiv:2604.23286, 2026. https://arxiv.org/abs/2604.23286. Formulation source.
• E1 Pavel Etingof and collaborators, Introduction to Representation Theory, author-hosted lecture notes, Chapters 3--4. https://math.mit.edu/~etingof/replect.pdf. Added primary expository source: Character orthogonality, Frobenius reciprocity, and symmetric-group representations. Consulted 27 September 2026.