Logarithmic bounds for Roth’s theorem via almost-periodicity

Logarithmic bounds for Roth’s theorem via almost-periodicity, Discrete Analysis 2019:4, 20pp.

A central result of additive combinatorics, Roth’s theorem, asserts that for every $\delta>0$ there exists $N$ such that every subset of $\{1,2,\dots,N\}$ of size at least $\delta N$ contains an arithmetic progression of length 3. This is the first non-trivial case of Szemerédi’s theorem, proved over 20 years later, which is the corresponding statement for progressions of general length. If we define $\rho_k(N)$ to be the minimum real number such that every subset of $\{1,2,\dots,N\}$ of density at least $\rho_k(N)$ contains an arithmetic progression of length $k$, then Roth’s theorem asserts that $\rho_3(N)\to 0$ and Szemerédi’s theorem asserts that $\rho_k(N)\to 0$ for all $k$.

These results leave open the question of bounds. Roth’s proof shows that $\rho_3(N)\leq C/\log\log N$ for an absolute constant $C$. Following a sequence of improvements by Szemerédi, Heath-Brown, Bourgain and Sanders, the current record, due to the first author of this paper, stands at $C(\log\log N)^4/\log N$. This is tantalizingly close to $1/\log N$, which is an important barrier because if one could get past it then one would be able to prove that every set $A\subset\mathbb N$ such that $\sum_{x\in A}x^{-1}=\infty$ contains an arithmetic progression of length 3, which is the first non-trivial case of perhaps the most famous of all conjectures of Erdős.

At the time of writing, the problem of beating the log barrier is particularly alive, because there is some evidence that we already have the technology needed to solve it. This evidence comes from a closely related problem, the cap-set problem, which concerns the density that a subset $A\subset\mathbb F_3^n$ must have in order to contain an affine line, which is the natural notion of an arithmetic progression of length 3 in $\mathbb F_3^n$. For a long time the best known upper bound was stuck at $Cn^{-1}$, which is also a logarithmic bound, since the cardinality of $\mathbb F_3^n$ is $3^n$. Then a few years ago, Michael Bateman and Nets Katz improved the bound to $Cn^{-(1+\epsilon)}$ for a small positive $\epsilon$, and more recently, in a spectacular development, Jordan Ellenberg and Dion Gijswijt, building on work of Ernie Croot, Seva Lev and Peter Pach, obtained an upper bound of $c^n$ for a constant $c<1$. Ellenberg and Gijswijt used the polynomial method, and it is far from clear whether any analogue of that method can be made to work for Roth’s theorem, so there is continued interest in the argument of Bateman and Katz, which involved a delicate analysis of the structure of the set of large Fourier coefficients of a dense set. Could a similar analysis be used to improve the current record for Roth’s theorem by a power of $\log n$? There are significant difficulties (not least of which is the complexity of the arguments that one would be trying to combine), but there does not appear to be a clear reason to suppose that such a programme cannot be carried out.

Given the difficulties, there is a premium on understanding existing results as well as possible, and that is the purpose of this paper. It does not improve on the best known bound for Roth’s theorem, but it obtains a comparable bound (that is, one of the form $(\log\log N)^t/\log N$) in a new way. The main tool used in the proof, which also played a very important role in Sanders’s proof, which was the first to obtain a bound of this type, is so-called almost periodicity, a kind of argument pioneered by Ernie Croot and the second author of this paper that takes place in physical space and thereby avoids certain recurring difficulties with Fourier analysis. The difference with previous proofs of strong bounds for Roth’s theorem is that it is somewhat simpler, and that the proportion of the argument that uses Fourier analysis is much smaller, and restricted to a relatively standard step. The paper thus gives us a new angle on the theorem, which should increase the chance that some suitable combination of techniques will be found that can break the log barrier.