Erdős Problem #176

The problem

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?$$

Statement quoted from erdosproblems.com/176, maintained by Thomas Bloom. Original source: [Er65b][Er73][Er74b][Er75b][ErGr79][Er80,p.91][ErGr80,p.15]. Current status there: open.

AI contributions

As recorded in Terence Tao's wiki AI contributions to Erdős problems (data as of 30 Jun 2026). 🟢 full, 🟡 partial, ⚪ unverified, 🔴 incorrect.

Caveats

The wiki's classifications are provisional and are not a benchmark. Many Erdős problems have never had a thorough literature review, so a result that looks new may later turn out to be known; some problems were also stated ambiguously or incorrectly. See the problem page for the full discussion.

∎