Roth's theorem on arithmetic progressions

Remarks

Let $r_3(N)$ be the largest size of a subset of $\set{1, \dots, N}$ with no three-term arithmetic progression. The theorem is equivalent to $r_3(N) / N \to 0$ as $N \to \infty$. Roth's proof uses Fourier analysis and a density increment. A set without three-term progressions has a large Fourier coefficient, so it is denser on some long sub-progression. This step cannot repeat forever, because the density cannot exceed $1$. Another proof goes through the triangle removal lemma. Behrend constructed sets showing $r_3(N) \ge N \exp(-c\sqrt{\log N})$ for a constant $c > 0$, so $r_3(N)$ is not bounded by $N^{1 - \varepsilon}$ for any $\varepsilon > 0$. Kelley and Meka proved in 2023 an upper bound of the form $r_3(N) \le N \exp(-c (\log N)^{\beta})$ with constants $c, \beta > 0$. The analogue in $\F_3^n$ is the cap set problem.

Going deeper

For a student

Roth's theorem is the case $k = 3$ of Szemerédi's theorem, and it was proved first. Its Fourier-analytic density-increment argument is a model for many proofs in additive combinatorics. The gap between Behrend's lower bound and the best upper bounds for $r_3(N)$ is still being studied.