Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 164 (Entropy Methods in Combinatorics)

The axioms for information entropy give the formula $H(X)=-{\sum }_{x}p(x)\log p(x)$ and hence the chain rule for information entropyBecause conditioning reduces entropy, $H(Y\mid X)\le H(Y)$, and thereforeThis is subadditivity of information entropy.

For the entropy submodularity rule, apply the chain rule for information entropy twice:The last quantity is conditional mutual information, whose nonnegativity again expresses that conditioning reduces entropy.

Solved by gpt-5.6-sol high.

Write $S_1=H(X)+H(Y)+H(Z)$ and $S_2=H(X,Y)+H(Y,Z)+H(Z,X)$. By the definition of mutual information,so the required right-hand side is $(2S_2-S_1)/3$.

Apply entropy submodularity to the pairs $(X,Y),(X,Z)$ and then cyclically permute the variables:Adding gives $2S_2\ge S_1+3H(X,Y,Z)$, which is exactly

Solved by gpt-5.6-sol high.

Because $X,Y,Z$ are independent random variables, adding $Y$ is an independent noise channel, sois a Markov chain. The data processing inequality for mutual information givesTranslation in the finite additive group preserves conditional entropy, and independence therefore givesandSubstitution proves the required entropy submodularity for three independent sums.

Solved by gpt-5.6-sol high.

For random variables $A,B$ in a finite additive group, take independent copies $A^{\prime },B^{\prime }$ with the same respective distributions and define the Entropic Ruzsa distance byFor the independent variables in the question, expansion givesPart iii, applied to the independent variables $X,Y,-Z$, saysSubtracting $H(X-Y)$ from both sides proves

Solved by gpt-5.6-sol high.

Write $r=|V_0|$, $s=|V_1|$, and $e=|E(G)|=\alpha |X||Y|$. We construct a random graph homomorphism $\Psi :T\to G$. Choose a root of the tree. Map it according to the degree-biased vertex distribution on the corresponding side of the bipartite graph; after mapping any vertex, map each child independently and uniformly to a neighbour of its parent's image.

Every oriented tree edge is then mapped uniformly onto the $e$ edges of $G$. Every tree vertex in $V_0$ has the degree-biased marginal on $X$, of entropy $H_X$, and every vertex in $V_1$ has the analogous marginal of entropy $H_Y$. Repeated use of the chain rule for information entropy along the rooted tree givesSince a $k$-vertex tree has $k-1$ edges,The maximum entropy distribution on a finite set gives $H_X\le \log |X|$ and $H_Y\le \log |Y|$. HenceIf $N$ is the number of bipartition-respecting graph homomorphisms $T\to G$, the support of $\Psi$ has size $N$, so the maximum entropy distribution on a finite set also gives $H(\Psi )\le \log N$. ThusThere are $|X{|}^r|Y{|}^s$ bipartition-respecting maps in total, so a uniformly chosen one is a graph homomorphism with probability at least ${\alpha }^{k-1}$. This proves the Sidorenko inequality for trees.

Solved by gpt-5.6-sol high.

Letwhere $\phi$ is the golden ratio. If the union-closed family consists of one nonempty set, any element of that set has frequency one, so assume its cardinality exceeds one. Choose independent uniform members $A,B$ and let $X,Y\in \{0,1{\}}^n$ be their characteristic vectors of sets. Then $H(X)=H(Y)=\log |\mathcal{A}|>0$.

Suppose for a contradiction that every element has frequency $p_i<c$. Put $q_i=1-p_i>1/\phi$, and let $Z=X\mathrm{OR}Y$, the characteristic vector of a set of $A\cup B$. The chain rule for information entropy and conditioning reduces entropy givebecause $Z_{<i}$ is a function of $(X_{<i},Y_{<i})$.

Fix the two prefixes and setThe two conditioned bits are independent random variables, and $Z_i=0$ exactly when both are zero. The supplied binary entropy product inequality therefore givesAveraging over the independent prefixes yieldswhenever either conditional entropy is positive. Summing and using $H(X)>0$ gives $H(Z)>H(X)$.

But set union keeps $A\cup B$ inside the union-closed family, so $Z$ is supported on $\mathcal{A}$. The maximum entropy distribution on a finite set gives $H(Z)\le \log |\mathcal{A}|=H(X)$, a contradiction. Some element must therefore occur in at least $c|\mathcal{A}|$ members, proving the entropy bound for a union-closed family.

Solved by gpt-5.6-sol high.

Let $\mathcal{Q}$ be the set of valid quintuples and choose $(A_1,\dots ,A_5)$ uniformly from $\mathcal{Q}$. ThenApply Shearer's inequality to the ten pairs $\{i,j\}\subseteq [5]$. Every index occurs in four pairs, so

Put $U_{ij}=A_i\cup A_j$. Since $U_{ij}\in \mathcal{A}$, it has cardinality $k$. For each element of $U_{ij}$, its membership bits in $(A_i,A_j)$ are one of $(1,0),(0,1),(1,1)$; outside $U_{ij}$ they are forced to be $(0,0)$. Thus at most $3^k$ ordered pairs have any prescribed union. The chain rule for information entropy, conditional entropy, and the support bound for information entropy givebecause every $U_{ij}$ belongs to $\mathcal{A}$. There are ten pairs, henceExponentiating proveswhich is the five-variable case of the entropy bound for pairwise-union tuples.

Solved by gpt-5.6-sol high.

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.

Write $\delta =d_R(X,Y)$, $A=U_1+U_2$, $B=V_1+V_2$, and $S=A+B$. Distances depend only on distributions, so all variables used in any one application may be realized as independent random variables.

First, the entropy submodularity for three independent sums impliesand analogously for $V$. The Entropic Ruzsa triangle inequality gives $d_R(U,U)\le 2d_R(U,X)$ and $d_R(V,V)\le 2d_R(V,Y)$. Consequently the relevance of independent self-sums gives

Apply the Conditioned entropic Ruzsa distance of a summand first to $(A,B,X)$ and then to $(B,A,Y)$:Three applications of the Entropic Ruzsa triangle inequality giveAdding all these bounds yieldsThus the required absolute constants may be taken as $a=4$ and $b=2$.

Solved by gpt-5.6-sol high.