Szemerédi's theorem
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(d, k) such that every subset A of {1, ..., N} of cardinality dN contains a length-k arithmetic progression, provided N > N(d, k).
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
- Problems involving arithmetic progressions
- Ergodic Ramsey theory
- Arithmetic combinatorics
- Szemerédi regularity lemma
- Green–Tao theorem
- Erdos conjecture on arithmetic progressions
Notes
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Roth, Klaus Friedrich (1972), "Irregularities of sequences relative to arithmetic progressions, IV", Periodica Math. Hungar., 2: 301–326, doi:10.1007/BF02018670, MR0369311.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Bourgain, Jean (1999), "On triples in arithmetic progression", Geom. Func. Anal., 9 (5): 968–984, doi:10.1007/s000390050105, MR1726234
- ^ arXiv:1011.0104, [1], see also [2]
Further reading
- Tao, Terence (2007). "The ergodic and combinatorial approaches to Szemerédi's theorem". In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József (eds.). Additive Combinatorics. CRM Proceedings & Lecture Notes. Vol. 43. American Mathematical Society. pp. 145–193. ISBN 978-0-8218-4351-2. Zbl 1159.11005.
External links
- PlanetMath source for initial version of this page
- Announcement by Ben Green and Terence Tao – the preprint is available at math.NT/0404188
- Discussion of Szemerédi's theorem (part 1 of 5)
- Ben Green and Terence Tao: Szemerédi's theorem on Scholarpedia
- Weisstein, Eric W. "SzemeredisTheorem". MathWorld.