Szemerédi's theorem

From Wikipedia, the free encyclopedia

"Erdős–Turán conjecture" redirects here. For another conjecture attributed to Erdős and Turán, see Erdős conjecture on arithmetic progressions.

In number theory Szemerédi's theorem refers to the proof of the Erdős–Turán conjecture. In 1936 Erdős and Turan 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 1956 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). Important alternative proofs of this theorem were later found by Hillel Furstenberg^[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

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^[8] (for k = 3) and Rankin,^[9] and the upper bound is due to Gowers.^[7] 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.^[10]

[edit] See also

[edit] References

^ Erdős, Paul & Turán, Paul (1936), “On some sequences of integers”, Journal of the London Mathematical Society 11: 261–264 .
^ Roth, Klaus Friedrich (1953), “On certain sets of integers, I”, Journal of the London Mathematical Society 28: 104–109, Zbl 0050.04002, MR 0051853 .
^ Szemerédi, Endre (1969), “On sets of integers containing no four elements in arithmetic progression”, Acta Math. Acad. Sci. Hung. 20: 89–104, Zbl 0175.04301, MR 0245555, DOI 10.1007/BF01894569 .
^ Roth, Klaus Friedrich (1972), “Irregularities of sequences relative to arithmetic progressions, IV”, Periodica Math. Hungar. 2: 301–326, MR 0369311, DOI 10.1007/BF02018670 .
^ Szemerédi, Endre (1975), “On sets of integers containing no k elements in arithmetic progression”, Acta Arithmetica 27: 199–245, Zbl 0303.10056, MR 0369312 .
^ Furstenberg, Hillel (1977), “Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions”, J. d’Analyse Math. 31: 204–256, MR 0498471 .
^ ^a ^b Gowers, Timothy (2001), “A new proof of Szemerédi's theorem”, Geom. Funct. Anal. 11 (3): 465–588, MR 1844079 .
^ Behrend, Felix A. (1946), “On the sets of integers which contain no three in arithmetic progression”, Proceedings of the National Academy of Sciences 23: 331–332, 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, MR 0142526 .
^ Bourgain, Jean (1999), “On triples in arithmetic progression”, Geom. Func. Anal. 9: 968–984, MR 1726234, DOI 10.1007/s000390050105 .