Problem 177

Erdős Problem #177: declared status 'open'. Formalized: no. Find the smallest $h(d)$ such that the following holds. There exists a function $f:\mathbb{N}\to\{-1,1\}$ such that, for every $d\geq 1$,$$\max_{P_d}\left\lvert \sum_{n\in P_d}f(n)\right\rvert\leq h(d),$$where $P_d$ ranges over all finite arithmetic progressions with common difference $d$. Current best: Roth's famous discrepancy lower bound [Ro64] implies that $h(d)\gg d^{1/2}$. Prize: no. Tags: arithmetic progressions, discrepancy.