Polynomial bound for the partition rank vs the analytic rank of tensors

Polynomial bound for the partition rank vs the analytic rank of tensors, Discrete Analysis 2020:7, 18 pp.

There are a number of proofs in additive combinatorics that involve bilinear forms on $\mathbb F_p^n$ that split into a high-rank case and a low-rank case. If the form has high rank, then it has useful quasirandomness properties, whereas if it has low rank, then it is constant on the cosets of a subspace of low codimension. This connection arises through the box norm, which is a norm on functions of two variables defined by the formula
$$\|f\|_\square^4=\mathop{\mathbb E}_{x_1,x_2,y_1,y_2}f(x_1,y_1)\overline{f(x_1,y_2)}\overline{f(x_2,y_1)}f(x_2,y_2).$$
The box norm measures quasirandomness – the smaller the box norm, the more quasirandom the function $f$. But an easy calculation shows that if a bilinear form $\beta$ has rank $r$, then the box norm of the function $f(x,y)=\mathbb E_{x,y}\exp(2\pi i\beta(x,y)/p)$ is equal to $p^{-r/4}$. Thus, there is a direct connection between the rank of $\beta$ and the box norm of the function $\exp(2\pi i\beta/p)$.

One would like to generalize many of these arguments to multilinear maps of higher degree. However, this is complicated for two reasons. The first is that there is not an agreed notion of rank for multilinear maps of degree greater than 2 – there are a number of different definitions, each with different advantages and disadvantages. However, in an additive combinatorics context, one definition has proved its utility, which is to say that a $d$-linear function has partition rank 1 if it can be written as a product of multilinear functions (in disjoint sets of variables) of lower degree, and to say that it has partition rank at most $k$ if it can be written as a sum of $k$ functions of partition rank 1.

The definition of the function $f$ above and the definition of the box norm have straightforward generalizations, which can be used to define a notion of rank that was called analytic rank in a paper of Gowers and Wolf [2], who proved that it was approximately subadditive, a result later improved by Lovett [6], who showed that it was exactly subadditive. The second complication is that proving that a multilinear function with low analytic rank must have low partition rank is not at all easy.

The first progress was made by Green and Tao [3], whose results were improved by Kaufmann and Lovett [5], and then Bhowmick and Lovett [1]. However, all these results (which were proved before the notion of analytic rank was explicitly formulated) gave an Ackermann-type dependence of the partition rank on the analytic rank, while in the other direction no example was (or is) known for which the dependence is superlinear. Thus, any proofs that made use of them led to extremely weak bounds.

Recently, the author of this paper proved a tower-type bound [4], and then subsequently realized that he could use more or less the same argument to improve the bound further to a polynomial dependence. More precisely, if the analytic rank of an order $d$ tensor is at most $r$, then its partition rank is at most $f(r,d,|\mathbb{F}|)$, where, for fixed $d$ and $\mathbb{F}$, $f$ is a polynomial in $r$. A similar bound was obtained by a different method by Luka Milićević [7]. Thanks to these results, one can now pass from analytic rank to partition rank without incurring a substantial penalty. In proofs, this essentially means that either a multilinear form has good quasirandomness properties or one can consider forms of lower degree and apply induction. The result has already had applications and is certain to have many more.

1. Abhisheck Bhowmick and Shachar Lovett, Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory, arXiv:1506.02047

2. W. T. Gowers and J. Wolf, Linear forms and higher-degree uniformity for functions on $\mathbb F_p^n$, arXiv:1002.2208

3. Ben Green and Terence Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms, arXiv:0711.3191

4. Oliver Janzer, Low analytic rank implies low partition rank for tensors, arXiv:1809.10931

5. Tali Kaufmann and Shachar Lovett, Worst case to average case reductions for polynomials, arXiv:0806.4535

6. Shachar Lovett, The analytic rank of tensors and its applications, Discrete Analysis 2019:7, 10 pp.

7. Luka Milićević, Polynomial bound for partition rank in terms of analytic rank arxiv:1902.09830