Sumset and inverse sumset theory for Shannon entropy

Terence Tao

2012 · 78 citations · 12 references

Concepts

Abstract

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) ≥

References

12