Let X be a uniform random bit string and Y be obtained by flipping each bit of X independently with probability p. Let C be a random bit obtained as a function of Y. We show that I(C:X)≤I(Y1:X) for all p∈[0,1], which resolves a conjecture posed by Courtade and Kumar in 2013.
Introduction
Let X be distributed uniformly on {0,1}n and let Y be obtained by flipping each coordinate of X with probability p, independently. In [12, 8], Courtade and Kumar ask: which bit C computed from Y is most informative about X? They conjecture that taking C=Yi for some i∈[n] maximizes the information conveyed about X. In particular, their Conjecture 1 states that
I(C:X)≤I(Y1:X)=1−H2(p).(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], 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,Y. Denoting the Tsallis entropy of C by Hˉ(C)=4μ(1−μ) and setting Ip=I(Y1:X) and Iˉp=(1−2p)2, we define the progressive entropy of C as
Q(C)=IˉpH(C)−(Iˉp−Ip)Hˉ(C).(2)
With this definition in hand, we prove the following.
Theorem 1.1. Let X be a uniform random bit string and Y be obtained by flipping each bit of X with probability p, independently. For a bit C obtained from Y, we have
I(C:X)≤Q(C)≤I(Y1:X)
for any p∈[0,1].
Comparison with earlier bounds
The strong data-processing inequality [1] gives I(C:X)≤IˉpH(C), the upper-right corner of Figure 1. Courtade and Kumar’s [8] Conjecture 2 concerns the stronger upper bound IpH(C) at the upper-left corner. This bound was later shown to be too strong in general [5, 11]. Our refinement Q(C) subtracts a Tsallis correction (Iˉp−Ip)Hˉ(C) from the strong data-processing bound and sits between the two.
Figure 1. Arrows point toward the larger quantity. Q(C) lies on the top edge, and its distance to IˉpHˉ(C) equals the length of the bottom edge, (Iˉp−Ip)Hˉ(C). Blue: quantities that are always at most I(Y1:X). Purple: quantities that upper bound I(C:X). Only 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) is a surprisingly sharp bound, which is already violated by a natural generalization of the problem. Let X∘ be distributed uniformly on the unit cube [0,1]n and Y∘ be obtained by independently resampling each coordinate of X∘ uniformly from [0,1] with probability 2p. Assume C∘ is a random bit obtained as a function of Y∘ with μ=E[C∘].
Let Tμ be the indicator of Y∘,1≤μ, so that E[Tμ]=μ. In Lemma A.1 we show that Q(C∘)<I(Tμ:X∘) for 0<μ<1, μ=1/2, and 0<p<1/2, which shows that Q(C∘) 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∘, Y∘ and C∘ be as constructed and Tμ be the indicator of the event Y∘,1≤μ as above. It holds that
I(C∘:X∘)≤I(Tμ:X∘)
for 0≤p≤1/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 C from Y revealing I(C:X) bits of information, we can quantize Y∘ by rounding each coordinate to 0 or 1 with threshold 1/2 and apply the strategy to obtain C∘. We get I(C∘:X∘)=I(C:X) and it can be shown that I(Tμ:X∘)≤I(Y1:X).
Preliminaries
We use H(⋅) and I(⋅:⋅) for Shannon entropy and mutual information, with logarithms in base 2. We denote the natural logarithm by ln. We only need Tsallis entropy for bits, while the observed variables may be arbitrary. For a bit C with mean μ, we define
Hˉ(C)=4μ(1−μ).
For a bit C and an arbitrary random variable Z, Tsallis information is defined by
Iˉ(C;Z)=Hˉ(C)−Hˉ(C∣Z).
Note that for bits B, C, the quantities Iˉ(B;C) and Iˉ(C;B) need not be equal. We denote
Ip=1−H2(p),Iˉp=(1−2p)2,
and
Jp=Iˉp−Ip.
Thus Ip=I(Yi:Xi) and Iˉp=Iˉ(Yi;Xi). With these shorthands, we have
Q(C)=IˉpH(C)−JpHˉ(C).
For all our entropy and information quantities H(⋅), I(⋅:⋅), Hˉ(⋅), Iˉ(⋅;⋅), and Q, conditioning on U means evaluating the quantity under the conditional law given U and taking expectation over U, with p held fixed. For instance, Q(C∣U)=Eu∼U[Q(C∣U=u)]. Next, we gather some facts about Tsallis and Shannon information.
Lemma 2.1. Let B and C be bits and Z, W, U be arbitrary random variables. We have
0≤Iˉ(C;Z∣U)≤Hˉ(C∣U) and Hˉ(C∣U)≤H(C∣U)≤(1+Hˉ(C∣U))/2.
Iˉ(C;Z,W∣U)=Iˉ(C;Z∣U)+Iˉ(C;W∣Z,U). If C−Z−W is a Markov chain, then Iˉ(C;W)≤Iˉ(C;Z).
Iˉ(C;Z∣U)≤2ln2I(C:Z∣U). If C is unbiased and independent of U, then also I(C:Z∣U)≤Iˉ(C;Z∣U).
Hˉ(C)Iˉ(B;C)=Hˉ(B)Iˉ(C;B). If B is unbiased, then Iˉ(C;B)=(2Pr[B=C]−1)2.
If B is independent of U, then Iˉ(B;C∣U)Hˉ(C∣U)≥Hˉ(B)Iˉ(C;B).
0≤Jp≤Ip for every p∈[0,1].
Proofs of the preceding and the next lemma are given in Appendix B. Let us define
c(μ)=4(1−μ)2ln(1/μ),(1/2≤μ<1),
extending it to 0<μ<1/2 by c(μ)=c(1−μ).
Lemma 2.2. For a nonconstant bit C with mean μ and every random variable U,
I(C:U)≤ln2c(μ)Iˉ(C;U),andHˉ(C)c(μ)≤1.
The proof
Our proof proceeds by induction on n, the number of coordinates of X,Y. Given the random bit C and the bit string Y, we adaptively pick a coordinate i∈[n] and establish the bound
Q(C)−I(C:X)≥1+λ1(Q(C∣Yi)−I(C:X∣Yi))(3)
for some λ≥0. When Yi is fixed, C depends on n−1 coordinates and therefore the induction hypothesis applies for Yi=0 and Yi=1 separately, showing that Q(C∣Yi)≥I(C:X∣Yi). Plugging into (⋆), we get Q(C)≥I(C:X), which implies (CK) as we show next.
Lemma 3.1. For all p∈[0,1], we have Q(C)≤I(Y1:X).
Proof. From Lemma 2.1[6] and (1), we have Jp≤Ip and H(C)−Hˉ(C)≤1−H(C). Let us write
Therefore Q(C)≤Ip(1−H(C))+IpH(C)=I(Y1:X) as desired.
The property we want from the coordinate i is fairly mild: I(C;Yi)≤1/4. The next lemma shows that such a coordinate always exists.
Lemma 3.2. When n≥2, there exists an i∈[n] such that I(C;Yi)≤1/4.
Proof. Let i,j∈[n] be distinct. We may relabel Yi,Yj so that E[C(2Yi−1)] and E[C(2Yj−1)] are nonnegative. Since Yi,Yj are independent uniform bits,
using 0≤C≤1. At least one of the two square roots is at most 1/2.
Let us fix such an i satisfying I(C;Yi)≤1/4 and use the shorthands A=Xi, B=Yi, and U=X−i in the rest of the paper. The following lemma is the crux of our argument, which establishes (⋆) giving the induction step.
Lemma 3.3. Assuming I(C;B)≤1/4, we have
Q(C)−I(C:X)≥1+λ1(Q(C∣B)−I(C:X∣B))
for some λ≥0.
§ 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).
Proof. The second inequality is Lemma 3.1. For the first, the cases p∈{0,1/2,1} and constant C are immediate. Complementing Y if necessary lets us assume 0<p<1/2. We proceed by induction on n. When n=1, the bit C is a constant, Y1, or its negation, and the bound holds with equality. For n≥2, by Lemma 3.2 there exists a coordinate i with I(C;Yi)≤1/4. Conditioning on B=Yi reduces the problem to n−1 coordinates, so the induction hypothesis applies to the B=0 and B=1 cases individually, giving
Let U be a random variable and A,B be unbiased bits jointly independent of U. Let C be a bit obtained from (B,U) using private randomness, with H(C∣U)>0. We compare C with an unbiased bit C′ obtained from B alone using private randomness, subject to the matching condition
I(B:C′)=H(C∣U)I(B:C∣U).(4)
Lemma 3.4. A bit C′ satisfying (B) exists. Every such bit satisfies
I(A:C′)≥H(C∣U)I(A:C∣U).
Proof. For the fixed channel between A and B, let F be the function determined by
F(I(B:D))=I(A:D)
as D ranges over unbiased bits generated from B. It can be shown that F is increasing and concave (cf. Lemma A.2), and
I(B:C∣U=u)≤H(C∣U=u),
I(A:C∣U=u)≤H(C∣U=u)F(H(C∣U=u)I(B:C∣U=u)).
Values of u with zero conditional Tsallis entropy contribute zero to both informations and may be omitted. The first inequality, averaged over U, places the right-hand side of (B) in [0,1]. Varying the noise in the channel from B to C′ therefore gives a matching bit. Applying Jensen’s inequality to the second inequality, with weights proportional to Hˉ(C∣U=u), gives
Lemma 3.5. Every bit C′ satisfying (B) also satisfies
Iˉ(C′;B)≥Hˉ(C∣U)2I(C;B).
Proof. Let us write v=Hˉ(C∣U) and d=E[(2B−1)(2C−1)]. Since B is unbiased, Iˉ(C;B)=d2. As shown in Appendix § 5, ∣d∣≤v and
vI(B:C∣U)≥D2(21+d/v21).
If θ=E[(2B−1)(2C′−1)], then Iˉ(C′;B)=θ2 and I(B:C′)=D2(21+θ21). The matching identity and monotonicity of this divergence in ∣θ∣ imply θ2≥d2/v2.
The induction step
Recalling that A=Xi, B=Yi and U=X−i, in this section we would like to lower bound the gap Q(C)−I(C:X) by a factor of the conditional gap
Δ=Q(C∣B)−I(C:X∣B).
We obtain two lower bounds on Q(C)−I(C:X). The first involves Δ and benefits from C depending on U, through a positive term in Iˉ(C:U). The second has a negative term in Iˉ(C:U) and benefits from weaker dependence. We add λ times the second bound to the first, choosing λ to cancel these terms, so that the bound works whether or not C depends on U.
To analyze the remaining terms, we introduce an unbiased comparison bit C′ obtained from B 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, allow us to charge these terms to quantities involving I(A:C′) and I(B:C′). What remains is an inequality about the three unbiased bits in the Markov chain A−B−C′, which we analyze in § 3.3.
Figure 2. Arrows indicate dependence. The original bit C depends on Y−i and B, while the comparison bit C′ depends only on B and private randomness.
Let us start with a lemma that we use in obtaining the first lower bound.
Proof of Lemma 3.3. The cases p∈{0,1/2,1} are immediate, so we may assume 0<p<1/2, complementing Y if necessary. If Iˉ(C;B)=0, then C and B are independent. Consequently Q(C)=Q(C∣B) and I(C:X∣B)≥I(C:X), proving the claim with λ=0.
We may therefore assume Iˉ(C;B)>0. Then Hˉ(C∣U)>0: otherwise C would be determined by U and hence independent of B. By Lemma 3.4, there is an unbiased bit C′ obtained from B alone and satisfying (B). Let us write
λ=2Hˉ(C)Hˉ(C∣U)(c(μ)+αp)Iˉ(C;B).
All factors are positive. When we multiply (6) by λ and add it to (5), the terms involving Iˉ(C;U) cancel, giving
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′); the second is a conditional mutual information. Applying Lemma 3.9, we therefore obtain
Thus the last three terms in (7) have nonnegative sum. Dividing by 1+λ proves the lemma. □
The three-bit lemma
In this subsection, let A−B−C be an unbiased binary Markov chain with 0<Iˉ(A;B)<1 and Iˉ(B;C)>0. For the calculation, let us write ρ and u for the absolute correlations of A,B and B,C, respectively, and let
The first ingredient compares the divergence tails in two ways.
Lemma 3.10. For 0<u<1 and N≥1,
GN(u)≥BNbNsN(u).(9)
For N≥2, we also have
ubNsN(u)≥uN/2b2s2(uN/2).(10)
Proof. First, sj(u)/bj is the expectation of the decreasing function (u−x)+/(1−x) under the probability density proportional to x2j/(1+x) on (0,1). Increasing j tilts this density by an increasing function, so sj(u)/bj decreases with j. For 1≤j≤N, therefore, sj(u)≥bjsN(u)/bN; summing proves (9). Here is the elementary order principle used in this argument. If Z,Z′ are independent with the same distribution, then
Cov(f(Z),g(Z))=21E[(f(Z)−f(Z′))(g(Z)−g(Z′))].
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≥0 and write
MN(a)=e−a/NbNsN(e−a/N).
Changing variables in the two tail integrals gives
The quotient inside the expectation increases with z because coth decreases. It also increases with N, since xcothx increases for x>0: its derivative has the sign of sinhxcoshx−x>0. Moreover, for K>N the density ratio πK/πN increases with z, as its logarithmic derivative is
1+e−z/NN−1−1+e−z/KK−1>0.
The order principle and then the pointwise comparison of quotients show that MN(a) increases with N. Taking a=−Nlnu gives e−a/N=u and e−a/2=uN/2, proving (10). All the densities are integrable; at a=0 the quotient in (11) equals one.
The second ingredient gives estimates uniform in the coefficient index N. Let us write
Summing over i+j=N and including the b0bN=bN term proves BN≤bNRN. For the second bound, let us write t=2/N∈(0,1]. We will use
eN≥67−2t≥1−3t.(12)
The first inequality is equality at N=2. Its right-hand side increases from N to N+1 by at most eN+1−eN=1/(4N+2), because
NN+1(N+N+1)≥(2N+1)N≥(2N+1)2.
This proves the first inequality by induction; the second uses t≤1. We also have
139<ln2<3625.
For the lower bound, the first three terms of ln2=2∑j≥0((2j+1)32j+1)−1 sum to 842/1215>9/13. Replacing 2j+1 by 3 for every j≥1 and summing the resulting geometric series gives the upper bound. Writing γ=ln2−1/2>5/26, we obtain
NbN≤4+t2/21≤41−36t2,
18NbN−eN≤310+2t−t2≤2483<1345<18γ.
Since RN=2eN+2NbN−2γ, this is equivalent to RN/(2eN)<19/18. For the third bound, we use the first three nonnegative terms of the binomial expansion of 1−(1−x)a, where 0<a≤1. Let us write s=1/N=t2/2 and e=eN. The moment identities
On (0,4/5], the increasing ratio J′(w)/w3 and the inequality J′(4/5)<0 show that J decreases. Its value there is consequently at least J(4/5)>0.
We now apply these estimates to the coefficients
cN(u)=CN(u)+u4GN(u)−2BN,N≥1,0<u≤1.
Lemma 3.13.For every integer N≥1 and 0<u≤1, we have cN(u)>0.
Proof. For N≥2 and 0<u<1, let us write
k=ubN4sN(u)−2,w=uN/2,x=1−w4.
By Lemma 3.10, cN(u)≥CN(u)+BNk. If k≥0, this is positive because CN(u)>0. If k<0, Lemma 3.11 gives
2eNbNcN(u)≥2eNbNCN(u)+2eNRNk
≥2x+43x2+81x3+1819k.
Here the upper bounds on BN and RN/(2eN) give lower bounds after multiplication by the negative number k. Since b2=ln2−7/12<1/9, the rescaled tail comparison gives
k≥36ws2(w)−2.
Substituting this and x=1−w4 into the preceding lower bound gives exactly J(w)>0. For u=1, we instead have sj(1)=bj and CN(1)=0, so cN(1)=2BN>0. It remains to treat N=1. Writing γ=ln2−1/2<7/36 and retaining the first two terms of s1(u) gives
This is strictly decreasing: the numerator decreases and both factors in the denominator increase. Hence, for 0<ρ<1,
ρ2F(ρ)=∫01(1−t)F′′(ρt)dt>F(1).
Since Iˉp=ρ2, this is precisely I(Tμ:X∘)>Q(Tμ).
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.
Here W1=1 and Wk≥1. This proves ℓ(x,d)≥Vf(d/V), as required for the lower bound.
Let us choose τ∈[0,1] so that f(τ)=ℓ(x,d)/V. Cauchy–Schwarz gives Wk2≤Wk−1Wk+1 for $k\geq 2. Together with W1=1 and Wk≥1, this implies that Wk is nondecreasing. Indeed, successive differences of lnWk are nondecreasing, so
lnWk+1−lnWk≥k−1lnWk(k≥2).
Consequently the terms
2k(2k−1)ln2Wk(x)(d/V)2k−τ2k
change sign at most once, from negative to positive. Their absolutely convergent sum is zero by the choice of τ. Multiplication by the decreasing weights ρ2k therefore gives a nonpositive sum: subtracting a weight at the sign change makes each summand nonpositive. Thus
ℓ(x,ρd)≤Vf(ρτ)=VFρ(Vℓ(x,d)).
The cases with no sign change, and ρ=0,1, follow directly.
It remains to prove concavity. For y=f(t) with 0<t<1,
Fρ′(y)=ρ2∑j≥0t2j/(2j+1)∑j≥0ρ2jt2j/(2j+1)≥0.
This ratio decreases with t: differentiating and pairing terms indexed by j,k gives factors (j−k)(ρ2j−ρ2k)≤0. Since y increases with t, the derivative decreases with y. Continuity gives the assertion on [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)>0 and d=E[(2B−1)(2C−1)]. For each value u of U, let us write Vu and du for the corresponding conditional entropy and correlation. Independence of B and U gives Eu∼Udu=d. Since ∣du∣≤Vu, we have ∣d∣≤v. Jensen’s inequality for the convex function f, with weights Vu/v, gives
I(B:C∣U)≥Eu∼U[Vuf(du/Vu)]≥vf(d/v).
Values with Vu=0 have du=0 and contribute zero.
Shannon and Tsallis information
Lemma B.1. For a∈[0,1] and b∈[1/2,1),
ln22(a−b)2≤D2(a∥b)≤(1−b)2ln2ln(1/b)(a−b)2.
The lower bound holds for every b∈(0,1); complementing a,b gives the corresponding upper bound for b<1/2.
Proof. The second derivative of the divergence in a is 1/(a(1−a)ln2)≥4/ln2, and its value and first derivative vanish at a=b. This proves the lower bound. For the upper bound, Taylor’s integral formula gives
The quotient extends continuously to a=b and is convex in a, because 1/(x(1−x))=1/x+1/(1−x) is convex. It therefore attains its maximum at an endpoint. For b≥1/2, the value at a=1 is at least the value at a=0: equivalently,
−b2lnb+(1−b)2ln(1−b)≥0.
The expression vanishes at b=1/2 and b=1, and its second derivative is 2ln((1−b)/b)≤0 on this interval. The value at a=1 is the claimed coefficient. □
For bits, we write Dˉ2(a∥b)=4(a−b)2 and Hˉ(a)=4a(1−a). The binary divergence has the expansion
D2(21+u∥21)=k≥1∑2k(2k−1)ln2u2k,−1≤u≤1.(15)
Indeed, expanding its second derivative 1/((1−u2)ln2) as a geometric series and integrating twice proves the identity for ∣u∣<1; continuity gives the endpoints. The coefficients ck=1/(2k(2k−1)ln2) are nonnegative and satisfy ∑kck=1 (set u=1). Hence,
D2(21+u∥21)=k≥1∑cku2k≤u2=Dˉ2(21+u∥21),
@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 τ. Multiplication by the decreasing weights ρ2k therefore gives a nonpositive sum: subtracting a weight at the sign change makes each summand nonpositive. Thus
ℓ(x,ρd)≤Vf(ρτ)=VFρ(Vℓ(x,d)).
The cases with no sign change, and ρ=0,1, follow directly.
It remains to prove concavity. For y=f(t) with 0<t<1,
Fρ′(y)=ρ2∑j≥0t2j/(2j+1)∑j≥0ρ2jt2j/(2j+1)≥0.
This ratio decreases with t: differentiating and pairing terms indexed by j,k gives factors (j−k)(ρ2j−ρ2k)≤0. Since y increases with t, the derivative decreases with y. Continuity gives the assertion on [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)>0 and d=E[(2B−1)(2C−1)]. For each value u of U, let us write Vu and du for the corresponding conditional entropy and correlation. Independence of B and U gives Eu∼Udu=d. Since ∣du∣≤Vu, we have ∣d∣≤v. Jensen’s inequality for the convex function f, with weights Vu/v, gives
I(B:C∣U)≥Eu∼U[Vuf(du/Vu)]≥vf(d/v).
Values with Vu=0 have du=0 and contribute zero.
Shannon and Tsallis information
Lemma B.1. For a∈[0,1] and b∈[1/2,1),
ln22(a−b)2≤D2(a∥b)≤(1−b)2ln2ln(1/b)(a−b)2.
The lower bound holds for every b∈(0,1); complementing a,b gives the corresponding upper bound for b<1/2.
Proof. The second derivative of the divergence in a is 1/(a(1−a)ln2)≥4/ln2, and its value and first derivative vanish at a=b. This proves the lower bound. For the upper bound, Taylor’s integral formula gives
The quotient extends continuously to a=b and is convex in a, because 1/(x(1−x))=1/x+1/(1−x) is convex. It therefore attains its maximum at an endpoint. For b≥1/2, the value at a=1 is at least the value at a=0: equivalently,
−b2lnb+(1−b)2ln(1−b)≥0.
The expression vanishes at b=1/2 and b=1, and its second derivative is 2ln((1−b)/b)≤0 on this interval. The value at a=1 is the claimed coefficient. □
For bits, we write Dˉ2(a∥b)=4(a−b)2 and Hˉ(a)=4a(1−a). The binary divergence has the expansion
D2(21+u∥21)=k≥1∑2k(2k−1)ln2u2k,−1≤u≤1.(16)
Indeed, expanding its second derivative 1/((1−u2)ln2) as a geometric series and integrating twice proves the identity for ∣u∣<1; continuity gives the endpoints. The coefficients ck=1/(2k(2k−1)ln2) are nonnegative and satisfy ∑kck=1 (set u=1). Hence,
D2(21+u∥21)=k≥1∑cku2k≤u2=Dˉ2(21+u∥21),
with equality iff u∈{−1,0,1}. Since H2(a)=1−D2(a∥1/2) and Hˉ(a)=1−Dˉ2(a∥1/2), this gives
Hˉ(a)≤H2(a)(0≤a≤1),I(B:Z)≤Iˉ(B;Z)
when B is a uniform bit.
In particular Hˉ(B)≤H(B) and I(Y1:X)=Ip≤Iˉp=Iˉ(Y1;X), the orderings used in Figure 1. The second inequality needs the uniform reference: for a nonconstant biased bit B, taking Z=B gives I(B:B)=H(B)>Hˉ(B)=Iˉ(B;B).
Proof of Lemma 2.1. Let us write μZ=Pr[C=1∣Z] and μ=EC. Expanding the definition gives
Iˉ(C;Z)=4E[(μZ−μ)2].
This proves nonnegativity, while the upper bound by Hˉ(C) follows from Hˉ(C∣Z)≥0. Both statements may be averaged over U. We already have Hˉ(C)≤H(C). The lower bound of Lemma B.1 with reference mean 1/2 also gives
1−H(C)=D2(μ∥1/2)≥2ln21−Hˉ(C)≥21−Hˉ(C).
Averaging over U completes part 1.
The chain rule follows by telescoping the entropy differences. If C−Z−W is a Markov chain, then Hˉ(C∣Z,W)=Hˉ(C∣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, gives
I(C:Z)≥ln22E[(μZ−μ)2]=2ln2Iˉ(C;Z).
The upper comparison for unbiased C was proved above using (B.1). Averaging both comparisons over U gives part 3; the upper one requires C to remain unbiased given U. If a conditional law of C 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).
If either bit is constant, all three terms vanish. When B 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.
This proves part 4.
For part 5, let us write Vu=Hˉ(C∣U=u) and σu=Cov(B,C∣U=u). The identity for two bits, applied conditionally, and Cauchy–Schwarz give
Terms with Vu=0 have σu=0 and contribute zero. Since B is independent of U, its conditional mean is constant, and hence Eu∼Uσu=Cov(B,C). The last display is therefore at least Hˉ(B)Iˉ(C;B), as required.
Finally, applying the Shannon comparisons to the unbiased noise bits gives Iˉp/(2ln2)≤Ip≤Iˉp. Since ln2<1, we have Iˉp≤2Ip, proving part 6. □
Proof of Lemma 2.2. Complementing C if necessary lets us assume μ≥1/2. Averaging the upper bound of Lemma B.1 over the conditional mean Pr[C=1∣U] gives the first inequality. For the second, ln(1+x)≤x gives
Hˉ(C)c(μ)=1−μμln(1+μ1−μ)≤1.
□
References
References
[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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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
Ali Imran, Abdalwhab Bakheet Mohammed Abdalwhab, Rafael Gomes Braga, Hélène Duval, Audrey Rochette, Vivek Shankar Varadharajan, Yann Bouteiller, Jean Mazerolle, Giovanni Beltrame, David St-Onge ·