Sumset and inverse sumset theorems for Shannon entropy TeX Export

@article{citeulike:5033779, 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 \$A \subset G\$ is replaced by a discrete random variable \$X\$ taking values in \$G\$, and the cardinality \$|A|\$ is replaced by the Shannon entropy \$\Ent(X)\$. In particular, we classify the random variable \$X\$ which have small doubling in the sense that \$\Ent(X\_1+X\_2) = \Ent(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 \$\Ent(Z) = O(1)\$. When \$G\$ is torsion-free, we also establish the sharp lower bound \$\Ent(X+X) \geq \Ent(X) + {1/2} \log 2 - o(1)\$, where \$o(1)\$ goes to zero as \$\Ent(X) \to \infty\$.}, archivePrefix = {arXiv}, author = {Tao, Terence}, citeulike-article-id = {5033779}, citeulike-linkout-0 = {http://arxiv.org/abs/0906.4387}, citeulike-linkout-1 = {http://arxiv.org/pdf/0906.4387}, eprint = {0906.4387}, keywords = {entropy, entropy-inequalities, information-theory}, month = {Jun}, posted-at = {2009-07-01 15:53:43}, priority = {2}, title = {Sumset and inverse sumset theorems for Shannon entropy}, url = {http://arxiv.org/abs/0906.4387}, year = {2009} }

TY - JOUR ID - citeulike:5033779 L3 - citeulike-article-id:5033779 N2 - 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 $A \subset G$ is replaced by a discrete random variable $X$ taking values in $G$, and the cardinality $|A|$ is replaced by the Shannon entropy $\Ent(X)$. In particular, we classify the random variable $X$ which have small doubling in the sense that $\Ent(X_1+X_2) = \Ent(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 $\Ent(Z) = O(1)$. When $G$ is torsion-free, we also establish the sharp lower bound $\Ent(X+X) \geq \Ent(X) + {1/2} \log 2 - o(1)$, where $o(1)$ goes to zero as $\Ent(X) \to \infty$. TI - Sumset and inverse sumset theorems for Shannon entropy KW - entropy KW - entropy-inequalities KW - information-theory AU - Tao, Terence PY - 2009/Jun/24/ UR - http://arxiv.org/abs/0906.4387 ER -