= Solution
The <Entropic Balog-Szemerédi-Gowers theorem> states that for finitely supported random variables $A,B$ in an <abelian group>,
$$
d_R(A;B\mathbin\Vert A+B)
\leq3I(A;B)+2H(A+B)-H(A)-H(B),
$$
where the left-hand side is the <Simultaneous conditional entropic Ruzsa distance>.
Put $S=A+B$ and take two copies $(A_1,B_1)$ and $(A_2,B_2)$ that are conditionally independent given $S$. Thus both sums equal $S$, and, given $S$, $A_1$ and $B_2$ are independent with the required conditional marginals. By <conditioning reduces entropy>,
$$
d_R(A;B\mathbin\Vert S)
\leq H(A_1-B_2)
-\frac12H(A_1\mid S)-\frac12H(B_2\mid S).
$$
The two conditional entropies are equal, since either $A$ or $B$ together with $S$ determines the other, and the <chain rule for information entropy> gives
$$
H(A\mid S)=H(B\mid S)
=H(A)+H(B)-I(A;B)-H(S).
$$
Set $D=A_1-B_2$. By <entropy submodularity>,
$$
H(D)\leq H(D,A_1)+H(D,B_1)-H(D,A_1,B_1).
$$
The first term is $H(A_1,B_2)\leq H(A)+H(B)$ by <subadditivity of information entropy>. Since $A_1+B_1=A_2+B_2$, we also have $D=A_2-B_1$, so the second term is at most $H(A)+H(B)$. Finally $(D,A_1,B_1)$ determines all four copied variables, and conditional independence gives
$$
\begin{aligned}
H(D,A_1,B_1)
&=H(A_1,B_1,A_2,B_2)\\
&=H(S)+2H(A,B\mid S)\\
&=2H(A,B)-H(S).
\end{aligned}
$$
As $H(A,B)=H(A)+H(B)-I(A;B)$, these estimates imply
$$
H(D)\leq H(S)+2I(A;B).
$$
Subtracting the common conditional-entropy term proves the stated <Entropic Balog-Szemerédi-Gowers theorem>.
Solved by gpt-5.6-sol high.
Back to article page
