The Entropic Sum-Product Phenomenon

Abstract

Let $X,X'$ be independent and identically distributed discrete real-valued random variables of finite Shannon entropy, and write $H(X)$ for the Shannon entropy of $X$. We prove that \[ \max\{H(X+X'),\,H(XX')\} \ge \frac87 H(X)-O(\log H(X)). \] This is the entropic analog of the celebrated sum-product phenomenon, and answers a question of Goh, which simply asked for a coefficient strictly larger than 1. An example by the author, Gavalakis, and Kontoyiannis showed the coefficient cannot exceed $\frac43$. Previous work by Gavalakis, Goh, and Kontoyiannis was able to prove a result of a weaker form, which could not translate to a coefficient strictly larger than 1 because of examples where the min-entropy is significantly smaller than the Shannon entropy. By splitting the distribution of $X$ into uniform pieces, which costs $O(\log H(X))$ entropy, we obviate this issue, establishing a coefficient of $\frac{10}{9}$. We augment this to $\frac87$ by adapting the work of Solymosi, which established the combinatorial sum-product phenomenon with coefficient $\frac43$ by bounding the multiplicative energy, to the entropy setting, again via a uniformization technique.

40 pages