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

Gowers, W. T.

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).

Reviewer: Štefan Porubský (Praha)

MSC:

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

Keywords:

Roth theorem; uniform sets; pseudo-randomness; Szemerédi theorem; van der Waerden theorem; Freiman inverse problem theorem; Freiman homomorphism

Citations:

Zbl 0303.10056