An optimal inverse theorem for tensors over large fields

A degree $k$ tensor $T$ over a finite field $\mathbf{F}_q$ can be viewed as a multilinear function $\mathbf{F}_n^q\times\cdot\ \cdot\ \cdot\ \times \mathbf{F}_n^q\to \mathbf{F}_q$ . The analytic rank of $T$ takes a value between 0 and $n$, and is small if the output distribution is far from uniform — in some sense, it is a measure of how randomly $T$ behaves. On the other hand, the partition rank of $T$ is small if $T$ can be decomposed into a few highly structured pieces. It is not hard to show that the analytic rank is less than the partition rank —or in other words, if $T$ is highly structured, then it does not behave randomly. In 2008 Green and Tao proved a qualitative inverse theorem stating that the partition rank is bounded by some (large) function of the analytic rank. We prove an optimal inverse theorem: Analytic rank and partition rank are equivalent up to linear factors (over large enough fields). This theorem allows us to explain any lack of randomness in $T$ by the presence of structure. Our techniques are very different from the usual methods in this area. We rely on algebraic geometry rather than additive combinatorics. This is joint work with Guy Moshkovitz.

Alex Cohen