Sumset and Inverse Sumset Theory for Shannon Entropy

Let G = (G, +) be an additive group. The sumset theory of Pliinnecke and Ruzsa gives several relations between the size of sumsets A + B of finite sets A, B, and related objects such as iterated sumsets kA and difference sets A - B, while the inverse sumset theory of Freiman, Ruzsa, and others characterizes those finite sets A for which A + A is small. In this paper we establish analogous results in which the finite set A subset of G is replaced by a discrete random variable X taking values in G. and the cardinality vertical bar A vertical bar is replaced by the Shannon entropy H(X). In particular, we classify those random variables X which have small doubling in the sense that H(X(1) + X(2)) = H(X) + O(1) when X(1), X(2) are independent copies of X, by showing that they factorize as X = U + Z, where U is uniformly distributed on a coset progression of bounded rank, and H(Z) = O(1). When G is torsion-free, we also establish the sharp lower bound H(X + X) >= H(X) + 1/2 log 2 - o(1), where o(1) goes to zero as H(X) -> infinity.