Entropy and set cardinality inequalities for partition-determined functions

Abstract

A new notion of partition-determined functions is introduced, and several basic inequalities are developed for the entropy of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Here a compound set means a set obtained by varying each argument of a function of several variables over a set associated with that argument, where all the sets are subsets of an appropriate algebraic structure so that the function is well defined. On the one hand, the entropy inequalities developed for partition-determined functions imply entropic analogues of general inequalities of Plünnecke-Ruzsa type. On the other hand, the cardinality inequalities developed for compound sets imply several inequalities for sumsets, including for instance a generalization of inequalities proved by Gyarmati, Matolcsi and Ruzsa (2010). We also provide partial progress towards a conjecture of Ruzsa (2007) for sumsets in nonabelian groups. All proofs are elementary and rely on properly developing certain information-theoretic inequalities.

26 pages. v2: Revised version incorporating referee feedback plus inclusion of some additional corollaries and discussion. v3: Final version with minor corrections. To appear in Random Structures and Algorithms

References in corpus (5)

• Generalized Entropy Power Inequalities and Monotonicity Properties of Information
• Information Inequalities for Joint Distributions, with Interpretations and Applications
• Sumset and inverse sumset theorems for Shannon entropy
• Reverse Brunn-Minkowski and reverse entropy power inequalities for convex measures
• Dimensional behaviour of entropy and information

Cited by in corpus (17)

• On self-similar sets with overlaps and inverse theorems for entropy
• Cryptanalysis of a Chaotic Image Encryption Algorithm Based on Information Entropy
• Forward and Reverse Entropy Power Inequalities in Convex Geometry
• Sumset and Inverse Sumset Inequalities for Differential Entropy and Mutual Information
• Entropy bounds on abelian groups and the Ruzsa divergence
• 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
• Conditional Rényi entropy and the relationships between Rényi capacities
• Volumes of subset Minkowski sums and the Lyusternik region
• Entropies of weighted sums in cyclic groups and an application to polar codes
• Quantum Ruzsa Divergence to Quantify Magic
• Self similar sets, entropy and additive combinatorics
• Information Inequalities via Submodularity and a Problem in Extremal Graph Theory
• Notes on use of generalized entropies in counting
• Computing from projections of random points: a dense hierarchy of subideals of the $K$-trivial degrees
• Countably Infinite Multilevel Source Polarization for Non-Stationary Erasure Distributions