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

8:13 pm

new question: Prime numbers out of sequence by Rubens373

Oct 7

new question: Lorenz system by David Bankom

Oct 19

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag

new question: Prime numbers out of sequence by Rubens373

Oct 7

new question: Lorenz system by David Bankom

Oct 19

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag