Sumset and Inverse Sumset Inequalities for Differential Entropy and Mutual Information

Abstract

The sumset and inverse sumset theories of Freiman, Plünnecke and Ruzsa, give bounds connecting the cardinality of the sumset $A+B=\{a+b;a\in A,b\in B\}$ of two discrete sets $A,B$, to the cardinalities (or the finer structure) of the original sets $A,B$. For example, the sum-difference bound of Ruzsa states that, $|A+B||A||B|\le |A-B{|}^3$, where the difference set $A-B=\{a-b;a\in A,b\in B\}$. Interpreting the differential entropy $h(X)$ of a continuous random variable $X$ as (the logarithm of) the size of the effective support of $X$, the main contribution of this paper is a series of natural information-theoretic analogs for these results. For example, the Ruzsa sum-difference bound becomes the new inequality, $h(X+Y)+h(X)+h(Y)\le 3h(X-Y)$, for any pair of independent continuous random variables $X$ and $Y$. Our results include differential-entropy versions of Ruzsa's triangle inequality, the Plünnecke-Ruzsa inequality, and the Balog-Szemerédi-Gowers lemma. Also we give a differential entropy version of the Freiman-Green-Ruzsa inverse-sumset theorem, which can be seen as a quantitative converse to the entropy power inequality. Versions of most of these results for the discrete entropy $H(X)$ were recently proved by Tao, relying heavily on a strong, functional form of the submodularity property of $H(X)$. Since differential entropy is {\em not} functionally submodular, in the continuous case many of the corresponding discrete proofs fail, in many cases requiring substantially new proof strategies. We find that the basic property that naturally replaces the discrete functional submodularity, is the data processing property of mutual information.

23 pages

Cited by in corpus (24)

• Absolute continuity of Bernoulli convolutions for algebraic parameters
• Entropy bounds on abelian groups and the Ruzsa divergence
• On the dimension of Bernoulli convolutions
• Combinatorial Entropy Power Inequalities: A Preliminary Study of the Stam region
• Entropy Inequalities for Sums in Prime Cyclic Groups
• Majorization and Rényi Entropy Inequalities via Sperner Theory
• Degrees of freedom in vector interference channels
• Sharp moment-entropy inequalities and capacity bounds for log-concave distributions
• Two remarks on generalized entropy power inequalities
• Stability of the Shannon-Stam inequality via the Föllmer process
• Quantum Ruzsa Divergence to Quantify Magic
• Entropies of weighted sums in cyclic groups and an application to polar codes
• Conditional Rényi entropy and the relationships between Rényi capacities
• The Entropy Power Inequality and Mrs. Gerber's Lemma for Abelian Groups of Order 2^n
• The Capacity of 3 User Linear Computation Broadcast
• On the Generic Capacity of $K$-User Symmetric Linear Computation Broadcast
• Entropy of Bernoulli convolutions and uniform exponential growth for linear groups
• Information Inequalities via Submodularity and a Problem in Extremal Graph Theory
• Entropic additive energy and entropy inequalities for sums and products
• Sumset estimates in convex geometry
• Countably Infinite Multilevel Source Polarization for Non-Stationary Erasure Distributions
• Typical sumsets of linear codes
• Canonical Conditions for K/2 Degrees of Freedom
• A new entropy power inequality for integer-valued random variables