# Szemerédi's theorem

﻿
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"} 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 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 the Hardy-Littlewood circle method. The case "k" = 4 was established in 1969 by Endre 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, using ergodic theory, and by Timothy Gowerscitation|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 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

:"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^\left\{log\left(1/delta\right)^\left\{k-1 leq N\left(k,delta\right) leq 2^\left\{2^\left\{delta^\left\{-2^\left\{2^\left\{k+9\right\}$

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\left(3,delta\right) leq C^\left\{delta^\left\{-2\right\}log\left(1/delta\right)\right\},$

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

* [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] on Scholarpedia.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Szemerédi–Trotter theorem — In mathematics, the Szemerédi–Trotter theorem is a result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane,the number of incidences (i.e. the number of point line pairs, such that the point lies on… …   Wikipedia

• Szemerédi regularity lemma — In mathematics, Szemerédi s regularity lemma states that every large enough (finite undirected simple) graph can be approximated by a composition of a structured and a pseudo random part.Formal statement of the regularity lemmaThe formal… …   Wikipedia

• Endre Szemerédi — (born August 21 1940) is a Hungarian mathematician, working in the field of combinatorics, currently professor of computer science at Rutgers University. He was born in Budapest. His advisers in mathematics were Paul Erdős and András Hajnal.He is …   Wikipedia

• Van der Waerden's theorem — is a theorem of the branch of mathematics called Ramsey theory. The theorem is about the basic structure of the integers. It is named for Dutch mathematician B. L. van der Waerden. [B.L. van der Waerden, Beweis einer Baudetschen Vermutung , Nieuw …   Wikipedia

• Beck's theorem (geometry) — In incidence geometry, Beck s theorem is a more quantitative form of the more classical Sylvester–Gallai theorem. It says that finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a… …   Wikipedia

• Green–Tao theorem — In mathematics, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, [Ben Green and Terence Tao, [http://arxiv.org/abs/math.NT/0404188 The primes contain arbitrarily long arithmetic progressions] ,8 Apr 2004.] states that the… …   Wikipedia

• Hales–Jewett theorem — In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory, concerning the degree to which high dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to… …   Wikipedia

• Roth's theorem — There are two major results of Klaus Roth in mathematics which go by the name Roth s theorem :* The Thue Siegel Roth theorem in Diophantine approximation, which concerns the rarity to which an irrational algebraic number can be approximated by a… …   Wikipedia

• Erdős–Stone theorem — In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán s theorem to bound the number of edges in an H free graph for a non complete graph H . It is named after Paul Erdős and Arthur Stone, who proved it in… …   Wikipedia

• Corners theorem — In mathematics, the corners theorem is an important result, proved by Miklós Ajtai and Endre Szemerédi, of a statement in arithmetic combinatorics. It states that for every ε > 0 there exists N such that given at least εN2 points in… …   Wikipedia