|
|
In mathematics, Szemerédi's theorem states that a set of natural numbers of density > 0 contains finite arithmetic progressions, of any length k we may ask for. This generalizes the statement of van der Waerden's theorem. It was conjectured by Paul Erdős and Paul Turán in 1936 [3]. The cases k=1 and k=2 are trivial. The case k = 3 was established in 1956 by Klaus Roth [4] using methods from Fourier analysis. The case k = 4 was established in 1969 by Endre Szemerédi [7] by a combinatorial method. Finally, the case of general k was settled in 1975 by Endre Szemerédi [8] 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 [4] 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
- <math>C^{\log(1/\delta)^{k-1}} \leq N(k,\delta) \leq 2^{2^{\delta^{-2^{2^{k+9}}}}}<math>
with C > 0. The lower bound is due to Behrend [1] (for k = 3) and Rankin [5], and the upper bound is due to Gowers [4]. When k = 3 better upper bounds are known; the current record is
- <math>N(3,\delta) \leq C^{\delta^{-2}\log(1/\delta)},<math>
due to Bourgain[2].
It was conjectured by Erdős and Turán [3] that 'positive density' could here be relaxed to 'positive logarithmic density', i.e. a sequence whose series of reciprocals diverges (see small set). This would in particular apply to the series of prime numbers, implying that
- the sequence of primes numbers contains arithmetic progressions of any length.
A proof of this result on primes was announced by Ben Green and Terence Tao in April 2004.
References
- 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.
- Jean Bourgain, On triples in arithmetic progression, Geom. Func. Anal. 9 (1999), 968--984
- Paul Erdős, Paul Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261--264.
- 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.
- 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.
- Klaus Friedrich Roth, On certain sets of integers, J. London Math. Soc., 28:245-252, 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.
- Endre Szemerédi, On sets of integers containing no elements in arithmetic progression, Acta. Arith., 27:299-345, 1975, Zbl 0303.10056.
External links
- PlanetMath source for initial version of this page (http://planetmath.org/encyclopedia/SzemeredisTheorem.html)
- Announcement by Ben Green and Terence Tao (http://www.math.ucla.edu/~tao/whatsnew.html) - the preprint is available at math.NT/0404188 (http://front.math.ucdavis.edu/math.NT/0404188)