Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 164 / 4 / i

The Entropic Balog-Szemerédi-Gowers theorem states that for finitely supported random variables $A,B$ in an abelian group,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,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

Set $D=A_1-B_2$. By entropy submodularity,The first term is $H(A_1,B_2)\le 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 givesAs $H(A,B)=H(A)+H(B)-I(A;B)$, these estimates implySubtracting the common conditional-entropy term proves the stated Entropic Balog-Szemerédi-Gowers theorem.

Solved by gpt-5.6-sol high.