On sets of integers containing no \(k\) elements in arithmetic progression. (English) Zbl 0303.10056

Szemerédi, Endre

Acta Arith. 27, 199-245 (1975).

In this paper, the author, by an exceedingly ingenious method, settles in the affirmative the following famous conjecture:
For all \(\varepsilon\) and \(k\), there exists \(N(k,\varepsilon)\) such that if \(n>N(k,\varepsilon)\) and \(R\) is a set of natural numbers \(\subseteq [0,n)\) with \(| R|>\varepsilon n\), then \(R\) contains an arithmetic progression with \(k\) terms.
Previously the conjecture was settled for the case \(k=3\) by K. F. Roth in 1952 [J. Lond. Math. Soc. 28, 104–109 (1953; Zbl 0050.04002)] and for the case \(k=4\) by E. Szemerédi himself in 1967 [Acta Math. Acad. Sci. Hung. 20, 89–104 (1969; Zbl 0175.04301)]. The method of proof in the present paper, though very complicated, is ‘elementary’.

Reviewer: S. L. G. Choi (Vancouver)

MSC:

11B25	Arithmetic progressions
05D05	Extremal set theory

Keywords:

arithmetic progressions

Citations:

Zbl 0050.04002; Zbl 0175.04301