Let $N(k,\ell )$ be the minimal $N$ such that for any $f:\{1,\dots ,N\}\to \{-1,1\}$ there must exist a $k$-term arithmetic progression $P$ such that$$\left|\sum _{n\in P}f(n)\right|\ge \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)\le C^k?$$What about$$N(k,2)\le C^k$$or$$N(k,\sqrt{k})\le C^k?$$