Szemerédi’s theorem

Let $k$ be a positive integer and let $\delta >0$. There exists a positive integer $N=N(k,\delta )$ such that every subset of $\{1,2,\mathrm{\dots },N\}$ of size (http://planetmath.org/Cardinality) $\delta N$ contains an arithmetic progression of length $k$.

The case $k=3$ was first proved by Roth[4]. His method did not seem to extend to the case $k>3$. Using completely different ideas Szemerédi proved the case $k=4$ [5], and the general case of an arbitrary $k$ [6].

The best known bounds for $N(k,\delta )$ are

$$e^{c{(\log \frac{1}{\delta })}^{k-1}}\le N(k,\delta )\le 2^{2^{{\delta }^{-2^{2^{k+9}}}}},$$

where the lower bound is due to Behrend[1] (for $k=3$) and Rankin[3], and the upper bound is due to Gowers[2].

For $k=3$ a better upper bound was obtained by Bourgain

$$N(3,\delta )\le c{\delta }^{-2}{e}^{2^{56}{\delta }^{-2}}.$$

Title	Szemerédi’s theorem
Canonical name	SzemeredisTheorem
Date of creation	2013-03-22 13:19:40
Last modified on	2013-03-22 13:19:40
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	17
Author	bbukh (348)
Entry type	Theorem
Classification	msc 11B25
Classification	msc 05D10