Sumset and Inverse Sumset Theory for Shannon Entropy

DOI10.1017/S0963548309990642MaRDI QIDQ4933603zbMATH OpenOpenAlexFDO

Authors Terence Tao

Publication date 14 October 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

additive combinatoricsentropysumset

Mathematics Subject Classification ID

Additive bases, including sumsets (11B13) Representation functions (11B34) Measures of information, entropy (94A17)

Abstract: Let $G=(G,+)$ be an additive group. The sumset theory of Pl"unnecke 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 $AsubsetG$ is replaced by a discrete random variable $X$ taking values in $G$, and the cardinality $|A|$ is replaced by the Shannon entropy $mathrmEnt(X)$. In particular, we classify the random variable $X$ which have small doubling in the sense that $mathrmEnt(X_1+X_2)=mathrmEnt(X)+O(1)$ when $X_1,X_2$ 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 $mathrmEnt(Z)=O(1)$. When $G$ is torsion-free, we also establish the sharp lower bound $mathrmEnt(X+X)geqmathrmEnt(X)+1/2log2-o(1)$, where $o(1)$ goes to zero as $mathrmEnt(X)oinfty$.

Recommendations

• Sumset and Inverse Sumset Inequalities for Differential Entropy and Mutual Information
• Sumsets and entropy
• An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets
• Generalization of Shannon entropy of capacities on set systems
• scientific article; zbMATH DE number 1166262
• On the Shannon entropy and related functionals on convex sets
• scientific article; zbMATH DE number 1574609
• Shannon entropy: axiomatic characterization and application
• Asymptotics of the Shannon and Renyi entropies for sums of independent random variables
• Projections, entropy and sumsets

Cites work

• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• A statistical theorem of set addition
• Freiman's theorem in an arbitrary abelian group
• John-type theorems for generalized arithmetic progressions and iterated sumsets
• Product set estimates for non-commutative groups
• Solution of Shannon’s problem on the monotonicity of entropy

Cited in

(30)

• Working session: Additive combinatorics, entropy, and fractal geometry. Abstracts from the working session held October 8--13, 2017
• The convexification effect of Minkowski summation
• Entropy versions of additive inequalities
• Entropy of Bernoulli convolutions and uniform exponential growth for linear groups
• Deletion correcting codes meet the Littlewood-Offord problem
• Majorization and Rényi entropy inequalities via Sperner theory
• On the dimension of Bernoulli convolutions
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Entropy and set cardinality inequalities for partition-determined functions
• Sumset and Inverse Sumset Inequalities for Differential Entropy and Mutual Information
• Shadowing, Entropy and Minimal Sets
• Sumsets and entropy
• Plünnecke and Kneser type theorems for dimension estimates
• Projections, entropy and sumsets
• An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets
• Absolute continuity of Bernoulli convolutions for algebraic parameters
• Entropy inequalities for sums in prime cyclic groups
• Some applications of relative entropy in additive combinatorics
• Covering the large spectrum and generalized Riesz products
• Information in Probability: Another Information-Theoretic Proof of a Finite de Finetti Theorem
• Entropy and the discrete central limit theorem
• Approximate discrete entropy monotonicity for log-concave sums
• Marton's conjecture in abelian groups with bounded torsion
• Discretised sum-product theorems by Shannon-type inequalities
• Convex geometry and its applications. Abstracts from the workshop held December 15--20, 2024
• On a conjecture of Marton
• Sumsets and entropy revisited
• On an entropic analogue of additive energy
• On the monotonicity of discrete entropy for log-concave random vectors on \(\mathbb{Z}^d\)
• On self-similar sets with overlaps and inverse theorems for entropy

This page was built for publication: Sumset and Inverse Sumset Theory for Shannon Entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933603)