# 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,\ldots,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}}\leq N(k,\delta)\leq 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)\leq c\delta^{-2}e^{2^{56}\delta^{-2}}.$

## References

• 1 Felix A. Behrend. On the sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 23:331–332, 1946. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0060.10302Zbl 0060.10302.
• 2 A new proof of Szemerédi’s theorem. Geom. Funct. Anal., 11(3):465–588, 2001. Preprint available at http://www.dpmms.cam.ac.uk/ wtg10/papers.htmlhttp://www.dpmms.cam.ac.uk/ wtg10/papers.html.
• 3 Robert A. Rankin. Sets of integers containing not more than a given number of terms in arithmetical progression. Proc. Roy. Soc. Edinburgh Sect. A, 65:332–344, 1962. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0104.03705Zbl 0104.03705.
• 4 Klaus Friedrich Roth. On certain sets of integers. J. London Math. Soc., 28:245–252, 1953. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0050.04002Zbl 0050.04002.
• 5 Endre Szemerédi. On sets of integers containing no four elements in arithmetic progression. Acta Math. Acad. Sci. Hung., 20:89–104, 1969. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0175.04301Zbl 0175.04301.
• 6 Endre Szemerédi. On sets of integers containing no $k$ elements in arithmetic progression. Acta. Arith., 27:299–345, 1975. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0303.10056Zbl 0303.10056.
Title Szemerédi’s theorem SzemeredisTheorem 2013-03-22 13:19:40 2013-03-22 13:19:40 bbukh (348) bbukh (348) 17 bbukh (348) Theorem msc 11B25 msc 05D10