Sumset and Inverse Sumset Theory for Shannon Entropy

Abstract

Let $G = (G,+)$ be an additive group. The sumset theory of Pl\"unnecke 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 characterises those finite sets $A$ for which $A+A$ is small. In this paper we establish analogous results in which the finite set $A \subset G$ is replaced by a discrete random variable $X$ taking values in $G$, and the cardinality $|A|$ is replaced by the Shannon entropy $\mathrm{Ent}(X)$. In particular, we classify the random variable $X$ which have small doubling in the sense that $\mathrm{Ent}(X_1+X_2) = \mathrm{Ent}(X)+O(1)$ when $X_1,X_2$ are independent copies of $X$, by showing that they factorise as $X = U+Z$ where $U$ is uniformly distributed on a coset progression of bounded rank, and $\mathrm{Ent}(Z) = O(1)$. When $G$ is torsion-free, we also establish the sharp lower bound $\mathrm{Ent}(X+X) \geq \mathrm{Ent}(X) + {1/2} \log 2 - o(1)$, where $o(1)$ goes to zero as $\mathrm{Ent}(X) \to \infty$.

Locations

• Combinatorics Probability Computing - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• arXiv (Cornell University) - View - PDF
• DataCite API - View
• Combinatorics Probability Computing - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• arXiv (Cornell University) - View - PDF
• DataCite API - View
• Combinatorics Probability Computing - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• arXiv (Cornell University) - View - PDF
• DataCite API - View