# Rusza triangle inequality for Shannon entropy

Define the entropy of a random variable $$X$$ by : $$H(X):=\sum_{x\in X(\Omega)}p(x)\log\left(\frac{1}{p(x)} \right),$$ with $$0\log 0:=0$$ and $$p(x)=P(X=x)$$.

A fundamental inequality satisfied by $$H$$ is : $$H(X)\le |range(X)|,$$ with equality if and only if $$X$$ is a uniform random variable.

The entropic Ruzsa triangle inequality claims that for $$X,Y,Z$$ independent random variables, we have : $$H(X-Z)\le H(X-Y)+H(Y-Z)-H(Y)\quad (*)$$ My question is : can we deduce from $$(*)$$ that If $$A,B,C$$ are three finite subsets of a group $$G$$, then : $$|B||A-C|\le |A-B||B-C|,$$ where $$P+Q:=\{p+q|(p,q)\in P\times Q \}$$.

I still ignore if the result is true, but here is my attempt :

Let $$Y$$ a uniform random variable on $$B$$ and $$X,Z$$ random variables such that $$X-Z$$ is a uniform random variable on $$A-C$$ and $$X,Y,Z$$ are independant (does it exist ?). Then $$H(Y)=\log|B|$$, and : \begin{align*} \log|A-C|+\log|B|&=H(X-Z)+H(Y)\\&\le H(X-Y)+H(Y-Z)\\&\le log|A-B|+\log|B-C| \end{align*} Hence, the question would be : can we find $$X,Y,Z$$ such that $$X,Y,Z$$ are independent and $$Y$$ and $$X-Z$$ are uniform ?

• Uh, after over a year, while going through my old answers, I realized I answered this question incorrectly, since I don't think the (X,Z) pair I gave you was independent. I am truly sorry.
– E-A
Aug 12, 2020 at 21:09

Edit: Note that in this construction, $$X$$ and $$Z$$ are not necessarily independent, so the proof does not actually go through; you might need to construct your (X,Z) pair by going through a bijection like this. (https://en.wikipedia.org/wiki/Ruzsa_triangle_inequality)