Problem Statement
Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(N)$.
Categories:
Additive Combinatorics Arithmetic Progressions
Progress
A conjecture of Erdős and Turán. Proved by Szemerédi [Sz75]. The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$ (with further slight improvements in [BlSi23]), Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$.In [Er80] Erdős reports that Rothe-Ille was given the problem of estimating $r_k(n)$ by Schur in the 1930s, and so 'perhaps Schur conjectured $r_k(N)=o(N)$ before Turán and myself'.
See also [3].
This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.
Source: erdosproblems.com/139 | Last verified: January 13, 2026