On a conjecture of Gowers and Wolf

On a conjecture of Gowers and Wolf, Discrete Analysis 2022:10, 13 pp.

Szemerédi’s theorem asserts that for every $\delta>0$ and every positive integer $k$ there exists $n$ such that every subset $A$ of $\{1,2,\dots,n\}$ of size at least $\delta n$ contains an arithmetic progression of length $k$. We can very slightly reformulate the conclusion of this statement by saying that if $\phi_i$ is the linear form $(x,y)\mapsto x+(i-1)y$, then there exist $a,d$ with $d\ne 0$ such that $\phi_i(a,d)\in A$ for $i=1,2,\dots,k$.

Several proofs of Szemerédi’s theorem involve looking at expressions of the form
$$\mathbb E_{x,d}f(x)f(x+d)\dots f(x+(k-1)d)$$
or in the alternative notation
$$\mathbb E_{x,d}f(\phi_1(x,d))\dots f(\phi_k(x,d)).$$
Here $x$ and $d$ are chosen uniformly at random from a large cyclic group (or from other finite Abelian groups when related questions are studied). In particular, it is useful to find conditions that guarantee that averages of this kind are small.

In particular, Gowers showed that if $\|f\|_\infty\leq 1$, then the average above is small if a certain norm of $f$, known as the $U^{k-1}$ norm, is small. This is often expressed by saying that the average is “controlled by the $U^{k-1}$ norm”.

The $U^k$ norms are defined as follows. First we define a “difference operator” $\partial_a$ by $\partial_af(x)=f(x)\overline{f(x-a)}$. Then the $U^k$ norm of a function $f$ is given by the formula
$$\|f\|_{U^k}^{2^k}=\mathbb E_{x,a_1,\dots,a_k}\partial_{a_1}\dots\partial_{a_k}f(x).$$
It is not immediately obvious that this formula defines a norm, but this can be shown (except in the case $k=1$ when one obtains a seminorm).

A rough intuitive sense of what this statement says is that if $f$ has a small $U^k$ norm, then it behaves “sufficiently quasirandomly” to guarantee that a lot of cancellation occurs in the average in question.

The $U^k$ norms can be shown to increase with $k$. A key example of a function with large $U^k$ norm but small $U^j$ norm for all $j<k$ is the function $f(x)=\exp(2\pi ix^{k-1}/p)$ defined on the cyclic group of integers mod $p$. It is not hard to prove that $\partial_{a_1}\dots\partial_{a_j}f$ is identically 0 when $j<k$, making the $U^k$ norm equal to 1 (its maximum possible value given that $\|f\|_\infty=1$) and it turns out that for all smaller $j$ the average is small.

In their celebrated paper Linear equations in primes, Green and Tao were interested in asymptotics for the number of configurations in the first $n$ primes. Their first aim was to obtain asymptotics for the number of arithmetic progressions of length $k$, thereby obtaining a more precise version of the Green-Tao theorem, which states (or rather easily implies) that this number tends to infinity with $n$. However, they also looked at more general configurations, which led them to consider averages of the form mentioned above for other sequences of linear forms. They showed that the proof that the average is controlled by the $U^{k-1}$ norm in the case $\phi_i(x,y)=x+(i-1)y$ can be generalized to other systems of linear forms, and gave a criterion for which $k$ is needed in order for the $U^k$ norm to control the average.

Later, Gowers and Wolf observed that although the criterion identified by Green and Tao accurately identified the $k$ for which the proof (which involved repeated applications of the Cauchy-Schwarz inequality) worked, it did not appear to be best possible, in the sense that for some systems of linear forms, a smaller $k$ seemed to suffice. They conjectured that if for each $i=1,\dots,t$, $\psi_i:\mathbb{Z}^D\to\mathbb{Z}$ is a linear form, then the smallest $s$ such that the $U^s$ norm controls the corresponding average is also the smallest $s$ such that the functions $\psi_1^{s},\ldots, \psi_t^{s}$ are linearly independent.

They proved this conjecture when $s\leq 2$, and also proved the whole conjecture when instead of a cyclic group one takes the group $\mathbb F_p^n$ for $p$ bounded (but also not too small – additional complications arose in small characteristic). For this they made use of an inverse theorem for the $U^k$ norms due to Bergelson, Tao and Ziegler, which gave a description of bounded functions with large $U^k$ norms (showing that they correlate with polynomial examples).

At the time of that result, the corresponding inverse theorem for functions defined on cyclic groups was still a major open problem. However, later it was solved by Green, Tao and Ziegler, and shortly after that, Green and Tao used the resulting inverse theorem to solve the conjecture of Gowers and Wolf in the cyclic groups case. Or so it seemed. Ten years later, the author of this paper noticed that their proof subtly used an assumption about the linear forms that does not always hold, which Green and Tao dubbed the “flag condition”. The result is that the proof of Green and Tao works for systems of linear forms that satisfy the flag condition, and therefore covers many examples of interest, but does not work for all systems of linear forms.

In this paper, the author finally proves the conjecture in full generality. The first step of the argument is to generalize Green and Tao’s result in various ways for systems that do satisfy the flag condition. This results in a theorem that is invariant under dilations of the linear forms. The second step is to show that for any system of linear forms one can dilate the individual forms in such a way that they satisfy the flag condition.