A Universal Sequence of Tensors for the Asymptotic Rank Conjecture

Abstract

The exponent σ(T) of a tensor T ∈ Fd ⊗ Fd ⊗ Fd over a field F captures the base of the exponential growth rate of the tensor rank of T under Kronecker powers. Tensor exponents are fundamental from the standpoint of algorithms and computational complexity theory; for example, the exponent ω of square matrix multiplication can be characterized as ω = 2σ(MM2), where MM2 ∈ F4 ⊗ F4 ⊗ F4 is the tensor that represents 2 × 2 matrix multiplication. Strassen [FOCS 1986] initiated a duality theory for spaces of tensors that enables one to characterize the exponent of a tensor via objects in a dual space, called the asymptotic spectrum of the primal (tensor) space. While Strassen’s theory has considerable generality beyond the setting of tensors – Wigderson and Zuiddam [Asymptotic Spectra: Theory, Applications, and Extensions, preprint, 2023] give a recent exposition – progress in characterizing the dual space in the tensor setting has been slow, with the first universal points in the dual identified by Christandl, Vrana, and Zuiddam [J. Amer. Math. Soc. 36 (2023)]. In parallel to Strassen’s theory, the algebraic geometry community has developed a geometric theory of tensors aimed at characterizing the structure of the primal space and tensor exponents therein; the latter study was motivated in particular by an observation of Strassen (implicit in [J. Reine Angew. Math. 384 (1988)]) that matrix-multiplication tensors have limited universality in the sense that σ(Fd ⊗ Fd ⊗ Fd) ≤23ω =43 σ(MM2) holds for all d ≥ 1. In particular, this limited universality of the tensor MM2 puts forth the question whether one could construct explicit universal tensors that exactly characterize the worst-case tensor exponent in the primal space. Such explicit universal objects would, among others, give means towards a proof or a disproof of Strassen’s asymptotic rank conjecture [Progr. Math. 120 (1994)]; the former would immediately imply ω = 2 and, among others, refute the Set Cover Conjecture (cf. Björklund and Kaski [STOC 2024] and Pratt [STOC 2024]). Our main result is an explicit construction of a sequence Ud of zero-one-valued tensors that is universal for the worst-case tensor exponent; more precisely, we show that σ(Ud) = σ(d) where σ(d) = supT∈Fd ⊗ Fd ⊗ Fd σ(T). We also supply an explicit universal sequence U∆ localised to capture the worst-case exponent σ(∆) of tensors with support contained in ∆ ⊆ [d] × [d] × [d]; by combining such sequences, we obtain a universal sequence Td such that σ(Td) = 1 holds if and only if Strassen’s asymptotic rank conjecture holds for d. Finally, we show that the limit limd→∞ σ(d) exists and can be captured as limd→∞ σ(Dd) for an explicit sequence (Dd)∞d=1 of tensors obtained by diagonalisation of the sequences Ud. As our second result we relate the absence of polynomials of fixed degree vanishing on tensors of low rank, or more generally asymptotic rank, with upper bounds on the exponent σ(d). Using this technique, one may bound asymptotic rank for all tensors of a given format, knowing enough specific tensors of low asymptotic rank.