OctoInformBeta

The Courtade–Kumar and Hellinger conjectures

Let n≥0n\ge0 be an integer and let XX be uniform on Ωn={−1,1}n\Omega_n=\{-1,1\}^n. For −1≤ρ≤1-1\le\rho\le1, the noisy observation is Y=(XiZi)i=1nY=(X_iZ_i)_{i=1}^n, where the signs ZiZ_i are mutually independent, independent of XX, and have mean ρ\rho. A binary channel is specified by a function u:Ωn→[−1,1]u:\Omega_n\to[-1,1], the conditional mean of an auxiliary sign given XX. A Boolean summary is a channel f:Ωn→{−1,1}f:\Omega_n\to\{-1,1\}. All logarithms are natural. The entropy of a sign of mean r∈[−1,1]r\in[-1,1] is H(r)=−1+r2log⁡1+r2−1−r2log⁡1−r2H(r)=-\frac{1+r}{2}\log\frac{1+r}{2}-\frac{1-r}{2}\log\frac{1-r}{2}, with 0log⁡0=00\log0=0. Its entropy deficit is ψ(r)=log⁡2−H(r)\psi(r)=\log2-H(r). The information of a binary channel is I(u)=H(𝔼u)−𝔼H(u)I(u)=H(\mathbb E u)-\mathbb E H(u). The noise operator is Tρu(y)=𝔼[u(X)∣Y=y]T_\rho u(y)=\mathbb E[u(X)\mid Y=y]. Entropy production is the instantaneous decrease of information along Te−tT_{e^{-t}} for t≥0t\ge0. The extremal question asks which binary channel maximizes I(Tρu)I(T_\rho u) at fixed initial information I(u)I(u).

Courtade and Kumar conjectured that a single coordinate is optimal among Boolean summaries at every noise level and in every dimension. Ordentlich, Shayevitz, and Weinstein obtained asymptotically sharp high-noise bounds for Boolean functions whose mean is zero. Samorodnitsky proved the conjecture for all Boolean functions in a dimension-independent high-noise range.

Write ψ−1\psi^{-1} for the increasing inverse of ψ\psi from [0,log⁡2][0,\log2] to [0,1][0,1]. The preprint proves I(Tρu)≤ψ(|ρ|ψ−1(I(u)))I(T_\rho u)\le\psi(|\rho|\psi^{-1}(I(u))) for every binary channel and every −1≤ρ≤1-1\le\rho\le1. Soft coordinates are channels of the form u(x)=axiu(x)=a x_i, with |a|≤1|a|\le1. They attain equality when n≥1n\ge1. The preprint also derives a Boolean upper bound that uses the entropy of the output.

The Lean library BooleanNoise proves the universal Boolean inequality I(Tρf)≤ψ(ρ)I(T_\rho f)\le\psi(\rho) for 0≤ρ≤10\le\rho\le1, including dimension zero. Soft coordinates that are Boolean summaries attain the Lean library’s Boolean bound when n≥1n\ge1. The Lean library does not contain the output-entropy refinement. The Lean library proves an entropy-production bound for binary channels taking values in (−1,1)(-1,1) that are increasing in each coordinate. For binary channels taking values in (−1,1)(-1,1), the Lean library proves a sharp entropy-production bound only when information is at most ψ(1/5)\psi(1/5). Lean has checked every result of the Lean library, so the Lean library is the reference for these statements. The preprint guides only the order and names of the results.