Szemerédi’s theorem


Let k be a positive integer and let δ>0. There exists a positive integer N=N(k,δ) such that every subset of {1,2,,N} of size (http://planetmath.org/Cardinality) δN contains an arithmetic progressionPlanetmathPlanetmath of length k.

The case k=3 was first proved by Roth[4]. His method did not seem to extend to the case k>3. Using completely different ideas Szemerédi proved the case k=4 [5], and the general case of an arbitrary k [6].

The best known bounds for N(k,δ) are

ec(log1δ)k-1N(k,δ)22δ-22k+9,

where the lower boundMathworldPlanetmath is due to Behrend[1] (for k=3) and Rankin[3], and the upper bound is due to Gowers[2].

For k=3 a better upper bound was obtained by Bourgain

N(3,δ)cδ-2e256δ-2.

References

  • 1 Felix A. Behrend. On the sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 23:331–332, 1946. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0060.10302Zbl 0060.10302.
  • 2 Timothy Gowers. A new proof of Szemerédi’s theoremMathworldPlanetmath. Geom. Funct. Anal., 11(3):465–588, 2001. Preprint available at http://www.dpmms.cam.ac.uk/ wtg10/papers.htmlhttp://www.dpmms.cam.ac.uk/ wtg10/papers.html.
  • 3 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. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0104.03705Zbl 0104.03705.
  • 4 Klaus Friedrich Roth. On certain sets of integers. J. London Math. Soc., 28:245–252, 1953. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0050.04002Zbl 0050.04002.
  • 5 Endre Szemerédi. On sets of integers containing no four elementsMathworldMathworld in arithmetic progression. Acta Math. Acad. Sci. Hung., 20:89–104, 1969. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0175.04301Zbl 0175.04301.
  • 6 Endre Szemerédi. On sets of integers containing no k elements in arithmetic progression. Acta. Arith., 27:299–345, 1975. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0303.10056Zbl 0303.10056.
Title Szemerédi’s theorem
Canonical name SzemeredisTheorem
Date of creation 2013-03-22 13:19:40
Last modified on 2013-03-22 13:19:40
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 17
Author bbukh (348)
Entry type Theorem
Classification msc 11B25
Classification msc 05D10