OctoInformBeta

OpenAI preprint, September 2026 · Section 2. Finite observations and amplification

Proposition 2.3: Deterministic switching tables give a fixed multiplicative gain under iteration

Finite observations attain unbounded variance-to-cost ratios.

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

How large can the variance of a conditional coordinate sum be relative to a common Fourier degree bound for the observation’s cells?

For a finite coordinate set II, the sign cube is {−1,1}I\{-1,1\}^I, equipped with the uniform distribution.✦ For a real function f:{−1,1}I→ℝf:\{-1,1\}^I\to\mathbb R, a subset A⊆IA\subseteq I and a point x∈{−1,1}Ix\in\{-1,1\}^I, the uniform mean, Fourier characters and real Fourier-Walsh coefficients are defined by (1). 𝔼f=2−|I|∑x∈{−1,1}If(x),χA(x)=∏i∈Axi,fˆ(A)=𝔼[fχA],deg⁡f=max⁡({|A|:fˆ(A)≠0}∪{0}).\begin{aligned} \mathbb E f&=2^{-|I|}\sum_{x\in\{-1,1\}^I}f(x),& \chi_A(x)&=\prod_{i\in A}x_i,\\ \widehat f(A)&=\mathbb E[f\chi_A],& \deg f&=\max\bigl(\{|A|:\widehat f(A)\ne0\}\cup\{0\}\bigr). \end{aligned}(1) The degree in (1) is ordinary real multilinear Fourier degree, with degree zero for constants and the zero function.

A finite observation F:{−1,1}I→BF:\{-1,1\}^I\to B is a map to a finite report set BB. For a finite observation F:{−1,1}I→BF:\{-1,1\}^I\to B and a report b∈Bb\in B, the fiber indicator 𝟏F=b\mathbf1_{F=b} is the function on {−1,1}I\{-1,1\}^I that equals one on the fiber of bb and zero elsewhere.✦ The fiber probability pbp_b, restricted moment mb(g)m_b(g) and fiber conditional mean cb(g)c_b(g) of a real observable gg are given in (2); the conditional expectation evaluates this mean at the observed report. pb=𝔼𝟏F=b,mb(g)=𝔼[g𝟏F=b],cb(g)=mb(g)pb,𝔼[g∣F](x)=cF(x)(g).\begin{aligned} p_b&=\mathbb E\mathbf1_{F=b},& m_b(g)&=\mathbb E[g\mathbf1_{F=b}],& c_b(g)&=\frac{m_b(g)}{p_b},\\ \mathbb E[g\mid F](x)&=c_{F(x)}(g). \end{aligned}(2) The fiber conditional mean on an empty fiber is zero. The coordinate sum TIT_I, conditional score sFs_F and retained variance v(F)v(F) are defined by (3); the score is centered. TI(x)=∑i∈Ixi,sF=𝔼[TI∣F],v(F)=𝔼[sF2].T_I(x)=\sum_{i\in I}x_i,\qquad s_F=\mathbb E[T_I\mid F],\qquad v(F)=\mathbb E[s_F^2].(3)

A degree-controlled observation F:{−1,1}I→BF:\{-1,1\}^I\to B is a finite observation with positive retained variance and an assigned positive natural cell cost DFD_F bounding the Fourier degree of every fiber indicator.✦ Write 𝒪\mathcal O for these observations and ρ(F)\rho(F) for their ratio of retained variance to cell cost, as in (4). DF∈ℕ>0,v(F)>0,deg⁡𝟏F=b≤DF(b∈B),ρ(F)=v(F)DF.D_F\in\mathbb N_{>0},\qquad v(F)>0,\qquad \deg\mathbf1_{F=b}\le D_F\quad(b\in B),\qquad \rho(F)=\frac{v(F)}{D_F}.(4) The one-bit observation F0:{−1,1}→{−1,1}F_0:\{-1,1\}\to\{-1,1\} is the identity map with assigned cost DF0=1D_{F_0}=1.✦

Deterministic Switching Tables

For a finite block index set KK, the independent observation blocks of FF form the map FK:{−1,1}K×I→BKF^K:\{-1,1\}^{K\times I}\to B^K in (5).✦ A point of this cube is identified with its family of blocks xj=(xj,i)i∈Ix_j=(x_{j,i})_{i\in I}.✦ FK(x)j=F(xj)(j∈K).F^K(x)_j=F(x_j)\qquad(j\in K).(5) This identification is called the block coordinate equivalence.

Let Λ\Lambda be a finite leaf index set. For a block input space α\alpha, the selector and leaf input space is α×αΛ\alpha\times\alpha^\Lambda, and the full input space is (α×αΛ)×α(\alpha\times\alpha^\Lambda)\times\alpha✦; the last coordinate is the fallback block. For α={−1,1}I\alpha=\{-1,1\}^I, these spaces are identified with cubes on disjoint copies of II. Write a full input as (x0,(xi)i∈Λ,x*)(x_0,(x_i)_{i\in\Lambda},x_*). For a full input to the event-switched observation of FF, the old report is c=(F(x0),(F(xi))i∈Λ)c=(F(x_0),(F(x_i))_{i\in\Lambda}). For an event A⊆B×BΛA\subseteq B\times B^\Lambda, the event-switched observation sw⁡A(F)\operatorname{sw}_A(F) is the map in (6), whose two report sets are disjoint. sw⁡A(F)(x0,(xi),x*)={(1,F(x*)),c∈A,(0,c),c∉A.\operatorname{sw}_A(F)(x_0,(x_i),x_*)= \begin{cases} (1,F(x_*)),&c\in A,\\ (0,c),&c\notin A. \end{cases}(6) The switching block index set JJ consists of one selector index 00, one leaf index for each i∈Λi\in\Lambda, and one fallback index **. The switching block equivalence is the bijection from αJ\alpha^J to (α×αΛ)×α(\alpha\times\alpha^\Lambda)\times\alpha that sends a family to its selector block, its family of leaf blocks and its fallback block; its inverse reads the corresponding block at each index. The switching cube equivalence is the bijection from {−1,1}J×I\{-1,1\}^{J\times I} to ({−1,1}I×({−1,1}I)Λ)×{−1,1}I(\{-1,1\}^I\times(\{-1,1\}^I)^\Lambda)\times\{-1,1\}^I obtained by the block coordinate equivalence followed by the switching block equivalence.

A selector table S:B→ΛS:B\to\Lambda chooses a leaf from the selector report, and a leaf table L:Λ×B→{0,1}L:\Lambda\times B\to\{0,1\} assigns a pass or fail value to each leaf report. For a selector table S:B→ΛS:B\to\Lambda and a leaf table L:Λ×B→{0,1}L:\Lambda\times B\to\{0,1\}, the unique failing leaf event AS,L⊆B×BΛA_{S,L}\subseteq B\times B^\Lambda is the subset given in (7); the table-switched observation is sw⁡(F;S,L)=sw⁡AS,L(F)\operatorname{sw}(F;S,L)=\operatorname{sw}_{A_{S,L}}(F). AS,L={(c0,(ci)):L(S(c0),cS(c0))=0,L(i,ci)=1for every i≠S(c0)}.A_{S,L}=\bigl\{(c_0,(c_i)): L(S(c_0),c_{S(c_0)})=0,\quad L(i,c_i)=1\ \text{for every }i\ne S(c_0)\bigr\}.(7)✦

The Fixed Gaussian Parameters

The grid half-size NN, radius r0r_0, spacing δ\delta and tent width hh are the constants in (8). The leaf set is Λ={0,…,2N}\Lambda=\{0,\ldots,2N\}, with middle index NN and leaf centers aia_i given there. N=(2128)8,r0=96,δ=r0N,h=1(2128)12,ai=1+δ(i−N)(i∈Λ).\begin{aligned} N&=(2^{128})^8,\qquad r_0=96,\qquad \delta=\frac{r_0}{N},\qquad h=\frac{1}{(2^{128})^{12}},\\ a_i&=1+\delta(i-N)\qquad(i\in\Lambda). \end{aligned}(8) The clipping function qq takes values in [0,1][0,1]. The grid ramp differences HiH_i define the selector weights wiw_i, and the tent functions τa,h\tau_{a,h} define the leaf tests ℓi\ell_i, by (9). The selector tests are wiw_i. q(t)=max⁡{0,min⁡{1,t}},Hi(t)=q(t/δ+N−i+1)−q(t/δ+N−i),wi(t)=Hi(t)+𝟏{i=N}(1−∑j∈ΛHj(t)),τa,h(t)=max⁡{0,1−|t−a|/h},ℓi(t)=τai,h(t).\begin{aligned} q(t)&=\max\{0,\min\{1,t\}\},\\ H_i(t)&=q(t/\delta+N-i+1)-q(t/\delta+N-i),\\ w_i(t)&=H_i(t)+\mathbf1_{\{i=N\}}\Bigl(1-\sum_{j\in\Lambda}H_j(t)\Bigr),\\ \tau_{a,h}(t)&=\max\{0,1-|t-a|/h\},\qquad \ell_i(t)=\tau_{a_i,h}(t). \end{aligned}(9)

For a measure PP, a real observable TT and weights ui:ℝ→ℝu_i:\mathbb R\to\mathbb R, the weighted moments Mk(P,T,u;i)M_k(P,T,u;i) are the integrals in (10), for k∈{0,1,2}k\in\{0,1,2\}.✦ With γ\gamma the standard normal law, the Gaussian leaf and selector moment arrays are ll and ss, respectively. Mk(P,T,u;i)=∫ui(T(x))T(x)kdP(x),lki=Mk(γ,id⁡,ℓ;i),ski=Mk(γ,id⁡,w;i).\begin{aligned} M_k(P,T,u;i)&=\int u_i(T(x))T(x)^k\,dP(x),\\ l_{ki}&=M_k(\gamma,\operatorname{id},\ell;i),\qquad s_{ki}=M_k(\gamma,\operatorname{id},w;i). \end{aligned}(10) For moment arrays l,sl,s, the weighted means μi(l)\mu_i(l), weighted variances σi2(l)\sigma_i^2(l) and moment gain Γ(l,s)\Gamma(l,s) are defined by (11); quotients with zero denominator are assigned value zero. μi(l)=l1il0i,σi2(l)=l2il0i−μi(l)2,Γ(l,s)=(∏i∈Λl0i)(1+∑i∈Λσi2(l)−∑i∈Λs2i+2(1−μi(l))s1i+((1−μi(l))2+∑j≠iσj2(l))s0il0i).\begin{aligned} \mu_i(l)&=\frac{l_{1i}}{l_{0i}},\qquad \sigma_i^2(l)=\frac{l_{2i}}{l_{0i}}-\mu_i(l)^2,\\ \Gamma(l,s)&=\Bigl(\prod_{i\in\Lambda}l_{0i}\Bigr) \Biggl(1+\sum_{i\in\Lambda}\sigma_i^2(l)\\ &\qquad-\sum_{i\in\Lambda} \frac{\begin{gathered} s_{2i}+2(1-\mu_i(l))s_{1i}\\ +\bigl((1-\mu_i(l))^2+\sum_{j\ne i}\sigma_j^2(l)\bigr)s_{0i} \end{gathered}}{l_{0i}}\Biggr). \end{aligned}(11) The gain threshold η\eta is half the moment gain of the Gaussian arrays in (10), as specified in (12). η=12Γ(l,s).\eta=\frac12\Gamma(l,s).(12)✦

Definition 1. The amplification cost factor CC is the positive natural number in (13), and the amplification factor aa is the real number in (14). C=2N+2.C=2N+2.(13)✦ a=1+ηC.a=1+\frac{\eta}{C}.(14)✦

The Claim

Theorem 1. Let II and BB be finite sets, and let F:{−1,1}I→BF:\{-1,1\}^I\to B have v(F)>0v(F)>0. For a positive integer nn, write [n]={1,…,n}[n]=\{1,\ldots,n\} and let F[n]F^{[n]} denote the block map in (5) for K=[n]K=[n]. There are such an integer nn, a selector table S:B[n]→ΛS:B^{[n]}\to\Lambda and a leaf table L:Λ×B[n]→{0,1}L:\Lambda\times B^{[n]}\to\{0,1\} satisfying (15). nv(F)(|Λ|+1+η)<v(sw⁡(F[n];S,L)).n\,v(F)(|\Lambda|+1+\eta) < v\bigl(\operatorname{sw}(F^{[n]};S,L)\bigr).(15)✦ The fixed amplification factor satisfies (16). 1<a.1<a.(16)✦ Each degree-controlled observation F∈𝒪F\in\mathcal O admits a degree-controlled observation G∈𝒪G\in\mathcal O satisfying (17). aρ(F)<ρ(G).a\rho(F)<\rho(G).(17)✦ The one-bit observation has the ratio in (18). ρ(F0)=1.\rho(F_0)=1.(18)✦ At each nonnegative integer kk, some degree-controlled observation Fk∈𝒪F_k\in\mathcal O satisfies (19). ak≤ρ(Fk).a^k\le\rho(F_k).(19)✦ The ratio of retained variance to cell cost exceeds any prescribed real bound RR for some degree-controlled observation F∈𝒪F\in\mathcal O, as in (20). R<ρ(F).R<\rho(F).(20)✦

In the paper, the result reads: if integers 1≤d<r1\le d<r and a measurable observation rule WW on rr real inputs have every output indicator, on every product of finite input alphabets, expressible as a finite linear combination of functions of at most dd coordinates, and there is η0>0\eta_0>0 such that for every centered variance-one sequence ZjZ_j converging weakly to a standard normal with uniformly bounded fourth moments, independent copies 𝒁j=(Zj,1,…,Zj,r)\mathbf Z_j=(Z_{j,1},\ldots,Z_{j,r}) eventually satisfy Var⁡(𝔼[∑i=1rZj,i∣W(𝒁j)])≥d+η0\operatorname{Var}(\mathbb E[\sum_{i=1}^rZ_{j,i}\mid W(\mathbf Z_j)])\ge d+\eta_0, then finite observations have arbitrarily large v(F)/DFv(F)/D_F, and Theorem 1.1 follows.

What Is Checked

The variance statements concern uniform finite sign cubes and deterministic selector and leaf tables; the ratio statements concern observations with positive retained variance and assigned positive natural cell costs bounding every fiber indicator’s Fourier degree.