Sumset and inverse sumset theorems for Shannon entropy

Details Sumset and inverse sumset theorems for Shannon entropy Sumset and inverse sumset theorems for Shannon entropy

2009-06-24

arxiv.org/abs/0906.4387v4

Mathematics

Combinatorics

32 pages, no figures, to appear, Combinatorics, Probability, and Computing. This is the final version, incorporating the secon

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

Sumset and inverse sumset theorems for Shannon entropy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sumset and inverse sumset theorems for Shannon entropy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sumset and inverse sumset theorems for Shannon entropy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105516