Sumset and Inverse Sumset Theory for Shannon Entropy

Source abstract

Let G = ( G , +) be an additive group. The sumset theory of Plünnecke 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 ⊂ G is replaced by a discrete random variable X taking values in G , and the cardinality | A | 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 $\Ent(X+X) \geq \Ent(X) + \frac{1}{2} \log 2 - o(1)$ , where o (1) goes to zero as H ( X ) → ∞.