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