New bound for Roth’s theorem with generalized coefficients

New bound for Roth’s theorem with generalized coefficients, Discrete Analysis 2022:16, 21 pp.

Roth’s theorem states 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. It is the first non-trivial case of Szemerédi’s theorem (which is the generalization from 3 to arbitrary \(k\)), and as such has played an absolutely central role in additive combinatorics.

Surprisingly, given the simplicity of the statement, obtaining upper and lower bounds that are reasonably close to each other has turned out to be a very hard problem. These are usually stated the other way: given \(n\), how large does the density \(\delta\) need to be in order to guarantee a progression of length 3. Roth’s proof gave an upper bound of \(C/\log\log n\) for an absolute constant \(C\). This was improved by Szemerédi and Heath-Brown (independently) to \((\log n)^{-c}\). Bourgain showed that \(c\) could be taken to be 1/2 (up to \(\log\log\) factors). After a couple more improvements, Sanders obtained the first bound with \(c=-1\), though again with \(\log\log\) factors, which was significant because proving the result with a density of \(c\log\log n/\log n\) for a sufficiently small constant \(c>0\) is enough to show by purely combinatorial means that the primes contain infinitely many progressions of length 3.

Sanders’s result was not quite strong enough to do this, but eventually Bloom and Sisask managed to combine earlier ideas of Bloom (that had obtained a result slightly stronger than that of Sanders but of a similar type) with ideas of Bateman and Katz (connected with the cap-set problem, which is a natural analogue Roth’s theorem in \(\mathbb F_3^n\)), to obtain a bound of the form \((\log n)^{-(1+c)}\) for a positive constant \(c\). This proved the case \(k=3\) of a famous conjecture of Erdős, which states that if \(A\) is a subset of \(\mathbb N\) such that \(\sum_{a\in A}a^{-1}=\infty\), then \(A\) contains an arithmetic progression of length \(k\) for every \(k\).

In the other direction, the best we know (give or take some small refinements) is a construction of Behrend from 1947 that gives a set of density \(\exp(-c\sqrt{\log n})\) that does not contain an arithmetic progression of length 3. This is a far smaller density than \((\log n)^{-(1+c)}\), so the gap between the best known upper and lower bounds is still very large, though Bloom and Sisask speculate that their methods could be pushed to give bounds much more like the Behrend bound – see the concluding remarks of their paper for more details.

Szemerédi’s theorem has many generalizations, among which are higher-dimensional generalizations. For instance, given any subset \(K\subset\mathbb Z^d\) and any \(\delta>0\) there exists \(n\) such that every subset \(A\) of \(\{1,2,\dots,n\}^d\) of density at least \(\delta\) contains a homothetic copy (that is, a translate of a dilate) of \(K\). For this result we know much less about quantitative bounds. The simplest case that does not follow immediately from Szemerédi’s theorem is the corners theorem, which is the case where \(K\) is the set \(\{(0,0), (1,0), (0,1)\}\) in \(\mathbb Z^2\). Here, Behrend’s construction still gives the best known lower bound, but the best upper bound, due to Shkredov, is \((\log\log n)^{-c}\).

However, the problem becomes more like Roth’s theorem if one allows not just translates and dilates, but also rotated copies of \(K\). Roughly speaking, this allows one to carry out similar kinds of Fourier-analysis arguments to those that are used to prove Roth’s theorem. As a result of this, Shkredov and Solymosi conjectured that a bound of a similar type to the one obtained by Bloom and Sisask should be true for this problem too. That is, they conjectured that every subset of \(\{1,2,\dots,n\}^2\) of density at least \((\log n)^{-(1+c)}\) (for some suitable positive \(c\)) contains the vertices of an isosceles right-angled triangle.

This paper proves the conjecture of Shkredov and Solymosi. In fact, it proves a statement about more general configurations of three points \(x,y,z\) with linear relations between them of the form \(T_1x+T_2y+T_3z=0\), where \(T_1,T_2,T_3\) are linear maps. (To obtain isosceles right-angled triangles one can use the relation \((z-x)=T(y-x)\), where \(T\) is a rotation by \(\pi/2\).)

As one might expect, the paper uses several lemmas from Bloom and Sisask’s paper as black boxes, but some parts of the proof do not carry over straightforwardly, and have had to be modified in non-obvious ways in order to prove this more general result. In order to find these modifications, it was necessary for the author to read Bloom and Sisask’s long and technically difficult paper in great detail, so an incidental benefit of this work is that that paper has now been thoroughly checked.