Szemerédi's_theorem

Szemerédi's theorem

In number theory Szemerédi's theorem refers to the proof of the Erdős–Turán conjecture. In 1936 Erdős and Turan conjectured for every value d called density 0 < d <1 and every integer k there is a number N(d,k) such that every subset A of {1,...,N} of cardinality dN contains a length-k arithmetic progression, provided N > N(d,k).

This generalizes the statement of van der Waerden's theorem.

The cases k=1 and k=2 are trivial. The case k = 3 was established in 1956 by Klaus Roth by an adaptation of the Hardy-Littlewood circle method. The case k = 4 was established in 1969 by Endre Szemerédi by a combinatorial method. Using an approach similar to the one he used for the case k = 3, Roth gave a second proof for this in 1972.

Finally, the case of general k was settled in 1975, also by Szemerédi, by an ingenious and complicated extension of the previous combinatorial argument ("a masterpiece of combinatorial reasoning", R. L. Graham). Important alternative proofs of this theorem were later found by Hillel Furstenberg in 1977, using ergodic theory, and by Timothy Gowers in 2001, using both Fourier analysis and combinatorics.

Let k be a positive integer and let 0 < δ ≤ 1/2. A finitary version of the theorem states that there exists a positive integer

N = N(k, δ)

such that every subset of {1, 2, ..., N} of size at least δN contains an arithmetic progression of length k. The best-known bounds for N(k, δ) are

C^{log(1/delta)^{k-1}} leq N(k,delta) leq 2^{2^{delta^{-2^{2^{k+9}}}}}

with C > 0. The lower bound is due to Behrend (for k = 3) and Rankin, and the upper bound is due to Gowers. When k = 3 better upper bounds are known; the current record is