This is essentially asking for good bounds on $r_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a non-trivial $k$-term arithmetic progression. For example, a bound like\[r_k(N) \ll_k \frac{N}{(\log N)(\log\log N)^2}\]would be sufficient.



Even the case $k=3$ is non-trivial, but was proved by Bloom and Sisask [BlSi20]. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka [KeMe23]. Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers [Go01] proved\[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\]where $c_k>0$ is a small constant depending on $k$. The current best bounds for general $k$ are due to Leng, Sah, and Sawhney [LSS24], who show that\[r_k(N) \ll \frac{N}{\exp((\log\log N)^{c_k})}\]for some constant $c_k>0$ depending on $k$.



Curiously, Erdős [Er83c] thought this conjecture was the 'only way to approach' the conjecture that there are arbitrarily long arithmetic progressions of prime numbers, now a theorem due to Green and Tao [GrTa08] (see [219]).

In [Er81] Erdős makes the stronger conjecture that\[r_k(N) \ll_C\frac{N}{(\log N)^C}\]for every $C>0$ (now known for $k=3$ due to Kelley and Meka [KeMe23]) - see [140].

See also [139] and [142].

This is discussed in problem A5 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 28 December 2025.