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 ( δ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


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



  • 1 Felix A. Behrend. On the sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 23:331–332, 1946. 0060.10302.
  • 2 Timothy Gowers. A new proof of Szemerédi’s theoremMathworldPlanetmath. Geom. Funct. Anal., 11(3):465–588, 2001. Preprint available at wtg10/papers.html 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. 0104.03705.
  • 4 Klaus Friedrich Roth. On certain sets of integers. J. London Math. Soc., 28:245–252, 1953. 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. 0175.04301.
  • 6 Endre Szemerédi. On sets of integers containing no k elements in arithmetic progression. Acta. Arith., 27:299–345, 1975. 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