Canonical: https://knowlpedia.com/discrete-structures/szemeredi-theorem/

# Szemerédi theorem

Every positive-density subset of the integers contains arithmetic progressions of arbitrary finite length.

If \(E\subseteq\mathbb Z\) has positive [upper Banach density](https://knowlpedia.com/discrete-structures/upper-banach-density/), then for every \(k\geq1\) there exist integers \(a\) and \(r\geq1\) such that
\[
a,a+r,\ldots,a+kr\in E.
\]
In particular, the conclusion holds for a subset of \(\mathbb N\) with positive ordinary upper density. This is **Szemerédi's theorem**.

## Ergodic proof route

Use the [correspondence principle](https://knowlpedia.com/ergodic-theory/furstenberg-correspondence-principle/) to obtain an event of positive probability. [Multiple recurrence](https://knowlpedia.com/ergodic-theory/furstenberg-multiple-recurrence/) gives a positive intersection of its translates at \(0,r,\ldots,kr\). The correspondence inequality forces a nonempty intersection \(E\cap(E-r)\cap\cdots\cap(E-kr)\), and any element of it is the required starting point.

The common difference is positive, so the progression is nonconstant. Positive density is a sufficient hypothesis; many zero-density sets also contain long progressions.

## References

1. Asgar Jamneshan and Henrik Kreidler, [*Ergodic Structure Theory and Applications*](https://ajamnesh.github.io/pdf/ISem28_notes.pdf), ISEM 28 lecture notes. Theorem 1.1.8 and Lecture 10.
