Asymptotic Tensor Rank Is Characterized by Polynomials

Christandl, Matthias and Hoeberechts, Koen and Nieuwboer, Harold and Vrana, Péter and Zuiddam, Jeroen (2025) Asymptotic Tensor Rank Is Characterized by Polynomials. In: 57th Annual ACM Symposium on Theory of Computing.

Preview

Text 3717823.3718122.pdf - Published Version Available under License Creative Commons Attribution Non-commercial. Download (651kB) | Preview

Abstract

Asymptotic tensor rank, originally developed to characterize the complexity of matrix multiplication, is a parameter that plays a fundamental role in problems in mathematics, computer science and quantum information. This parameter is notoriously difficult to determine; indeed, determining its value for the 2×2 matrix multiplication tensor would determine the matrix multiplication exponent, a long-standing open problem. Strassen's asymptotic rank conjecture, on the other hand, makes the bold statement that asymptotic tensor rank equals the largest dimension of the tensor and is thus as easy to compute as matrix rank. Recent works have proved strong consequences of Strassen's asymptotic rank conjecture in computational complexity theory. Despite tremendous interest, much is still unknown about the structural and computational properties of asymptotic rank; for instance whether it is computable. We prove that asymptotic tensor rank is “computable from above”, that is, for any real number r there is an (efficient) algorithm that determines, given a tensor T, if the asymptotic tensor rank of T is at most r. The algorithm has a simple structure; it consists of evaluating a finite list of polynomials on the tensor. Indeed, we prove that the sublevel sets of asymptotic rank are Zariski-closed (just like matrix rank). While we do not exhibit these polynomials explicitly, their mere existence has strong implications on the structure of asymptotic rank. As one such implication, we find that the values that asymptotic tensor rank takes, on all tensors, is a well-ordered set. In other words, any non-increasing sequence of asymptotic ranks stabilizes (“discreteness from above”). In particular, for the matrix multiplication exponent (which is the base-2 logarithm of an asymptotic rank) there is no sequence of exponents of bilinear maps that approximates it arbitrarily closely from above without being eventually constant. In other words, any such upper bound on the matrix multiplication exponent that is close enough, will “snap” to it. Previously such discreteness results were only known for finite fields or for other tensor parameters (e.g., asymptotic slice rank). We obtain them for infinite fields like the complex numbers. We prove our result more generally for a large class of functions on tensors, and in particular obtain similar properties for all functions in Strassen's asymptotic spectrum of tensors. We prove a variety of related structural results on the way. For instance, we prove that for any converging sequence of asymptotic ranks, the limit is also an asymptotic rank for some tensor. We leave open whether asymptotic rank is also discrete from below (which would be implied by Strassen's asymptotic rank conjecture).

Actions (login required)

Edit Item