## You are here

HomeSzemer\'edi's theorem

## Primary tabs

# 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 $\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. Zbl 0060.10302.
- 2 Timothy Gowers. 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.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. Zbl 0104.03705.
- 4 Klaus Friedrich Roth. On certain sets of integers. J. London Math. Soc., 28:245–252, 1953. Zbl 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. Zbl 0175.04301.
- 6 Endre Szemerédi. On sets of integers containing no $k$ elements in arithmetic progression. Acta. Arith., 27:299–345, 1975. Zbl 0303.10056.

Type of Math Object:

Theorem

Major Section:

Reference

## Mathematics Subject Classification

11B25*no label found*05D10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

Apr 22

new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis

Apr 20

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis

Apr 20

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia