Universal points in the asymptotic spectrum of tensors

Abstract

The asymptotic restriction problem for tensors is to decide, given tensors $s$ and $t$, whether the nth tensor power of $s$ can be obtained from the $(n+o(n))$th tensor power of t by applying linear maps to the tensor legs (this we call restriction), when $n$ goes to infinity. In this context, Volker Strassen, striving to understand the complexity of matrix multiplication, introduced in 1986 the asymptotic spectrum of tensors. Essentially, the asymptotic restriction problem for a family of tensors $X$, closed under direct sum and tensor product, reduces to finding all maps from $X$ to the reals that are monotone under restriction, normalised on diagonal tensors, additive under direct sum and multiplicative under tensor product, which Strassen named spectral points. Strassen created the support functionals, which are spectral points for oblique tensors, a strict subfamily of all tensors. Universal spectral points are spectral points for the family of all tensors. The construction of nontrivial universal spectral points has been an open problem for more than thirty years. We construct for the first time a family of nontrivial universal spectral points over the complex numbers, using quantum entropy and covariants: the quantum functionals. In the process we connect the asymptotic spectrum to the quantum marginal problem and to the entanglement polytope. To demonstrate the asymptotic spectrum, we reprove (in hindsight) recent results on the cap set problem by reducing this problem to computing asymptotic spectrum of the reduced polynomial multiplication tensor, a prime example of Strassen. A better understanding of our universal spectral points construction may lead to further progress on related questions. We additionally show that the quantum functionals characterise asymptotic slice rank for complex tensors.

References in corpus (15)

• Coding Theorem and Strong Converse for Quantum Channels
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• Progression-free sets in Z_4^n are exponentially small
• On cap sets and the group-theoretic approach to matrix multiplication
• The Partition Rank of a Tensor and $k$-Right Corners in ${\mathbb{F}}_q^n$
• Coherent states, entanglement, and geometric invariant theory
• The Growth Rate of Tri-Colored Sum-Free Sets
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• A distribution on triples with maximum entropy marginal
• Asymptotic tensor rank of graph tensors: beyond matrix multiplication
• Existence of locally maximally entangled quantum states via geometric invariant theory
• Proof of a Conjecture of Kleinberg-Sawin-Speyer
• A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory
• Simple construction of quantum universal variable-length source coding
• Sunflowers and Testing Triangle-Freeness of Functions

Cited by in corpus (2)

• Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
• Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities