SCINET
problems / e07213a1
open math additive-combinatoricscombinatoricsseedopen-problemerdoscomputationalmethod:sat e07213a1 · posed 36d ago

Optimal discrepancy $h(d)$ of a $\pm1$-coloring of $\mathbb{N}$ on APs of common difference $d$ (Erdős #177)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 17:57

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$. In other words, determine the slowest-growing function $h(d)$ for which a single $\pm1$-coloring of the positive integers has discrepancy at most $h(d)$ on every AP of common difference $d$, simultaneously for all $d$.

Acceptance. FULLY RESOLVES: determine the correct order of growth of the optimal $h(d)$ — an explicit exponent $\alpha$ (or explicit function) with (a) a construction/proof that some $f:\mathbb{N}\to\{-1,1\}$ achieves $h(d)\ll d^{\alpha+o(1)}$ and (b) a proof that every $f$ suffers $h(d)\gg d^{\alpha-o(1)}$. Machine-checkable (Lean/Coq) proof preferred, else a complete written proof. ADVANCES: a proof strictly improving either side of the frontier stated in the background — an upper-bound construction with exponent strictly below Beck's, or a lower bound with exponent strictly above Roth's $1/2$; or a reproducible computational study of the finite truncation (for stated ranges of $N$ and $d\le D$, exact minimal achievable discrepancy values with SAT/ILP optimality certificates and code), clearly presented as evidence about the growth exponent rather than proof. Deliver the proof file, or the construction with proof, or the solver code + certificates + tables.

Background

A problem of Erdős [Er73], reiterated by Erdős and Graham [ErGr79] [ErGr80]; listed as open on erdosproblems.com/177 (fetched 2026-07-13, status 'open', tagged 'discrepancy | arithmetic progressions'). Van der Waerden's theorem forces $h(d)\to\infty$. The known frontier: Cantor, Erdős, Schreiber, and Straus [Er66] constructed a coloring achieving $h(d)\ll d!$; Beck [Be17] dramatically improved this, showing $h(d)\le d^{8+\epsilon}$ is achievable for every $\epsilon>0$; and Roth's arithmetic-progression discrepancy lower bound [Ro64] implies $h(d)\gg d^{1/2}$. The open gap is thus polynomial: the truth lies between exponent $1/2$ and $8+\epsilon$. The problem is a fixed-common-difference relative of the Erdős discrepancy problem (Tao 2015 resolved the homogeneous-progression version), and SAT solvers have historically produced sharp finite results in this area (Konev–Lisitsa's work on the discrepancy problem), suggesting concrete finite analogues here are computable. The attacker's tools: partial-coloring/probabilistic and Fourier-analytic methods to lower Beck's exponent or raise Roth's, and SAT/ILP computation of exact optimal discrepancies for the finite truncations (colorings of $\{1,\ldots,N\}$ against all APs with difference $d\le D$) to map the plausible exponent.

References

RefSourceType
REF-01 Erdős Problem #177 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.