PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal points in the asymptotic spectrum of tensors

Matthias Christandl, Péter Vrana, Jeroen Zuiddam

arXiv:1709.07851v3math.COcs.CCquant-ph

TL;DR

The asymptotic restriction problem asks whether one tensor asymptotically restricts to another, while nontrivial universal spectral points had remained unconstructed for over thirty years. The paper introduces quantum functionals and proves they are universal spectral points over the complex numbers.

  • Problem

    The asymptotic restriction problem asks whether one tensor asymptotically restricts to another, while nontrivial universal spectral points had remained unconstructed for over thirty years.

    Source: §1.1 · pp. 3–4

  • Method

    The paper introduces quantum functionals on complex tensors, using quantum entropy and partial traces of transformed tensors, and proves these maps are universal spectral points.

    Source: §1.1 · p. 4

  • Results

    The quantum functionals are nontrivial universal spectral points over the complex numbers, resolving a construction problem open for more than thirty years.

    Source: §1.1 · p. 4, §3.4 · p. 27

  • Takeaways & Limitations

    For complex tensors, the quantum functionals upper-bound asymptotic multi-slice rank and slice rank under the respective parameter conditions.

    Source: §5.3 · p. 47

    The quantum functionals do not apply to the cap-set problem because the authors cannot work over the complex numbers for that problem.

    Source: §1.1 · p. 5

Abstract

from arXiv · show

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.

1. Introduction

The introduction frames spectral points as obstructions to asymptotic restriction and presents quantum functionals as nontrivial universal spectral points over the complex numbers. It also situates cap-set and slice-rank results as applications of the framework.

1.2. Asymptotic spectra for tensors

  • Spectral points provide obstructions to asymptotic restriction: if a point evaluates the source below the target, the source cannot asymptotically restrict to it.The spectral theorem characterizes asymptotic restriction through pointwise comparison across the spectrum.Source: §1.1 · p. 4, §1.2 · p. 6

1.1. The asymptotic restriction problem

  • Strassen's support functionals apply to oblique tensors, a strict subfamily of all tensors, whereas universal spectral points apply to the full tensor family.Oblique tensors have support that is an antichain in some basis.Source: §1.1 · p. 4, §1.2 · p. 7

1.3. This paper

  • The quantum functionals give the first nontrivial universal spectral points over the complex numbers, with restriction monotonicity, normalization, additivity, and multiplicativity.The paper also establishes monotonicity under degeneration.Source: §1.1 · p. 4, §1.3 · p. 8

1.1. The asymptotic restriction problem

  • The quantum-functional construction connects the asymptotic spectrum to quantum marginal entropies and entanglement polytopes through an optimization over the polytope.The entanglement polytope is formed from the single-system marginal entropies across the closure of a tensor's group orbit.Source: §1.1 · p. 4
  • The lower quantum functional is super-additive and super-multiplicative, while the upper version is sub-additive and sub-multiplicative for noncrossing parameters.Both extensions are monotone under restriction and normalized on the unit tensor.Source: §1.1 · p. 5
  • The cap-set tensor shares its asymptotic spectrum with F3[x]/(x3), whose minimal point reproves the Ellenberg–Gijswijt bound [Str91, Table 1].The reduction identifies the cap-set tensor with a tensor in the orbit of reduced polynomial multiplication.Source: §1.1 · p. 5
  • The quantum functionals do not apply directly to cap sets because that problem cannot be treated over the complex numbers.The paper suggests that better understanding of the construction may help with related combinatorial questions.Source: §1.1 · p. 5

1.3. This paper

  • For complex tensors, the quantum functionals characterize asymptotic slice rank; for tight 3-tensors, asymptotic slice rank and asymptotic subrank coincide.The upper quantum and Strassen support functionals also bound slice rank and multi-slice rank asymptotically.Source: §1.1 · pp. 5–6

2. Strassen support functionals

The section develops Strassen’s upper and lower support functionals over an arbitrary field and explains when they yield spectral points. Their agreement on oblique tensors supplies such points for that strict subfamily.

2.1. Upper support functional

  • The upper support functional is restriction-monotone and normalized, and is sub-additive under direct sum and sub-multiplicative under tensor product.It is constructed from weighted marginal entropies of a tensor’s support.Source: §2 · p. 9, §2.1 · p. 10

2.2. Lower support functional

  • The lower support functional is restriction-monotone and normalized, and is super-additive and super-multiplicative, but is not generally additive.For θ_i>0, its typical value on F^n ⊗ F^n ⊗ F^n is (1−min_i θ_i) log2 n+o(n), unlike the upper functional’s log2 n.Source: §2 · p. 9, §2.2 · p. 12

2.3. Comparing the support functionals

  • A flag-based characterization compares the functionals through a minimization for the upper functional and a maximization for the lower one.This distinction is useful for computations, and the comparison proof relates maximal support points across flags by coordinate permutations.Source: §2.3 · p. 13

2.4. Robust and oblique tensors; spectral points

  • Robustness means the upper and lower functionals agree; obliqueness guarantees this equality, and robust tensors are closed under direct sum and tensor product.Obliqueness requires a basis in which the support equals its maximal points.Source: §2.4 · pp. 15–16
  • On oblique tensors, the upper and lower support functionals coincide, yielding restriction-monotone, normalized, additive, and multiplicative spectral points.Oblique tensors have a basis in which their support is an antichain.Source: §2 · p. 9, §2.4 · p. 16

3. Quantum functionals

Over the complex numbers, this section develops upper and lower quantum functionals as candidates for universal spectral points on tensors, establishing key properties of the lower functional and relating the quantum functionals to support functionals. It compares the two functionals, identifies a regularisation result, and shows that in the singleton-cut regime they coincide as universal spectral points, with the upper functional equal to the regularized upper support functional.

3. Quantum functionals

  • For singleton-cut distributions, the upper and lower quantum functionals coincide and are universal spectral points; the upper functional also equals the regularized upper support functional.For every distribution θ, the upper functional is at least the lower one, and the upper functional is at most the support functional ζθ.Source: §3 · p. 16

3.1. Upper quantum functional

  • The upper quantum functional is defined using isotypic projections, and for any θ it is monotone under tensor degeneration.For noncrossing θ, the projections commute, so their product does not depend on its order.Source: §3.1 · pp. 18–19

3.2. Lower quantum functional

  • The lower quantum functional is defined from quantum entropy, optimized over invertible local maps on the tensor legs.It takes the value r on the diagonal tensor ⟨r⟩.Source: §3.2 · pp. 23–24
  • The lower quantum functional is restriction-monotone, super-additive, and super-multiplicative.The proofs use continuity for monotonicity, entropy recursivity for direct sums, and additivity of quantum entropy on tensor products.Source: §3.2 · pp. 24–25

3.3. Comparing the quantum functionals

  • For general θ ∈ P(B), the upper quantum functional is at least the lower quantum functional.The comparison is proved using the gentle measurement lemma and spectrum estimation.Source: §3.3 · p. 25

3.4. Universal spectral points

  • For singleton-regime θ ∈ P_s(B), the upper and lower quantum functionals coincide and define a universal spectral point.The proof relates the functionals through the entanglement polytope.Source: §3.4 · p. 27
  • The upper quantum functional is at least the lower support functional for θ ∈ P_s(B).The section also identifies the regularisation of the upper support functional with the upper quantum functional.Source: §3.4 · pp. 28, 30

4. Several families of tensors

The section surveys tight tensors, reduced polynomial multiplication, and free tensors. For complex free tensors, the upper support functional agrees with the quantum functionals in the singleton regime.

4. Several families of tensors

  • Tight tensors are oblique, and Strassen's support functionals compute asymptotic subrank for tight 3-tensors.Tightness is useful in the discussion of reduced polynomial multiplication and the cap set problem.Source: §4 · p. 30
  • For complex free tensors, the upper support functional and quantum functionals coincide in the singleton regime.Oblique tensors are free.Source: §4 · p. 30
  • The section computes generic quantum-functional values and uses the Hilbert–Mumford criterion to relate non-maximality of the upper quantum functional to non-maximality of the upper support functional.Source: §4 · p. 30

4.1. Tight tensors

This section defines tightness and explains why tight 3-tensors are tractable through Strassen's support functionals. It also discusses extensions through combinatorial degeneration and the more limited bounds available for higher-order tensors.

4.1. Tight tensors

  • A set is tight when injective coordinate maps into Z make the sum of their values zero on every element.Source: §4.1 · p. 31
  • Tight tensors form a semiring under tensor product and direct sum, and every subset of a tight set is tight.Source: §4.1 · p. 31
  • Tightness can depend on the field: a diagonal tensor is shown tight when the field contains a primitive nth root of unity, and also in characteristic n.Source: §4.1 · p. 31
  • For tight 3-tensors, asymptotic subrank equals the minimum of Strassen's support functionals over θ ∈ P([3]).Thus these functionals compute asymptotic subrank exactly within this class.Source: §4.1 · p. 32
  • For k ≥ 4, the three-party entropy expression does not extend as stated, and the available lower bound on asymptotic subrank is not generally known to be tight.The section gives an example where the lower bound is tight.Source: §4.1 · p. 32
  • A combinatorial degeneration Ψ ⊵ Φ assigns positive coordinate-map sums outside Φ and zero sums on Φ, and implies f ⊵ f|Φ for a tensor supported on Ψ.The section considers using a tight subset Φ of Ψ to lower-bound asymptotic subrank.Source: §4.1 · p. 33

4.2. The cap set problem

The cap set problem is recast through tensor subrank and reduced polynomial multiplication. This connection places the cap-set bounds in the asymptotic-spectrum framework.

4.2. The cap set problem

  • The cap set tensor lies in the GL3(F3)×3-orbit of the reduced polynomial multiplication tensor, connecting cap-set bounds to its asymptotic spectrum.The paper presents this as a route to reprove recent cap-set results using Theorem 4.11.Source: §4.2 · p. 35, §4.2.2 · p. 37

4.2.1. Reduced polynomial multiplication

  • For F[x]/(x^n), Strassen’s asymptotic spectrum coincides with its support simplex and is an interval determined using z(n).The support Φ_n is tight, and its minimum support-functional value equals the tensor’s asymptotic subrank.Source: §4.2.1 · pp. 35–36

4.2.2. The cap set problem

  • For prime-power m, s3(Z/mZ) equals the asymptotic subrank z(m) of F_m[x]/(x^m).The proof connects the modular sum-free tensor to the reduced polynomial multiplication tensor by identifying its support with the tight set Φ_m.Source: §4.2.2 · pp. 37–38

4.3. Free tensors

Free tensors are introduced as a setting where quantum and support functionals align. The section also establishes that this setting does not include all tensors.

4.3. Free tensors

  • Free tensors include oblique tensors, and tight tensors are included among oblique tensors.The stated inclusion is {tight} ⊆ {oblique} ⊆ {free}.Source: §4.3 · p. 39
  • For n ≥ 5, a nonempty Zariski-open set of tensors in C^n⊗C^n⊗C^n is not free.Free supports have size at most n^2, while tensors in that open set have support size greater than n^2 in every basis.Source: §4.3 · p. 39
  • For a free tensor, the quantum functional equals the entanglement-polytope functional and the support functional for every θ in the stated regime.The result is stated as ρθ(t) = Eθ(t) = Eθ(t).Source: §4.3 · pp. 39–40
  • For the easy Coppersmith–Winograd tensor, the quantum functional lower bound is 3 log2 q + h(1/3), with equality at uniform θ.For q ≥ 2, the cited comparison gives an upper bound of log2(q + 1) for ρθ(CWq).Source: §4.3 · pp. 40–41

4.4. Generic tensors

The section characterizes typical functional values for generic tensors and relates quantum-functional values to entanglement polytopes. It also connects functional deficits to instability.

4.4.1. Generic value of the Strassen support functionals

  • For every tensor format over an algebraically closed field, each Strassen support functional is constant on a nonempty Zariski-open subset.The paper calls this constant value typical or generic.Source: §4.4.1 · p. 41

4.4.2. Generic value of the quantum functionals

  • For each fixed complex tensor format, the quantum functional has a constant value on a nonempty Zariski-open set.The entanglement polytope is maximal on that set, since all its covariant generators are nonzero.Source: §4.4.2 · p. 42
  • For complex tensors, the generic quantum-functional value is maximal exactly when the format admits a pure state with completely mixed marginals.The quantum functional is maximized over the tensor’s entanglement polytope; when such a state exists, the generic value is n1^θ(1)⋯nk^θ(k).Source: §4.4.2 · p. 43

4.4.3. Hilbert–Mumford criterion and instability

  • If Eθ(t) is below n1^θ(1)⋯nk^θ(k), the tensor is unstable and its support-functional value is also strictly below that bound.The paper further gives a quantitative instability result over all fields, improving [BCC+17] for sufficiently nonuniform formats.Source: §4.4.3 · p. 44

5. Subrank, slice rank and multi-slice rank

The section studies slice rank and multi-slice rank alongside subrank, establishing quantum-functional upper bounds and an exact asymptotic slice-rank formula for complex tensors.

5.2. Key properties

  • Slice rank and multi-slice rank are neither sub-multiplicative nor super-multiplicative, so their tensor-power growth limits are not assured by those properties.The section nevertheless proves that the asymptotic slice-rank limit exists.Source: §5.2 · p. 47

5.3. Upper bound by support and quantum functionals

  • For complex tensors, quantum functionals upper-bound asymptotic multi-slice rank and slice rank in their respective stated regimes.Theorem 5.3 states MSR∼(t) ≤ Fθ(t) and SR∼(t) ≤ Fθ(t).Source: §5.3 · p. 47
  • For complex tensors, asymptotic slice rank exists and equals the minimum quantum-functional value over θ ∈ P([k]).The formula is lim_n→∞ slicerank(t⊗n)^(1/n) = min_θ∈P([k]) Fθ(t).Source: §5 · p. 46, §5.3 · p. 50
  • For tight 3-tensors, asymptotic slice rank coincides with asymptotic subrank.This follows from the tight-tensor result that asymptotic subrank equals the minimum support-functional value.Source: §5.3 · p. 50
Loading 1709.07851v3…