Added to Favorites

Related Searches

Definitions

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 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).## See also

## References

## External links

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 by an adaptation of the Hardy-Littlewood circle method. The case k = 4 was established in 1969 by Endre Szemerédi by a combinatorial method. Using an approach similar to the one he used for the case k = 3, Roth gave a second proof for this in 1972.

Finally, the case of general k was settled in 1975, also by Szemerédi, 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 in 1977, using ergodic theory, and by Timothy Gowers 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 (for k = 3) and Rankin, 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.

- 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.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday July 01, 2008 at 23:18:45 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday July 01, 2008 at 23:18:45 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.