Asymptotic Tensor Rank is Characterized by Polynomials

Asymptotic tensor rank 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. On the other hand, Strassen's asymptotic rank conjecture makes the bold claim that asymptotic tensor rank equals the largest dimension of the tensor and is thus as easy to compute as matrix rank. Despite tremendous interest, much is still unknown about the structural and computational properties of asymptotic rank.

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 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"). For instance, there is no sequence of asymptotic ranks that approximate 2^omega arbitrarily closely from above without being eventually constant.

https://arxiv.org/abs/2411.15789

This seminar is part of the Problems in Algebraic Geometry Coming from Complexity Theory series.