Logarithmic bounds for Roth’s theorem via almost-periodicity

- Department of Pure Mathematics and Mathematical Statistics, University of Cambridge
- More about Thomas Bloom

- Department of Mathematics, Uppsala University
- More about Olof Sisask

*Discrete Analysis*, May. https://doi.org/10.19086/da.7884.

### Editorial introduction

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 δ>0 there exists N such that every subset of {1,2,…,N} of size at least δ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 ρk(N) to be the minimum real number such that every subset of {1,2,…,N} of density at least ρk(N) contains an arithmetic progression of length k, then Roth’s theorem asserts that ρ3(N)→0 and Szemerédi’s theorem asserts that ρk(N)→0 for all k.

These results leave open the question of bounds. Roth’s proof shows that ρ3(N)≤C/loglogN 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(loglogN)4/logN. This is tantalizingly close to 1/logN, which is an important barrier because if one could get past it then one would be able to prove that every set A⊂N such that ∑x∈Ax−1=∞ 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⊂Fn3 must have in order to contain an affine line, which is the natural notion of an arithmetic progression of length 3 in Fn3. For a long time the best known upper bound was stuck at Cn−1, which is also a logarithmic bound, since the cardinality of Fn3 is 3n. Then a few years ago, Michael Bateman and Nets Katz improved the bound to Cn−(1+ϵ) for a small positive ϵ, 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 cn 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 logn? 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 (loglogN)t/logN) 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.