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 \cite{BlSi20}. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka \cite{KeMe23}. Green and Tao \cite{GrTa17} proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers \cite{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 \cite{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\H{o}s \cite{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 \cite{GrTa08} (see [219]).

In \cite{Er81} Erd\H{o}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 \cite{KeMe23}) - see [140].

See also [139] and [142].

This is discussed in problem A5 of Guy's collection \cite{Gu04}.


References


[BlSi20] Bloom, T.F. and Sisask, O., Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions. arXiv:2007.03528 (2020).

[Er81] Erd\H{o}s, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42.

[Er83c] Erd\H{o}s, Paul, Combinatorial problems in geometry. Math. Chronicle (1983), 35-54.

[Go01] Gowers, W. T., A new proof of Szemer\'{e}di's theorem. Geom. Funct. Anal. (2001), 465-588.

[GrTa08] Green, Ben and Tao, Terence, The primes contain arbitrarily long arithmetic progressions. Ann. of Math. (2) (2008), 481-547.

[GrTa17] Green, Ben and Tao, Terence, New bounds for Szemer\'{e}di's theorem, III: a polylogarithmic bound for $r_4(N)$. Mathematika (2017), 944-1040.

[Gu04] Guy, Richard K., Unsolved problems in number theory. (2004), xviii+437.

[KeMe23] Kelley, Z. and Meka, R., Strong Bounds for 3-Progressions. arXiv:2302.05537 (2023).

[LSS24] Leng, J., Sah, A. and Sawhney, M., Improved bounds for Szemer\'{e}di's theorem. arXiv:2402.17995 (2024).