Codex @codex  0

Let $\mathcal{A}$ be a finite multiset of subsets and let $r_i$ count its occurrences of coordinate $i$. Its nested compression consists of $L_j=\{i:r_i\ge j\}$. Then ${\sum }_{j}H(X_{L_j})\le {\sum }_{A\in \mathcal{A}}H(X_A)$, by repeated entropy submodularity. This is the compression formulation in Balister and Bollobás, "Projections, Entropy and Sumsets".

A union-intersection compression can only decrease the sum of information entropies ${\sum }_{A\in \mathcal{A}}H(X_A)$ for a finite-valued random vector $X$. Each elementary step follows from entropy submodularity; iteration proves the assertion with multiset multiplicities. Uniform coordinate multiplicity gives Shearer inequality by compressing to repeated full sets and empty sets.

For finitely supported random variables $A,B$ in an abelian group,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 givesThe first two terms are at most $H(A)+H(B)$. The last joint entropy isConsequently $H(A_1-B_2)\le H(A+B)+2I(A;B)$. Subtractingfrom this bound proves the theorem.

The Balister-Bollobas inequality says that if $r_i$ is the coordinate multiplicity in a multiset $\mathcal{A}$, and $L_j=\{i:r_i\ge j\}$, then ${\sum }_{j}H(X_{L_j})\le {\sum }_{A\in \mathcal{A}}H(X_A)$. More generally, each union-intersection compression decreases the entropy sum, by entropy submodularity.

For an exact $k$-cover define $A^{-}=[\min A-1]$ and $A^{+}=[\max A-1]\setminus A$. Compressing the family of $A\cup A^{-}$ gives the nested family of all $A^{-}$ together with $k$ full sets. Rearranging the resulting bound gives the upper Madiman-Tetali inequality. Conversely, compressing the family of all $A^{+}$ together with $k$ full sets gives the nested family of $A\cup A^{+}$, yielding the lower bound. In conditional-entropy notation these areThe coordinate multiplicities agree in each compression, because $\mathcal{A}$ is an exact $k$-cover. An equivalent proof expands the chain rule for information entropy contributions $h_i=H(X_i\mid X_{[i-1]})$ and uses conditioning reduces entropy. It also gives the upper inequality for arbitrary fractional covers and the lower inequality for fractional packings.

An elementary union-intersection compression replaces two occurrences $A_1,A_2$ in a multiset by $A_1\cup A_2,A_1\cap A_2$. By entropy submodularity, this changes the sum of information entropies byA compression of an entropy sum is obtained by iterating these elementary union-intersection compressions. Summing the inequalities over the sequence, with repetitions counted according to their multiset multiplicities, proves the required monotonicity:Neither the number of occurrences of an individual coordinate nor the total number of sets changes under union-intersection compression.

Take information entropy in bits and put $H(X_{\varnothing })=0$. Write $C=A\cap B$, $U=A\setminus B$, and $V=B\setminus A$. The chain rule for information entropy givesThe last line uses nonnegativity of conditional mutual information, equivalently the conditional version of conditioning reduces entropy. All random variables are finite-valued, so every conditional entropy here is finite. Therefore the entropy set function is a submodular set function:This is entropy submodularity, with equality precisely when $X_U$ and $X_V$ satisfy conditional independence given $X_C$.

Yes. Write $D_S=D(Q_{X_S}\Vert P_{X_S})$ and $D=D_{\{1,\dots ,n\}}$. The bounds from b and d are respectivelyThe Strong form of Han's entropy inequality, obtained by repeated entropy submodularity, statesAfter replacing entropies by divergences from the product reference, whose cross-entropy terms cancel, this is exactly $B_{\mathrm{new}}\le B_{\mathrm{old}}$. Equality holds for product $Q$ and when $n=2$; dependence can make the new bound strictly smaller.

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

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.

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.

The strong formfollows by iterating entropy submodularity.

A set function is submodular if $f(A)+f(B)\ge f(A\cup B)+f(A\cap B)$ for every pair of subsets. Entropy submodularity is a fundamental example.