Szemerédi's theorem

From Wikipedia, the free encyclopedia

In mathematics, Szemerédi's theorem states that a set of natural numbers of upper asymptotic density > 0 contains finite arithmetic progressions, of any arbitrary length k. This generalizes the statement of van der Waerden's theorem. It was conjectured by Paul Erdős and Paul Turán in 1936.^[1]

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

Finally, the case of general k was settled in 1975, also by Szemerédi,^[5] 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^[6] in 1977, using ergodic theory, and by Timothy Gowers^[7] in 2001, using both Fourier analysis and combinatorics.

Let k be a positive integer and let 0 < δ ≤ 1. 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^[8] (for k = 3) and Rankin,^[9] and the upper bound is due to Gowers.^[7]. When k = 3 better upper bounds are known; the current record is

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

due to Bourgain.^[10]

It was conjectured by Erdős and Turán^[1] that 'positive density' could here be relaxed to any sequence whose series of reciprocals diverges (see small set). This would in particular apply to the series of prime numbers, implying the corollary

the sequence of primes numbers contains arithmetic progressions of any length.

This result (only the corollary, not the Erdős-Turán conjecture) was proven by Ben Green and Terence Tao in 2004 and is now known as the Green-Tao theorem.

[edit] See also

Bartel Leendert van der Waerden

[edit] References

^ ^a ^b Paul Erdős, Paul Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261--264.
^ Klaus Friedrich Roth, On certain sets of integers I, J. London Math. Soc., 28:104-109, 1953, Zbl 0050.04002.
^ Endre Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hung., 20:89-104, 1969, Zbl 0175.04301.
^ K. F. Roth, Irregularities of sequences relative to arithmetic progressions IV. Periodica Math. Hungar., 2, pages 301-26 (1972)
^ Endre Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica, 27:199-245, 1975, Zbl 0303.10056.
^ H. Furstenberg, Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. d’Analyse Math., 31, pages 204-256
^ ^a ^b Timothy Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(3):465-588, 2001, Preprint available at http://www.dpmms.cam.ac.uk/~wtg10/papers.html.
^ Felix A. Behrend, On the sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sci., 23:331-332, 1946, Zbl 0060.10302.
^ Robert A. Rankin Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A, 65:332-344, 1962, Zbl 0104.03705.
^ Jean Bourgain, On triples in arithmetic progression, Geom. Func. Anal. 9 (1999), 968--984