A new proof of Szemerédi's theorem for arithmetic progressions of length four (Q1266182): Difference between revisions

This remarkable paper gives a new proof that every subset of the integers with positive density must contain arithmetic progressions of length four. This was conjectured by \textit{P. Erdös} and \textit{P. Turán} [J. Lond. Math. Soc. 11, 261-264 (1936; Zbl 0015.15203)], and eventually proved by \textit{E. Szemerédi} [Acta Math. Acad. Sci. Hung. 20, 89-104 (1969; Zbl 0175.04301)]. Szemerédi's proof depended on the theorem of van der Waerden. It gave no explicit function \(\eta (N)\), tending to zero with \(N\), such that an integer subset of \([1,N]\) of size at least \(\eta (N)N\) must contain a progression of length 4. Since then it has been an important open problem, which this paper solves, to prove Szemerédi's result with an explicit function \(\eta (N)\). The result given here is that there is a positive constant \(c\) such that any integer subset of \([1,N]\) with at least \(N(\log \log \log N)^{-c}\) elements contains an arithmetic progression of length 4. In a future paper it is promised that the number of logarithms will be reduced to 2. Moreover the author plans to extend the technique to arithmetic progressions of arbitrary length \(k\geq 4\), obtaining bounds of the same form, but with the constant \(c\) depending on \(k\). The initial stages of the proof are motivated by \textit{K. F. Roth}'s treatment [J. Lond. Math. Soc. 28, 104-109 (1953; Zbl 0050.04002)] of progressions of length 3, in which the circle method was used. However it is clear that the usual notion of uniform distribution is not sufficient to handle progressions of length 4. Instead Gowers uses `quadratic uniformity'. If \(A\subseteq[1,N]\) is an integer set with \(\eta N\) elements, and characteristic function \(\chi_A\), define \(a_n= \chi_A(n)-\eta\). Roughly speaking, one says that \(A\) is quadratically uniform if \[ \sum_{n\leq N} a_na_{n+k} \exp (2\pi in\theta) =o(\eta N), \] uniformly in \(\theta\), for `almost all' relevant \(k\). It is shown that a quadratically uniform set contains arithmetic progressions of length 4. For a set that fails to be quadratically uniform, one can find many values of \(k\) for which the above sum is large at some value \(\theta= \gamma (k)/N\), with \(\gamma (k)\) integral. The proof proceeds to find a large set \({\mathcal K}\) of values of \(k\) for which the graph \(\Gamma= \{(k,\gamma (k)):k \in {\mathcal K}\}\) has a difference set whose cardinality is little more than that of \(\Gamma\) itself. This is the situation described by the theorem of \textit{G. Freiman} [Foundations of a structural theory of set addition, Transl. Math. Monogr. 37 (1973; Zbl 0271.10044)]. A quantitative version of this result, due to \textit{I. Ruzsa} [Acta Math. Hung. 65, 379-388 (1994; Zbl 0816.11008)] is applied to show that there is a long arithmetic progression, almost all of whose elements lie in \(\Gamma\). Using this information it is shown that if \(A\) is not quadratically uniform, then there exist \(\alpha\) and \(\beta\), and a long arithmetic progression \(P\), such that \[ \sum_{n\in P} a_n \exp\bigl (2\pi i(\alpha n^2+ \beta n) \bigr) \] is large. The proof is now completed by showing that there is a further large arithmetic progression \(Q\), say, such that \(\sum_{n\in Q}a_n\) is large and positive. It follows that the density \(\eta\) for the original set \(A\) must be appreciably smaller than for \(A\cup Q\). As in Roth's theorem, one can now iterate this fact to get the bound \(\eta\ll (\log \log \log N)^{-c}\). It is natural to ask to what extent the proof can be adapted to attack the problem of 4 primes in arithmetic progression. In fact large parts of the argument go through. However it is clear that the use of anything like Freiman's theorem will provide bounds which are too weak for such an application.