Entropy and set cardinality inequalities for partition-determined functions

Entropy and set cardinality inequalities forpartition-determined functions y zMokshay Madiman Adam W. Marcus Prasad TetaliAbstractA new notion of partition-determined functions is introduced, and several basic newinequalities are presented for the entropy of such functions of independent random vari-ables, as well as for cardinalities of compound sets obtained using these functions. Herea compound set means a set obtained by varying each argument of a function of severalvariables over a set associated with that argument, where all the sets are subsets of anappropriate algebraic structure so that the function is well de ned. The compound setinequalities imply, in turn, several inequalities for sumsets, providing for instance partialprogress towards a conjecture of Ruzsa (2007) for sumsets in nonabelian groups.Keywords: Sumsets, additive combinatorics, entropy inequalities, cardinality inequalities.1 IntroductionIt is well known in certain circles that there appears to exist an informal parallelism betweenentropy inequalities on the one hand, and set cardinality inequalities on the other. In thispaper, we clarify some aspects of this parallelism, while presenting new inequalities for bothentropy and set cardinalities.A natural connection between entropy and set cardinalities arises from the fact that theentropy of the uniform distribution on a nite set of size m is just logm, and this is themaximum entropy of any distribution supported on the same set. ...