Problem Statement
Let $N(k,\ell)$ be the minimal $N$ such that for any $f:\{1,\ldots,N\}\to\{-1,1\}$ there must exist a $k$-term arithmetic progression $P$ such that\[ \left\lvert \sum_{n\in P}f(n)\right\rvert\geq \ell.\]Find good upper bounds for $N(k,\ell)$. Is it true that for any $c>0$ there exists some $C>1$ such that\[N(k,ck)\leq C^k?\]What about\[N(k,2)\leq C^k\]or\[N(k,\sqrt{k})\leq C^k?\]
Categories:
Additive Combinatorics Arithmetic Progressions Discrepancy
Progress
When $\ell=k$ this is the van der Waerden number $W(k)$ (see [138]). Spencer [Sp73] has proved that if $k=2^tm$ with $m$ odd then\[N(k,1)=2^t(k-1)+1.\]Erdős and Graham write that 'no decent bound' is known even for $N(k,2)$.Erdős [Er63d] proved that, for every $c>0$,\[N(k,ck)> (1+\alpha_c)^k\]where $\alpha_c\to 0$ as $c\to 0$ and $\alpha_c\to \sqrt{2}-1$ as $c\to 1$.
Source: erdosproblems.com/176 | Last verified: January 14, 2026