Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T15:22:54.341Z Has data issue: false hasContentIssue false
  • English
  • Français

Sumset and Inverse Sumset Theory for Shannon Entropy

Published online by Cambridge University Press:  22 January 2010

TERENCE TAO
TERENCE TAO*
Affiliation:
Department of Mathematics, UCLA, Los Angeles CA 90095-1555, USA (e-mail: tao@math.ucla.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 characterizes 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 those random variables 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 factorize 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 $\Ent(X+X) \geq \Ent(X) + \frac{1}{2} \log 2 - o(1)$, where o(1) goes to zero as H(X) → ∞.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 4 , July 2010 , pp. 603 - 639
Copyright
Copyright © Cambridge University Press 2010

References

[1]Artstein, S., Ball, K., Barthe, F. and Naor, A. (2004) Solution of Shannon's problem on the monotonicity of entropy. J. Amer. Math. Soc. 17 975–982.CrossRefGoogle Scholar
[2]Balister, P. and Bollobás, B. Projections, entropy and sumsets. Combinatorica, to appear.Google Scholar
[3]Balog, A. and Szemerédi, E. (1994) A statistical theorem of set addition. Combinatorica 14 263–268.CrossRefGoogle Scholar
[4]Gowers, T. (1998) A new proof of Szemerédi's theorem for arithmetic progressions of length four. Geom. Funct. Anal. 8 529–551.CrossRefGoogle Scholar
[5]Green, B. and Ruzsa, I. (2007) Freiman's theorem in an arbitrary abelian group. J. London Math. Soc. 75 163–175.CrossRefGoogle Scholar
[6]Gyarmati, K., Matolcsi, M. and Ruzsa, I. A superadditivity and submultiplicativity property for cardinalities of sumsets. Combinatorica, to appear.Google Scholar
[7]Madiman, M., Marcus, A. and Tetali, P. Entropy and set cardinality inequalities for partition-determined functions, with applications to sumsets. Preprint.Google Scholar
[8]Plünnecke, H. (1969) Eigenschaften und Abschätzungen von Wirkungsfunktionen. BMwF-GMD-22 Gesellschaft für Mathematik und Datenverarbeitung, Bonn.Google Scholar
[9]Ruzsa, I. (1996) Sums of finite sets. In Number Theory: New York Seminar (Chudnovsky, D. V., Chudnovsky, G. V. and Nathanson, M. B., eds), Springer.Google Scholar
[10]Tao, T. (2008) Product set estimates for non-commutative groups. Combinatorica (5) 28 547–594.CrossRefGoogle Scholar
[11]Tao, T. Freiman's theorem for solvable groups. Preprint.Google Scholar
[12]Tao, T. and Vu, V. (2006) Additive Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[13]Tao, T. and Vu, V. (2008) John-type theorems for generalized arithmetic progressions and iterated sumsets. Adv. Math. 219 428–449.CrossRefGoogle Scholar