A quantitative ergodic theory proof of Szemerédi's theorem

Terence Tao

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

A famous theorem of Szemerédi asserts that given any density $0 < \delta \leq 1$ and any integer $k \geq 3$, any set of integers with density $\delta$ will contain infinitely many proper arithmetic progressions of length $k$. For general $k$ there are essentially four known proofs of this fact; Szemerédi's original combinatorial proof using the Szemerédi regularity lemma and van der Waerden's theorem, Furstenberg's proof using ergodic theory, Gowers' proof using Fourier analysis and the inverse theory of additive combinatorics, and the more recent proofs of Gowers and Rödl-Skokan using a hypergraph regularity lemma. Of these four, the ergodic theory proof is arguably the shortest, but also the least elementary, requiring passage (via the Furstenberg correspondence principle) to an infinitary measure preserving system, and then decomposing a general ergodic system relative to a tower of compact extensions. Here we present a quantitative, self-contained version of this ergodic theory proof, and which is "elementary" in the sense that it does not require the axiom of choice, the use of infinite sets or measures, or the use of the Fourier transform or inverse theorems from additive combinatorics. It also gives explicit (but extremely poor) quantitative bounds.

Détail

DOI : 10.37236/1125

Classification : 11B25, 05C75, 37B20
Mots-clés : van der Waerden theorem, Szemerédi theorem, Furstenberg ergodic proof, Gowers proof, Fourier analysis, ergodig theory, inverse theory, hypergraph regularity lemma, van der Corput lemma, generalized von Neumann theorem, Gowers norms, Gowers uniform functions, uniformity norms, almost periodic functions