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

Step 6 of 9: How Theorem 1.10 is proved: the entropy decrement argument

In plain words

The logarithmically averaged Elliott conjecture is itself a hard theorem, proved by Tao in a separate 2015 paper using a genuinely new technique borrowed from information theory rather than classical analytic number theory. The rough idea: consider the "uncertainty" (Shannon entropy) in the values of a multiplicative function across many different residue classes and scales at once.

If the correlation Tao wants to bound were NOT small, it would force these many different pieces of the function to be unexpectedly informative about each other — in effect, secretly dependent rather than independent. But entropy is a quantity that can only decrease so many times before hitting its floor of zero; Tao shows that this forced dependence would have to make entropy decrease again and again across a long sequence of scales, which is simply not allowed. The contradiction shows the correlation must have been small after all, except in the one case (pretentiousness) that the argument cannot fully suppress.

H(X_1,\ldots,X_k) \text{ cannot decrease across scales indefinitely} \implies \text{approximate independence forces the correlation bound}

Detailed analysis

Tao's companion paper "The logarithmically averaged Chowla and Elliott conjectures for two-point correlations" (arXiv:1509.05422, Forum of Mathematics, Pi, 2016) proves Theorem 1.10 using what he calls the entropy decrement argument. Rather than the classical circle method or sieve-theoretic manipulations that face the parity obstruction, the argument works with the Shannon entropy $H(X)$ of discrete random variables built from the values of the multiplicative function $g_1$ restricted to short intervals around many different, widely-separated scales.

The technical core: if $g_1$ fails to correlate appropriately, one can show (using multiplicativity at small primes and the Matomäki–Radziwiłł theorem on multiplicative functions in short intervals) that certain of these entropy-measuring random variables would need to become significantly more informative about (i.e. less independent of) one another than generic random variables of their type. Since Shannon entropy is bounded below by $0$ and can only decrease a limited, controllable number of times as one passes through a long chain of scales (each decrease being quantitatively bounded), demanding this informativeness at every one of many scales produces an outright contradiction if $g_1$ is genuinely non-pretentious.

This argument, while it yields no explicit rate of convergence and is famously described by Tao himself as "unreasonably effective" for a problem that had resisted classical methods, was quickly recognised as an important new tool in analytic number theory; it directly enabled not only this resolution of the Erdős discrepancy problem but subsequent work by Tao and others on the logarithmically averaged Chowla and Sarnak conjectures for higher-order correlations.

Terms in this step

Shannon entropy: A measure, from information theory, of how much uncertainty or "surprise" a random variable carries; entropy is always non-negative and decreases when a variable becomes more predictable from other information.

Knowledge used in this step

Szemerédi's theorem