OctoInformBeta

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

§1 (setting): uniform cube, binary channels and information: Entropy deficits in natural units and mutual information in bits for a binary symmetric channel

Binary information on the uniform cube.

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

A Boolean function of a uniform cube point and a noisy copy of that point have a joint distribution whose mutual information can be expressed through bias entropy. For a nonnegative integer nn, the uniform cube Ωn={−1,1}n\Omega_n=\{-1,1\}^n assigns mass 2−n2^{-n} to each point.✦ The uniform average 𝔼g\mathbb E g of a real function g:Ωn→ℝg:\Omega_n\to\mathbb R is the scalar in (1). 𝔼g=12n∑x∈Ωng(x).\mathbb E g=\frac{1}{2^n}\sum_{x\in\Omega_n}g(x).(1)✦

Write L=log⁡2L=\log 2, with natural logarithms throughout the entropy definitions, and use the convention 0log⁡0=00\log 0=0.✦ The entropy gap ψ(v)\psi(v) of a bias v∈[−1,1]v\in[-1,1] is the scalar defined by (2). ψ(v)=1+v2log⁡(1+v)+1−v2log⁡(1−v).\psi(v)=\frac{1+v}{2}\log(1+v)+\frac{1-v}{2}\log(1-v).(2)✦ For a bias v∈[−1,1]v\in[-1,1], the bias entropy H(v)H(v) is given by (3). H(v)=L−ψ(v).H(v)=L-\psi(v).(3)✦ Averaging the bias entropy over the cube gives the mean bias entropy 𝔼H(g)\mathbb E H(g) of a field g:Ωn→[−1,1]g:\Omega_n\to[-1,1], as in (4). 𝔼H(g)=12n∑x∈ΩnH(g(x)).\mathbb E H(g)=\frac{1}{2^n}\sum_{x\in\Omega_n}H(g(x)).(4)✦ The information deficit I(g)I(g) of a field g:Ωn→[−1,1]g:\Omega_n\to[-1,1] is the entropy difference in (5). I(g)=H(𝔼g)−𝔼H(g).I(g)=H(\mathbb E g)-\mathbb E H(g).(5)✦ The logarithmic product tlog⁡tt\log t is the real function that multiplies a real argument tt by its natural logarithm.✦

The transition kernel BεB_\varepsilon of a binary symmetric channel on Ωn\Omega_n with crossover probability ε∈[0,1]\varepsilon\in[0,1] is the function of two cube points given by (6). Bε(x,y)=∏i=1n{1−ε,xi=yi,ε,xi≠yi.B_\varepsilon(x,y)=\prod_{i=1}^n \begin{cases} 1-\varepsilon,&x_i=y_i,\\ \varepsilon,&x_i\ne y_i. \end{cases}(6)✦ The noise kernel KρK_\rho with correlation ρ=1−2ε\rho=1-2\varepsilon is the function of two cube points in (7). Kρ(x,y)=∏i=1n{(1+ρ)/2,xi=yi,(1−ρ)/2,xi≠yi.K_\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}(7)✦ The noise operator TρT_\rho sends a real function gg on Ωn\Omega_n to the function defined by (8). (Tρg)(x)=∑y∈ΩnKρ(x,y)g(y).(T_\rho g)(x)=\sum_{y\in\Omega_n}K_\rho(x,y)g(y).(8)✦ The sign representation sfs_f of a Boolean function f:Ωn→{0,1}f:\Omega_n\to\{0,1\} is the real function on Ωn\Omega_n given by (9). sf(x)={1,f(x)=1,−1,f(x)=0.s_f(x)= \begin{cases} 1,&f(x)=1,\\ -1,&f(x)=0. \end{cases}(9)✦

Let XX be uniform on Ωn\Omega_n, and let YY be the channel output with conditional law Bε(X,⋅)B_\varepsilon(X,\cdot). The joint probability qb(y)q_b(y) of f(X)=bf(X)=b and Y=yY=y, for b∈{0,1}b\in\{0,1\}, is defined by (10). qb(y)=12n∑x∈Ωn𝟏{f(x)=b}Bε(x,y).q_b(y)=\frac{1}{2^n}\sum_{x\in\Omega_n} \mathbf 1_{\{f(x)=b\}}B_\varepsilon(x,y).(10)✦ Summing over the observation gives the function marginal pb=Pr⁡{f(X)=b}p_b=\Pr\{f(X)=b\} in (11). pb=∑y∈Ωnqb(y).p_b=\sum_{y\in\Omega_n}q_b(y).(11)✦ The observation marginal pY(y)=Pr⁡{Y=y}p_Y(y)=\Pr\{Y=y\} is given by (12). pY(y)=∑b∈{0,1}qb(y).p_Y(y)=\sum_{b\in\{0,1\}}q_b(y).(12)✦ The mutual information 𝖨(f(X);Y)\mathsf I(f(X);Y), measured in bits, is the functional of the joint law of f(X)f(X) and YY given by (13). 𝖨(f(X);Y)=1L∑b∈{0,1},y∈Ωnqb(y)>0qb(y)log⁡qb(y)pbpY(y).\mathsf I(f(X);Y)=\frac{1}{L} \sum_{\substack{b\in\{0,1\},\ y\in\Omega_n\\q_b(y)>0}} q_b(y)\log\frac{q_b(y)}{p_b p_Y(y)}.(13)✦ The binary entropy h2(ε)h_2(\varepsilon) of a bit with success probability ε\varepsilon is the function in (14), also measured in bits. h2(ε)=−εlog⁡ε+(1−ε)log⁡(1−ε)L.h_2(\varepsilon)= -\frac{\varepsilon\log\varepsilon+ (1-\varepsilon)\log(1-\varepsilon)}{L}.(14)✦

The Claim

Theorem 1. Let f:Ωn→{0,1}f:\Omega_n\to\{0,1\} be a Boolean function, and let 0≤ε≤120\le\varepsilon\le\tfrac12. For the uniform input XX and binary symmetric channel output YY, the mutual information and information deficit satisfy (15). 𝖨(f(X);Y)=I(T1−2εsf)L.\mathsf I(f(X);Y)=\frac{I(T_{1-2\varepsilon}s_f)}{L}.(15)✦

What Is Checked

The identity (15) is stated over Boolean functions on any uniform cube and binary symmetric channels whose crossover probability lies in [0,12][0,\tfrac12].