OctoInformBeta

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

Section 2 (setting): the cell-degree and conditioning calculus: Cell degree bounds and conditional coordinate sums for observations on a cube and its independent blocks

Degree and scores under finite observations.

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 finite observation records a report at each point of a sign cube. Its fibers specify which distinctions between inputs remain available to a function of the report; the conditional coordinate sum measures the information about that sum retained by the observation.

The sign cube on a finite coordinate set II is ΩI={−1,1}I\Omega_I=\{-1,1\}^I, whose coordinate signs xix_i are real numbers.✦ For a real-valued function hh on a finite set AA, its uniform mean is 𝔼Ah={|A|−1∑a∈Ah(a),A≠⌀,0,A=⌀.\mathbb E_A h= \begin{cases} |A|^{-1}\displaystyle\sum_{a\in A}h(a),&A\ne\varnothing,\\ 0,&A=\varnothing. \end{cases}(1)✦ Every cube average uses the mean in (1).

For S⊆IS\subseteq I, the Fourier character χS\chi_S is the product of the coordinate signs in SS.✦ The real Fourier-Walsh coefficient of f:ΩI→ℝf:\Omega_I\to\mathbb R and its ordinary real multilinear Fourier degree are defined by χS(x)=∏i∈Sxi,fˆ(S)=𝔼ΩI(fχS),deg⁡f=max⁡({0}∪{|S|:S⊆I,fˆ(S)≠0}).\chi_S(x)=\prod_{i\in S}x_i, \qquad \widehat f(S)=\mathbb E_{\Omega_I}(f\chi_S), \qquad \deg f=\max\bigl(\{0\}\cup \{|S|:S\subseteq I,\ \widehat f(S)\ne0\}\bigr).(2)

Cells and Conditional Scores

An observation F:A→BF:A\to B on a finite set AA is a map assigning a report in BB to each input. For an observation F:A→BF:A\to B and a report b∈Bb\in B, the cell indicator cF,b:A→ℝc_{F,b}:A\to\mathbb R is the indicator function of the fiber F−1(b)F^{-1}(b).✦ For an observation F:A→BF:A\to B on a finite set AA and a report b∈Bb\in B, the cell mass pF(b)p_F(b) is the uniform mean of the cell indicator cF,bc_{F,b}✦, and the restricted moment mF,g(b)m_{F,g}(b) of a function g:A→ℝg:A\to\mathbb R is the uniform mean of the product cF,bgc_{F,b}g: cF,b(a)=𝟏{F(a)=b},pF(b)=𝔼AcF,b,mF,g(b)=𝔼A(cF,bg).c_{F,b}(a)=\mathbf 1_{\{F(a)=b\}}, \qquad p_F(b)=\mathbb E_A c_{F,b}, \qquad m_{F,g}(b)=\mathbb E_A(c_{F,b}g).(3) The fiber conditional mean qF,g:B→ℝq_{F,g}:B\to\mathbb R is the ratio of the restricted moment to the cell mass in (3), with value zero on an empty fiber.✦ For an observation F:A→BF:A\to B on a finite set AA and a function g:A→ℝg:A\to\mathbb R, the conditional average 𝔼[g∣F]:A→ℝ\mathbb E[g\mid F]:A\to\mathbb R is the function whose value on the fiber F−1(b)F^{-1}(b) is the fiber conditional mean qF,g(b)q_{F,g}(b): qF,g(b)=mF,g(b)pF(b),𝔼[g∣F](a)=qF,g(F(a)),00=0.q_{F,g}(b)=\frac{m_{F,g}(b)}{p_F(b)}, \qquad \mathbb E[g\mid F](a)=q_{F,g}(F(a)), \qquad \frac00=0.(4)

The coordinate sum sI:ΩI→ℝs_I:\Omega_I\to\mathbb R and the score SF:ΩI→ℝS_F:\Omega_I\to\mathbb R of an observation F:ΩI→BF:\Omega_I\to B are sI(x)=∑i∈Ixi,SF=𝔼[sI∣F].s_I(x)=\sum_{i\in I}x_i, \qquad S_F=\mathbb E[s_I\mid F].(5) For a finite block set JJ, write xj=(xj,i)i∈Ix_j=(x_{j,i})_{i\in I} for the jjth block of x∈ΩJ×Ix\in\Omega_{J\times I}. The grouped observation F[J]:ΩJ×I→BJF^{[J]}:\Omega_{J\times I}\to B^J applies FF to each block: F[J](x)=(F(xj))j∈J.F^{[J]}(x)=\bigl(F(x_j)\bigr)_{j\in J}.(6)✦ Its score uses (5) with coordinate set J×IJ\times I.

For an observation F:A→BF:A\to B, a function g:A→ℝg:A\to\mathbb R, and a finite set JJ, the observation tuple TF:AJ→BJT_F:A^J\to B^J and block sum Gg:AJ→ℝG_g:A^J\to\mathbb R are defined by TF(y)=(F(yj))j∈JT_F(y)=(F(y_j))_{j\in J} and Gg(y)=∑j∈Jg(yj)G_g(y)=\sum_{j\in J}g(y_j). For an observation tuple TF:AJ→BJT_F:A^J\to B^J and a map H:BJ→CH:B^J\to C, the coarsened observation CH:AJ→CC_H:A^J\to C is the composite CH=H∘TFC_H=H\circ T_F.

The Claim

Theorem 1. Let II be finite. Let tt be a finite index set and dd a degree bound. For a family of real-valued functions fj:ΩI→ℝf_j:\Omega_I\to\mathbb R indexed by tt and satisfying deg⁡fj≤d\deg f_j\le d for every j∈tj\in t, deg⁡(∑j∈tfj)≤d.\deg\left(\sum_{j\in t}f_j\right)\le d.(7)✦ For arbitrary real-valued functions f,g:ΩI→ℝf,g:\Omega_I\to\mathbb R, deg⁡(fg)≤deg⁡f+deg⁡g.\deg(fg)\le\deg f+\deg g.(8)✦ For any finite set ss and real-valued cube functions fjf_j, deg⁡(∏j∈sfj)≤∑j∈sdeg⁡fj.\deg\left(\prod_{j\in s}f_j\right) \le\sum_{j\in s}\deg f_j.(9)✦

Let BB be finite, and let F:ΩI→BF:\Omega_I\to B have deg⁡cF,b≤D\deg c_{F,b}\le D for every b∈Bb\in B. For every u:B→ℝu:B\to\mathbb R, deg⁡(u∘F)≤D.\deg(u\circ F)\le D.(10)✦ More generally, let JJ be finite and let Fj:ΩI→BF_j:\Omega_I\to B satisfy deg⁡cFj,b≤Dj\deg c_{F_j,b}\le D_j for every j∈Jj\in J and b∈Bb\in B. For every u:BJ→ℝu:B^J\to\mathbb R, deg⁡(x↦u((Fj(x))j∈J))≤∑j∈JDj.\deg\bigl(x\mapsto u((F_j(x))_{j\in J})\bigr) \le\sum_{j\in J}D_j.(11)✦

Let AA be finite, F:A→BF:A\to B, g:A→ℝg:A\to\mathbb R, and H:B→CH:B\to C. Then 𝔼[g∣H∘F]=𝔼[𝔼[g∣F]∣H∘F].\mathbb E[g\mid H\circ F] =\mathbb E[\mathbb E[g\mid F]\mid H\circ F].(12)✦ For a finite set JJ and any H:BJ→CH:B^J\to C, 𝔼[Gg∣CH]=𝔼[y↦∑j∈J𝔼[g∣F](yj)|CH].\mathbb E[G_g\mid C_H] =\mathbb E\left[y\mapsto \sum_{j\in J}\mathbb E[g\mid F](y_j)\,\middle|\,C_H\right].(13)✦ For the observation tuple itself, 𝔼[Gg∣TF](y)=∑j∈J𝔼[g∣F](yj).\mathbb E[G_g\mid T_F](y) =\sum_{j\in J}\mathbb E[g\mid F](y_j).(14)✦

Let F:ΩI→BF:\Omega_I\to B satisfy deg⁡cF,b≤D\deg c_{F,b}\le D for every b∈Bb\in B. For every b∈BJb\in B^J, the grouped observation in (6) satisfies deg⁡cF[J],b≤|J|D.\deg c_{F^{[J]},b}\le |J|D.(15)✦ For every observation F:ΩI→BF:\Omega_I\to B, its grouped score satisfies SF[J](x)=∑j∈JSF(xj).S_{F^{[J]}}(x)=\sum_{j\in J}S_F(x_j).(16)✦

In the paper, the result reads: every function of FF has degree at most its cell degree bound DD; functions of observations on disjoint blocks with bounds DjD_j have degree at most ∑jDj\sum_jD_j; products have degree at most the sum of the degrees; for independent uniform blocks, conditioning the total sum on the observation tuple gives the sum of the block scores, and conditioning further on any function QQ of that tuple preserves this score identity.

What Is Checked

The bounds (7), (8), (9), (10), (11), and (15) are stated for real-valued functions on finite sign cubes and, where observations occur, finite report sets; the identities (12), (13), (14), and (16) use conditional averages on finite uniform spaces and their products.