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

Step 4 of 9: Setting up the contradiction: assume some random multiplicative function stays bounded

In plain words

To prove the discrepancy is always infinite, Tao argues by contradiction: suppose, for the sake of argument, that some stochastic completely multiplicative function $\mathbf{g}$ manages to keep its expected squared partial sums bounded by a fixed constant $C$ , no matter how far out $n$ you look. The entire remainder of the proof is devoted to showing this assumption is impossible — it inevitably leads to a numerical contradiction.

This is exactly the same proof-by-contradiction shape used in classical arguments like Euclid's proof of infinitely many primes: assume the opposite of what you want, follow the logic wherever it leads, and show it collapses.

\text{Suppose (for contradiction): } \mathbb{E}\left|\sum_{j=1}^n \mathbf{g}(j)\right|^2 \le C \text{ for all } n, \text{ some stochastic completely multiplicative } \mathbf{g}

Detailed analysis

By the previous step's equivalence, it suffices to derive a contradiction from the assumption that there exists a stochastic completely multiplicative function $\mathbf{g}:\mathbb{N}\to S^1$ and a constant $C$ such that $\mathbb{E}\left|\sum_{j=1}^n \mathbf{g}(j)\right|^2 \le C$ for every $n$ . This is the negation of the target statement $\sup_n\mathbb{E}|\cdots|^2=\infty$ , so proving it is impossible finishes the theorem.

A short averaging argument (a form of the van der Corput inequality, Proposition 1.11 in Tao's paper) upgrades this single-scale bound into a bound valid on all dyadic ranges: $\mathbb{E}\frac1H\sum_{H<H'\le 2H}\left|\sum_{m=1}^{H'}\mathbf{g}(n+m)\right|^2 \ll 1$ , uniformly in $n$ . This particular averaged, shifted form of the hypothesis is what makes it possible to bring in correlation estimates for multiplicative functions in the next step, since those estimates are naturally stated in exactly this shifted, averaged language.

The overall shape of the rest of the argument is: this boundedness hypothesis forces $\mathbf{g}$ to have very specific, rigid structure (via the logarithmically averaged Elliott conjecture); that rigid structure is then shown, by an explicit construction, to be incompatible with the boundedness hypothesis itself — a contradiction.

Knowledge used in this step

Szemerédi's theorem