= Entropic Balog-Szemerédi-Gowers theorem
{c}
For finitely supported random variables $A,B$ in an <abelian group>,
$$
d_R(A;B\mathbin\Vert A+B)
\leq 3I(A;B)+2H(A+B)-H(A)-H(B).
$$
To prove it, take two conditionally independent copies $(A_1,B_1)$ and $(A_2,B_2)$ of $(A,B)$ given $A+B$. Since $A_1+B_1=A_2+B_2$, <entropy submodularity> gives
$$
H(A_1-B_2)
\leq H(A_1-B_2,A_1)+H(A_1-B_2,B_1)-H(A_1-B_2,A_1,B_1).
$$
The first two terms are at most $H(A)+H(B)$. The last joint entropy is
$$
2H(A,B)-H(A+B).
$$
Consequently $H(A_1-B_2)\leq H(A+B)+2I(A;B)$. Subtracting
$$
H(A\mid A+B)=H(B\mid A+B)
=H(A)+H(B)-I(A;B)-H(A+B)
$$
from this bound proves the theorem.
Back to article page
