Problem Statement
Let $G_k(N)$ be such that any set of $N$ integers contains a subset of size at least $G_k(N)$ which does not contain a $k$-term arithmetic progression. Determine the size of $G_k(N)$. How does it relate to $R_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a $k$-term arithmetic progression? Is it true that\[\lim_{N\to \infty}\frac{R_3(N)}{G_3(N)}=1?\]
Categories:
Additive Combinatorics Arithmetic Progressions
Progress
First asked and investigated by Riddell [Ri69]. It is trivial that $G_k(N)\leq R_k(N)$, and it is possible that $G_k(N) <R_k(N)$ (for example $G_3(5)=3$ and $R_3(5)=4$, and $G_3(14)\leq 7$ and $R_3(14)=8$).Komlós, Sulyok, and Szemerédi [KSS75] have shown that $R_k(N) \ll_k G_k(N)$.
Source: erdosproblems.com/201 | Last verified: January 14, 2026