On vanishing of Kronecker coefficients

Abstract

We show that the problem of deciding positivity of Kronecker coefficients is NP-hard. Previously, this problem was conjectured to be in P, just as for the Littlewood-Richardson coefficients. Our result establishes in a formal way that Kronecker coefficients are more difficult than Littlewood-Richardson coefficients, unless P=NP. We also show that there exists a #P-formula for a particular subclass of Kronecker coefficients whose positivity is NP-hard to decide. This is an evidence that, despite the hardness of the positivity problem, there may well exist a positive combinatorial formula for the Kronecker coefficients. Finding such a formula is a major open problem in representation theory and algebraic combinatorics. Finally, we consider the existence of the partition triples $(\lambda ,\mu ,\pi )$ such that the Kronecker coefficient $k_{\mu ,\pi }^{\lambda }=0$ but the Kronecker coefficient $k_{l\mu ,l\pi }^{l\lambda }>0$ for some integer $l>1$. Such "holes" are of great interest as they witness the failure of the saturation property for the Kronecker coefficients, which is still poorly understood. Using insight from computational complexity theory, we turn our hardness proof into a positive result: We show that not only do there exist many such triples, but they can also be found efficiently. Specifically, we show that, for any $0<\epsilon \le 1$, there exists $0<a<1$ such that, for all $m$, there exist $\Omega (2^{m^a})$ partition triples $(\lambda ,\mu ,\mu )$ in the Kronecker cone such that: (a) the Kronecker coefficient $k_{\mu ,\mu }^{\lambda }$ is zero, (b) the height of $\mu$ is $m$, (c) the height of $\lambda$ is $\le m^{\epsilon }$, and (d) $|\lambda |=|\mu |\le m^3$. The proof of the last result illustrates the effectiveness of the explicit proof strategy of GCT.

43 pages, 1 figure

References in corpus (8)

• Quantum marginal problem and representations of the symmetric group
• Kronecker coefficients for one hook shape
• Multipartite Quantum States and their Marginals
• Computing Multiplicities of Lie Group Representations
• Membership in moment polytopes is in NP and coNP
• Computation of Dilated Kronecker Coefficients
• Permanent versus determinant, obstructions, and Kronecker coefficients
• Explicit Proofs and The Flip

Cited by in corpus (22)

• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Membership in moment polytopes is in NP and coNP
• Combinatoric topological string theories and group theory algorithms
• Integrality, Duality and Finiteness in Combinatoric Topological Strings
• The quantum detection of projectors in finite-dimensional algebras and holography
• Interior-point methods on manifolds: theory and applications
• All-orders asymptotics of tensor model observables from symmetries of restricted partitions
• Permanent versus determinant, obstructions, and Kronecker coefficients
• The Horn inequalities from a geometric point of view
• Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
• The co-Pieri rule for Kronecker coefficients
• NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications
• Computational complexity of counting coincidences
• All Kronecker coefficients are reduced Kronecker coefficients
• Polynomial time algorithms in invariant theory for torus actions
• Combinatorics of KP hierarchy structural constants
• Necessary conditions for the positivity of Littlewood-Richardson and plethystic coefficients
• Refuting spectral compatibility of quantum marginals
• Some Properties of Generalized Foulkes Module
• Deterministically approximating the volume of a Kostka polytope
• Machine Checked Proofs and Programs in Algebraic Combinatorics