Erdős discrepancy problem

Solved, 2015Combinatorics and discrete mathematicsArithmetic and number theoryErdős

Statement

For every infinite sequence $f(1), f(2), f(3), \dots$ taking values in $\{-1, +1\}$ and every constant $C > 0$ , there exist positive integers $n$ and $d$ such that $\left|\sum_{j=1}^{n} f(jd)\right| > C$ ; equivalently, $\sup_{n, d \in \mathbb{N}} \left|\sum_{j=1}^{n} f(jd)\right| = \infty$ .

Terence Tao proved the conjecture in September 2015 (published in Discrete Analysis in 2016) by combining the Fourier-analytic reduction from the 2010 Polymath5 collaborative project—which reduced the problem to completely multiplicative functions—with a new logarithmically averaged form of the Elliott conjecture on correlations of multiplicative functions, building on the breakthrough of Kaisa Matomäki and Maksym Radziwiłł.

Posed by, 1932Paul Erdős Solved by, 2015Terence Tao

Tao's proof also establishes the vector-valued generalization conjectured by Tchudaikoff, where each $f(n)$ is a unit vector in a Hilbert space. A central remaining question is to determine the growth rate of the longest sequence of discrepancy at most $C$ as a function of $C$ , and to sharpen the quantitative bounds in the Matomäki–Radziwiłł–Tao theory of multiplicative functions.

References

Terence Tao (2016). The Erdős discrepancy problem · DOI:10.19086/da.609 · arXiv:1509.05363
Boris Konev, Alexei Lisitsa (2014). A SAT attack on the Erdős discrepancy conjecture · arXiv:1402.2184

History of the problem

1932Paul Erdős poses the discrepancy problem for $\pm 1$ sequences on homogeneous arithmetic progressions and later offers a cash prize for its resolution.Paul Erdős
2010Timothy Gowers launches the Polymath5 online collaborative project; participants including Terence Tao show that the problem reduces to bounding averages of stochastic completely multiplicative functions.Terence Tao
2014Boris Konev and Alexei Lisitsa use a SAT solver to settle the $C = 2$ case, proving that a $\pm 1$ sequence of length $1160$ can have discrepancy at most $2$ , whereas every sequence of length $1161$ reaches discrepancy at least $3$ .
2015Terence Tao proves the logarithmically averaged Chowla and Elliott conjectures and completes the full proof of the Erdős discrepancy problem for all $C$ , including vector-valued sequences in a Hilbert space.Terence Tao