Problem 178

Let $A_1,A_2,\ldots$ be an infinite collection of infinite sets of integers, say $A_i=\{a_{i1}<a_{i2}<\cdots\}$ . Does there exist some $f:\mathbb{N}\to\{-1,1\}$ such that

\max_{m, 1\leq i\leq d} \left\lvert \sum_{1\leq j\leq m} f(a_{ij})\right\rvert \ll_d 1

for all $d\geq 1$ ?

Source: erdosproblems.com/178

Discrepancy

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN): Beck [Be81] answered yes, and [Be17] made the bound quantitative, $\ll d^{4+\epsilon}$ for every $\epsilon>0$ ; a Lean 4 proof of a theorem erdos_178, whose statement formal-conjectures adopted in its answer form on 26 June 2026, following Beck's argument, was posted to the site's thread on 21 April 2026. The accepted claim is Beck 1981. A claim of 19 September 2026, Korsky 2026, would reprove the statement with the explicit bound $\ll d^{3/2+\sqrt2}$ in place of Beck's exponent and is unreviewed.

Problem 178

Status

Proof claims

Discussion