Jump to content

Szemerédi's theorem

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Deltahedron (talk | contribs) at 06:32, 3 August 2012 (Further reading: Tao). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture (not to be confused with Erdős–Turán conjecture on additive bases). In 1936 Erdős and Turán conjectured[1] for every value d called density 0 < d < 1 and every integer k there is a number N(dk) such that every subset A of {1, ..., N} of cardinality dN contains a length-k arithmetic progression, provided N > N(dk).

This 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] 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). Several further proofs are now known, the most important amongst them being those by Hillel Fürstenberg[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/2. A finitary version of the theorem states that there exists a positive integer

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

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

In 2010, Sanders has proved that a subset of {1, 2, ..., N} with no arithmetic subsequence of length three is of size . [11]

See also

Notes

  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, MR0051853.
  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, MR0245555.
  4. ^ Roth, Klaus Friedrich (1972), "Irregularities of sequences relative to arithmetic progressions, IV", Periodica Math. Hungar., 2: 301–326, doi:10.1007/BF02018670, MR0369311.
  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, MR0369312.
  6. ^ Fürstenberg, 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, MR0498471.
  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, MR1844079.
  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, MR0142526.
  10. ^ Bourgain, Jean (1999), "On triples in arithmetic progression", Geom. Func. Anal., 9 (5): 968–984, doi:10.1007/s000390050105, MR1726234
  11. ^ arXiv:1011.0104, [1], see also [2]

Further reading