Sumset and inverse sumset theorems for Shannon entropy

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 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)\ge \mathrm{Ent}(X)+1/2\log 2-o(1)$, where $o(1)$ goes to zero as $\mathrm{Ent}(X)\to \infty$.

32 pages, no figures. An error in the quantitative bounds in Lemma 6.1 (pointed out by Lampros Gavalakis and Ioannis Kontoyiannis) has been fixed (at the cost of making these bounds exponentially worse)

Cited by in corpus (29)

• On self-similar sets with overlaps and inverse theorems for entropy
• Entropic Inequalities and Marginal Problems
• Forward and Reverse Entropy Power Inequalities in Convex Geometry
• Sumset and Inverse Sumset Inequalities for Differential Entropy and Mutual Information
• Absolute continuity of Bernoulli convolutions for algebraic parameters
• Entropy bounds on abelian groups and the Ruzsa divergence
• Entropy and set cardinality inequalities for partition-determined functions
• Rogozin's convolution inequality for locally compact groups
• On self-similar sets with overlaps and inverse theorems for entropy in ${\mathbb{R}}^d$
• On the dimension of Bernoulli convolutions
• Entropy Inequalities for Sums in Prime Cyclic Groups
• Majorization and Rényi Entropy Inequalities via Sperner Theory
• Sumsets and entropy revisited
• Bounds on Information Combining With Quantum Side Information
• Entropies of weighted sums in cyclic groups and an application to polar codes
• Quantum Ruzsa Divergence to Quantify Magic
• Conditional Rényi entropy and the relationships between Rényi capacities
• Self similar sets, entropy and additive combinatorics
• Entropic No-Disturbance as a Physical Principle
• The Capacity of 3 User Linear Computation Broadcast
• On the Generic Capacity of $K$-User Symmetric Linear Computation Broadcast
• Information Inequalities via Submodularity and a Problem in Extremal Graph Theory
• Entropy of Bernoulli convolutions and uniform exponential growth for linear groups
• Better Sample -- Random Subset Sum in $2^{0.255n}$ and its Impact on Decoding Random Linear Codes
• Entropic additive energy and entropy inequalities for sums and products
• Equivalence of additive-combinatorial linear inequalities for Shannon entropy and differential entropy
• Additive combinatorics with a view towards computer science and cryptography: An exposition
• Countably Infinite Multilevel Source Polarization for Non-Stationary Erasure Distributions
• Typical sumsets of linear codes