- Szemerédi's theorem
In
number theory Szemerédi's theorem refers to the proof of the Erdős–Turán conjecture. In 1936 Erdős and Turan conjecturedcitation|authorlink1=Paul Erdős|first1=Paul|last1=Erdős|authorlink2=Paul Turán|first2=Paul|last2=Turán|title=On some sequences of integers|journal=Journal of the London Mathematical Society |volume=11|year=1936|pages=261–264.] 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"} ofcardinality "dN" contains a length-karithmetic 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 1956 by
Klaus Roth [citation|authorlink=Klaus Friedrich Roth|first=Klaus Friedrich|last=Roth|title=On certain sets of integers, I|journal=Journal of the London Mathematical Society |volume=28|pages=104–109|year=1953|id=Zbl 0050.04002, MathSciNet|id=0051853.] by an adaptation of theHardy-Littlewood circle method . The case "k" = 4 was established in 1969 byEndre Szemerédi [citation|authorlink=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no four elements in arithmetic progression|journal=Acta Math. Acad. Sci. Hung.|volume=20|pages=89–104|year=1969|id=Zbl 0175.04301, MathSciNet|id=0245555|doi=10.1007/BF01894569.] by a combinatorial method. Using an approach similar to the one he used for the case "k" = 3, Roth [citation|authorlink=Klaus Friedrich Roth|first=Klaus Friedrich|last=Roth|title=Irregularities of sequences relative to arithmetic progressions, IV|journal=Periodica Math. Hungar.|volume=2|pages=301–326|year=1972|id=MathSciNet|id=0369311|doi=10.1007/BF02018670.] gave a second proof for this in 1972.Finally, the case of general "k" was settled in 1975, also by Szemerédi, [citation|authorlink=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no "k" elements in arithmetic progression|journal=Acta Arithmetica|volume=27|pages=199–245|year=1975|id=Zbl 0303.10056, MathSciNet|id=0369312.] by an ingenious and complicated extension of the previous combinatorial argument ("a masterpiece of combinatorial reasoning", R. L. Graham). Important alternative proofs of this theorem were later found by
Hillel Furstenberg [citation|authorlink=Hillel Furstenberg|first=Hillel|last=Furstenberg|title=Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions|journal=J. d’Analyse Math.|volume=31|pages=204–256|year=1977|id=MathSciNet|id=0498471.] in 1977, usingergodic theory , and byTimothy Gowers citation|authorlink=Timothy Gowers|first=Timothy|last=Gowers|title=A new proof of Szemerédi's theorem|journal=Geom. Funct. Anal.|volume=11|issue=3|pages=465–588|year=2001|id=MathSciNet|id=1844079.] in 2001, using bothFourier 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:"N" = "N"("k", δ)
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" > 0. The lower bound is due to
Behrend [citation|authorlink=Felix A. Behrend|first=Felix A.|last=Behrend|title=On the sets of integers which contain no three in arithmetic progression|journal=Proceedings of the National Academy of Sciences |volume=23|pages=331–332|year=1946|id=Zbl 0060.10302.] (for "k" = 3) and Rankin, [citation|authorlink=Robert A. Rankin|first=Robert A.|last=Rankin|title=Sets of integers containing not more than a given number of terms in arithmetical progression|journal=Proc. Roy. Soc. Edinburgh Sect. A|volume=65|pages=332–344|year=1962|id=Zbl 0104.03705, MathSciNet|id=0142526.] and the upper bound is due to Gowers. When "k" = 3 better upper bounds are known; the current record is:N(3,delta) leq C^{delta^{-2}log(1/delta)},
due to
Bourgain . [citation|authorlink=Jean Bourgain|first=Jean|last=Bourgain|title=On triples in arithmetic progression|journal=Geom. Func. Anal.|volume=9|year=1999|pages=968–984|id=MathSciNet|id=1726234|doi=10.1007/s000390050105.]ee also
*
Problems involving arithmetic progressions
*Ergodic Ramsey theory
*Arithmetic combinatorics References
External links
* [http://planetmath.org/encyclopedia/SzemeredisTheorem.html PlanetMath source for initial version of this page]
* [http://www.math.ucla.edu/~tao/whatsnew.html Announcement by Ben Green and Terence Tao] - the preprint is available at [http://front.math.ucdavis.edu/math.NT/0404188 math.NT/0404188]
* [http://in-theory.blogspot.com/2006/06/szemeredis-theorem.html Discussion of Szemerédi's theorem (part 1 of 5)]
*Ben Green and Terence Tao: [http://www.scholarpedia.org/article/Szemeredi%27s_Theorem Szemerédi's theorem] onScholarpedia .
Wikimedia Foundation. 2010.