The Erdős discrepancy problem

The Erdős discrepancy problem, Discrete Analysis 2016:1, 27 pp.

One of Erdős’s most famous problems was his discrepancy problem, which is the following deceptively simple question. Let $\epsilon_1,\epsilon_2,\dots$ be a sequence of 1s and -1s and let $m$ be a positive integer. Must there exist positive integers $n$ and $d$ such that $|\sum_{i=1}^n\epsilon_{id}|\geq m$? This would tell us that when we restrict to the arithmetic progression $\{d,2d,\dots,nd\}$ the number of 1s and the number of -1s differ by at least $m$ – hence the word “discrepancy”.

A simple observation is that if the sequence $(\epsilon_i)$ is completely multiplicative (that is, $\epsilon_{ij}=\epsilon_i\epsilon_j$ for every $i$ and $j$), then the question reduces to asking whether the partial sums $\sum_{i=1}^n\epsilon_i$ must be unbounded. Even this special case is surprisingly hard.

Very roughly, Tao’s strategy can be described as follows. First, he reduces the general problem to one that is closely related to the special case just described. Next, he proves, using a recent result of his that he calls a logarithmically averaged nonasymptotic Elliott conjecture, that any multiplicative counterexample to the Erdõs discrepancy problem would have to be of a very special form that would make it similar to a Dirichlet character. And finally, he proves that multiplicative functions that resemble Dirichlet characters must give rise to at least logarithmic growth on average in the partial sums.

The second step is related to a recent breakthrough of Matomäki and Radziwiłł, who established results about correlations of successive values of certain multiplicative functions. Note that if one can show that there is very little correlation between nearby values of such functions, then one has shown that they are not counterexamples to the Erdõs discrepancy problem, since one cannot keep the partial sums bounded without significant local correlation. Before the work of Matomäki and Radziwiłł it was thought that saying anything about such correlations was completely out of reach, but with their work and subsequent extensions by Tao the picture has changed dramatically, to the point where it is possible to contemplate an argument such as the one in this paper.