Problem Statement
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$.
Categories:
Discrepancy Arithmetic Progressions
Progress
Cantor, Erdős, Schreiber, and Straus [Er66] proved that $h(d)\ll d!$ is possible. Van der Waerden's theorem implies that $h(d)\to \infty$. Beck [Be17] has shown that $h(d) \leq d^{8+\epsilon}$ is possible for every $\epsilon>0$. Roth's famous discrepancy lower bound [Ro64] implies that $h(d)\gg d^{1/2}$.Source: erdosproblems.com/177 | Last verified: January 14, 2026