Entropy and set cardinality inequalities for partition-determined functions

DOI10.1002/RSA.20385zbMATH Open1244.05024arXiv0901.0055OpenAlexW3106140828MaRDI QIDQ2904591FDOQ2904591

Prasad Tetali, Mokshay Madiman, Adam W. Marcus

Publication date: 14 August 2012

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0901.0055

zbMATH Keywords

entropy inequalitiesadditive combinatoricssumsetscardinality inequalities

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Partitions of sets (05A18) Additive bases, including sumsets (11B13)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Random walks on discrete groups: Boundary and entropy
• Some intersection theorems for ordered sets and graphs
• Hypergraphs, Entropy, and Inequalities
• Compressions and isoperimetric inequalities
• Generalized Entropy Power Inequalities and Monotonicity Properties of Information
• Nonnegative entropy measures of multivariate symmetric correlations
• Reverse Brunn-Minkowski and reverse entropy power inequalities for convex measures
• Sumset and Inverse Sumset Theory for Shannon Entropy
• Dimensional behaviour of entropy and information
• Polymatroidal dependence structure of a set of random variables
• Information Inequalities for Joint Distributions, With Interpretations and Applications
• A superadditivity and submultiplicativity property for cardinalities of sumsets
• Two Constructions on Limits of Entropy Functions
• Sumsets and entropy

Cited In (12)

• 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
• Deletion correcting codes meet the Littlewood-Offord problem
• Entropy versions of additive inequalities
• Majorization and Rényi entropy inequalities via Sperner theory
• Notes on use of generalized entropies in counting
• Entropy Inequalities for Sums in Prime Cyclic Groups
• Volumes of subset Minkowski sums and the Lyusternik region
• Log-concavity, ultra-log-concavity, and a maximum entropy property of discrete compound Poisson measures
• Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

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)