Entropy and set cardinality inequalities for partition-determined functions
From MaRDI portal
Publication:2904591
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"unnecke-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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5081149 (Why is no real title available?)
- scientific article; zbMATH DE number 36206 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 5219606 (Why is no real title available?)
- A superadditivity and submultiplicativity property for cardinalities of sumsets
- Compressions and isoperimetric inequalities
- Dimensional behaviour of entropy and information
- Generalized Entropy Power Inequalities and Monotonicity Properties of Information
- Hypergraphs, entropy, and inequalities
- Information Inequalities for Joint Distributions, With Interpretations and Applications
- Nonnegative entropy measures of multivariate symmetric correlations
- Polymatroidal dependence structure of a set of random variables
- Projections of Bodies and Hereditary Properties of Hypergraphs
- Random walks on discrete groups: Boundary and entropy
- Reverse Brunn-Minkowski and reverse entropy power inequalities for convex measures
- Some intersection theorems for ordered sets and graphs
- Sumset and Inverse Sumset Theory for Shannon Entropy
- Sumsets and entropy
- Two Constructions on Limits of Entropy Functions
Cited in
(14)- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- The cardinality of sumsets: different summands
- The convexification effect of Minkowski summation
- Computing from projections of random points
- On self-similar sets with overlaps and inverse theorems for entropy
- Entropy inequalities for sums in prime cyclic groups
- Projections, entropy and sumsets
- Deletion correcting codes meet the Littlewood-Offord problem
- Sumsets and entropy
- Entropy versions of additive inequalities
- Majorization and Rényi entropy inequalities via Sperner theory
- Notes on use of generalized entropies in counting
- Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures
- Volumes of subset Minkowski sums and the Lyusternik region
This page was built for publication: Entropy and set cardinality inequalities for partition-determined functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904591)
