OctoInformBeta

OpenAI preprint, September 2026 · §1. The contraction theorem and its mechanism

Corollary 1.2: Uniform finite cubes, including dimension zero, with noise correlation 0≤ρ≤10\le\rho\le1

Coordinates attain the Boolean information bound.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let XX be uniform on the discrete cube Ωn={−1,1}n\Omega_n=\{-1,1\}^n, where n≥0n\ge0. An observation YY is obtained by flipping each coordinate independently with probability ϵ\epsilon. The question is how much information about YY a single Boolean function of XX can retain. A sign-valued function f:Ωn→ℝf:\Omega_n\to\mathbb R is a function taking only the values −1-1 and 11.✦

The uniform cube expectation 𝔼g\mathbb E g of a real function g:Ωn→ℝg:\Omega_n\to\mathbb R is the real number given by (1). 𝔼g=2−n∑x∈Ωng(x).\mathbb E g=2^{-n}\sum_{x\in\Omega_n}g(x).(1)✦

The dictator did_i and its complement d‾i\bar d_i on Ωn\Omega_n are the coordinate functions in (2), for 1≤i≤n1\le i\le n. di(x)=xi,d‾i(x)=−xi.d_i(x)=x_i,\qquad \bar d_i(x)=-x_i.(2)

The bit-flip kernel Kϵ(x,y)K_\epsilon(x,y) for ϵ∈ℝ\epsilon\in\mathbb R and x,y∈Ωnx,y\in\Omega_n is defined by (3). For 0≤ϵ≤10\le\epsilon\le1, it is the conditional probability of observing yy given X=xX=x. Kϵ(x,y)=∏i=1n{1−ϵ,xi=yi,ϵ,xi≠yi.K_\epsilon(x,y)=\prod_{i=1}^n \begin{cases} 1-\epsilon,&x_i=y_i,\\ \epsilon,&x_i\ne y_i. \end{cases}(3)✦ The correlation parameter is ρ=1−2ϵ\rho=1-2\epsilon. The noise transition kernel NρN_\rho and the noise operator TρT_\rho on real functions are defined by (4), for real ρ\rho. Nρ(x,y)=∏i=1n{(1+ρ)/2,xi=yi,(1−ρ)/2,xi≠yi,(Tρg)(x)=∑y∈ΩnNρ(x,y)g(y).N_\rho(x,y)=\prod_{i=1}^n \begin{cases} (1+\rho)/2,&x_i=y_i,\\ (1-\rho)/2,&x_i\ne y_i, \end{cases} \qquad (T_\rho g)(x)=\sum_{y\in\Omega_n}N_\rho(x,y)g(y).(4)

Entropy and Information

Put L=log⁡2L=\log2.✦ The logarithmic function χ:ℝ→ℝ\chi:\mathbb R\to\mathbb R is defined by (5). χ(t)={tlog⁡|t|,t≠0,0,t=0.\chi(t)=\begin{cases}t\log|t|,&t\ne0,\\0,&t=0.\end{cases}(5)✦ The binary entropy deficit ψ\psi and entropy function HH, in nats, are the real-valued functions on ℝ\mathbb R given by (6). ψ(v)=χ(1+v)+χ(1−v)2,H(v)=L−ψ(v)(v∈ℝ).\psi(v)=\frac{\chi(1+v)+\chi(1-v)}2, \qquad H(v)=L-\psi(v)\qquad(v\in\mathbb R).(6) The binary entropy function h:ℝ→ℝh:\mathbb R\to\mathbb R, in bits, is given by (7). h(ϵ)=−χ(ϵ)+χ(1−ϵ)L.h(\epsilon)=-\frac{\chi(\epsilon)+\chi(1-\epsilon)}{L}.(7)✦ The mean binary entropy 𝔼H(g)\mathbb E H(g) of a real field g:Ωn→ℝg:\Omega_n\to\mathbb R is the cube average of its pointwise entropies✦, and the information deficit I(g)I(g) of gg is the entropy Jensen gap in (8). I(g)=H(𝔼g)−𝔼H(g).I(g)=H(\mathbb E g)-\mathbb E H(g).(8)✦

The joint law pϵfp_\epsilon^f of f(X)f(X) and YY, and its function and observation marginals pϵ,Bfp_{\epsilon,B}^f and pϵ,Yfp_{\epsilon,Y}^f, are given by (9) and (10), for b∈{−1,1}b\in\{-1,1\} and y∈Ωny\in\Omega_n. pϵf(b,y)=2−n∑x∈Ωn𝟏{f(x)=b}Kϵ(x,y).p_\epsilon^f(b,y)=2^{-n}\sum_{x\in\Omega_n} \mathbf1_{\{f(x)=b\}}K_\epsilon(x,y).(9)✦ pϵ,Bf(b)=∑y∈Ωnpϵf(b,y),pϵ,Yf(y)=∑b∈{−1,1}pϵf(b,y).p_{\epsilon,B}^f(b)=\sum_{y\in\Omega_n}p_\epsilon^f(b,y), \qquad p_{\epsilon,Y}^f(y)=\sum_{b\in\{-1,1\}}p_\epsilon^f(b,y).(10) The mutual information 𝖨ϵ(f)\mathsf I_\epsilon(f) between f(X)f(X) and YY, measured in bits, is the sum in (11). 𝖨ϵ(f)=1L∑b∈{−1,1},y∈Ωnpϵf(b,y)>0pϵf(b,y)log⁡pϵf(b,y)pϵ,Bf(b)pϵ,Yf(y).\mathsf I_\epsilon(f)=\frac1L \sum_{\substack{b\in\{-1,1\},\ y\in\Omega_n\\p_\epsilon^f(b,y)>0}} p_\epsilon^f(b,y)\log \frac{p_\epsilon^f(b,y)}{p_{\epsilon,B}^f(b)p_{\epsilon,Y}^f(y)}.(11)✦

The Claim

Theorem 1 (Boolean information bound). Let n≥0n\ge0, let f:Ωn→{−1,1}f:\Omega_n\to\{-1,1\}, and suppose 0≤ϵ≤120\le\epsilon\le\tfrac12, with ρ=1−2ϵ\rho=1-2\epsilon. The entropy-gap bound is (12), and the mutual information bound is (13). I(Tρf)≤ψ(ρ).I(T_\rho f)\le\psi(\rho).(12)✦ 𝖨ϵ(f)≤1−h(ϵ).\mathsf I_\epsilon(f)\le1-h(\epsilon).(13)✦ For n≥1n\ge1 and 1≤i≤n1\le i\le n, the coordinate and complemented coordinate have the mutual information values in (14) and (15), respectively. 𝖨ϵ(di)=1−h(ϵ).\mathsf I_\epsilon(d_i)=1-h(\epsilon).(14)✦ 𝖨ϵ(d‾i)=1−h(ϵ).\mathsf I_\epsilon(\bar d_i)=1-h(\epsilon).(15)✦ For every real ρ\rho, their entropy gaps satisfy (16) and (17). I(Tρdi)=ψ(ρ).I(T_\rho d_i)=\psi(\rho).(16)✦ I(Tρd‾i)=ψ(ρ).I(T_\rho\bar d_i)=\psi(\rho).(17)✦ The Courtade-Kumar assertion 𝒞\mathcal C in (18) is the universal positive-dimension version of (13) throughout 0≤ϵ≤120\le\epsilon\le\tfrac12.✦ 𝒞.\mathcal C.(18)✦ The dictator attainment assertion 𝒜\mathcal A in (19) requires (14) and (15) for every coordinate in every positive dimension throughout 0≤ϵ≤120\le\epsilon\le\tfrac12.✦ 𝒜.\mathcal A.(19)✦ The sharp information assertion 𝒮\mathcal S in (20) is 𝒞\mathcal C together with 𝒜\mathcal A.✦ 𝒮.\mathcal S.(20)✦

In the paper, the result reads: for n≥0n\ge0, ρ∈[−1,1]\rho\in[-1,1], and f:Ωn→{−1,1}f:\Omega_n\to\{-1,1\}, put m=𝔼fm=\mathbb E f and rm=(ψ|[0,1])−1(H(m))r_m=(\psi|_{[0,1]})^{-1}(H(m)); then the information in nats satisfies L𝖨(1−ρ)/2(f)≤ψ(|ρ|rm)≤ψ(|ρ|)L\mathsf I_{(1-\rho)/2}(f)\le\psi(|\rho|r_m)\le\psi(|\rho|), with signed coordinates attaining the bound when n≥1n\ge1 and m=0m=0, and with ψ(|ρ|rm)<ψ(|ρ|)\psi(|\rho|r_m)<\psi(|\rho|) when 0<|m|<10<|m|<1 and 0<|ρ|≤10<|\rho|\le1.

What Is Checked

The claims are stated over uniform finite cubes, sign-valued functions and the product noise law (9), including dimension zero in (12) and (13), with 0≤ρ≤10\le\rho\le1 for the general bounds and arbitrary real ρ\rho for the coordinate entropy-gap identities.