# Szemerédi's theorem

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Finite version. For every $\delta\gt0$ and every positive integer k there exists n such that every subset $A\subset [n]$ of size at least $\delta n$ contains an arithmetic progression of length k.
It is known that for fixed $\delta$ and n sufficiently large one can take k to be $\log\log\log\log\log\log n.$ (This is not quite the best known bound but is easier to state.)