Szemerédi's theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Szemerédi's theorem is a result in arithmetic combinatorics, concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured[1] that every set of integers A with positive natural density contains a k term arithmetic progression for every k. This conjecture, which became Szemerédi's theorem, 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 1953 by Klaus Roth[2] via an adaptation of the Hardy–Littlewood circle method. The case k = 4 was established in 1969 by Endre Szemerédi[3] via 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] via an ingenious and complicated extension of the previous combinatorial argument (called "a masterpiece of combinatorial reasoning" by R. L. Graham). Several further proofs are now known, the most important amongst them being those by Hillel Furstenberg[6] in 1977, using ergodic theory, and by Timothy Gowers[7] in 2001, using both Fourier analysis and combinatorics.

Finitary version[edit]

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[8] (for k = 3) and Rankin,[9] and the upper bound is due to Gowers.[7] When k = 3 better upper bounds are known; Bourgain[10] has proved that

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

This was improved by Sanders[11] to

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

See also[edit]


  1. ^ Erdős, Paul; Turán, Paul (1936), "On some sequences of integers" (PDF), Journal of the London Mathematical Society 11 (4): 261–264, doi:10.1112/jlms/s1-11.4.261 .
  2. ^ Roth, Klaus Friedrich (1953), "On certain sets of integers, I", Journal of the London Mathematical Society 28: 104–109, doi:10.1112/jlms/s1-28.1.104, Zbl 0050.04002, MR 0051853 .
  3. ^ Szemerédi, Endre (1969), "On sets of integers containing no four elements in arithmetic progression", Acta Math. Acad. Sci. Hung. 20: 89–104, doi:10.1007/BF01894569, Zbl 0175.04301, MR 0245555 .
  4. ^ Roth, Klaus Friedrich (1972), "Irregularities of sequences relative to arithmetic progressions, IV", Periodica Math. Hungar. 2: 301–326, doi:10.1007/BF02018670, MR 0369311 .
  5. ^ Szemerédi, Endre (1975), "On sets of integers containing no k elements in arithmetic progression" (PDF), Acta Arithmetica 27: 199–245, Zbl 0303.10056, MR 0369312 .
  6. ^ Furstenberg, Hillel (1977), "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", J. D'Analyse Math. 31: 204–256, doi:10.1007/BF02813304, MR 0498471 .
  7. ^ a b Gowers, Timothy (2001), "A new proof of Szemerédi's theorem", Geom. Funct. Anal. 11 (3): 465–588, doi:10.1007/s00039-001-0332-9, MR 1844079 .
  8. ^ Behrend, Felix A. (1946), "On the sets of integers which contain no three in arithmetic progression", Proceedings of the National Academy of Sciences 23 (12): 331–332, doi:10.1073/pnas.32.12.331, Zbl 0060.10302 .
  9. ^ Rankin, Robert A. (1962), "Sets of integers containing not more than a given number of terms in arithmetical progression", Proc. Roy. Soc. Edinburgh Sect. A 65: 332–344, Zbl 0104.03705, MR 0142526 .
  10. ^ Bourgain, Jean (1999), "On triples in arithmetic progression", Geom. Func. Anal. 9 (5): 968–984, doi:10.1007/s000390050105, MR 1726234 
  11. ^ Sanders, Tom (2011), "On Roth's theorem on progressions", Annals of Mathematics 174 (1): 619–636, doi:10.4007/annals.2011.174.1.20, MR 2811612 

Further reading[edit]

External links[edit]