Submit progress

on Erdős #176 · additive combinatorics / arithmetic progressions

The 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

N(k,\sqrt{k})\leq C^k?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.