Asymptotic tensor rank is characterized by polynomials

This paper proves that asymptotic tensor rank is "computable from above" via the evaluation of polynomials, establishing that its sublevel sets are Zariski-closed and that the set of all possible asymptotic rank values is well-ordered, implying that upper bounds on parameters like the matrix multiplication exponent must eventually stabilize rather than merely approach them.

The Gist

Imagine you have a giant, multi-dimensional block of data, like a Rubik's cube that has been stretched into a complex, multi-layered structure. In the world of mathematics and computer science, this is called a tensor. One of the most important things we want to know about these blocks is their "rank."

Think of tensor rank as a measure of how "complicated" or "messy" the block is. A low rank means the block is simple and can be built from just a few basic Lego bricks. A high rank means it's incredibly complex and requires millions of bricks to construct.

For decades, mathematicians have been trying to figure out the rank of these blocks, especially for a specific type used in matrix multiplication (the math behind multiplying huge grids of numbers, which powers everything from video games to AI). The difficulty of this task is so high that solving it would unlock the secrets of how fast computers can multiply numbers in the future.

The Big Mystery: The "Asymptotic" Rank

The paper focuses on a special version of this problem called asymptotic tensor rank.

Imagine you have a single Lego block. If you make a copy of it, then copy the copy, and keep doing this forever, you get a massive, growing structure. The "asymptotic rank" asks: As this structure grows infinitely large, how does its complexity grow?

It's like asking: "If I keep stacking these Lego towers higher and higher, does the number of bricks needed to build them grow slowly, or does it explode?"

This is a notoriously difficult question. For a long time, we didn't even know if there was a way to calculate it at all. It was like trying to find the exact height of a cloud that keeps changing shape.

The Paper's Big Discovery: "Computable from Above"

The authors of this paper made a breakthrough. They proved that while we might not be able to calculate the exact rank instantly, we can determine if the rank is below a certain limit.

The Analogy:
Imagine you are trying to guess the weight of a mysterious box. You don't have a scale that gives you the exact number. However, the authors found a special set of polynomials (which are just fancy mathematical recipes or tests).

They proved that if you run your box through a specific list of these tests:

• If the box fails any of the tests, you know for sure it is too heavy (its rank is higher than your limit).
• If the box passes all the tests, you know for sure it is light enough (its rank is at or below your limit).

This means the problem is "computable from above." We can't necessarily pinpoint the exact number immediately, but we can systematically eliminate possibilities until we find the answer. It's like having a sieve that catches all the heavy rocks, leaving only the light ones behind.

The "Snap" Effect: Discreteness from Above

One of the most surprising findings is about the values these ranks can take.

In many mathematical systems, numbers can be infinitely close to each other. You can have 3.1, 3.14, 3.141, 3.1415... getting closer and closer to a limit without ever quite reaching it.

The authors proved that for asymptotic tensor rank, this does not happen from the top down.

The Analogy:
Imagine a staircase where the steps get smaller and smaller as you go up. Usually, you might think you could climb infinitely close to the ceiling without ever touching it. But the authors proved that for these tensors, there is a "snap" effect.

If you have a sequence of tensors getting closer and closer to a specific complexity level from above, they cannot just "hover" there forever. Eventually, they must snap onto a specific, exact value. There is a "gap" between the values. You can't have a tensor with a rank of 2.0000001 if the next possible rank is 2.0000000. There is a hard floor (or rather, a hard ceiling for the next step down) that prevents infinite hovering.

This is huge for the matrix multiplication exponent (the speed limit of computer multiplication). It means that if we find an algorithm that is "almost" the fastest possible, it will eventually snap to the true fastest speed. We can't have a sequence of algorithms that get infinitely closer to the perfect speed without actually hitting it.

What This Means for the Future

The paper doesn't solve the ultimate mystery (we still don't know the exact speed limit of matrix multiplication), but it gives us a powerful new map.

1. We have a checklist: We now know there is a finite list of mathematical tests (polynomials) that can tell us if a tensor is "simple enough."
2. The values are orderly: The possible complexity levels of these tensors are not a chaotic, continuous blur. They are structured like a well-ordered list where you can't sneak in infinitely small steps from the top.
3. It applies broadly: This isn't just about one type of math problem; it applies to a whole family of similar problems in quantum physics and computer science.

In short, the authors took a problem that seemed like an endless, foggy maze and showed us that the maze actually has a grid system. We can't see the exit yet, but we now know the rules of the grid, and we know that the path to the exit isn't as slippery as we thought.

Technical Summary

Technical Summary: Asymptotic Tensor Rank is Characterized by Polynomials

Problem Context
Asymptotic tensor rank, denoted $\tilde{R}(T)$, is a fundamental parameter in algebraic complexity theory, defined as the limit $\lim_{n \to \infty} R(T^{\boxtimes n})^{1/n}$, where $R$ is the standard tensor rank and $\boxtimes$ is the Kronecker product. This parameter is central to determining the matrix multiplication exponent $\omega$, as $2\omega = \tilde{R}(\langle 2, 2, 2 \rangle)$. Despite its importance, the computational and structural properties of asymptotic rank are poorly understood. A major open problem is whether $\tilde{R}(T)$ is computable. Furthermore, Strassen's asymptotic rank conjecture posits that $\tilde{R}(T)$ equals the largest flattening rank of $T$, implying it is always an integer and easy to compute. While recent works have established discreteness properties for asymptotic parameters over finite fields, the behavior over infinite fields (such as the complex numbers) remained largely unknown.

Methodology
The authors approach the problem by analyzing the geometric structure of the sublevel sets of asymptotic rank and related functionals. They introduce the concept of "admissible functionals," a class of functions on tensor powers satisfying specific properties (subadditivity, submultiplicativity, permutation invariance, etc.), which includes asymptotic rank and all points in Strassen's asymptotic spectrum.

The core methodological innovation is proving that for any such admissible functional $\mathcal{F}$ and any real number $r$, the sublevel set $\{T : \tilde{\mathcal{F}}(T) \leq r\}$ is Zariski-closed. This is achieved through a decomposition argument showing that the supremum of the functional over the Zariski closure of a set $A$ equals the supremum over $A$ itself. This relies on expressing elements in the closure as linear combinations of tensor powers of elements in $A$ and utilizing asymptotic double-blocking analysis.

To extend these results from fixed tensor formats to the set of all tensors (arbitrary dimensions), the authors develop new lower bounds on tensor-to-matrix transformations (specifically, quantities $Q_{i,j}(T)$ representing the largest matrix rank obtainable on specific legs via restriction). They prove an inequality relating the product of these transformation ranks to the flattening rank $R_I(T)$, generalizing previous results for $k=3$.

Key Contributions and Results

1. Polynomial Characterization and Computability from Above:
   The paper proves that asymptotic tensor rank is "computable from above." For any computable field $F$ and any real bound $r$, there exists an algorithm that, given a tensor $T$, decides whether $\tilde{R}(T) \leq r$. This algorithm relies on the fact that the sublevel set is Zariski-closed, meaning it is defined by the vanishing of a finite list of polynomials. While the paper does not explicitly construct these polynomials, their existence is guaranteed.

2. Zariski-Closed Sublevel Sets:
   Theorem 1.2 establishes that for any field $F$, order $k$, and bound $r$, the set $\{T : \tilde{R}(T) \leq r\}$ is Zariski-closed. Consequently, the asymptotic rank is lower-semicontinuous in the Euclidean topology over $\mathbb{C}$. This implies that if a sequence of tensors converges to a limit tensor, and all tensors in the sequence have asymptotic rank at most $r$, the limit tensor also has asymptotic rank at most $r$.

3. Discreteness from Above (Well-Orderedness):
   Theorem 1.3 proves that the set of values $\mathcal{R} = \{\tilde{R}(T) : T \in F^{d_1} \otimes \dots \otimes F^{d_k}, d_i \in \mathbb{Z}_{\geq 1}\}$ is well-ordered. This means any non-increasing sequence of asymptotic ranks must eventually stabilize.

   • Implication for Matrix Multiplication: There exists a constant $\epsilon > 0$ such that no tensor has an asymptotic rank strictly between $2\omega$ and $2\omega + \epsilon$. Any sequence of upper bounds on $\omega$ that approaches it from above must eventually "snap" to the true value.
   • This result generalizes to all functions in Strassen's asymptotic spectrum (Theorem 1.5).

4. Euclidean Closedness over $\mathbb{C}$:
   Theorem 1.4 and Theorem 4.1 show that when the base field is $\mathbb{C}$, the set of values taken by the asymptotic rank is closed in the Euclidean topology. This means the limit of any converging sequence of asymptotic ranks is itself an asymptotic rank of some tensor.

5. Generalization to the Asymptotic Spectrum:
   The authors extend these structural results to the entire asymptotic spectrum of tensors $\Delta(F, k)$. They prove that for any $F \in \Delta(F, k)$, the set of values attained is well-ordered. This is achieved via Strassen's duality and a "growth argument" involving the newly derived tensor-to-matrix lower bounds (Theorem 3.2).

Significance and Claims
The paper claims that these results provide a fundamental structural understanding of asymptotic tensor rank that was previously missing, particularly over infinite fields.

• Computational Implications: The "computable from above" property suggests that while computing the exact rank may be hard, verifying an upper bound is algorithmically feasible via polynomial evaluation.
• Structural Implications: The well-orderedness (discreteness from above) rules out the possibility of asymptotic ranks accumulating arbitrarily close to a value from above without reaching it. This provides evidence supporting Strassen's conjecture, which would imply that the set of values is simply the natural numbers $\mathbb{N}$.
• Open Problems: The authors explicitly state that they do not prove discreteness from below (i.e., whether increasing sequences of ranks must stabilize). They note that Strassen's conjecture would imply this, but it remains an open question. They also leave open the irreducibility of the sublevel sets for $k \geq 3$.

The work bridges algebraic geometry (Zariski topology) and complexity theory, offering new tools to analyze the matrix multiplication exponent and the structure of tensor parameters without resolving the asymptotic rank conjecture itself.