The Courtade–Kumar and Hellinger conjectures

← All digests

Family 119 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

If you compress a collection of independent fair bits into one bit, which summary remains most informative after the original bits are independently corrupted? Family 119 claims sharp inequalities saying that a single coordinate is optimal. Its two manuscripts also distinguish a general randomized-summary theorem from a stronger-looking square-root comparison involving Hellinger affinity.

1. The question

Let $X=(X_1,\ldots,X_n)$ be independent uniform signs, each equal to plus or minus one. Before noise is applied, choose a Boolean summary $f(X)$, also taking values plus or minus one.

Each coordinate then passes through an independent bit-flip channel, producing a noisy vector $Y$. A receiver sees all of $Y$, rather than only one further Boolean summary. How much information about $f(X)$ remains?

A natural candidate is a coordinate, $f(X)=X_i$. Majority combines many inputs, while parity uses all inputs symmetrically, but combining more bits need not preserve more information about a one-bit summary.

The Courtade–Kumar conjecture says no Boolean summary beats a coordinate. The family claims this conclusion, a sharp extension to randomized binary summaries, and a separate Hellinger inequality that also implies the Boolean information bound.

2. Background and essential definitions

The noise parameter

Write $Y_i=X_iZ_i$, where the independent noise signs satisfy $\mathbb E Z_i=\rho$. For ordinary flip probability $\varepsilon\in[0,1/2]$,

$$\rho=1-2\varepsilon.$$

Thus $\rho=1$ means no noise and $\rho=0$ means the output is independent of the input. The manuscripts also allow negative correlation; symmetry makes absolute correlation the relevant quantity in the information bound.

Entropy and mutual information

The binary entropy in bits is

$$h_2(p)=-p\log_2p-(1-p)\log_2(1-p),$$

with $0\log_2 0=0$. It is one for a fair bit and zero for a deterministic bit.

Mutual information $I(U;Y)=H(U)-H(U\mid Y)$ measures how much observing $Y$ reduces uncertainty about $U$. It is not the same as the probability of predicting $U$ correctly.

For a coordinate summary, the other noisy coordinates carry no extra information, and

$$I(X_i;Y)=1-h_2(\varepsilon).$$

The main Boolean comparison says this is an upper bound for every $f$.

Randomized summaries and output bias

A randomized binary summary $U$ can be described by its conditional mean

$$u(x)=\mathbb E[U\mid X=x]\in[-1,1].$$

The value $u(x)$ determines the conditional probabilities of its two outputs. Ordinary Boolean functions are the special case $u(x)\in\{-1,1\}$.

The mean $m=\mathbb E f(X)$ measures output bias. A fair input vector need not produce a fair summary: an AND-like rule may output one only rarely.

The noise operator is the conditional averaging map $T_\rho u(y)=\mathbb E[u(X)\mid Y=y]$. It describes the receiver’s posterior mean of the summary. A single coordinate satisfies $T_\rho x_i=\rho y_i$.

3. Development history and previous partial results

Courtade and Kumar formulated the information question in work presented in 2013 and published in 2014. Its simple appearance hides a dimension-independent comparison over every Boolean function.

Partial results established the conjecture in high-noise regimes. Samorodnitsky proved it for all Boolean functions in a dimension-independent high-noise range. Yu’s work on stability and later local optimality enlarged ranges for balanced functions.

Other results addressed neighboring formulations. Pichler, Piantanida, and Matz proved coordinate optimality when the noisy observation is itself reduced to one Boolean output. That is not the same as letting the receiver observe the full vector.

The 2017 Hellinger conjecture of Anantharam and collaborators replaced the entropy comparison by a square-root affinity inequality and showed that it implies the Courtade–Kumar conclusion. Chen and Nair developed mean-dependent bounds and dimension-induction methods in this direction.

Chen, Gohari, and Nair proposed a differential approach: control instantaneous information loss under gradually increasing noise, then integrate the inequality. Both manuscripts in this family develop that viewpoint.

The source history also includes several September 2026 preprints announcing full Courtade–Kumar proofs, including Chen and collaborators, Ky and Tran, and Mahdavifar and Beirami. M1 explicitly acknowledges overlap: an estimate in the first of these also yields its soft-channel contraction when integrated while retaining initial information. Its additional claims concern its proof route and mean-dependent production bound. M2’s Hellinger statement is a distinct functional inequality.

4. What the new manuscripts claim

In bit units, the Boolean consequence is

$$I(f(X);Y)\le1-h_2(\varepsilon)$$

for every dimension and every Boolean $f$. Signed coordinates attain equality.

To state M1’s more general comparison, define

$$\psi(a)=1-h_2\!\left(\frac{1+a}{2}\right),\qquad 0\le a\le1.$$

This is increasing, so it has an inverse on $[0,1]$. M1 claims that every randomized binary summary satisfies

$$I(U;Y)\le\psi\!\left(|\rho|\,\psi^{-1}(I(U;X))\right).$$

The papers use natural logarithms; this display is the same normalized statement in bits. A soft coordinate with $u(x)=a x_i$ attains the bound at the corresponding initial information level.

For a deterministic summary, $I(f(X);X)=H(f(X))$. Substituting its actual output entropy gives a stricter upper curve when the output is biased. This does not assert that every fixed output bias attains that refined curve.

For M2, put $K(t)=\sqrt{1-t^2}$. Its claim is

$$K(m)-\mathbb E K(T_\rho f)\le1-K(\rho), \qquad m=\mathbb E f.$$

It applies to every Boolean output bias and every $\rho\in[-1,1]$. Signed coordinates attain equality. M2 also reproduces the established implication from this inequality to the Boolean information bound.

M1 additionally states a mean-dependent lower bound on instantaneous entropy production, stronger than the information-only rate in specified regimes. It should be distinguished from simply restating the finite-noise Boolean conclusion.

5. Why the advance matters

Importance: 4/5, provisional. The problem asks for an exact extremal principle at the intersection of information theory and Boolean-function analysis. A dimension-independent sharp comparison explains how much information a single-bit compression can retain through product noise.

The randomized-summary result is especially interpretable: match two summaries by the information they initially contain, then compare how much survives. The coordinate-based summary supplies the claimed optimal curve at every initial-information level.

The Hellinger inequality connects this information question with another measure of statistical distinguishability. Its inclusion of biased outputs matters because restricting to balanced functions would omit much of the Boolean class.

The rating reflects the scope of the functional statements and methods. It does not imply exclusive priority for the ordinary Courtade–Kumar conclusion, which the manuscripts themselves compare with contemporaneous claims.

6. The main idea

Increase the noise continuously

Set $\rho=e^{-t}$, so increasing time $t$ adds more noise. The operators $T_{e^{-t}}$ compose like a continuous evolution.

Information decreases along this evolution. Its derivative can be expressed through local costs on edges of the discrete cube, where neighboring inputs differ in one bit. If one bounds the rate of information loss by the rate for a coordinate carrying the same information, integration yields the desired finite-noise comparison.

A linear rate estimate is not sharp enough. The coordinate curve is nonlinear, and the proof must preserve the extra information in that curvature.

Join two smaller cubes carefully

Splitting along one input coordinate produces two lower-dimensional functions. Their information-loss rates contribute, but joining them adds another cost.

M1 optimizes that joining cost while tracking both mean and conditional entropy. Its local optimizer consists of one interior pair and possibly the two corners corresponding to common deterministic outputs. The construction uses two entropy capacities and comparisons describing how adding common outputs changes the required cost.

Keeping the mean is essential: an information-only local inequality does not close the induction for every coupled pair. The manuscript combines profiles so the dimension induction survives all bias regimes.

Interpret the square-root expression

For a nonconstant Boolean summary, let $P_+$ and $P_-$ be the laws of the noisy vector conditional on the two summary outputs. Their Hellinger affinity is

$$A(P_+,P_-)=\sum_y\sqrt{P_+(y)P_-(y)}.$$

Large affinity means the two conditional laws overlap substantially. The left side of M2’s inequality equals $K(m)(1-A(P_+,P_-))$, a bias-weighted distinguishability measure.

M2 combines an asymmetric dimension induction in one noise range with an energy-continuation argument in the remaining range. At a hypothetical first failure, the rate comparison would contradict the required crossing behavior. It treats different bias regimes separately and attributes fixed scalar inequalities to exact finite arithmetic certificates included with the manuscript.

7. Scope, limitations, and open questions

The input bits are independent and uniform. Arbitrary output bias means the summary may be unbalanced; it does not mean the theorem permits arbitrary nonuniform input distributions.

The summary is binary. Multi-bit compression, correlated input noise, and other channels require separate statements. Nor is the bound a universal claim that a coordinate optimizes every conceivable accuracy or stability criterion.

M1’s sharpness is at fixed initial information over randomized binary channels. Determining all optimizers under additional fixed-bias constraints is a different question, and the manuscript does not claim every biased Boolean source reaches its refined upper curve.

8. Sources and further reading

M1 states the soft-channel theorem, Boolean refinement, and entropy-production comparison. M2 defines the Hellinger affinity interpretation and its implication to Courtade–Kumar. The original conjecture papers and the differential-method sources linked above provide the main historical path without requiring their technical details to follow the claims.

Source manuscripts

• M1. OpenAI, Sharp binary-information contraction on the discrete cube (September 24, 2026).
• M2. OpenAI, Hellinger contraction with arbitrary Boolean output bias (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.