The analytic rank of tensors and its applications

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

There are several arguments in additive combinatorics concerning two-variable functions taking values in a field that interpret those functions as matrices and make use of the notion of rank. For many such arguments, one would like to be able to generalize them to functions of three or more variables, which one can interpret as tensors, but the difficulty arises that there are several genuinely different notions of the rank of a tensor, and no single one stands out as the “correct” notion: rather, different notions are useful for different purposes. For three-variable functions, one obvious definition is that the rank of a function $f:X\times Y\times Z\to\mathbb F$ is the smallest $m$ such that there exist functions $u_i:X\to\mathbb F$, $v_i:Y\to\mathbb F$ and $w_i:Z\to\mathbb F$ for $i=1,\dots,m$ with the property that

$$f(x,y,z)=\sum_iu_i(x)v_i(y)w_i(z)$$

for all $(x,y,z)\in X\times Y\times Z$. More concisely, it is the smallest $m$ such that $f$ has a decomposition into $m$ rank-1 tensors $u_i\otimes v_i\otimes w_i$.

A less obvious definition, which played a crucial role in a reformulation by Terence Tao of the solution of the cap-set problem is that of the slice rank. For three-variable functions it is defined to be the smallest $m$ such that $f$ can be decomposed into a sum of $m$ functions $g_i$ such that each $g_i$ is a product of a function of one of the variables and a function of the other two variables (so in particular the slice rank is at most as big as the rank).

A third definition, introduced by Gowers and Wolf, arises out of the following observation. Let $\beta$ be a bilinear form on $(\mathbb F_p^n)^2$ given by a formula of the type $\beta(x,y)=\sum_i a_{ij}x_iy_j$. Now let $\omega=\exp(2\pi i/p)$, and consider the average $\mathbb E_{x,y}\omega^{\beta(x,y)}$. Writing $\alpha$ for the linear map with matrix $(a_{ij})$ and $u.v$ for $\sum_iu_iv_i$, we can rewrite this as $\mathbb E_{x,y}\omega^{x.\alpha y}$. For each $y$, the average over $x$ is zero unless $\alpha y=0$, in which case it is 1. Therefore, this last expression is equal to the probability that $\alpha y=0$, which is $p^{-r(\alpha)}$, where $r(\alpha)$ is the rank of $\alpha$. It follows that an equivalent definition of the rank of a bilinear form $\beta$ on $(\mathbb F_p^n)^2$ is $-\log_p(\mathbb E_{x,y}\omega^{\beta(x,y)}$.

This definition generalizes straightforwardly to multilinear forms – one just replaces $\beta(x,y)$ by $\mu(x_1,\dots,x_k)$ in the formula – and gave rise to a notion that Gowers and Wolf called the analytic rank of a multilinear form.

For many purposes in additive combinatorics, averages of the kind just calculated are what one principally cares about when one invokes the rank of $\beta$, so there are good reasons to expect the definition to be useful. However, there are two important caveats. The first is that a useful property of rank is subadditivity. If rank is defined as the minimum number of “simple” functions needed in a decomposition, then it is trivially subadditive, but for the analytic definition above, it is less obvious. Gowers and Wolf proved an inequality of the form $r(\mu_1+\mu_2)\leq C_k(r(\mu_1)+r(\mu_2)$, which was enough for several applications, but left open the question of whether the constant $C_k$ was really needed. The main result of this paper shows that it is not: the inequality holds with $C_k=1$, so analytic rank is exactly subadditive. Applications are given of this more precise result. One of these is the interesting result that it is possible to prove an exponential upper bound for the cap-set problem using analytic rank rather than slice rank.

The second caveat is that for applications in additive combinatorics one often wants to split arguments about multilinear forms into two cases – the familiar structure/randomness dichotomy. When the analytic rank of a multilinear form is high, it has good quasirandomness properties that can be exploited in proofs. But it is also important to understand the structure of multilinear forms of low analytic rank. As in the familiar case of bilinear forms, one would like to be able to show that such a form can be decomposed as a sum of not too many forms that are simpler (for example, they might be products of lower-degree forms). Such results are known, and discussed in the paper. Until recently they were known with very poor bounds, but power-type bounds are now known: they were obtained independently by Oliver Janzer and Luka Milićević.