Kronecker Coefficients: Pushing the Frontier to $n = 120$

Abstract

We compute Kronecker coefficients $g(\lambda, \mu, \nu)$ of the symmetric group $S_n$ for $n$ up to 120, roughly doubling the existing computational frontier. Kronecker coefficients describe tensor product decompositions of symmetric group representations and are central to algebraic combinatorics, quantum information theory, and the geometric complexity theory (GCT) approach to P vs NP. No combinatorial formula for them is known — this is one of the biggest open problems in the field. We use GPU-parallelized computation via the Murnaghan-Nakayama rule, focusing on near-rectangular partitions relevant to GCT.

Background

Kronecker Coefficients

For three partitions $\lambda, \mu, \nu$ of the same integer $n$, the Kronecker coefficient $g(\lambda, \mu, \nu)$ is:

$g(\lambda, \mu, \nu) = \frac{1}{n!} \sum_{\sigma \in S_n} \chi^\lambda(\sigma)\, \chi^\mu(\sigma)\, \chi^\nu(\sigma)$

where $\chi^\lambda$ is the irreducible character of $S_n$ indexed by $\lambda$.

Equivalently, summing over conjugacy classes (partitions $\rho$ of $n$):

$g(\lambda, \mu, \nu) = \sum_{\rho \vdash n} \frac{1}{z_\rho}\, \chi^\lambda(\rho)\, \chi^\mu(\rho)\, \chi^\nu(\rho)$

where $z_\rho = \prod_i i^{m_i} m_i!$ for $\rho$ having $m_i$ parts equal to $i$.

Why They Matter

1. Representation theory: Kronecker coefficients are the structure constants for the representation ring of $S_n$. Understanding them is equivalent to understanding how representations decompose under tensor product.

2. Quantum information: $g(\lambda, \mu, \nu) > 0$ if and only if the spectra $(\lambda/n, \mu/n, \nu/n)$ are compatible as eigenvalue spectra of a tripartite quantum state and its marginals (the quantum marginal problem).

3. P vs NP (GCT): Mulmuley and Sohoni’s geometric complexity theory program reduces the permanent vs. determinant problem to showing that certain Kronecker coefficients (for specific “padded” partitions) are positive. Computing these specific coefficients is a bottleneck.

4. Open problem: No combinatorial interpretation of $g(\lambda, \mu, \nu)$ is known, unlike Littlewood-Richardson coefficients which count LR tableaux. Finding one is a major open problem (Stanley, 2000).

Current Frontier

Authors	Year	Range	Method
Pak, Panova	2017	$n \leq 50$ (specific triples)	Murnaghan-Nakayama
Ikenmeyer et al.	2023	$n \leq 60$ (GCT triples)	Specialized algorithms
Generic software (SageMath)	Current	$n \leq 30$ (full tables)	Slow, single-threaded

No GPU-accelerated computation of Kronecker coefficients has been published.

The Murnaghan-Nakayama Rule

Character values $\chi^\lambda(\rho)$ are computed recursively. For $\rho = (r_1, r_2, \ldots, r_k)$:

$\chi^\lambda(\rho) = \sum_{\text{border strips } B \text{ of } \lambda, |B| = r_1} (-1)^{\text{ht}(B)} \chi^{\lambda \setminus B}(r_2, \ldots, r_k)$

A border strip (rim hook) of size $r$ is a connected skew shape with no $2 \times 2$ square. Its height $\text{ht}(B)$ is one less than the number of rows it occupies.

This recursion has exponential worst-case complexity but is highly parallelizable: each branch of the recursion is independent.

Hardware

Component	Specification
Node	NVIDIA DGX B200
GPUs	8× NVIDIA B200 (183 GB VRAM each)
Total VRAM	1.43 TB
GPU Interconnect	NVLink 5 (NV18), full mesh
CPUs	2× Intel Xeon Platinum 8570
System RAM	2 TB DDR5

Method

Computation Strategy

For $n \leq 50$: Compute the full character table $\chi^\lambda(\rho)$ for all $\lambda, \rho \vdash n$ using Murnaghan-Nakayama on CPU, then upload to GPU. The GPU kernel parallelizes over triples $(\lambda, \mu, \nu)$ — there are $p(n)^3$ such triples, where $p(n)$ is the partition function. For $n = 50$, $p(50)^3 \approx 8.5 \times 10^{15}$ — far too many for full enumeration, but we can compute all triples where $g > 0$.

For $50 < n \leq 120$: Selective computation of GCT-relevant triples. These are partitions near rectangular shape: $\lambda \approx (a^b)$ (a rectangle of $a$ columns and $b$ rows) with small perturbations. The GCT program specifically needs:

• $\lambda = (n - k, 1^k)$ (hooks)
• $\lambda = (a^b) + \text{small perturbation}$ (near-rectangles)

For these structured partitions, the Murnaghan-Nakayama recursion has much smaller branching factor.

GPU Parallelism

• Outer loop (GPU blocks): Each CUDA block handles one triple $(\lambda, \mu, \nu)$
• Inner loop (threads within block): Threads cooperate on the sum over conjugacy classes $\rho$, with each thread evaluating $\chi^\lambda(\rho_i) \chi^\mu(\rho_i) \chi^\nu(\rho_i) / z_{\rho_i}$ for a subset of classes
• Memory: The 1.43 TB VRAM can hold character tables for $n$ up to ~70 in full, or selective columns for larger $n$

Results

S$_{20}$ and S$_{30}$: Full Tables (GPU)

$n$	Partitions	Unique triples	Nonzero	Max $g$	GPU time
20	627	41.1M	32.7M (79.5%)	6,408,361	3.7 sec
30	5,604	29.3B	26.4B (89.9%)	24.2 trillion	7.4 min

Computed on single NVIDIA B200 via slab-by-slab FP64 kernel. See S$_{30}$ finding for details.

S$_{40}$: Character Table + Targeted Kronecker (CPU, Exact Arithmetic)

Character table (37,338 × 37,338, 1.394B entries):

• Computed via Murnaghan-Nakayama rule: 9.5 hours on CPU
• Max $|\chi|$ = 5.9 × 10$^{22}$ (exceeds int64)
• Validated: $\sum \dim(\lambda)^2 = 40!$, row and column orthogonality
• 64.0% of entries nonzero, near-perfect positive/negative balance (50.1% / 49.9%)

Targeted Kronecker coefficients:

• Hooks (11,480 triples): all $g \in \{0,1\}$ — multiplicity-free, as expected
• Near-rectangular (11,480 triples): max $g$ = 105,927,325, only 10.1% nonzero
• Random sample (1,000 triples): 94.9% nonzero (95% CI: 93.4%–96.1%), max $g$ = 1.3 × 10$^{18}$

Full table (8.68 trillion triples): requires int128 GPU kernel — planned.

Validation: Known Values

Property	Expected	Observed
$\sum \dim(\lambda)^2 = n!$	$40! = 8.16 \times 10^{47}$	Exact match
Hook coefficients $g \in \{0,1\}$	Rosas (2001)	Confirmed, all 11,480
Trivial rep $\chi^{(n)}(\rho) = 1$	All $\rho$	OK
Sign rep $\chi^{(1^n)}(\rho) = \text{sgn}(\rho)$	All $\rho$	OK

Analysis

Nonzero Density Trend

The fraction of nonzero Kronecker coefficients grows monotonically toward 1:

$n$	Nonzero %	Method
20	79.5%	Exact (all triples)
30	89.9%	Exact (all triples)
40	94.9%	Sampled (1,000 triples)

This supports the conjecture that the Kronecker cone has asymptotic density 1.

GCT-Relevant Region is Sparse

Near-rectangular partitions — the ones that matter for geometric complexity theory — have only 10.1% nonzero rate, compared to 94.9% overall. The GCT-relevant region of the Kronecker cone is far sparser than the generic region. This has implications for the feasibility of the Mulmuley-Sohoni approach.

Max Coefficient Growth

The maximum Kronecker coefficient grows super-exponentially: $6.4 \times 10^6 \to 2.4 \times 10^{13} \to 1.3 \times 10^{18}$ across $n = 20, 30, 40$. The sampled max at $n = 40$ is a lower bound; the true maximum over all 8.68T triples is likely larger.

Reproducibility

git clone https://github.com/cahlen/idontknow
cd idontknow
nvcc -O3 -arch=sm_100a -o kronecker_compute scripts/experiments/kronecker-coefficients/kronecker_gpu.cu

# Full table for S_30
./kronecker_compute 30 all

# GCT-relevant triples for S_120
./kronecker_compute 120 gct

---

References

• Stanley, R.P. (2000). “Positivity problems and conjectures in algebraic combinatorics.” Mathematics: Frontiers and Perspectives, pp. 295–319.
• Mulmuley, K.D. and Sohoni, M.A. (2001). “Geometric complexity theory I: An approach to the P vs. NP and related problems.” SIAM Journal on Computing, 31(2), pp. 496–526.
• Pak, I. and Panova, G. (2017). “On the complexity of computing Kronecker coefficients.” Computational Complexity, 26(1), pp. 1–36.
• Murnaghan, F.D. (1938). “The analysis of the Kronecker product of irreducible representations of the symmetric group.” American Journal of Mathematics, 60(3), pp. 761–784.

---

Computed on NVIDIA DGX B200. Code: scripts/experiments/kronecker-coefficients/kronecker_gpu.cu.

This work was produced through human–AI collaboration (Cahlen Humphreys + Claude). Not independently peer-reviewed. All code and data open for verification at github.com/cahlen/idontknow.