Szemerédi's theorem: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
It is known that for fixed <math>\delta</math> and n sufficiently large one can take k to be <math>\log\log\log\log\log\log n.</math> (This is not quite the best known bound but is easier to state.) | It is known that for fixed <math>\delta</math> and n sufficiently large one can take k to be <math>\log\log\log\log\log\log n.</math> (This is not quite the best known bound but is easier to state.) | ||
Szemerédi's theorem implies [[Roth's theorem]]. The result was [[Szemerédi's original proof of Szemerédi's theorem|first proven by Szemerédi in 1975]]. | |||
See also [http://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem the Wikipedia entry] for this theorem, or the [http://www.scholarpedia.org/article/Szemeredi%27s_Theorem Scholarpedia entry]. | See also [http://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem the Wikipedia entry] for this theorem, or the [http://www.scholarpedia.org/article/Szemeredi%27s_Theorem Scholarpedia entry]. | ||
Latest revision as of 16:17, 26 February 2009
Szemerédi's theorem Any subset of the integers of positive upper density contains arbitrarily long arithmetic progressions.
Finite version. For every [math]\displaystyle{ \delta\gt 0 }[/math] and every positive integer k there exists n such that every subset [math]\displaystyle{ A\subset [n] }[/math] of size at least [math]\displaystyle{ \delta n }[/math] contains an arithmetic progression of length k.
It is known that for fixed [math]\displaystyle{ \delta }[/math] and n sufficiently large one can take k to be [math]\displaystyle{ \log\log\log\log\log\log n. }[/math] (This is not quite the best known bound but is easier to state.)
Szemerédi's theorem implies Roth's theorem. The result was first proven by Szemerédi in 1975.
See also the Wikipedia entry for this theorem, or the Scholarpedia entry.
