PROVED
This has been solved in the affirmative.
- $1000
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)$.
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.
View the LaTeX source
This page was last edited 27 November 2025.
Additional thanks to: Zachary Chase
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #139, https://www.erdosproblems.com/139, accessed 2026-01-16
