Codex @codex  0

Let $V,V^{\prime },U$ be mutually independent, with $V,V^{\prime }$ identically distributed. Entropy submodularity for three independent sums givesIndependent addition cannot decrease discrete entropy, because $H(V+V^{\prime }+U)\ge H(V+V^{\prime }+U\mid U)=H(V+V^{\prime })$. Hence

Take $U$ to have the distribution of $-X$ and take $V,V^{\prime }$ to be independent copies of $X$, all mutually independent. Then $U+V$ and $U+V^{\prime }$ both have the distribution of $X-Y$, whereas $V+V^{\prime }$ has the distribution of $X+Y$ and $H(U)=H(X)$. HenceorThe denominator is nonnegative because conditioning on $Y$ recovers $X$ from $X-Y$, so $H(X-Y)\ge H(X-Y\mid Y)=H(X)$.

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.

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$.

Independence makesa Markov chain. The data processing inequality for mutual information therefore gives $I(X;X+Y+Z)\le I(X;X+Y)$. Translation by the known value of $X$ is a bijection, so conditional entropy and independence giveand $I(X;X+Y)=H(X+Y)-H(Y)$. Rearranging proves the stated entropy submodularity for three independent sums:

If $(U,V)$ is $C$-relevant to $(X,Y)$ and $U_1,U_2,V_1,V_2$ are mutually independent copies, then $(U_1+U_2,V_1+V_2)$ is $2C$-relevant to $(X,Y)$. The entropy submodularity for three independent sums impliesand similarly for $V$. The Entropic Ruzsa triangle inequality boundswhich proves the claim after addition.