Szemerédi's theorem: Difference between revisions
New page: '''Szemerédi's theorem''' Any subset of the integers of positive upper density contains arbitrarily long arithmetic progressions. This implies Roth's theorem. The result was [[Szem... |
No edit summary |
||
| Line 1: | Line 1: | ||
'''Szemerédi's theorem''' Any subset of the integers of positive upper density contains arbitrarily long arithmetic progressions. | '''Szemerédi's theorem''' Any subset of the integers of positive upper density contains arbitrarily long arithmetic progressions. | ||
'''Finite version.''' For every <math>\delta>0</math> and every positive integer k there exists n such that every subset <math>A\subset [n]</math> of size at least <math>\delta n</math> contains an arithmetic progression of length k. | |||
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.) | |||
This implies [[Roth's theorem]]. The result was [[Szemerédi's original proof of Szemerédi's theorem|first proven by Szemerédi in 1975]]. | This 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]. | ||
Revision as of 16:16, 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.)
This 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.
