Sharp binary-information contraction on the discrete cube

1 The contraction theorem and its mechanism

A one-bit summary of independent fair bits can be chosen before those bits pass through independent binary symmetric channels. Which summary retains the most information about the noisy observation? Kumar and Courtade formulated the conjecture that a single input coordinate is optimal at every noise level and in every dimension [13, 7]. We prove a sharp comparison for arbitrary randomized binary summaries, together with a mean-dependent bound on their instantaneous information loss.

Let \Omega_n=\{-1,1\}^n carry uniform measure. All information is measured with natural logarithms. For r\in[-1,1], define

with 0\log0=0. Thus H(r) is the entropy of a sign of mean r. For a soft binary channel u:\Omega_n\to[-1,1], define

Let X be uniform on \Omega_n. If an auxiliary sign U has conditional mean \E[U\mid X]=u(X), then I(u)=I(U;X). For -1\le\rho\le1, let Y_i=X_iZ_i, where the signs Z_i are independent of (X,U) and each other, with \E Z_i=\rho. The noise operator is T_\rho u(y)=\E[u(X)\mid Y=y]. Thus \E[U\mid Y]=T_\rho u(Y) and I(T_\rho u)=I(U;Y).

The parameter \psi^{-1}(I(u)) is the amplitude of a fair soft coordinate with the same information as u. The theorem says that this effective amplitude contracts at least as fast as a coordinate. Sharpness concerns all soft channels at a given initial information; it does not assert that every biased Boolean source attains the bound.

For noise crossover probability \varepsilon\in[0,1/2], one has \rho=1-2\varepsilon. Writing h_2(p)=-p\log_2p-(1-p)\log_2(1-p), the universal bound in bits is

This is the Courtade–Kumar conjecture. The refinement uses the actual entropy of the Boolean output, while the input distribution remains uniform.

1.1 Prior work and related results

Ordentlich, Shayevitz, and Weinstein [17] obtained asymptotically sharp high-noise bounds for balanced Boolean functions. Samorodnitsky [19] proved the conjecture for all Boolean functions in a dimension-independent high-noise range. Yu’s work on \Phi-stability and local optimality [21, 22] enlarged the proved range for balanced functions; the latter gives 0\le\rho\le0.914 by a computer-assisted argument. Javanmard and Woodruff [10] extended Courtade and Kumar’s coordinatewise sum bound [7, Theorem 1] from balanced functions to arbitrary output bias and refined high-noise entropy estimates.

Several nearby formulations clarify the role of the full noisy vector. Pichler, Piantanida, and Matz [18] proved coordinate optimality when the observation is also reduced to one Boolean output. At fixed output mean, Li and Médard [15] identified lexicographic optimizers at sufficiently low noise and related high-noise optimizers to first-level Fourier weight, in dimension-dependent ranges. Barnes and Özgür [1] proved the equivalence of the balanced conjecture and a symmetrized Li–Médard moment inequality. Kindler, O’Donnell, and Witmer [11] proved fixed-mean Gaussian and spherical analogues. These fixed-mean questions are distinct from attainability of the refined upper curve in Corollary 1.2.

Chen, Gohari, and Nair [6] developed the differential approach that we use: prove a local entropy-production inequality, lift it by induction on the cube dimension, and integrate along the noise semigroup. Their approach builds on the auxiliary receiver method of Gohari and Nair [8]. The August 2026 revision of Chen–Gohari–Nair disproves one proposed auxiliary inequality [6, Appendix B]; the local comparisons below are proved directly. Their symmetric optimizer is a predecessor of our arbitrary-mean joining problem, as explained in Section 3.

Recent preprints announce proofs of the Courtade–Kumar conjecture by several routes. Chen, Gohari, Javanmard, Lin, Mirrokni, Nair, and Woodruff [5] use a computer-assisted Bellman inequality; Ky and Tran [14] develop entropy-production and spectral estimates with computer-assisted verification; Mahdavifar and Beirami [16] use entropy flow, Fourier analysis, and bounds for pivotal sets; and Kramer and Saglam [12] prove a finite-noise bound that retains the Boolean output bias. The overlap with the first work extends beyond the Boolean conjecture: its Lemma 9.2 applies to arbitrary binary channels, and retaining the initial information when integrating its production bound gives Theorem 1.1 and Corollary 1.2. Our proof solves the joining problem with a common entropy budget and uses two capacities and common-output thinning. It also proves the additional mean-dependent production estimate in Theorem 1.3; we compare the two production profiles in Section 8.1.

1.2 From information loss to a local joining inequality

For an interior soft field g:\Omega_n\to(-1,1), put

where V(r)=\operatorname{atanh}r and

Here \mathrm{flip}_i flips coordinate i. Mean conservation and finite-dimensional differentiation give

The production of a soft coordinate g(x)=r x_i is rV(r). We therefore define its rate by F(\psi(r))=rV(r) for 0\le r<1 and seek the inequality D(g)\ge F(I(g)). Once this is proved, r_t=\psi^{-1}(I(P_tg)) satisfies r_t'\le-r_t whenever I(P_tg)>0. Integrating gives Theorem 1.1; Section 8 treats zero information and boundary-valued inputs.

The local-to-global program is due to Chen–Gohari–Nair [6, Definition 1 and Theorem 2]. To see the required local comparison, split the cube along one coordinate into fields g_+,g_- on \Omega_{n-1}. Their productions satisfy the exact identity

where the last expectation is over the remaining coordinates. Write m_\pm=\E g_\pm and I_\pm=I(g_\pm). For a profile with \Phi_m(0)=0, the required induction step is that the joining edges pay its increase:

The information-only choice \Phi_m(I)=F(I) does not satisfy the corresponding local comparison for every coupled pair law [6, Remark 5]. The proof must retain the mean as well as the information.

1.3 Two profiles and the geometry of the joining cost

The linear estimate D(g)\ge2I(g) follows from the classical cube logarithmic Sobolev inequality and its entropy-dissipation consequence, within the hypercontractive framework of Bonami, Gross, and Beckner [4, 9, 2]; see also Bobkov–Tetali [3, Example 3.7] for the modified logarithmic Sobolev formulation. Mrs. Gerber’s lemma [20] contains the same scalar one-bit entropy curve, but its direct vector form has dimension-normalized arguments. The nonlinear surplus above 2I is the part that needs a new local comparison.

Since F'(0)=2, define

For |m|<1 and 0\le I<H(m), set

The factor 1-m^2 is useful because the average of the two child variance factors at means m\pm\delta is 1-m^2-\delta^2. Convexity therefore pools their surplus terms in the same form. Section 5 explains the two-capacity allocation behind this profile and proves its local joining inequality. The same two capacities occur in the Boolean finite-noise bound of Kramer and Saglam [12]; that section gives the comparison.

To prove the local joining inequality for \mathcal B, regard (g_+(X'),g_-(X')) as a coupled pair of random variables, where X' is uniform on the remaining cube. We minimize the joining cost over all coupled pair laws with the same child means and average conditional entropy, extending c by zero at the equal corners and by +\infty at every other boundary pair. The exact optimizer has one interior pair (a_c,b_c) and possibly the two equal-output corners (1,1) and (-1,-1). Section 3 proves this description by assigning a nonnegative price to entropy. Section 4 proves the one-bit inequality that pays the interior pair. Adding either common output reduces the payment required by \mathcal B at least in proportion to the retained mass. Composing these two operations pays the full optimizer. Throughout this minimization, the original face entropies remain in the child profiles; only their average enters the cost problem.

At mean zero, \mathcal B_0=F, but at other means neither profile can be discarded. We prove local joining for their maximum,

Two comparisons make this possible. First,

Thus only parents below half information can require the F branch. At such a parent, convexity at the original child states reduces the unpaid amount to F(I)-F(j), where j=(I_++I_-)/2.

For the second comparison, reflect the output signs if necessary so that the parent mean is nonnegative. An optimizer with one corner then combines a core of nonnegative center with (1,1). Section 6 shows that this addition reduces the increment at least in proportion to the retained mass, and so the one-bit inequality pays the mixture. When both corners occur, the core is reflected, (r,-r). Holding the core and its mass fixed preserves the separation of the child means, their average conditional entropy, and the joining cost. We increase the common mean until one corner disappears, as in Figure 1. Below half information the required increment increases during this motion. The one-corner endpoint therefore pays the original state as well.

Section 7 combines these comparisons and performs dimension induction to prove the following strengthening of the scalar rate inequality.

The scalar facts needed by the local comparisons are proved in Section 2. Section 8 integrates the production bound and compares its mean-dependent part with the profile of Chen et al. [5].

2 The scalar rate and its curvature

A soft coordinate fixes the rate used throughout the proof. We need its convexity, two bounds on its entropy-scaled curvature, and one comparison of logarithmic slopes. These facts follow from a positive hyperbolic integral and two elementary moment comparisons.

All logarithms are natural. For a sign with mean r\in[-1,1], put

with 0\log0=0. Thus H is binary entropy and \psi is its gap from the entropy of a fair sign. Write V(r)=\operatorname{atanh}r for -1<r<1. Then

The restriction of \psi to [0,1) increases bijectively onto [0,L). Define the production rate and its surplus over the linear rate by

3 A joining cost with one entropy budget

The energy decomposition (1.5) leaves the cost of joining the two faces of a coordinate split. We minimize this cost at fixed child means and average conditional entropy. Allowing arbitrary coupled pair laws is a valid relaxation because only a lower bound on the actual joining cost is needed; no independence of the faces is assumed. The symmetric fixed-entropy problem of Chen–Gohari–Nair [6, Theorem 4 and Section IV-C] has an optimizer supported on a reflected interior pair and the two equal-output corners. Chen et al. [5, Section 3.1, Theorem 3.10] characterize related three-point optimizers when both means and both entropy moments are prescribed, under explicit contact and mass conditions. Here we prescribe the two means but constrain only the average entropy. Pricing this common entropy budget gives the optimizer throughout the domain, including the transition from two corners to one.

For interior x,y, use the joining cost

It is symmetric and nonnegative. Extend it by zero at the equal corners (1,1),(-1,-1) and by +\infty at every other boundary pair. This is a lower semicontinuous, jointly convex function. Indeed,

and J is the sum of two relative-entropy perspectives.

Fix -1<b<a<1, and write

Jensen’s inequality makes e_{\max} the largest possible average entropy; the deterministic pair attains it. We call this boundary the capacity state of the joining problem. For 0<e\le e_{\max}, define

The infimum is over joint laws on [-1,1]^2. Only the average entropy is constrained.

3.1 Constructing and certifying the priced core

We first construct candidate laws of the form

The prescribed mean difference forces \lambda(x-y)=2\delta; the mean sum and total mass then determine the two corner masses. We will minimize a priced objective within this family, and then prove optimality against all coupled laws by an affine lower bound.

For an ordered interior pair x>y, set

Then

In these coordinates, the masses required by the two means are

They sum to one, and the corner masses are nonnegative exactly when

For a price p\ge0, define

The corners contribute neither cost nor entropy. Hence the priced objective of the candidate law (3.3) is

This explains the normalization by x-y: the prescribed mean difference absorbs the core mass. The remaining task is to minimize F_p subject to (3.6) and certify that its value also bounds every other pair law.

The normalized entropy has the positive series

Here is a direct verification. The normalized entropy of x is [n\log n-(u+1)\log(u+1)-v\log v]/2, and that of y is its transpose. Put \xi=e^{-z} and \zeta=e^{-w}. After subtracting [q(z)+q(w)]/2, the sum becomes

The coefficient of \xi^i\zeta^j is 1/i+1/j-1/\min(i,j)=1/\max(i,j), which proves (3.8). The series and its derivatives converge uniformly on compact subsets of the positive quadrant.

The function \mathcal H is symmetric and strictly convex. In fact, with v_t=(e^t-1)^{-1},

because t(2v_t+1)=t\coth(t/2)>2. Each term in the double series is convex; its exponential direction vectors span the plane.

3.2 The two canonical geometries

By reflection assume m\ge0, so z_0\le w_0. Symmetry and uniqueness imply z\le w at the priced minimizer: otherwise swapping the coordinates is feasible and has the same value. The case p=0 is already deterministic, so assume p>0 in the following strict-convexity argument. If w>w_0 and z<w, then (F_p)_w=0 while strict convexity and symmetry give (F_p)_z<(F_p)_w, contradicting constrained optimality. Thus either z=w or w=w_0.

In the first case, the core is (r,-r), with

At fixed \delta,e, the radius r and the cost do not depend on m. Uniqueness of r follows because H(r)/r strictly decreases.

In the second case, \pi_-=0. With core mass k,

Indeed z\le w means the core center is nonnegative, and

The two geometries meet at k=1-m, where the reflected core has only a positive common corner. Thus their entropy threshold is

To check the direction of the threshold, differentiate the one-corner entropy in (3.11) at fixed a,b:

The reflected entropy kH(\delta/k) also strictly increases in k, since its derivative is H(r)+rV(r)>0. Consequently the reflected geometry has e\le e_0, and the one-corner geometry has e\ge e_0. This is a support threshold for the exact cost optimizer, separate from the analytic threshold (1.8) for the production profile. At capacity k=1 and the law is deterministic. If \delta=0, taking A=B with mean m and arbitrarily small entropy gives \mathcal K=0; that case requires no canonical classification.

Figure 1 displays the motion within the reflected geometry. The path preserves the optimizer’s cost and its average entropy; the original law’s individual entropies are retained separately when applying the local production inequalities.

4 The deterministic capacity comparison

The scalar profile is calibrated at balanced one-bit channels. At a biased one-bit channel, the two output labels have unequal posterior correlations. Their separation provides the extra reserve needed by the variance-weighted profile. The inequality below also follows by differentiating at correlation one the pointwise one-bit comparison in the proof of Kramer–Saglam [12, Lemma 2.4]. We give a direct proof using size-biased posterior information.

The ordinary one-bit bound follows at once:

The last inequality is convexity with F(0)=0 and 0<\alpha\le1. We retain the variance-refined form because it pays the deterministic base of the reserve profile, while its ordinary consequence pays the information increment at a core.

5 A reserve that survives adding either common output

The linear rate 2I leaves a remainder that has a simple behavior under mixing. Write S=F-2I, as in (2.4), and put

using the zero extension of S at negative arguments. The profile (1.6) is

Its construction can be read as an allocation of information between two capacities. Set \alpha=1-m^2 and c_m=H(m)-\alpha L\ge0. Then

Indeed, F'\ge2 makes the optimum u=\min\{I,c_m\}. The capacity c_m is paid at the linear rate, while the remaining capacity \alpha L uses the exact coordinate rate. This is an identity for the profile, not a decomposition of an actual channel. The finite-noise bound of Kramer and Saglam [12, Theorem 1.1] reads, in the present normalization,

for a Boolean field f on the uniform cube with \E f=m. It uses the same coefficients \alpha and c_m; here they define the local production profile \mathcal B_m.

To determine the payment required by a join, consider a physical state

and write

Set a=m+\delta and b=m-\delta. Let e_a,e_b>0 satisfy e_a\le H(a), e_b\le H(b), and (e_a+e_b)/2=e, and put I_a=H(a)-e_a, I_b=H(b)-e_b. Their average information is j, and their average variance capacity is [(1-a^2)+(1-b^2)]/2=\beta. Since R is a convex perspective, the child profiles satisfy

The parent information is I=H(m)-e=J+j. Subtracting the pooled bound from \mathcal B_m(I)=2(J+j)+R(\alpha,e) gives the required payment

Thus

It is enough to prove W\le\mathcal K. The deterministic capacity comparison pays the interior core; the next two lemmas show that this payment survives adding either common output.

5.1 A logarithmic bound for the corner geometry

5.2 The common-output contraction

5.3 From one core to the local inequality

The pooling step has a useful exact interpretation. If e<\beta L, its minimum over the entropy split is attained at e_a/(1-a^2)=e_b/(1-b^2)=e/\beta; these entropies are physical because H(a)\ge(1-a^2)L, and similarly for b. If e\ge\beta L, allocate both child entropies in the intervals [(1-a^2)L,H(a)] and [(1-b^2)L,H(b)] with the prescribed average. Both remainders vanish. Thus the perspective in (5.3) is the exact common-budget value of the child reserve, rather than an additional approximation.

6 Paying the information increment by thinning

The canonical optimizer with one positive common corner has a useful feature: its cost is linear in the mass of its interior core. We will show that the information-rate increment is at most the core’s increment multiplied by that mass. At full mass the increment is paid by the one-bit posterior comparison. This will settle the whole high-entropy branch of the canonical cost problem.

The scalar inputs already proved here are

Indeed, the slope follows from Lemma 2.2, the curvature bound from Lemma 2.4, and the strict margin from Lemma 2.1. The proof isolates the roles of these two bounds: the slope supplies a positive term, while the curvature controls the possible loss over an entropy interval.

6.1 The common-output path

Fix an interior ordered pair a_c>b_c with nonnegative center, and write

For 0<\lambda\le1, put mass \lambda on this core and mass 1-\lambda on (1,1). The second atom is a common output: its coordinates agree, and it contributes neither entropy nor cost. The mixture has means x+d and x-d, where

For this path define

The average child information is \nu, and J is the entropy gained by averaging the two child means. Since 0<d_c<1-x_c\le1, the mixture has x\ge0 and 0<d<1-x. Entropy concavity gives \nu\ge0; strict concavity gives J>0; and e>0 gives I<L. Thus every rate argument lies in [0,L).

These quantities have a channel interpretation. Let X be a fair sign and let B\in\{0,1\} be an independent flag with \Pr(B=1)=\lambda. Given X,B, draw a sign U with conditional mean

Thus B=0 selects the common output and B=1 selects the core. The three relevant entropies are H(U)=H(x), H(U\mid X)=\bar h, and H(U\mid X,B)=e. The chain rule therefore reads

In particular, \nu is the information about the flag after the input has been revealed.

We prove this by showing that [F(\nu+J)-F(\nu)]/\lambda increases with \lambda. This normalization matches the mixture’s cost \lambda c(a_c,b_c). We first compute its derivative and identify the entropy-interval estimate that makes it nonnegative.

6.2 The normalized derivative

For the state (6.2), set

In particular s-q=J and 0<q<s\le L. Write

For h_{\mathrm{bin}}(t)=H(1-2t), the entropy identity is

Apply it first to I=h_{\mathrm{bin}}(\lambda(1-x_c)/2)-\lambda h_c, then to the two child expressions with initial probabilities (1-a_c)/2 and (1-b_c)/2, and average. The result is

For the second identity, the two logarithms have average

Substitution gives the exact Euler derivative

Indeed, at the chosen value of \lambda, the derivative in u of (u-A)F'(u)-F(u) is (u-A)F''(u). The value of A is held fixed only during this auxiliary integration; both path derivatives have already been included.

The last term in (6.8) is at least 2\kappa. Convexity makes the integrand nonnegative where u\ge A. On the remaining part, the curvature bound F''(u)\le M/(L-u)^2 and the substitution h=L-u give

Thus it suffices to prove that this integral is at most 3\kappa: the strict margin 2>3M will then make (\Delta/\lambda)' nonnegative. The cutoff b marks exactly the part of the entropy interval where the curvature term can be negative. We will first prove an interval estimate for this kernel, then check its hypotheses using the entropy of the core.

The positive term also has a channel interpretation. For the channel in (6.4), the posterior of the fair input at the positive output is

Consequently

This is the relative entropy from the prior to the positive-output posterior, with the flag marginalized. It is an auxiliary path quantity, distinct from the canonical cost \mathcal K.

6.3 An estimate for entropy intervals

6.4 The entropy interval of the channel

We now return to the quantities in (6.6). To apply the interval estimate to [q,s], we need a lower bound on its position and an upper bound on its length J. Both follow from the entropy of the oriented core.

6.5 The canonical high-entropy value

The canonical optimizer is used here only to evaluate a lower bound on joining cost. For an original pair law with means x\pm d and individual entropies e_a,e_b, the value of e in (6.20) is their actual average. The original child information values remain H(x+d)-e_a and H(x-d)-e_b; their average is \bar h(x,d)-e. Convexity of F therefore gives the common floor at those original child states:

No individual entropy moment of the canonical law is substituted for either original child entropy.

7 From the linear reserve to the sharp rate

The local reserve inequality does not by itself give the sharp rate F(I) at every state. We now join their maximum

Closure under a maximum is a useful feature of the local-production framework [6, Lemma 3], but F alone does not satisfy a joining inequality for every law. We therefore prove the needed comparison in the part of the domain where the reserve is insufficient. Two comparisons organize the proof. Above half information, the reserve already dominates F. Below half information, the demand from F increases with the common mean of the child states. Thus every reflected core can be paid at its one-corner wall by the same thinning theorem used for a one-corner optimizer.

7.1 The reserve above half information

7.2 A direct comparison with the one-corner wall

7.3 The local inequality and dimension induction

8 Sharp entropy interpolation under noise

The sharp production bound has a direct dynamical meaning: a soft field loses information at least as fast as a noisy coordinate with the same information. The appropriate coordinate for this comparison is the inverse entropy deficit, rather than information itself. In that coordinate the comparison flow is simply exponential decay.

8.1 Comparison of mean-dependent production bounds

Theorem 1.3 gives more than the scalar rate needed for Theorem 1.1. For 0<m<1 and 0\le I<H(m), put h=H(m)-I. The hybrid production profile of Chen et al. [5, Section 9 and Lemma 9.2], converted to natural logarithms and the generator N used here, is

The equation for s has a unique solution: H(s)/s decreases strictly from H(m)/m to zero on [m,1). In particular, the F(I) branch yields Theorem 1.1 by the inverse-entropy integration above, with the initial information left unchanged.

The mean-dependent estimate in Theorem 1.3 has a different strength. At every fixed m\in(0,1),

Here is a direct verification. For r=1-\varepsilon,

Consequently F(L-h)\sim\tfrac12\log(1/h). The equation H(s)=hs/m gives s\to1 and V(s)\sim\tfrac12\log(1/h). As F(H(m)-h) remains bounded, these facts give the second equivalent in (8.2). The first follows from

and S(u)=F(u)-2u for positive u. Thus the displayed profile C_m does not dominate \mathcal B_m: the ratio \mathcal B_m(H(m)-h)/C_m(H(m)-h) tends to 1+m>1 as h\downarrow0. This comparison concerns the two explicit production profiles.