Szemerédi's theorem - Revision history

Gowers at 00:17, 27 February 2009

2009-02-27T00:17:22Z

← Older revision		Revision as of 17:17, 26 February 2009
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.)

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

Gowers at 00:16, 27 February 2009

2009-02-27T00:16:47Z

← Older revision		Revision as of 17:16, 26 February 2009
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].

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

2009-02-14T17:17:33Z

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

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