betaFeedback

WorksComputer Science

On the most informative Boolean function under noise

Abstract

Let XX be a uniform random bit string and YY be obtained by flipping each bit of XX independently with probability pp. Let CC be a random bit obtained as a function of YY. We show that I(C:X)≤I(Y1:X)\mathbf{I}(C:X)\le \mathbf{I}(Y_1:X) for all p∈[0,1]p\in[0,1], which resolves a conjecture posed by Courtade and Kumar in 2013.

Introduction

Let XX be distributed uniformly on {0,1}n\{0,1\}^n and let YY be obtained by flipping each coordinate of XX with probability pp, independently. In [12, 8], Courtade and Kumar ask: which bit CC computed from YY is most informative about XX? They conjecture that taking C=YiC=Y_i for some i∈[n]i \in[n] maximizes the information conveyed about XX. In particular, their Conjecture 1 states that

I(C:X)≤I(Y1:X)=1−H2(p).(1)I(C:X) \le I(Y_1:X) = 1-H_2(p). \tag*{(1)}

They further remark that, despite its resemblance to a simple homework exercise, the statement appears to involve substantial depth. Indeed, even after extensive efforts and partial progress [2, 3, 4, 7, 9, 10, 11, 14, 18, 19, 20, 22, 21, 23, 24, 25, 26], a full resolution of the conjecture remained elusive.

In this work, we observe that if we study the inequality parametrized by μ=E[C]\mu=\mathbb{E}[C], a delicate refinement of (CK) interpolating between Shannon and Tsallis entropies emerges. This refinement admits a proof by induction on the number of coordinates of X,YX,Y. Denoting the Tsallis entropy of CC by Hˉ(C)=4μ(1−μ)\bar H(C)=4\mu(1-\mu) and setting Ip=I(Y1:X)I_p=I(Y_1:X) and Iˉp=(1−2p)2\bar I_p=(1-2p)^2, we define the progressive entropy of CC as

Q(C)=IˉpH(C)−(Iˉp−Ip)Hˉ(C).(2)Q(C)=\bar I_pH(C)-(\bar I_p-I_p)\bar H(C). \tag*{(2)}

With this definition in hand, we prove the following.

Theorem 1.1. Let XX be a uniform random bit string and YY be obtained by flipping each bit of XX with probability pp, independently. For a bit CC obtained from YY, we have

I(C:X)≤Q(C)≤I(Y1:X)I(C:X) \le Q(C) \le I(Y_1:X)

for any p∈[0,1]p \in[0,1].

Comparison with earlier bounds

The strong data-processing inequality [1] gives I(C:X)≤IˉpH(C)I(C : X) \le\bar{I}_p H(C), the upper-right corner of Figure 1. Courtade and Kumar’s [8] Conjecture 2 concerns the stronger upper bound IpH(C)I_p H(C) at the upper-left corner. This bound was later shown to be too strong in general [5, 11]. Our refinement Q(C)Q(C) subtracts a Tsallis correction (Iˉp−Ip)Hˉ(C)(\bar{I}_p-I_p)\bar{H}(C) from the strong data-processing bound and sits between the two.

Figure 1. Arrows point toward the larger quantity. Q(C)Q(C) lies on the top edge, and its distance to IˉpHˉ(C)\bar I_p\bar H(C) equals the length of the bottom edge, (Iˉp−Ip)Hˉ(C)(\bar I_p-I_p)\bar H(C). Blue: quantities that are always at most I(Y1:X)I(Y_1:X). Purple: quantities that upper bound I(C:X)I(C:X). Only Q(C)Q(C) lies in both.

Concurrent work

Concurrently with our work, Ky and Tran [13], Chen et al. [6], and Mahdavifar and Beirami [15] announced proofs of the Courtade–Kumar conjecture. Their preprints were first submitted to arXiv on September 21–22, 2026. We had obtained a proof using Fourier analysis by September 17, 2026, and completed writing down the simpler induction proof, which we present here, by September 20, 2026. Both versions are recorded in our public repository.1

OpenAI subsequently released two further proofs in its openai/math repository on October 6, 2026.2 Both manuscripts are dated September 24, 2026. The first [16] derives (CK) from a Hellinger-contraction inequality and uses computer-assisted verification of scalar inequalities. The second [17] proves sharp information contraction for randomized binary outputs.

The continuous case

We note that I(C:X)≤Q(C)I(C : X) \le Q(C) is a surprisingly sharp bound, which is already violated by a natural generalization of the problem. Let X∘X_{\circ} be distributed uniformly on the unit cube [0,1]n[0,1]^n and Y∘Y_{\circ} be obtained by independently resampling each coordinate of X∘X_{\circ} uniformly from [0,1][0,1] with probability 2p2p. Assume C∘C_{\circ} is a random bit obtained as a function of Y∘Y_{\circ} with μ=E[C∘]\mu= \mathbb{E}[C_{\circ}].

Let TμT_{\mu} be the indicator of Y∘,1≤μY_{\circ,1} \le\mu, so that E[Tμ]=μ\mathbb{E}[T_{\mu}] = \mu. In Lemma A.1 we show that Q(C∘)<I(Tμ:X∘)Q(C_{\circ}) < I(T_{\mu} : X_{\circ}) for 0<μ<10 < \mu< 1, μ≠1/2\mu\ne1/2, and 0<p<1/20 < p < 1/2, which shows that Q(C∘)Q(C_{\circ}) is too strong for the continuous problem. We conjecture that the threshold functions maximize mutual information at each fixed mean.

Conjecture 1.2. Let X∘X_{\circ}, Y∘Y_{\circ} and C∘C_{\circ} be as constructed and TμT_{\mu} be the indicator of the event Y∘,1≤μY_{\circ,1} \le\mu as above. It holds that

I(C∘:X∘)≤I(Tμ:X∘)I(C_{\circ} : X_{\circ}) \le I(T_{\mu} : X_{\circ})

for 0≤p≤1/20 \le p \le1/2 and $0 \le \mu \le 1.

Note that a proof of Conjecture 1.2 directly implies (CK)—though not our Theorem 1.1—since given a strategy to output CC from YY revealing I(C:X)I(C : X) bits of information, we can quantize Y∘Y_{\circ} by rounding each coordinate to 0 or 1 with threshold 1/2 and apply the strategy to obtain C∘C_{\circ}. We get I(C∘:X∘)=I(C:X)I(C_{\circ} : X_{\circ}) = I(C : X) and it can be shown that I(Tμ:X∘)≤I(Y1:X)I(T_{\mu} : X_{\circ}) \le I(Y_1 : X).

Preliminaries

We use H(⋅)H(\cdot) and I(⋅:⋅)I(\cdot: \cdot) for Shannon entropy and mutual information, with logarithms in base 2. We denote the natural logarithm by ln⁡\ln. We only need Tsallis entropy for bits, while the observed variables may be arbitrary. For a bit CC with mean μ\mu, we define

Hˉ(C)=4μ(1−μ).\bar{H}(C) = 4\mu(1-\mu).

For a bit CC and an arbitrary random variable ZZ, Tsallis information is defined by

Iˉ(C;Z)=Hˉ(C)−Hˉ(C∣Z).\bar{I}(C; Z) = \bar{H}(C) - \bar{H}(C \mid Z).

Note that for bits BB, CC, the quantities Iˉ(B;C)\bar{I}(B;C) and Iˉ(C;B)\bar{I}(C;B) need not be equal. We denote

Ip=1−H2(p),Iˉp=(1−2p)2,I_p = 1 - H_2(p), \qquad\bar{I}_p = (1-2p)^2,

and

Jp=Iˉp−Ip.J_p = \bar{I}_p-I_p.

Thus Ip=I(Yi:Xi)I_p=I(Y_i:X_i) and Iˉp=Iˉ(Yi;Xi)\bar{I}_p=\bar{I}(Y_i;X_i). With these shorthands, we have

Q(C)=IˉpH(C)−JpHˉ(C).Q(C)=\bar{I}_pH(C)-J_p\bar{H}(C).

For all our entropy and information quantities H(⋅)H(\cdot), I(⋅:⋅)I(\cdot:\cdot), Hˉ(⋅)\bar{H}(\cdot), Iˉ(⋅;⋅)\bar{I}(\cdot;\cdot), and QQ, conditioning on UU means evaluating the quantity under the conditional law given UU and taking expectation over UU, with pp held fixed. For instance, Q(C∣U)=Eu∼U[Q(C∣U=u)]Q(C\mid U)=\mathbb{E}_{u\sim U}[Q(C\mid U=u)]. Next, we gather some facts about Tsallis and Shannon information.

Lemma 2.1. Let BB and CC be bits and ZZ, WW, UU be arbitrary random variables. We have

  1. 0≤Iˉ(C;Z∣U)≤Hˉ(C∣U)0\leq\bar{I}(C;Z\mid U)\leq\bar{H}(C\mid U) and Hˉ(C∣U)≤H(C∣U)≤(1+Hˉ(C∣U))/2\bar{H}(C\mid U)\leq H(C\mid U)\leq(1+\bar{H}(C\mid U))/2.

  1. Iˉ(C;Z,W∣U)=Iˉ(C;Z∣U)+Iˉ(C;W∣Z,U)\bar{I}(C;Z,W\mid U)=\bar{I}(C;Z\mid U)+\bar{I}(C;W\mid Z,U). If C−Z−WC-Z-W is a Markov chain, then Iˉ(C;W)≤Iˉ(C;Z)\bar{I}(C;W)\leq\bar{I}(C;Z).

  1. Iˉ(C;Z∣U)≤2ln⁡2 I(C:Z∣U)\bar{I}(C;Z\mid U)\leq2\ln2\,I(C:Z\mid U). If CC is unbiased and independent of UU, then also I(C:Z∣U)≤Iˉ(C;Z∣U)I(C:Z\mid U)\leq\bar{I}(C;Z\mid U).

  1. Hˉ(C)Iˉ(B;C)=Hˉ(B)Iˉ(C;B)\bar{H}(C)\bar{I}(B;C)=\bar{H}(B)\bar{I}(C;B). If BB is unbiased, then Iˉ(C;B)=(2Pr⁡[B=C]−1)2\bar{I}(C;B)=(2\Pr[B=C]-1)^2.

  1. If BB is independent of UU, then Iˉ(B;C∣U)Hˉ(C∣U)≥Hˉ(B)Iˉ(C;B)\bar{I}(B;C\mid U)\bar{H}(C\mid U)\geq\bar{H}(B)\bar{I}(C;B).

  1. 0≤Jp≤Ip0\leq J_p\leq I_p for every p∈[0,1]p\in[0,1].

Proofs of the preceding and the next lemma are given in Appendix B. Let us define

c(μ)=ln⁡(1/μ)4(1−μ)2,(1/2≤μ<1),c(\mu)=\frac{\ln(1/\mu)}{4(1-\mu)^2}, \qquad(1/2\leq\mu<1),

extending it to 0<μ<1/20<\mu<1/2 by c(μ)=c(1−μ)c(\mu)=c(1-\mu).

Lemma 2.2. For a nonconstant bit CC with mean μ\mu and every random variable UU,

I(C:U)≤c(μ)ln⁡2Iˉ(C;U),andHˉ(C)c(μ)≤1.I(C:U)\leq\frac{c(\mu)}{\ln2}\bar{I}(C;U), \qquad\text{and} \qquad\bar{H}(C)c(\mu)\leq1.

The proof

Our proof proceeds by induction on nn, the number of coordinates of X,YX,Y. Given the random bit CC and the bit string YY, we adaptively pick a coordinate i∈[n]i\in[n] and establish the bound

Q(C)−I(C:X)≥11+λ(Q(C∣Yi)−I(C:X∣Yi))(3)Q(C)-I(C:X)\geq\frac{1}{1+\lambda}\bigl(Q(C\mid Y_i)-I(C:X\mid Y_i)\bigr) \tag*{(3)}

for some λ≥0\lambda\geq0. When YiY_i is fixed, CC depends on n−1n-1 coordinates and therefore the induction hypothesis applies for Yi=0Y_i=0 and Yi=1Y_i=1 separately, showing that Q(C∣Yi)≥I(C:X∣Yi)Q(C\mid Y_i)\geq I(C:X\mid Y_i). Plugging into (⋆), we get Q(C)≥I(C:X)Q(C)\geq I(C:X), which implies (CK) as we show next.

Lemma 3.1. For all p∈[0,1]p\in[0,1], we have Q(C)≤I(Y1:X)Q(C)\leq I(Y_1:X).

Proof. From Lemma 2.1[6] and (1), we have Jp≤IpJ_p\leq I_p and H(C)−Hˉ(C)≤1−H(C)H(C)-\bar{H}(C)\leq1-H(C). Let us write

Q(C)−IpH(C)=JpH(C)−JpHˉ(C)=Jp(H(C)−Hˉ(C))≤Ip(1−H(C)).\begin{aligned} Q(C)-I_pH(C)&=J_pH(C)-J_p\bar{H}(C)\\ &=J_p\bigl(H(C)-\bar{H}(C)\bigr)\\ &\leq I_p\bigl(1-H(C)\bigr). \end{aligned}

Therefore Q(C)≤Ip(1−H(C))+IpH(C)=I(Y1:X)Q(C)\leq I_p(1-H(C))+I_pH(C)=I(Y_1:X) as desired.

The property we want from the coordinate ii is fairly mild: I‾(C;Yi)≤1/4\overline{I}(C;Y_i) \le1/4. The next lemma shows that such a coordinate always exists.

Lemma 3.2. When n≥2n \ge2, there exists an i∈[n]i \in[n] such that I‾(C;Yi)≤1/4\overline{I}(C;Y_i) \le1/4.

Proof. Let i,j∈[n]i,j \in[n] be distinct. We may relabel Yi,YjY_i,Y_j so that E[C(2Yi−1)]\mathbb{E}[C(2Y_i-1)] and E[C(2Yj−1)]\mathbb{E}[C(2Y_j-1)] are nonnegative. Since Yi,YjY_i,Y_j are independent uniform bits,

I‾(C;Yi)+I‾(C;Yj)=2E[C(2Yi−1)+C(2Yj−1)]≤4Pr⁡[Yi=Yj=1]=1,\sqrt{\overline{I}(C;Y_i)}+\sqrt{\overline{I}(C;Y_j)}=2\mathbb{E}[C(2Y_i-1)+C(2Y_j-1)]\le4\Pr[Y_i=Y_j=1]=1,

using 0≤C≤10\le C\le1. At least one of the two square roots is at most 1/21/2.

Let us fix such an ii satisfying I‾(C;Yi)≤1/4\overline{I}(C;Y_i)\le1/4 and use the shorthands A=XiA=X_i, B=YiB=Y_i, and U=X−iU=X_{-i} in the rest of the paper. The following lemma is the crux of our argument, which establishes (⋆)(\star) giving the induction step.

Lemma 3.3. Assuming I‾(C;B)≤1/4\overline{I}(C;B)\le1/4, we have

Q(C)−I(C:X)≥11+λ(Q(C∣B)−I(C:X∣B))Q(C)-I(C:X)\ge\frac{1}{1+\lambda}\left(Q(C\mid B)-I(C:X\mid B)\right)

for some λ≥0\lambda\ge0.

§ 3.2 is devoted to proving Lemma 3.3; here we show that it implies the main theorem.

Theorem 1.1 (restated). It holds that I(C:X)≤Q(C)≤I(Y1:X)I(C:X)\le Q(C)\le I(Y_1:X).

Proof. The second inequality is Lemma 3.1. For the first, the cases p∈{0,1/2,1}p\in\{0,1/2,1\} and constant CC are immediate. Complementing YY if necessary lets us assume 0<p<1/20<p<1/2. We proceed by induction on nn. When n=1n=1, the bit CC is a constant, Y1Y_1, or its negation, and the bound holds with equality. For n≥2n\ge2, by Lemma 3.2 there exists a coordinate ii with I‾(C;Yi)≤1/4\overline{I}(C;Y_i)\le1/4. Conditioning on B=YiB=Y_i reduces the problem to n−1n-1 coordinates, so the induction hypothesis applies to the B=0B=0 and B=1B=1 cases individually, giving

I(C:X∣B)=I(C:U∣B)≤Q(C∣B).I(C:X\mid B)=I(C:U\mid B)\le Q(C\mid B).

Applying Lemma 3.3, we conclude Q(C)−I(C:X)≥0Q(C)-I(C:X)\ge0.

A comparison lemma

Let UU be a random variable and A,BA,B be unbiased bits jointly independent of UU. Let CC be a bit obtained from (B,U)(B,U) using private randomness, with H‾(C∣U)>0\overline{H}(C\mid U)>0. We compare CC with an unbiased bit C′C' obtained from BB alone using private randomness, subject to the matching condition

I(B:C′)=I(B:C∣U)H‾(C∣U).(4)I(B:C')=\frac{I(B:C\mid U)}{\overline{H}(C\mid U)}. \tag*{(4)}

Lemma 3.4. A bit C′C' satisfying (B) exists. Every such bit satisfies

I(A:C′)≥I(A:C∣U)H‾(C∣U).I(A:C')\ge\frac{I(A:C\mid U)}{\overline{H}(C\mid U)}.

Proof. For the fixed channel between AA and BB, let FF be the function determined by

F(I(B:D))=I(A:D)F(I(B:D))=I(A:D)

as DD ranges over unbiased bits generated from BB. It can be shown that FF is increasing and concave (cf. Lemma A.2), and

I(B:C∣U=u)≤H‾(C∣U=u),I(B:C\mid U=u)\le\overline{H}(C\mid U=u),
I(A:C∣U=u)≤H‾(C∣U=u)F(I(B:C∣U=u)H‾(C∣U=u)).I(A:C\mid U=u)\le\overline{H}(C\mid U=u)F\left(\frac{I(B:C\mid U=u)}{\overline{H}(C\mid U=u)}\right).

Values of uu with zero conditional Tsallis entropy contribute zero to both informations and may be omitted. The first inequality, averaged over UU, places the right-hand side of (B) in [0,1][0,1]. Varying the noise in the channel from BB to C′C' therefore gives a matching bit. Applying Jensen’s inequality to the second inequality, with weights proportional to Hˉ(C∣U=u)\bar{H}(C \mid U=u), gives

I(A:C∣U)≤Hˉ(C∣U)F(I(B:C∣U)Hˉ(C∣U))=Hˉ(C∣U)I(A:C′).I(A:C \mid U) \leq\bar{H}(C \mid U) F\left(\frac{I(B:C \mid U)}{\bar{H}(C \mid U)}\right)=\bar{H}(C \mid U)I(A:C').

as required.

Lemma 3.5. Every bit C′C' satisfying (B) also satisfies

Iˉ(C′;B)≥I(C;B)Hˉ(C∣U)2.\bar{I}(C';B) \geq\frac{I(C;B)}{\bar{H}(C \mid U)^2}.

Proof. Let us write v=Hˉ(C∣U)v=\bar{H}(C \mid U) and d=E[(2B−1)(2C−1)]d=\mathbb{E}[(2B-1)(2C-1)]. Since BB is unbiased, Iˉ(C;B)=d2\bar{I}(C;B)=d^2. As shown in Appendix § 5, ∣d∣≤v\lvert d\rvert\leq v and

I(B:C∣U)v≥D2(1+d/v2∥12).\frac{I(B:C \mid U)}{v} \geq D_2\left(\left.\frac{1+d/v}{2}\right\Vert\frac{1}{2}\right).

If θ=E[(2B−1)(2C′−1)]\theta=\mathbb{E}[(2B-1)(2C'-1)], then Iˉ(C′;B)=θ2\bar{I}(C';B)=\theta^2 and I(B:C′)=D2(1+θ2∥12)I(B:C')=D_2\left(\left.\frac{1+\theta}{2}\right\Vert\frac{1}{2}\right). The matching identity and monotonicity of this divergence in ∣θ∣\lvert\theta\rvert imply θ2≥d2/v2\theta^2 \geq d^2/v^2.

The induction step

Recalling that A=XiA=X_i, B=YiB=Y_i and U=X−iU=X_{-i}, in this section we would like to lower bound the gap Q(C)−I(C:X)Q(C)-I(C:X) by a factor of the conditional gap

Δ=Q(C∣B)−I(C:X∣B).\Delta=Q(C \mid B)-I(C:X \mid B).

We obtain two lower bounds on Q(C)−I(C:X)Q(C)-I(C:X). The first involves Δ\Delta and benefits from CC depending on UU, through a positive term in Iˉ(C:U)\bar{I}(C:U). The second has a negative term in Iˉ(C:U)\bar{I}(C:U) and benefits from weaker dependence. We add λ\lambda times the second bound to the first, choosing λ\lambda to cancel these terms, so that the bound works whether or not CC depends on UU.

To analyze the remaining terms, we introduce an unbiased comparison bit C′C' obtained from BB using private randomness. The comparisons in Lemma 3.4 and Lemma 3.5, together with our choice of coordinate with Iˉ(C;B)≤1/4\bar{I}(C;B)\leq1/4, allow us to charge these terms to quantities involving I(A:C′)I(A:C') and I(B:C′)I(B:C'). What remains is an inequality about the three unbiased bits in the Markov chain A−B−C′A-B-C', which we analyze in § 3.3.

Dependence diagram for the original and comparison bits

Figure 2. Arrows indicate dependence. The original bit CC depends on Y−iY_{-i} and BB, while the comparison bit C′C' depends only on BB and private randomness.

Let us start with a lemma that we use in obtaining the first lower bound.

Lemma 3.6. If Hˉ(C∣U)>0\bar{H}(C \mid U)>0, then

I(B:C∣U)−I(B:C)≥12ln⁡2Iˉ(C;B)Iˉ(C;U)Hˉ(C)Hˉ(C∣U).I(B:C \mid U)-I(B:C)\geq\frac{1}{2\ln2}\frac{\bar{I}(C;B)\bar{I}(C;U)}{\bar{H}(C)\bar{H}(C \mid U)}.

Proof. Since BB and UU are independent, the Shannon and Tsallis chain rules give

I(B:C∣U)−I(B:C)=I(B:U∣C),I(B:C\mid U)-I(B:C)=I(B:U\mid C),
I‾(B;C∣U)−I‾(B;C)=I‾(B;U∣C).\overline{I}(B;C\mid U)-\overline{I}(B;C)=\overline{I}(B;U\mid C).

Since BB is unbiased and independent of UU, parts 3–5 of Lemma 2.1 give

I(B:U∣C)≥I‾(B;U∣C)2ln⁡2≥I‾(C;B)2ln⁡2(1H‾(C∣U)−1H‾(C))=I‾(C;B)I‾(C;U)2ln⁡2 H‾(C)H‾(C∣U),\begin{aligned} I(B:U\mid C)\geq\frac{\overline{I}(B;U\mid C)}{2\ln2} \\ &\geq\frac{\overline{I}(C;B)}{2\ln2}\left(\frac{1}{\overline{H}(C\mid U)}-\frac{1}{\overline{H}(C)}\right) \\ &=\frac{\overline{I}(C;B)\overline{I}(C;U)}{2\ln2\,\overline{H}(C)\overline{H}(C\mid U)}, \end{aligned}

as required.

When H‾(C∣U)>0\overline{H}(C\mid U)>0, let C′C' be an unbiased bit obtained from BB alone using private randomness and satisfying (B).

Lemma 3.7. If H‾(C∣U)>0\overline{H}(C\mid U)>0, then

Q(C)−I(C:X)≥Δ+H‾(C∣U)(I‾pI(B:C′)−I(A:C′))Q(C)-I(C:X)\geq\Delta+\overline{H}(C\mid U)\left(\overline{I}_p I(B:C')-I(A:C')\right)
+(1−I‾p)I‾(C;B)I‾(C;U)2ln⁡2 H‾(C)H‾(C∣U)−JpI‾(C;B).(5)\qquad+\frac{(1-\overline{I}_p)\overline{I}(C;B)\overline{I}(C;U)}{2\ln2\,\overline{H}(C)\overline{H}(C\mid U)}-J_p\overline{I}(C;B). \tag*{(5)}

Proof. The chain rules for Shannon and Tsallis information give

Q(C)−I(C:X)−Δ=I(C:B∣X)−(1−I‾p)I(B:C)−JpI‾(C;B).Q(C)-I(C:X)-\Delta=I(C:B\mid X)-(1-\overline{I}_p)I(B:C)-J_p\overline{I}(C;B).

The chain rule and Lemma 3.4 give

I(C:B∣X)=I(B:C∣U)−I(A:C∣U)≥(1−I‾p)I(B:C∣U)+H‾(C∣U)[I‾pI(B:C′)−I(A:C′)].\begin{aligned} I(C:B\mid X)=I(B:C\mid U)-I(A:C\mid U) \\ &\geq(1-\overline{I}_p)I(B:C\mid U)+\overline{H}(C\mid U)\left[\overline{I}_p I(B:C')-I(A:C')\right]. \end{aligned}

Substituting this into the preceding identity and applying Lemma 3.6 gives (3.1).

Lemma 3.8. If H‾(C∣U)>0\overline{H}(C\mid U)>0, then

Q(C)−I(C:X)≥H‾(C∣U)I(A:B∣C′)−[(1−I‾p)c(μ)ln⁡2+Jp]I‾(C;U).(6)Q(C)-I(C:X)\geq\overline{H}(C\mid U)I(A:B\mid C')-\left[\frac{(1-\overline{I}_p)c(\mu)}{\ln2}+J_p\right]\overline{I}(C;U). \tag*{(6)}

Proof. Using the comparison in I(C:X)=I(C:U)+I(A:C∣U)I(C:X)=I(C:U)+I(A:C\mid U) gives

Q(C)−I(C:X)≥I‾pH(C)−JpH‾(C)−I(C:U)−H‾(C∣U)I(A:C′)=H‾(C∣U)I(A:B∣C′)+I‾p[H(C∣U)−H‾(C∣U)]\begin{aligned} Q(C)-I(C:X)\geq\overline{I}_pH(C)-J_p\overline{H}(C)-I(C:U)-\overline{H}(C\mid U)I(A:C') \\ &=\overline{H}(C\mid U)I(A:B\mid C')+\overline{I}_p\left[H(C\mid U)-\overline{H}(C\mid U)\right] \end{aligned}
−(1−I‾p)I(C:U)−JpI‾(C;U).\qquad-(1-\overline{I}_p)I(C:U)-J_p\overline{I}(C;U).

Here we used Ip=I(A:B)I_p=I(A:B) and I(A:B∣C′)=I(A:B)−I(A:C′)I(A:B\mid C')=I(A:B)-I(A:C'). Now H(C∣U)≥H‾(C∣U)H(C\mid U)\geq\overline{H}(C\mid U) and Lemma 2.2 give (3.2).

For 0<p<10<p<1, we use the shorthand

αp=Jpln⁡21−I‾p.\alpha_p=\frac{J_p\ln2}{1-\overline{I}_p}.

The following fact about the unbiased chain A−B−C′A-B-C' is the remaining ingredient. We state it here and prove it in § 3.3.

Lemma 3.9. Let C′C' be an unbiased bit obtained from BB using private randomness. If 0<Iˉp<10 < \bar{I}_p < 1 and Iˉ(B;C′)>0\bar{I}(B ; C') > 0, then

Ip−I(A:C′)2(1+αp)+2(IˉpI(B:C′)−I(A:C′))Iˉ(B;C′)≥Jp.\frac{I_p-I(A:C')}{2(1+\alpha_p)}+\frac{2\left(\bar{I}_p I(B:C')-I(A:C')\right)}{\sqrt{\bar{I}(B;C')}}\ge J_p.

Proof of Lemma 3.3. The cases p∈{0,1/2,1}p \in\{0,1/2,1\} are immediate, so we may assume 0<p<1/20 < p < 1/2, complementing YY if necessary. If Iˉ(C;B)=0\bar{I}(C;B)=0, then CC and BB are independent. Consequently Q(C)=Q(C∣B)Q(C)=Q(C\mid B) and I(C:X∣B)≥I(C:X)I(C:X\mid B)\ge I(C:X), proving the claim with λ=0\lambda=0.

We may therefore assume Iˉ(C;B)>0\bar{I}(C;B)>0. Then Hˉ(C∣U)>0\bar{H}(C\mid U)>0: otherwise CC would be determined by UU and hence independent of BB. By Lemma 3.4, there is an unbiased bit C′C' obtained from BB alone and satisfying (B). Let us write

λ=Iˉ(C;B)2Hˉ(C)Hˉ(C∣U)(c(μ)+αp).\lambda=\frac{\bar{I}(C;B)}{2\bar{H}(C)\bar{H}(C\mid U)(c(\mu)+\alpha_p)}.

All factors are positive. When we multiply (6) by λ\lambda and add it to (5), the terms involving Iˉ(C;U)\bar{I}(C;U) cancel, giving

(1+λ)[Q(C)−I(C:X)]≥Q(C∣B)−I(C:X∣B)−JpIˉ(C;B)+Hˉ(C∣U)(IˉpI(B:C′)−I(A:C′))+λHˉ(C∣U)I(A:B∣C′).(7)\begin{aligned} (1+\lambda)\left[Q(C)-I(C:X)\right] &\ge Q(C\mid B)-I(C:X\mid B)-J_p\bar{I}(C;B)\\ &\quad+\bar{H}(C\mid U)\left(\bar{I}_p I(B:C')-I(A:C')\right) +\lambda\bar{H}(C\mid U)I(A:B\mid C'). \tag*{(7)} \end{aligned}

By Lemma 3.5 and the choice of coordinate,

Iˉ(C;B)Hˉ(C∣U)≤Iˉ(C;B)Iˉ(C′;B)≤12Iˉ(C′;B).\frac{\bar{I}(C;B)}{\bar{H}(C\mid U)} \le\sqrt{\bar{I}(C;B)\bar{I}(C';B)} \le\frac{1}{2}\sqrt{\bar{I}(C';B)}.

Also, Lemma 2.2 and 0<Hˉ(C)≤10<\bar{H}(C)\le1 give

Hˉ(C)(c(μ)+αp)≤1+Hˉ(C)αp≤1+αp.\bar{H}(C)(c(\mu)+\alpha_p)\le1+\bar{H}(C)\alpha_p\le1+\alpha_p.

Consequently,

λHˉ(C∣U)Iˉ(C;B)=12Hˉ(C)(c(μ)+αp)≥12(1+αp).\frac{\lambda\bar{H}(C\mid U)}{\bar{I}(C;B)} =\frac{1}{2\bar{H}(C)(c(\mu)+\alpha_p)} \ge\frac{1}{2(1+\alpha_p)}.

The two information quantities multiplied by these coefficients are nonnegative. For the first, the binary divergence series gives I(A:C′)≤Iˉ(A;B)I(B:C′)I(A:C')\le\bar{I}(A;B)I(B:C'); the second is a conditional mutual information. Applying Lemma 3.9, we therefore obtain

Hˉ(C∣U)Iˉ(C;B)(IˉpI(B:C′)−I(A:C′))+λHˉ(C∣U)Iˉ(C;B)I(A:B∣C′)≥Jp.\frac{\bar{H}(C\mid U)}{\bar{I}(C;B)} \left(\bar{I}_p I(B:C')-I(A:C')\right) +\frac{\lambda\bar{H}(C\mid U)}{\bar{I}(C;B)}I(A:B\mid C') \ge J_p.

Thus the last three terms in (7) have nonnegative sum. Dividing by 1+λ1+\lambda proves the lemma. □

The three-bit lemma

In this subsection, let A−B−CA-B-C be an unbiased binary Markov chain with 0<Iˉ(A;B)<10<\bar{I}(A;B)<1 and Iˉ(B;C)>0\bar{I}(B;C)>0. For the calculation, let us write ρ\rho and uu for the absolute correlations of A,BA,B and B,CB,C, respectively, and let

f(t)=D2((1+t)/2∥1/2).f(t)=D_2((1+t)/2\mathbin{\|}1/2).

Thus

I(A:B)=f(ρ),I(B:C)=f(u),I(A:C)=f(ρu),I(A:B∣C)=f(ρ)−f(ρu).I(A:B)=f(\rho),\qquad I(B:C)=f(u),\qquad I(A:C)=f(\rho u),\qquad I(A:B\mid C)=f(\rho)-f(\rho u).

Let us also write

r=ρ2,α=(ρ2−f(ρ))ln⁡21−ρ2.r=\rho^2,\qquad\alpha=\frac{(\rho^2-f(\rho))\ln2}{1-\rho^2}.

In these parameters, it suffices to prove

f(ρ)−f(ρu)2(1+α)+2(ρ2f(u)−f(ρu))u>ρ2−f(ρ).(8)\frac{f(\rho)-f(\rho u)}{2(1+\alpha)}+\frac{2(\rho^2f(u)-f(\rho u))}{u}>\rho^2-f(\rho). \tag*{(8)}

We will prove this by expanding in rr and showing that every coefficient is positive. For integers N≥1N\ge1, let us define the divergence tails

bN=∑k>N12k(2k−1)=∫01x2N1+x dx,sN(u)=∑k>Nu2k2k(2k−1)=∫0u(u−x)x2N1−x2 dx.b_N=\sum_{k>N}\frac{1}{2k(2k-1)}=\int_0^1\frac{x^{2N}}{1+x}\,dx,\qquad s_N(u)=\sum_{k>N}\frac{u^{2k}}{2k(2k-1)}=\int_0^u\frac{(u-x)x^{2N}}{1-x^2}\,dx.

Let us set b0=1b_0=1 as a separate convention, and define

TN=∑i=0N−1bi,BN=∑i=0N−1bibN−i,T_N=\sum_{i=0}^{N-1}b_i,\qquad B_N=\sum_{i=0}^{N-1}b_i b_{N-i},
GN(u)=∑i=0N−1bisN−i(u),CN(u)=∑k=1N1−u2k2k(2k−1).G_N(u)=\sum_{i=0}^{N-1}b_i s_{N-i}(u),\qquad C_N(u)=\sum_{k=1}^{N}\frac{1-u^{2k}}{2k(2k-1)}.

The first ingredient compares the divergence tails in two ways.

Lemma 3.10. For 0<u<10<u<1 and N≥1N\ge1,

GN(u)≥BNsN(u)bN.(9)G_N(u)\ge B_N\frac{s_N(u)}{b_N}. \tag*{(9)}

For N≥2N\ge2, we also have

sN(u)ubN≥s2(uN/2)uN/2b2.(10)\frac{s_N(u)}{u b_N}\ge\frac{s_2(u^{N/2})}{u^{N/2}b_2}. \tag*{(10)}

Proof. First, sj(u)/bjs_j(u)/b_j is the expectation of the decreasing function (u−x)+/(1−x)(u-x)_+/(1-x) under the probability density proportional to x2j/(1+x)x^{2j}/(1+x) on (0,1)(0,1). Increasing jj tilts this density by an increasing function, so sj(u)/bjs_j(u)/b_j decreases with jj. For 1≤j≤N1\le j\le N, therefore, sj(u)≥bjsN(u)/bNs_j(u)\ge b_j s_N(u)/b_N; summing proves (9). Here is the elementary order principle used in this argument. If Z,Z′Z,Z' are independent with the same distribution, then

Cov⁡(f(Z),g(Z))=12E[(f(Z)−f(Z′))(g(Z)−g(Z′))].\operatorname{Cov}(f(Z),g(Z))=\frac{1}{2}\mathbb{E}\left[(f(Z)-f(Z'))(g(Z)-g(Z'))\right].

It is nonnegative when both functions increase and nonpositive when one increases and the other decreases. Applying this identity to a density ratio gives the stated comparison of expectations. For the second comparison, let us fix a≥0a\ge0 and write

MN(a)=sN(e−a/N)e−a/NbN.M_N(a)=\frac{s_N(e^{-a/N})}{e^{-a/N}b_N}.

Changing variables in the two tail integrals gives

MN(a)=e−2aEπN[sinh⁡(z/N)sinh⁡((z+a)/N)],πN(dz)∝e−2z1+ez/N dz,z>0.(11)M_N(a)=e^{-2a}\mathbb{E}_{\pi_N}\left[\frac{\sinh(z/N)}{\sinh((z+a)/N)}\right],\qquad\pi_N(dz)\propto\frac{e^{-2z}}{1+e^{z/N}}\,dz,\quad z>0. \tag*{(11)}

The quotient inside the expectation increases with zz because coth⁡\coth decreases. It also increases with NN, since xcoth⁡xx\coth x increases for x>0x>0: its derivative has the sign of sinh⁡xcosh⁡x−x>0\sinh x\cosh x-x>0. Moreover, for K>NK>N the density ratio πK/πN\pi_K/\pi_N increases with zz, as its logarithmic derivative is

N−11+e−z/N−K−11+e−z/K>0.\frac{N^{-1}}{1+e^{-z/N}}-\frac{K^{-1}}{1+e^{-z/K}}>0.

The order principle and then the pointwise comparison of quotients show that MN(a)M_N(a) increases with NN. Taking a=−Nln⁡ua=-N\ln u gives e−a/N=ue^{-a/N}=u and e−a/2=uN/2e^{-a/2}=u^{N/2}, proving (10). All the densities are integrable; at a=0a=0 the quotient in (11) equals one.

The second ingredient gives estimates uniform in the coefficient index NN. Let us write

eN=12∑k=1N12k−1,RN=2TN−1,x=1−u2N.e_N=\frac{1}{2}\sum_{k=1}^{N}\frac{1}{2k-1},\qquad R_N=2T_N-1,\qquad x=1-u^{2^N}.

Lemma 3.11. For N≥2N\ge2 and 0≤u≤10\le u\le1,

BN≤bNRN,RN2eN<1918,CN(u)2eNbN≥2x+34x2+18x3.B_N\le b_NR_N,\qquad\frac{R_N}{2e_N}<\frac{19}{18},\qquad\frac{C_N(u)}{2e_Nb_N}\ge2x+\frac{3}{4}x^2+\frac{1}{8}x^3.

Proof. The tail integral and finite summation give

14N+2≤bN≤14N+1,TN=1−ln⁡2+eN+NbN.\frac{1}{4N+2}\le b_N\le\frac{1}{4N+1},\qquad T_N=1-\ln2+e_N+Nb_N.

Indeed, the integral bounds follow from 1+x≤21+x\le2 and 1+x≥2x1+x\ge2\sqrt{x}. For positive integers i,ji,j, they imply

bi−1+bj−1≥4(i+j)+2≥bi+j−1,bibj≤bi+j(bi+bj).b_i^{-1}+b_j^{-1}\ge4(i+j)+2\ge b_{i+j}^{-1},\qquad b_ib_j\le b_{i+j}(b_i+b_j).

Summing over i+j=Ni+j=N and including the b0bN=bNb_0b_N=b_N term proves BN≤bNRNB_N\le b_NR_N. For the second bound, let us write t=2/N∈(0,1]t=\sqrt{2/N}\in(0,1]. We will use

eN≥76−t2≥1−t3.(12)e_N\ge\frac{7}{6}-\frac{t}{2}\ge1-\frac{t}{3}. \tag*{(12)}

The first inequality is equality at N=2N=2. Its right-hand side increases from NN to N+1N+1 by at most eN+1−eN=1/(4N+2)e_{N+1}-e_N=1/(4N+2), because

NN+1(N+N+1)≥(2N+1)N≥(2N+1)2.\sqrt{N}\sqrt{N+1}(\sqrt{N}+\sqrt{N+1})\ge(2N+1)\sqrt{N}\ge(2N+1)\sqrt{2}.

This proves the first inequality by induction; the second uses t≤1t\le1. We also have

913<ln⁡2<2536.\frac{9}{13}<\ln2<\frac{25}{36}.

For the lower bound, the first three terms of ln⁡2=2∑j≥0((2j+1)32j+1)−1\ln2=2\sum_{j\ge0}((2j+1)3^{2j+1})^{-1} sum to 842/1215>9/13842/1215>9/13. Replacing 2j+12j+1 by 33 for every j≥1j\ge1 and summing the resulting geometric series gives the upper bound. Writing γ=ln⁡2−1/2>5/26\gamma=\ln2-1/2>5/26, we obtain

NbN≤14+t2/2≤14−t236,Nb_N\le\frac{1}{4+t^2/2}\le\frac{1}{4}-\frac{t^2}{36},
18NbN−eN≤103+t−t22≤8324<4513<18γ.18Nb_N-e_N\le\frac{10}{3}+\frac{t-t^2}{2}\le\frac{83}{24}<\frac{45}{13}<18\gamma.

Since RN=2eN+2NbN−2γR_N=2e_N+2Nb_N-2\gamma, this is equivalent to RN/(2eN)<19/18R_N/(2e_N)<19/18. For the third bound, we use the first three nonnegative terms of the binomial expansion of 1−(1−x)a1-(1-x)^a, where 0<a≤10<a\le1. Let us write s=1/N=t2/2s=1/N=t^2/2 and e=eNe=e_N. The moment identities

∑k=1Nk2(2k−1)=N4+eN2,∑k=1Nk22(2k−1)=N(N+2)8+eN4\sum_{k=1}^{N}\frac{k}{2(2k-1)}=\frac{N}{4}+\frac{e_N}{2},\qquad\sum_{k=1}^{N}\frac{k^2}{2(2k-1)}=\frac{N(N+2)}{8}+\frac{e_N}{4}

follow by dividing the rational summands. Together with bN≤1/(4N+1)b_N\le1/(4N+1), they yield

CN(u)2eNbN≥4+s2[x+θ2x2+θ3x3],(13)\frac{C_N(u)}{2e_Nb_N}\ge\frac{4+s}{2}\left[x+\theta_2x^2+\theta_3x^3\right], \tag*{(13)}
θ2=12−s4−18e,θ3=13−s4+s224−5−2s48e.\theta_2=\frac{1}{2}-\frac{s}{4}-\frac{1}{8e},\qquad\theta_3=\frac{1}{3}-\frac{s}{4}+\frac{s^2}{24}-\frac{5-2s}{48e}.

By (12),

e−1≤(1−t/3)−1≤1+t/2.e^{-1}\le(1-t/3)^{-1}\le1+t/2.

Let a2=(4+s)θ2/2−3/4a_2=(4+s)\theta_2/2-3/4 and a3=(4+s)θ3/2−1/8a_3=(4+s)\theta_3/2-1/8. Substitution gives

a2≥−t8−5t232−t364−t432≥−21t64≥−t3,a_2\ge-\frac{t}{8}-\frac{5t^2}{32}-\frac{t^3}{64}-\frac{t^4}{32}\ge-\frac{21t}{64}\ge-\frac{t}{3},
a3−(13−t4)≥t384[2(1−t)(28−t)+t2((1−t)2+t3)]≥0.a_3-\left(\frac{1}{3}-\frac{t}{4}\right)\ge\frac{t}{384}\left[2(1-t)(28-t)+t^2\left((1-t)^2+t^3\right)\right]\ge0.

Consequently, the difference between the right-hand side of (13) and 2x+3x2/4+x3/82x+3x^2/4+x^3/8 is bounded below by

x[t24−tx3+(13−t4)x2]=x12[3(t−x)2+2tx(1−x)+x2(1−t)]x\left[\frac{t^2}{4}-\frac{tx}{3}+\left(\frac{1}{3}-\frac{t}{4}\right)x^2\right]=\frac{x}{12}\left[3(t-x)^2+2tx(1-x)+x^2(1-t)\right]
≥0.\ge0.

This proves the last bound.

The preceding estimates will reduce every coefficient of index at least two to the function

J(w)=5572−31w48+9w88−w128+38s2(w)w,0<w<1.\mathcal{J}(w)=\frac{55}{72}-\frac{31w^4}{8}+\frac{9w^8}{8}-\frac{w^{12}}{8}+38\frac{s_2(w)}{w},\qquad0<w<1.

Lemma 3.12. For 0<w<10<w<1, we have J(w)>0\mathcal{J}(w)>0.

Proof. Let us write g(w)=s2(w)/wg(w)=s_2(w)/w. Differentiation gives

g′(w)=−ln⁡(1−w2)2w2−12−w24=∑k≥3w2k−22k,g'(w)=-\frac{\ln(1-w^2)}{2w^2}-\frac{1}{2}-\frac{w^2}{4}=\sum_{k\ge3}\frac{w^{2k-2}}{2k},
g′′(w)=1w(1−w2)+ln⁡(1−w2)w3−w2.g''(w)=\frac{1}{w(1-w^2)}+\frac{\ln(1-w^2)}{w^3}-\frac{w}{2}.

Thus

J′(w)w3=−312+9w4−32w8+19∑k≥3w2k−5k\frac{\mathcal{J}'(w)}{w^3}=-\frac{31}{2}+9w^4-\frac{3}{2}w^8+19\sum_{k\ge3}\frac{w^{2k-5}}{k}

is strictly increasing on (0,1)(0,1). Also g′′′(w)>0g'''(w)>0, and for w≥4/5w\ge4/5,

(−31w48+9w88−w128)′′′=w(−93+378w4−165w8)>0.\left(-\frac{31w^4}{8}+\frac{9w^8}{8}-\frac{w^{12}}{8}\right)'''=w(-93+378w^4-165w^8)>0.

Indeed, the quadratic −93+378z−165z2-93+378z-165z^2 increases on [0,1][0,1] and is positive at z=2/5<(4/5)4z=2/5<(4/5)^4. Hence J′′′(w)>0\mathcal{J}'''(w)>0 for w≥4/5w\ge4/5. We need four finite estimates:

J′(4/5)<0,J′′(4/5)>25,J(5/6)>1256,∣J′(5/6)∣<15.(14)\mathcal{J}'(4/5)<0,\qquad\mathcal{J}''(4/5)>25,\qquad\mathcal{J}(5/6)>\frac{1}{256},\qquad|\mathcal{J}'(5/6)|<\frac{1}{5}. \tag*{(14)}

For completeness, the following rational bounds certify them. For z>1z>1, let us write v=(z−1)/(z+1)v=(z-1)/(z+1) and define

P(z)=2∑j=05v2j+12j+1,E(z)=2v1313(1−v2).P(z)=2\sum_{j=0}^{5}\frac{v^{2j+1}}{2j+1},\qquad E(z)=\frac{2v^{13}}{13(1-v^2)}.

The logarithm series gives P(z)<ln⁡z<P(z)+E(z)P(z)<\ln z<P(z)+E(z). Only z∈{2,3/2,5/4,11/8}z\in\{2,3/2,5/4,11/8\} are needed, using

ln⁡(9/25)=2ln⁡(3/2)−2ln⁡(5/4)−2ln⁡2,\ln(9/25)=2\ln(3/2)-2\ln(5/4)-2\ln2,
ln⁡(11/36)=ln⁡(11/8)−2ln⁡(3/2)−ln⁡2,\ln(11/36)=\ln(11/8)-2\ln(3/2)-\ln2,
(ln⁡2)D2(11/12∥1/2)=34ln⁡2+1112ln⁡(11/8)−ln⁡(3/2).(\ln2)D_2(11/12\mathbin{\|}1/2)=\frac{3}{4}\ln2+\frac{11}{12}\ln(11/8)-\ln(3/2).

Substituting the appropriate lower or upper bound for each logarithm in the displayed formulas for g′g', g′′g'', and

g(w)=(ln⁡2)D2((1+w)/2∥1/2)−w2/2−w4/12w.g(w) = \frac{(\ln2)D_2\left((1+w)/2 \mathbin{\|} 1/2\right)-w^2/2-w^4/12}{w}.

gives

quantitystrict lower boundstrict upper bound
J′(4/5)\mathcal{J}'(4/5)−1-1−9/10-9/10
J′′(4/5)\mathcal{J}''(4/5)25252626
J(5/6)\mathcal{J}(5/6)9/20009/20001/2001/200
J′(5/6)\mathcal{J}'(5/6)9/509/5019/10019/100

These are finite rational comparisons and imply (14). Since J′′′\mathcal{J}''' is positive on [4/5,1)[4/5,1), we have J′′>25\mathcal{J}''>25 there. Taylor’s formula at 5/65/6 therefore gives

J(w)≥J(5/6)+J′(5/6)(w−5/6)+252(w−5/6)2>1256−11250>0(4/5≤w<1).\begin{aligned} \mathcal{J}(w) \ge\mathcal{J}(5/6)+\mathcal{J}'(5/6)(w-5/6)+\frac{25}{2}(w-5/6)^2 \\ &> \frac{1}{256}-\frac{1}{1250}>0 \qquad(4/5\le w<1). \end{aligned}

On (0,4/5](0,4/5], the increasing ratio J′(w)/w3\mathcal{J}'(w)/w^3 and the inequality J′(4/5)<0\mathcal{J}'(4/5)<0 show that J\mathcal{J} decreases. Its value there is consequently at least J(4/5)>0\mathcal{J}(4/5)>0.

We now apply these estimates to the coefficients

cN(u)=CN(u)+4GN(u)u−2BN,N≥1,0<u≤1.c_N(u)=C_N(u)+\frac{4G_N(u)}{u}-2B_N,\qquad N\ge1,\qquad0<u\le1.

Lemma 3.13. For every integer N≥1N\ge1 and 0<u≤10<u\le1, we have cN(u)>0c_N(u)>0.

Proof. For N≥2N\ge2 and 0<u<10<u<1, let us write

k=4sN(u)ubN−2,w=uN/2,x=1−w4.k=\frac{4s_N(u)}{u b_N}-2,\qquad w=u^{N/2},\qquad x=1-w^4.

By Lemma 3.10, cN(u)≥CN(u)+BNkc_N(u)\ge C_N(u)+B_Nk. If k≥0k\ge0, this is positive because CN(u)>0C_N(u)>0. If k<0k<0, Lemma 3.11 gives

cN(u)2eNbN≥CN(u)2eNbN+RN2eNk\frac{c_N(u)}{2e_Nb_N}\ge\frac{C_N(u)}{2e_Nb_N}+\frac{R_N}{2e_N}k
≥2x+34x2+18x3+1918k.\ge2x+\frac{3}{4}x^2+\frac{1}{8}x^3+\frac{19}{18}k.

Here the upper bounds on BNB_N and RN/(2eN)R_N/(2e_N) give lower bounds after multiplication by the negative number kk. Since b2=ln⁡2−7/12<1/9b_2=\ln2-7/12<1/9, the rescaled tail comparison gives

k≥36s2(w)w−2.k\ge36\frac{s_2(w)}{w}-2.

Substituting this and x=1−w4x=1-w^4 into the preceding lower bound gives exactly J(w)>0\mathcal{J}(w)>0. For u=1u=1, we instead have sj(1)=bjs_j(1)=b_j and CN(1)=0C_N(1)=0, so cN(1)=2BN>0c_N(1)=2B_N>0. It remains to treat N=1N=1. Writing γ=ln⁡2−1/2<7/36\gamma=\ln2-1/2<7/36 and retaining the first two terms of s1(u)s_1(u) gives

c1(u)=1−u22+4s1(u)u−2γ≥Z(u):=19−u22+u33+2u515.\begin{aligned} c_1(u)=\frac{1-u^2}{2}+\frac{4s_1(u)}{u}-2\gamma\\ &\ge Z(u):=\frac{1}{9}-\frac{u^2}{2}+\frac{u^3}{3}+\frac{2u^5}{15}. \end{aligned}

To see that Z>0Z>0, note that Z′(u)/u=−1+u+2u3/3Z'(u)/u=-1+u+2u^3/3 increases and is negative at u=2/3u=2/3. Also Z′′(u)=−1+2u+8u3/3>1Z''(u)=-1+2u+8u^3/3>1 on [2/3,1][2/3,1]. At a=3/4a=3/4,

Z(a)=4923040>1512,Z′(a)=3128<132.Z(a)=\frac{49}{23040}>\frac{1}{512},\qquad Z'(a)=\frac{3}{128}<\frac{1}{32}.

Taylor’s formula on [2/3,1][2/3,1] yields

Z(u)≥Z(a)+Z′(a)(u−a)+12(u−a)2>1512−12048>0.Z(u) \ge Z(a) + Z'(a)(u-a) + \frac{1}{2}(u-a)^2 > \frac{1}{512} - \frac{1}{2048} > 0.

On (0,2/3](0,2/3], the monotonicity of Z′(u)/uZ'(u)/u makes ZZ decreasing, so Z(u)≥Z(2/3)>0Z(u) \ge Z(2/3) > 0 there as well.

Lemma 3.9 (restated).

I(A:B∣C)2(1+ln⁡2Iˉ(A;B)−I(A:B)H(Aˉ∣B))+2[Iˉ(A;B)I(B:C)−I(A:C)]Iˉ(B;C)≥Iˉ(A;B)−I(A:B).\frac{I(A:B\mid C)}{2\left(1+\ln2\frac{\bar I(A;B)-I(A:B)}{H(\bar A\mid B)}\right)}+\frac{2\left[\bar I(A;B)I(B:C)-I(A:C)\right]}{\sqrt{\bar I(B;C)}}\ge\bar I(A;B)-I(A:B).

Proof. The divergence-tail definitions give the absolutely convergent expansions

α=∑N≥1bNrN,\alpha=\sum_{N\ge1}b_Nr^N,
ln⁡21−ρ2[ρ2f(u)−f(ρu)]=∑N≥1sN(u)rN,\frac{\ln2}{1-\rho^2}\left[\rho^2f(u)-f(\rho u)\right]=\sum_{N\ge1}s_N(u)r^N,
ln⁡21−ρ2[f(ρ)−f(ρu)]=∑N≥1cN(u)rN.\frac{\ln2}{1-\rho^2}\left[f(\rho)-f(\rho u)\right]=\sum_{N\ge1}c_N(u)r^N.

In particular, α>0\alpha>0. Multiplying these series, with the convention b0=1b_0=1, gives

ln⁡21−ρ2[f(ρ)−f(ρu)+4(1+α)(ρ2f(u)−f(ρu))u−2(ρ2−f(ρ))(1+α)]=∑N≥1cN(u)rN.\frac{\ln2}{1-\rho^2}\left[f(\rho)-f(\rho u)+\frac{4(1+\alpha)\left(\rho^2f(u)-f(\rho u)\right)}{u}-2\left(\rho^2-f(\rho)\right)(1+\alpha)\right]=\sum_{N\ge1}c_N(u)r^N.

Every coefficient on the right is positive by Lemma 3.13. Since 0<r<10<r<1, the expression in brackets is positive. Dividing it by 2(1+α)2(1+\alpha) proves (8).

Statement on AI use

The proof has been obtained with interactive collaboration with GPT-6 Astra and DeepSeek-V4.1-Flash.

Remaining proofs

We use the setup of § 1.3.

Lemma A.1. For the threshold bit TμT_\mu defined in § 1.3, we have

Q(Tμ)≤I(Tμ:X∘).Q(T_\mu)\le I(T_\mu:X_\circ).

For 0<p<1/20<p<1/2, equality holds exactly when μ∈{0,1/2,1}\mu\in\{0,1/2,1\}. At p=0,1/2p=0,1/2, equality holds for every μ\mu.

Proof. The cases p∈{0,1/2}p\in\{0,1/2\} or μ∈{0,1/2,1}\mu\in\{0,1/2,1\} follow directly. Let us fix 0<μ<10<\mu<1, μ≠1/2\mu\ne1/2, and write

ρ=1−2p,F(ρ)=I(Tμ:X∘)−Hˉ(Tμ)Ip.\rho=1-2p,\qquad F(\rho)=I(T_\mu:X_\circ)-\bar H(T_\mu)I_p.

We have F(0)=F′(0)=0F(0)=F'(0)=0, F(1)=H(Tμ)−Hˉ(Tμ)F(1)=H(T_\mu)-\bar H(T_\mu), and differentiation gives

F′′(ρ)=Hˉ(Tμ)(1−Hˉ(Tμ))(1−ρ)ln⁡2(1+ρ)(4ρ+H(Tμ)(1−ρ)2).F''(\rho)=\frac{\bar H(T_\mu)(1-\bar H(T_\mu))(1-\rho)}{\ln2(1+\rho)(4\rho+H(T_\mu)(1-\rho)^2)}.

This is strictly decreasing: the numerator decreases and both factors in the denominator increase. Hence, for 0<ρ<10 < \rho< 1,

F(ρ)ρ2=∫01(1−t)F′′(ρt) dt>F(1).\frac{F(\rho)}{\rho^2}=\int_0^1(1-t)F''(\rho t)\,\mathrm{d}t>F(1).

Since Iˉp=ρ2\bar I_p=\rho^2, this is precisely I(Tμ:X∘)>Q(Tμ)\mathbf{I}(T_\mu:X_\circ)>Q(T_\mu).

We prove the properties of the comparison function used in § 3.1 and the estimate used in Lemma 3.5. All endpoint expressions are understood by continuity.

For the following calculations, let us write

f(t)=D2((1+t)/2∥1/2)=∑k≥1t2k2k(2k−1)ln⁡2,−1≤t≤1.f(t)=\mathbf{D}_2((1+t)/2\mathbin\Vert1/2)=\sum_{k\geq1}\frac{t^{2k}}{2k(2k-1)\ln2},\qquad-1\leq t\leq1.

Thus ff is even, convex, and strictly increasing on [0,1][0,1]. Its nonnegative coefficients sum to one, so f(t)≤t2f(t)\leq t^2.

Let A,BA,B be unbiased bits, with absolute correlation ρ\rho. Let CC be a nonconstant bit such that A−B−CA-B-C is a Markov chain, and write

V=Hˉ(C),d=E[(2B−1)(2C−1)].V=\bar H(C),\qquad d=\mathbb{E}[(2B-1)(2C-1)].

We define FρF_\rho on [0,1][0,1] by

Fρ(f(t))=f(ρt),0≤t≤1.F_\rho(f(t))=f(\rho t),\qquad0\leq t\leq1.

Lemma A.2. The function FρF_\rho is increasing and concave, and

I(B:C)≤V,I(A:C)≤VFρ(I(B:C)V).\mathbf{I}(B:C)\leq V,\qquad\mathbf{I}(A:C)\leq VF_\rho\left(\frac{\mathbf{I}(B:C)}{V}\right).

Moreover,

∣d∣≤V,I(B:C)≥Vf(d/V).|d|\leq V,\qquad\mathbf{I}(B:C)\geq Vf(d/V).

Proof. Let us write x=E[2C−1]x=\mathbb{E}[2C-1], so ∣x∣+∣d∣≤1|x|+|d|\leq1 and V=1−x2V=1-x^2. Bayes’ rule gives

I(B:C)=1+x2f(d1+x)+1−x2f(d1−x)=:ℓ(x,d),\mathbf{I}(B:C)=\frac{1+x}{2}f\left(\frac{d}{1+x}\right)+\frac{1-x}{2}f\left(\frac{d}{1-x}\right)=:\ell(x,d),
I(A:C)=ℓ(x,ρd).\mathbf{I}(A:C)=\ell(x,\rho d).

Relabeling AA if necessary makes its correlation with BB nonnegative and does not change either information. Since f(t)≤t2f(t)\leq t^2,

ℓ(x,d)≤d2V≤V,\ell(x,d)\leq\frac{d^2}{V}\leq V,

where ∣d∣≤1−∣x∣≤V|d|\leq1-|x|\leq V proves the second inequality.

The divergence series also gives

ℓ(x,d)V=∑k≥1Wk(x)(d/V)2k2k(2k−1)ln⁡2,Wk(x)=(1+x)2k−1+(1−x)2k−12.\frac{\ell(x,d)}{V}=\sum_{k\geq1}\frac{W_k(x)(d/V)^{2k}}{2k(2k-1)\ln2},\qquad W_k(x)=\frac{(1+x)^{2k-1}+(1-x)^{2k-1}}{2}.

Here W1=1W_1=1 and Wk≥1W_k\geq1. This proves ℓ(x,d)≥Vf(d/V)\ell(x,d)\geq Vf(d/V), as required for the lower bound.

Let us choose τ∈[0,1]\tau\in[0,1] so that f(τ)=ℓ(x,d)/Vf(\tau)=\ell(x,d)/V. Cauchy–Schwarz gives Wk2≤Wk−1Wk+1W_k^2\leq W_{k-1}W_{k+1} for $k\geq 2. Together with W1=1W_1=1 and Wk≥1W_k\geq1, this implies that WkW_k is nondecreasing. Indeed, successive differences of ln⁡Wk\ln W_k are nondecreasing, so

ln⁡Wk+1−ln⁡Wk≥ln⁡Wkk−1(k≥2).\ln W_{k+1}-\ln W_k\geq\frac{\ln W_k}{k-1}\qquad(k\geq2).

Consequently the terms

Wk(x)(d/V)2k−τ2k2k(2k−1)ln⁡2\frac{W_k(x)(d/V)^{2k}-\tau^{2k}}{2k(2k-1)\ln2}

change sign at most once, from negative to positive. Their absolutely convergent sum is zero by the choice of τ\tau. Multiplication by the decreasing weights ρ2k\rho^{2k} therefore gives a nonpositive sum: subtracting a weight at the sign change makes each summand nonpositive. Thus

ℓ(x,ρd)≤Vf(ρτ)=VFρ(ℓ(x,d)V).\ell(x,\rho d) \le V f(\rho\tau) = V F_\rho\left(\frac{\ell(x,d)}{V}\right).

The cases with no sign change, and ρ=0,1\rho=0,1, follow directly.

It remains to prove concavity. For y=f(t)y=f(t) with 0<t<10<t<1,

Fρ′(y)=ρ2∑j≥0ρ2jt2j/(2j+1)∑j≥0t2j/(2j+1)≥0.F_\rho'(y)=\rho^2\frac{\sum_{j\geq0}\rho^{2j}t^{2j}/(2j+1)}{\sum_{j\geq0}t^{2j}/(2j+1)}\geq0.

This ratio decreases with tt: differentiating and pairing terms indexed by j,kj,k gives factors (j−k)(ρ2j−ρ2k)≤0(j-k)(\rho^{2j}-\rho^{2k})\leq0. Since yy increases with tt, the derivative decreases with yy. Continuity gives the assertion on [0,1][0,1]. □

Finally, the lower pointwise comparison averages in the same way. In the setup of § 3.1, let us write v=Hˉ(C∣U)>0v=\bar{H}(C\mid U)>0 and d=E[(2B−1)(2C−1)]d=\mathbb{E}[(2B-1)(2C-1)]. For each value uu of UU, let us write VuV_u and dud_u for the corresponding conditional entropy and correlation. Independence of BB and UU gives Eu∼Udu=d\mathbb{E}_{u\sim U}d_u=d. Since ∣du∣≤Vu\lvert d_u\rvert\leq V_u, we have ∣d∣≤v\lvert d\rvert\leq v. Jensen’s inequality for the convex function ff, with weights Vu/vV_u/v, gives

I(B:C∣U)≥Eu∼U[Vuf(du/Vu)]≥vf(d/v).\mathbf{I}(B:C\mid U)\geq\mathbb{E}_{u\sim U}[V_u f(d_u/V_u)]\geq v f(d/v).

Values with Vu=0V_u=0 have du=0d_u=0 and contribute zero.

Shannon and Tsallis information

Lemma B.1. For a∈[0,1]a\in[0,1] and b∈[1/2,1)b\in[1/2,1),

2(a−b)2ln⁡2≤D2(a∥b)≤ln⁡(1/b)(1−b)2ln⁡2(a−b)2.\frac{2(a-b)^2}{\ln2}\leq D_2(a\mathbin\Vert b)\leq\frac{\ln(1/b)}{(1-b)^2\ln2}(a-b)^2.

The lower bound holds for every b∈(0,1)b\in(0,1); complementing a,ba,b gives the corresponding upper bound for b<1/2b<1/2.

Proof. The second derivative of the divergence in aa is 1/(a(1−a)ln⁡2)≥4/ln⁡21/(a(1-a)\ln2)\geq4/\ln2, and its value and first derivative vanish at a=ba=b. This proves the lower bound. For the upper bound, Taylor’s integral formula gives

D2(a∥b)(a−b)2=1ln⁡2∫011−t(b+t(a−b))(1−b−t(a−b)) dt.\frac{D_2(a\mathbin\Vert b)}{(a-b)^2}=\frac{1}{\ln2}\int_0^1\frac{1-t}{(b+t(a-b))(1-b-t(a-b))}\,\mathrm{d}t.

The quotient extends continuously to a=ba=b and is convex in aa, because 1/(x(1−x))=1/x+1/(1−x)1/(x(1-x))=1/x+1/(1-x) is convex. It therefore attains its maximum at an endpoint. For b≥1/2b\geq1/2, the value at a=1a=1 is at least the value at a=0a=0: equivalently,

−b2ln⁡b+(1−b)2ln⁡(1−b)≥0.-b^2\ln b+(1-b)^2\ln(1-b)\geq0.

The expression vanishes at b=1/2b=1/2 and b=1b=1, and its second derivative is 2ln⁡((1−b)/b)≤02\ln((1-b)/b)\leq0 on this interval. The value at a=1a=1 is the claimed coefficient. □

For bits, we write Dˉ2(a∥b)=4(a−b)2\bar{D}_2(a\mathbin\Vert b)=4(a-b)^2 and Hˉ(a)=4a(1−a)\bar{H}(a)=4a(1-a). The binary divergence has the expansion

D2(1+u2∥12)=∑k≥1u2k2k(2k−1)ln⁡2,−1≤u≤1.(15)D_2\left(\frac{1+u}{2}\mathbin\Vert\frac{1}{2}\right)=\sum_{k\geq1}\frac{u^{2k}}{2k(2k-1)\ln2},\qquad-1\leq u\leq1. \tag*{(15)}

Indeed, expanding its second derivative 1/((1−u2)ln⁡2)1/((1-u^2)\ln2) as a geometric series and integrating twice proves the identity for ∣u∣<1\lvert u\rvert<1; continuity gives the endpoints. The coefficients ck=1/(2k(2k−1)ln⁡2)c_k=1/(2k(2k-1)\ln2) are nonnegative and satisfy ∑kck=1\sum_k c_k=1 (set u=1u=1). Hence,

D2(1+u2∥12)=∑k≥1cku2k≤u2=Dˉ2(1+u2∥12),D_2\left(\frac{1+u}{2}\mathbin\Vert\frac{1}{2}\right)=\sum_{k\geq1}c_k u^{2k}\leq u^2=\bar{D}_2\left(\frac{1+u}{2}\mathbin\Vert\frac{1}{2}\right),

@page 14/17 starts_mid=1 ends_mid=1 change sign at most once, from negative to positive. Their absolutely convergent sum is zero by the choice of τ\tau. Multiplication by the decreasing weights ρ2k\rho^{2k} therefore gives a nonpositive sum: subtracting a weight at the sign change makes each summand nonpositive. Thus

ℓ(x,ρd)≤Vf(ρτ)=VFρ(ℓ(x,d)V).\ell(x,\rho d) \leq V f(\rho\tau) = V F_\rho\left(\frac{\ell(x,d)}{V}\right).

The cases with no sign change, and ρ=0,1\rho=0,1, follow directly.

It remains to prove concavity. For y=f(t)y=f(t) with 0<t<10<t<1,

Fρ′(y)=ρ2∑j≥0ρ2jt2j/(2j+1)∑j≥0t2j/(2j+1)≥0.F_\rho'(y)=\rho^2\frac{\sum_{j\geq0}\rho^{2j}t^{2j}/(2j+1)}{\sum_{j\geq0}t^{2j}/(2j+1)}\geq0.

This ratio decreases with tt: differentiating and pairing terms indexed by j,kj,k gives factors (j−k)(ρ2j−ρ2k)≤0(j-k)(\rho^{2j}-\rho^{2k})\leq0. Since yy increases with tt, the derivative decreases with yy. Continuity gives the assertion on [0,1][0,1]. □

Finally, the lower pointwise comparison averages in the same way. In the setup of § 3.1, let us write v=Hˉ(C∣U)>0v=\bar{H}(C\mid U)>0 and d=E[(2B−1)(2C−1)]d=\mathbb{E}[(2B-1)(2C-1)]. For each value uu of UU, let us write VuV_u and dud_u for the corresponding conditional entropy and correlation. Independence of BB and UU gives Eu∼Udu=d\mathbb{E}_{u\sim U}d_u=d. Since ∣du∣≤Vu\lvert d_u\rvert\leq V_u, we have ∣d∣≤v\lvert d\rvert\leq v. Jensen’s inequality for the convex function ff, with weights Vu/vV_u/v, gives

I(B:C∣U)≥Eu∼U[Vuf(du/Vu)]≥vf(d/v).\mathbf{I}(B:C\mid U)\geq\mathbb{E}_{u\sim U}[V_u f(d_u/V_u)]\geq v f(d/v).

Values with Vu=0V_u=0 have du=0d_u=0 and contribute zero.

Shannon and Tsallis information

Lemma B.1. For a∈[0,1]a\in[0,1] and b∈[1/2,1)b\in[1/2,1),

2(a−b)2ln⁡2≤D2(a∥b)≤ln⁡(1/b)(1−b)2ln⁡2(a−b)2.\frac{2(a-b)^2}{\ln2}\leq D_2(a\mathbin\Vert b)\leq\frac{\ln(1/b)}{(1-b)^2\ln2}(a-b)^2.

The lower bound holds for every b∈(0,1)b\in(0,1); complementing a,ba,b gives the corresponding upper bound for b<1/2b<1/2.

Proof. The second derivative of the divergence in aa is 1/(a(1−a)ln⁡2)≥4/ln⁡21/(a(1-a)\ln2)\geq4/\ln2, and its value and first derivative vanish at a=ba=b. This proves the lower bound. For the upper bound, Taylor’s integral formula gives

D2(a∥b)(a−b)2=1ln⁡2∫011−t(b+t(a−b))(1−b−t(a−b)) dt.\frac{D_2(a\mathbin\Vert b)}{(a-b)^2}=\frac{1}{\ln2}\int_0^1\frac{1-t}{(b+t(a-b))(1-b-t(a-b))}\,\mathrm{d}t.

The quotient extends continuously to a=ba=b and is convex in aa, because 1/(x(1−x))=1/x+1/(1−x)1/(x(1-x))=1/x+1/(1-x) is convex. It therefore attains its maximum at an endpoint. For b≥1/2b\geq1/2, the value at a=1a=1 is at least the value at a=0a=0: equivalently,

−b2ln⁡b+(1−b)2ln⁡(1−b)≥0.-b^2\ln b+(1-b)^2\ln(1-b)\geq0.

The expression vanishes at b=1/2b=1/2 and b=1b=1, and its second derivative is 2ln⁡((1−b)/b)≤02\ln((1-b)/b)\leq0 on this interval. The value at a=1a=1 is the claimed coefficient. □

For bits, we write Dˉ2(a∥b)=4(a−b)2\bar{D}_2(a\mathbin\Vert b)=4(a-b)^2 and Hˉ(a)=4a(1−a)\bar{H}(a)=4a(1-a). The binary divergence has the expansion

D2(1+u2∥12)=∑k≥1u2k2k(2k−1)ln⁡2,−1≤u≤1.(16)D_2\left(\frac{1+u}{2}\mathbin\Vert\frac{1}{2}\right)=\sum_{k\geq1}\frac{u^{2k}}{2k(2k-1)\ln2},\qquad-1\leq u\leq1. \tag*{(16)}

Indeed, expanding its second derivative 1/((1−u2)ln⁡2)1/((1-u^2)\ln2) as a geometric series and integrating twice proves the identity for ∣u∣<1\lvert u\rvert<1; continuity gives the endpoints. The coefficients ck=1/(2k(2k−1)ln⁡2)c_k=1/(2k(2k-1)\ln2) are nonnegative and satisfy ∑kck=1\sum_k c_k=1 (set u=1u=1). Hence,

D2(1+u2∥12)=∑k≥1cku2k≤u2=Dˉ2(1+u2∥12),D_2\left(\frac{1+u}{2}\mathbin\Vert\frac{1}{2}\right)=\sum_{k\geq1}c_k u^{2k}\leq u^2=\bar{D}_2\left(\frac{1+u}{2}\mathbin\Vert\frac{1}{2}\right),

with equality iff u∈{−1,0,1}u \in\{-1,0,1\}. Since H2(a)=1−D2(a∥1/2)H_2(a)=1-D_2(a\mathbin\Vert1/2) and Hˉ(a)=1−Dˉ2(a∥1/2)\bar{H}(a)=1-\bar{D}_2(a\mathbin\Vert1/2), this gives

Hˉ(a)≤H2(a)(0≤a≤1),I(B:Z)≤Iˉ(B;Z)\bar{H}(a)\le H_2(a)\qquad(0\le a\le1),\qquad I(B:Z)\le\bar{I}(B;Z)

when BB is a uniform bit.

In particular Hˉ(B)≤H(B)\bar{H}(B)\le H(B) and I(Y1:X)=Ip≤Iˉp=Iˉ(Y1;X)I(Y_1:X)=I_p\le\bar{I}_p=\bar{I}(Y_1;X), the orderings used in Figure 1. The second inequality needs the uniform reference: for a nonconstant biased bit BB, taking Z=BZ=B gives I(B:B)=H(B)>Hˉ(B)=Iˉ(B;B)I(B:B)=H(B)>\bar{H}(B)=\bar{I}(B;B).

Proof of Lemma 2.1. Let us write μZ=Pr⁡[C=1∣Z]\mu_Z=\Pr[C=1\mid Z] and μ=EC\mu=\mathbb{E}C. Expanding the definition gives

Iˉ(C;Z)=4E[(μZ−μ)2].\bar{I}(C;Z)=4\mathbb{E}\left[(\mu_Z-\mu)^2\right].

This proves nonnegativity, while the upper bound by Hˉ(C)\bar{H}(C) follows from Hˉ(C∣Z)≥0\bar{H}(C\mid Z)\ge0. Both statements may be averaged over UU. We already have Hˉ(C)≤H(C)\bar{H}(C)\le H(C). The lower bound of Lemma B.1 with reference mean 1/21/2 also gives

1−H(C)=D2(μ∥1/2)≥1−Hˉ(C)2ln⁡2≥1−Hˉ(C)2.1-H(C)=D_2(\mu\mathbin\Vert1/2)\ge\frac{1-\bar{H}(C)}{2\ln2}\ge\frac{1-\bar{H}(C)}{2}.

Averaging over UU completes part 1.

The chain rule follows by telescoping the entropy differences. If C−Z−WC-Z-W is a Markov chain, then Hˉ(C∣Z,W)=Hˉ(C∣Z)\bar{H}(C\mid Z,W)=\bar{H}(C\mid Z), so the chain rule also gives the data processing inequality in part 2.

The lower bound of Lemma B.1, averaged over the conditional mean μZ\mu_Z, gives

I(C:Z)≥2E[(μZ−μ)2]ln⁡2=Iˉ(C;Z)2ln⁡2.I(C:Z)\ge\frac{2\mathbb{E}\left[(\mu_Z-\mu)^2\right]}{\ln2}=\frac{\bar{I}(C;Z)}{2\ln2}.

The upper comparison for unbiased CC was proved above using (B.1). Averaging both comparisons over UU gives part 3; the upper one requires CC to remain unbiased given UU. If a conditional law of CC is constant, both informations are zero.

For two bits, evaluating the two conditional means gives

Hˉ(C)Iˉ(B;C)=16Cov⁡(B,C)2=Hˉ(B)Iˉ(C;B).\bar{H}(C)\bar{I}(B;C)=16\operatorname{Cov}(B,C)^2=\bar{H}(B)\bar{I}(C;B).

If either bit is constant, all three terms vanish. When BB is unbiased, the definition also gives

Iˉ(C;B)=(Pr⁡[C=1∣B=1]−Pr⁡[C=1∣B=0])2=(2Pr⁡[B=C]−1)2.\bar{I}(C;B)=\left(\Pr[C=1\mid B=1]-\Pr[C=1\mid B=0]\right)^2=(2\Pr[B=C]-1)^2.

This proves part 4.

For part 5, let us write Vu=Hˉ(C∣U=u)V_u=\bar{H}(C\mid U=u) and σu=Cov⁡(B,C∣U=u)\sigma_u=\operatorname{Cov}(B,C\mid U=u). The identity for two bits, applied conditionally, and Cauchy–Schwarz give

Iˉ(B;C∣U)Hˉ(C∣U)=16(Eu∼Uσu2Vu)(Eu∼UVu)≥16(Eu∼Uσu)2.\bar{I}(B;C\mid U)\bar{H}(C\mid U) =16\left(\mathbb{E}_{u\sim U}\frac{\sigma_u^2}{V_u}\right)\left(\mathbb{E}_{u\sim U}V_u\right) \ge16\left(\mathbb{E}_{u\sim U}\sigma_u\right)^2.

Terms with Vu=0V_u=0 have σu=0\sigma_u=0 and contribute zero. Since BB is independent of UU, its conditional mean is constant, and hence Eu∼Uσu=Cov⁡(B,C)\mathbb{E}_{u\sim U}\sigma_u=\operatorname{Cov}(B,C). The last display is therefore at least Hˉ(B)Iˉ(C;B)\bar{H}(B)\bar{I}(C;B), as required.

Finally, applying the Shannon comparisons to the unbiased noise bits gives Iˉp/(2ln⁡2)≤Ip≤Iˉp\bar{I}_p/(2\ln2)\le I_p\le\bar{I}_p. Since ln⁡2<1\ln2<1, we have Iˉp≤2Ip\bar{I}_p\le2I_p, proving part 6. □

Proof of Lemma 2.2. Complementing CC if necessary lets us assume μ≥1/2\mu\ge1/2. Averaging the upper bound of Lemma B.1 over the conditional mean Pr⁡[C=1∣U]\Pr[C=1\mid U] gives the first inequality. For the second, ln⁡(1+x)≤x\ln(1+x)\le x gives

Hˉ(C)c(μ)=μ1−μln⁡(1+1−μμ)≤1.\bar{H}(C)c(\mu)=\frac{\mu}{1-\mu}\ln\left(1+\frac{1-\mu}{\mu}\right)\le1.

□

References

References

  1. [1]Rudolf Ahlswede and Péter Gács. “Spreading of Sets in Product Spaces and Hypercontraction of the Markov Operator”. In: The Annals of Probability 4.6 (1976), pp. 925–939 (cited on page 2).DOI
  2. [2]Venkat Anantharam, Andrej Bogdanov, Amit Chakrabarti, T. S. Jayram, and Chandra Nair. “A Conjecture Regarding Optimality of the Dictator Function under Hellinger Distance”. In: Information Theory and Applications Workshop (ITA). 2017 (cited on page 1).
  3. [3]Erdal Arıkan. “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”. In: IEEE Transactions on Information Theory 55.7 (2009), pp. 3051–3073. DOI: 10.1109/TIT.2009.2021379 (cited on page 1).DOI
  4. [4]Leighton Pate Barnes and Ayfer Özğür. “The Courtade-Kumar Most Informative Boolean Function Conjecture and a Symmetrized Li-Médard Conjecture are Equivalent”. In: 2020 IEEE International Symposium on Information Theory (ISIT). 2020, pp. 2205–2209. DOI: 10.1109/ISIT44484.2020.9174063. arXiv: 2004.01277 (cited on page 1).DOI
  5. [5]Venkat Chandar and Aslan Tchamkerten. Most Informative Quantization Functions. Manuscript. 2014. URL: http://perso.telecom-paristech.fr/~tchamker/CTAT.pdf (cited on page 2).
  6. [6]Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, and David P. Woodruff. A Proof of the Most Informative Boolean Function Conjecture. 2026. arXiv: 2609.24931 [cs.DS] (cited on page 2).arxiv.org/abs/2609.24931
  7. [7]Zijie Chen and Chandra Nair. “On the Optimality of Dictator Functions and Isoperimetric Inequalities on Boolean Hypercubes”. In: 2024 IEEE International Symposium on Information Theory (ISIT). 2024, pp. 3380–3385. DOI: 10.1109/ISIT57864.2024.10619180 (cited on page 1).
  8. [8]Thomas A. Courtade and Gowtham R. Kumar. “Which Boolean Functions Maximize Mutual Information on Noisy Inputs?” In: IEEE Transactions on Information Theory 60.8 (2014), pp. 4515–4525. DOI: 10.1109/TIT.2014.2326877 (cited on pages 1, 2).DOI
  9. [9]Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. “Testing juntas”. In: Journal of Computer and System Sciences 68.4 (2004), pp. 753–787. DOI: 10.1016/j.jcss.2003.11.004 (cited on page 1).
  10. [10]Adel Javanmard and David P. Woodruff. Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information. 2026. arXiv: 2601.09679 [cs.IT] (cited on page 1).arxiv.org/abs/2601.09679
  11. [11]Guy Kindler, Ryan O’Donnell, and David Witmer. Remarks on the Most Informative Function Conjecture at fixed mean. 2015. arXiv: 1506.03167 [cs.IT] (cited on pages 1, 2).arxiv.org/abs/1506.03167
  12. [12]Gowtham R. Kumar and Thomas A. Courtade. “Which Boolean Functions are Most Informative?” In: 2013 IEEE International Symposium on Information Theory. 2013, pp. 226–230. DOI: 10.1109/ISIT.2013.6620221. arXiv: 1302.2512 (cited on page 1).DOI
  13. [13]Vu Khac Ky and Tuan Tran. Dictators are most informative. 2026. arXiv: 2609.24184 [cs.IT] (cited on page 2).arxiv.org/abs/2609.24184
  14. [14]Jiange Li and Muriel Médard. “Boolean Functions: Noise Stability, Non-Interactive Correlation Distillation, and Mutual Information”. In: IEEE Transactions on Information Theory 67.2 (2021), pp. 778–789. DOI: 10.1109/TIT.2020.3041028. arXiv: 1801.04462 (cited on page 1).DOI
  15. [15]Hessam Mahdavifar and Ahmad Beirami. The Most Informative Bit and Beyond: A Proof of the Courtade–Kumar Conjecture and Multibit Extensions. 2026. arXiv: 2609.26444 [cs.IT] (cited on page 2).arxiv.org/abs/2609.26444
  16. [16]OpenAI. Hellinger contraction with arbitrary Boolean output bias. OpenAI Math Release preprint. Dated September 24, 2026; publicly released October 6, 2026. 2026. URL: https://github.com/openai/math/blob/main/preprints/Hellinger-contraction-with-arbitrary-Boolean-output-bias-September-24-2026/main.pdf (cited on page 2).
  17. [17]OpenAI. Sharp binary-information contraction on the discrete cube. OpenAI Math Release preprint. Dated September 24, 2026; publicly released October 6, 2026. 2026. URL: https://github.com/openai/math/blob/main/preprints/Sharp-binary-information-contraction-on-the-discrete-cube-September-24-2026/main.pdf (cited on page 2).
  18. [18]Or Ordentlich, Ofer Shayevitz, and Omri Weinstein. An Improved Upper Bound for the Most Informative Boolean Function Conjecture. 2015. arXiv: 1505.05794 [cs.IT] (cited on page 1).
  19. [19]Michal Parnas, Dana Ron, and Alex Samorodnitsky. “Testing Basic Boolean Formulae”. In: SIAM Journal on Discrete Mathematics 16.1 (2002), pp. 20–46. DOI: 10.1137/S0895480101407444 (cited on page 1).DOI
  20. [20]Georg Pichler, Gerald Matz, and Pablo Piantanida. “A Tight Upper Bound on the Mutual Information of Two Boolean Functions”. In: 2016 IEEE Information Theory Workshop (ITW). 2016, pp. 16–20. DOI: 10.1109/ITW.2016.7606787 (cited on page 1).DOI
  21. [21]Alex Samorodnitsky. “On the Entropy of a Noisy Boolean Function”. In: IEEE Transactions on Information Theory 62.10 (2016), pp. 5446–5464. DOI: 10.1109/TIT.2016.2584625 (cited on page 1).DOI
  22. [22]Alex Samorodnitsky. The ”Most informative boolean function” conjecture holds for high noise. 2015. arXiv: 1510.08656 [cs.IT] (cited on page 1).arxiv.org/abs/1510.08656
  23. [23]Septimia Sarbu. On the Courtade-Kumar conjecture for certain classes of Boolean functions. 2017. arXiv: 1702.03953 [cs.IT] (cited on page 1).arxiv.org/abs/1702.03953
  24. [24]Septimia Sarbu. The maximum mutual information between the output of a discrete symmetric channel and several classes of Boolean functions of its input. Withdrawn. 2017. arXiv: 1701.05014 [cs.IT] (cited on page 1).arxiv.org/abs/1701.05014
  25. [25]Hengjie Yang and Richard D. Wesel. On the Most Informative Boolean Functions of the Very Noisy Channel. Short version in ISIT 2019. 2018. arXiv: 1807.11289 [cs.IT] (cited on page 1).arxiv.org/abs/1807.11289
  26. [26]Lei Yu. Local Optimality of Dictator Functions with Applications to Courtade–Kumar and Li–Médard Conjectures. Accepted for publication in the Annals of Applied Probability. 2024. arXiv: 2410.10147 [math.PR] (cited on page 1).arxiv.org/abs/2410.10147

Paper details

vlnc:W_wqa7peb2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents