Problem Statement
Let $1\leq k<\ell$ be integers and define $F_k(N,\ell)$ to be minimal such that every set $A\subset \mathbb{N}$ of size $N$ which contains at least $F_k(N,\ell)$ many $k$-term arithmetic progressions must contain an $\ell$-term arithmetic progression. Find good upper bounds for $F_k(N,\ell)$. Is it true that\[F_3(N,4)=o(N^2)?\]Is it true that for every $\ell>3$\[\lim_{N\to \infty}\frac{\log F_3(N,\ell)}{\log N}=2?\]
Categories:
Additive Combinatorics Arithmetic Progressions
Progress
Erdős remarks the upper bound $o(N^2)$ is certainly false for $\ell >\epsilon \log N$. The answer is yes: Fox and Pohoata [FoPo20] have shown that, for all fixed $1\leq k<\ell$,\[F_k(N,\ell)=N^{2-o(1)}\]and in fact\[F_{k}(N,\ell) \leq \frac{N^2}{(\log\log N)^{C_\ell}}\]where $C_\ell>0$ is some constant. In fact, they show that, if $r_\ell(N)$ is the size of the largest subset of $\{1,\ldots,N\}$ without an $\ell$-term arithmetic progression then there exists some absolute constant $c>0$ such that\[\left(c \frac{r_\ell(N)}{N}\right)^{2(k-1)}N^2 < F_k(N,\ell) <\left(\frac{r_\ell(N)}{N}\right)^{O(1)}N^2.\]Any improved bounds for Szemerédi's theorem (see [139]) therefore yield improved bounds for $F_k(N,\ell)$. In particular, the bounds of Leng, Sah, and Sawhney [LSS24] imply\[F_k(N,\ell) \leq \frac{N^2}{\exp((\log\log N)^{c_\ell})}\]for some constant $c_\ell>0$.Source: erdosproblems.com/179 | Last verified: January 14, 2026