Worked solution: Tao's proof of the Erdős discrepancy problem via logarithmically averaged correlations (2015)

The display defines the discrepancy of $f:\mathbb{N}\to\{-1,+1\}$: the supremum $\sup_{n,d\in\mathbb{N}}\left|\sum_{j=1}^n f(jd)\right|$ measures the worst imbalance of $f$ along homogeneous arithmetic progressions $d,2d,\ldots,nd$. Erdős conjectured in the 1930s that this supremum is infinite for every $f$ — that for every bound $C$ there exist $n,d$ with $\left|\sum_{j=1}^n f(jd)\right| > C$. For orientation, compare Roth's 1964 theorem, which forces discrepancy $\gg\sqrt{N}$ but only when all arithmetic progressions (with arbitrary starting point) are allowed; the restriction to progressions through $0$ is exactly where multiplicative structure can intervene, since a completely multiplicative $f$ obeys $\sum_{j=1}^n f(jd) = f(d)\sum_{j=1}^n f(j)$ and the problem collapses onto its own partial sums.

The conjecture survived eighty years and a dedicated polymath experiment. Polymath5 (2010, initiated by Gowers) verified small cases by hand and computer, exhibited a sequence of length $1160$ with discrepancy $2$, and developed the Fourier reduction used in the third step; Konev and Lisitsa's 2014 SAT-solver computation then showed every sequence of length $1161$ already has discrepancy at least $3$, while finding one of length about $13{,}000$ with discrepancy $3$ — so unbounded growth is real but can be arbitrarily slow.

Tao's 2015 proof (arXiv:1509.05363, Discrete Analysis 2016) settles in fact the stronger vector-valued statement for $f:\mathbb{N}\to H$ with $\|f(n)\|_H=1$ in a Hilbert space. The remaining steps follow the paper's architecture: reduction to a stochastic completely multiplicative $\mathbf{g}$ (Section 2), a logarithmically averaged Elliott conjecture (Theorem 1.10, imported from a companion paper), and a generalised Borwein–Choi–Coons argument (Section 4) that eliminates the last surviving case.