Szemerédi's Theorem

Szemerédi's theorem states that every sequence of integers that has positive upper Banach density contains arbitrarily long arithmetic progressions.

A corollary states that, for any positive integer  and positive real number , there exists a threshold number  such that for  every subset of  with cardinal number larger than  contains a -term arithmetic progression. van der Waerden's Theorem follows immediately by setting . The best bounds for van der Waerden numbers are derived from bounds for  in Szemerédi's theorem.

Szemerédi's theorem was conjectured by Erdős and Turán (1936). Roth (1953) proved the case , and was mentioned in his Fields Medal citation. Szemerédi (1969) proved the case , and the general theorem in 1975 as a consequence of Szemerédi's regularity lemma (Szemerédi 1975a), for which he collected a $1000 prize from Erdos. Fürstenberg and Katznelson (1979) proved Szemerédi's theorem using ergodic theory. Gowers (1998ab) subsequently gave a new proof, with a better bound on , for the case  (mentioned in his Fields Medal citation; Lepowsky et al. 1999).

REFERENCES:

Erdős, P. and Turán, P. "On Some Sequences of Integers." J. London Math. Soc. 11, 261-264, 1936.

Fürstenberg, H. "Ergodic Behavior of Diagonal Measures and a Theorem of Szemerédi on Arithmetic Progressions." J. Analyse Math. 31, 204-256, 1977.

Fürstenberg, H. and Katznelson, Y. "An Ergodic Szemerédi Theorem for Commuting Transformations." J. Analyse Math. 34, 275-291, 1979.

Fürstenberg, H. and Weiss, B. "A Mean Ergodic Theorem for ." In Convergence in Ergodic Theory and Probability (Columbus OH 1993). Berlin: de Gruyter, pp. 193-227, 1996.

Fürstenberg, H.; Katznelson, Y.; and Ornstein, D. "The Ergodic-Theoretical Proof of Szemerédi's Theorem." Bull. Amer. Math. Soc. 7, 527-552, 1982.

Gowers, W. T. "Fourier Analysis and Szemerédi's Theorem." In Proceedings of the International Congress of Mathematicians, Vol. I (Berlin, 1998). Doc. Math., Extra Vol. I, 617-629, 1998a.

Gowers, W. T. "A New Proof of Szemerédi's Theorem for Arithmetic Progressions of Length Four." Geom. Funct. Anal. 8, pp. 529-551, 1998b.

Gowers, W. T. "A New Proof of Szemerédi's Theorem." Geom. Funct. Anal. 11, 465-588, 2001.

Graham, R. L.; Rothschild, B. L.; and Spencer, J. H. Ramsey Theory, 2nd ed. New York: Wiley, 1990.

Green, B. and Tao, T. "The Primes Contain Arbitrarily Long Arithmetic Progressions." Preprint. 8 Apr 2004. https://arxiv.org/abs/math.NT/0404188.

Guy, R. K. "Theorem of van der Waerden, Szemerédi's Theorem. Partitioning the Integers into Classes; at Least One Contains an A.P." §E10 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 204-209, 1994.

Lepowsky, J.; Lindenstrauss, J.; Manin, Y.; and Milnor, J. "The Mathematical Work of the 1998 Fields Medalists." Not. Amer. Math. Soc. 46, 17-26, 1999.

Roth, K. "Sur quelques ensembles d'entiers." Comptes Rendus Acad. Sci. Paris 234, 388-390, 1952.

Roth, K. F. "On Certain Sets of Integers." J. London Math. Soc. 28, 104-109, 1953.

Szemerédi, E. "On Sets of Integers Containing No Four Elements in Arithmetic Progression." Acta Math. Acad. Sci. Hungar. 20, 89-104, 1969.

Szemerédi, E. "On Sets of Integers Containing No  Elements in Arithmetic Progression." Acta Arith. 27, 199-245, 1975a.

Szemerédi, E. "On Sets of Integers Containing No  Elements in Arithmetic Progression." In Proceedings of the International Congress of Mathematicians, Volume 2, Held in Vancouver, B.C., August 21-29, 1974. Montreal, Quebec: Canad. Math. Congress, pp. 503-505, 1975b.