Natural SciencesMathematicsInformation TheoryProbability TheorySet TheoryEntropyGroup TheoryDifference SetsDiscrete Random VariablesFreiman's TheoremShannon EntropySmall Doubling Sets
Abstract. Let G = (G,+) be an additive group. The sumset theory of Plünnecke and Ruzsa gives several relations between the size of sumsets A + B of finite sets A, B, and related objects such as iterated sumsets kA and difference sets A − B, while the inverse sumset theory of Freiman, Ruzsa, and others characterises those finite sets A for which A + A is small. In this paper we establish analogous results in which the finite set A ⊂ G is replaced by a discrete random variable X taking values in G, and the cardinality |A | is replaced by the Shannon entropy H(X). In particular, we classify the random variable X which have small doubling in the sense that H(X1+X2) = H(X)+ O(1) when X1, X2 are independent copies of X, by showing that they factorise as X = U + Z where U is uniformly distributed on a coset progression of bounded rank, and H(Z) = O(1). When G is torsion-free, we also establish the sharp lower bound H(X+X) ≥
12
Product set estimates for non-commutative groups
Terence Tao · COMBINATORICA · 2008 · 214 citations
Choice Reviews Online · 2007 · 212 citations
A statistical theorem of set addition
Antal Balog, Endre Szemer�di · COMBINATORICA · 1994 · 175 citations