Szemerédi's theorem

"Erdős–Turán conjecture" redirects here. For another conjecture attributed to Erdős and Turán, see Erdős conjecture on arithmetic progressions.

In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture (not to be confused with Erdős–Turán conjecture on additive bases). In 1936 Erdős and Turán 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). Several further proofs are now known, the most important amongst them being those by Hillel Fürstenberg 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,\delta)\,$

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 > 1. 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 best known is

$N(3,\delta) \leq C^{\delta^{-2}\log(1/\delta)},$

due to Bourgain.

See also

• Problems involving arithmetic progressions
• Ergodic Ramsey theory
• Arithmetic combinatorics
• Szemerédi regularity lemma
• Green–Tao theorem
• Erdos conjecture on arithmetic progressions

External links

• PlanetMath source for initial version of this page
• Announcement by Ben Green and Terence Tao – the preprint is available at math.NT/0404188
• Discussion of Szemerédi's theorem (part 1 of 5)
• Ben Green and Terence Tao: Szemerédi's theorem on Scholarpedia
• Weisstein, Eric W., "SzemeredisTheorem" from MathWorld.