MathLabs

Erdős discrepancy problem

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

For every infinite sequence f(1),f(2),f(3),…f(1), f(2), f(3), \dots taking values in {−1,+1}\{-1, +1\} and every constant C>0C > 0, there exist positive integers nn and dd such that ∣∑j=1nf(jd)∣>C\left|\sum_{j=1}^{n} f(jd)\right| > C; equivalently, sup⁡n,d∈N∣∑j=1nf(jd)∣=∞\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łł.

References

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