The Erdos discrepancy problem

Abstract

We show that for any sequence $f:\mathbf{N}\to \{-1,+1\}$ taking values in $\{-1,+1\}$, the discrepancy $$\underset{n,d\in \mathbf{N}}{\sup }\left|\sum _{j=1}^{n}f(jd)\right|$$ of $f$ is infinite. This answers a question of Erdős. In fact the argument also applies to sequences $f$ taking values in the unit sphere of a real or complex Hilbert space. The argument uses three ingredients. The first is a Fourier-analytic reduction, obtained as part of the Polymath5 project on this problem, which reduces the problem to the case when $f$ is replaced by a (stochastic) completely multiplicative function $\mathbf{g}$. The second is a logarithmically averaged version of the Elliott conjecture, established recently by the author, which effectively reduces to the case when $\mathbf{g}$ usually pretends to be a modulated Dirichlet character. The final ingredient is (an extension of) a further argument obtained by the Polymath5 project which shows unbounded discrepancy in this case.

29 pages, no figures. Formatted using the Discrete Analysis style file

References in corpus (2)

• An averaged form of Chowla's conjecture
• The logarithmically averaged Chowla and Elliott conjectures for two-point correlations

Cited by in corpus (1)

• The logarithmically averaged Chowla and Elliott conjectures for two-point correlations