A new proof of Szemerédi’s theorem. (English) Zbl 1028.11005

Geom. Funct. Anal. 11, No. 3, 465-588 (2001); Erratum 11, No. 4, 869 (2001).
The main result of the paper is the following improvement of E. Szemerédi’s theorem [Acta Arith. 27, 199-245 (1975; Zbl 0303.10056)]: For every positive integer \(k\), every subset of \(\{0,1,\dots,N\}\) of size at least \(N(\log\log N)^{-c}\) with \(c=2^{-2^{k+9}}\) contains an arithmetic progression of length \(k\). This has an immediate consequence also for an estimate for the least integer \(M=M(k,r)\) in van der Waerden’s theorem on \(k\) term arithmetic progressions in partitions of the set \(\{1,2,\dots,M\}\) into \(r\) subsets. The main ingredients of the machinery used to prove this result (together with many very clever modifications of ideas previously used in the solution of this problem) is a generalizations of Roth’s analytic argument for three term progressions and a variation of Freiman’s inverse problem theorem.
The author spares no effort to explain in detail the background and motivation for all important steps of the proof. So for instance, since the difficulties for progressions of length greater than four are considerably greater, the author devotes special attention to the case of arithmetic progressions of length four.
As a corollary he obtains: There is an absolute constant \(c>0\) such that if the set \(\{1,2,\dots,N\}\) is colored with at most \((\log\log N)^c\) colors, then there is a \(4\)-term monochromatic arithmetic progression.
From other results of the paper which could be of independent interest, let us mention the confirmation of Ron Graham’s conjecture that \(M(K,2)\) is bounded above by a tower of twos of height \(k\). The author proves this for \(k\geq 9\). (A bit confusing for the orientation is that the page numbers for the sections of this long paper given at the beginning do not agree with the actual ones).


11B25 Arithmetic progressions
05D10 Ramsey theory
11L07 Estimates on exponential sums
11P70 Inverse problems of additive number theory, including sumsets
11K38 Irregularities of distribution, discrepancy


Zbl 0303.10056
Full Text: DOI