OctoInformBeta

OpenAI preprint, September 2026 · §6. Conditional averaging in the shared environment · §6

Lemma 6.2 [Conditional averaging]: With high salt bits frozen, ll sampled steps leave a fourth moment about the panel mean of at most 16(1−λ)l16(1-\lambda)^l times the panel’s fourth moment

The mean over the hit set factorizes and the sampled average mixes.

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

Fix a prime nn and let Vn=(ℤ/n)4V_n=(\mathbb{Z}/n)^4.✦ A rank channel over nn is a pair c=(a,b)c=(a,b) of a direction aa in the punctured frame Fn=Vn\{0}F_n=V_n\setminus\{0\} and an offset b∈Vnb\in V_n✦; its point at a residue yy modulo nn is c(y)=b+yac(y)=b+ya. Write Chn\mathrm{Ch}_n for the set of rank channels and Sw=(ℤ/2w)4S_w=(\mathbb{Z}/2^w)^4 for the salts of width ww, four registers of ww bits each. The shared environment of width ww is Ew=Chn×Chn×Chn×Sw.E_w=\mathrm{Ch}_n\times\mathrm{Ch}_n\times\mathrm{Ch}_n\times S_w.(1)✦

Retention is membership in a small box. At level kk the box side length is mk=⌊(n−1)/2k⌋+1=⌈n/2k⌉m_k=\lfloor (n-1)/2^k\rfloor+1=\lceil n/2^k\rceil✦, the box Bk⊆VnB_k\subseteq V_n is the set of vectors whose four coordinates have least nonnegative representatives below mkm_k✦, and BkB_k fills the fraction pk=(mkn)4p_k=\Big(\frac{m_k}{n}\Big)^4(2)✦ of VnV_n, close to 2−4k2^{-4k}. A residue yy modulo nn is called an identifier; a channel cc retains the identifier yy at level kk when c(y)∈Bkc(y)\in B_k. For identifiers x,yx,y and levels k,jk,j, the hit set Hk,j(x,y)H_{k,j}(x,y) is the set of environments (c1,c2,c3,σ)(c_1,c_2,c_3,\sigma) in which c1c_1 retains xx at level kk and c2c_2 retains yy at level jj.✦

Two questions are asked of this set: what the mean of a function over it is, and how fast a random walk on it, driven by affine maps of the channels and the salt, forgets its starting point when the high salt bits are frozen.

Averages and the Slice

For a finite set XX and a real function gg on XX, 𝔼t∈Xg(t)\mathbb{E}_{t\in X}\,g(t) is the sum of the values of gg divided by |X||X|✦, and the fourth moment of gg is M4(g)=𝔼t∈Xg(t)4M_4(g)=\mathbb{E}_{t\in X}\,g(t)^4.✦

A padded channel of level kk is a pair e=(a,v)e=(a,v) of a direction a∈Fna\in F_n and a short offset v∈Vmk=(ℤ/mk)4v\in V_{m_k}=(\mathbb{Z}/m_k)^4; PkP_k is the set of them.✦ The widening vˆ∈Vn\hat v\in V_n of vv replaces each coordinate by its least nonnegative representative, read modulo nn.✦ Opening ee at xx gives the rank channel (a,vˆ−xa)(a,\hat v-xa), whose point at xx is vˆ\hat v, a vector of BkB_k.✦

The slice of levels k,jk,j and width dd is the set Σk,j,d=Pk×Pj×Chn×Sd\Sigma_{k,j,d}=P_k\times P_j\times\mathrm{Ch}_n\times S_d(3)✦ of two padded channels, a rank channel and a salt. The opening map Φx,y:Σk,j,w→Ew\Phi_{x,y}\colon\Sigma_{k,j,w}\to E_w opens the first padded channel at xx and the second at yy, and keeps the rank channel and the salt.✦ For a real function ff on EwE_w, the conditional average of ff at (x,y)(x,y) is f‾k,j(x,y)=𝔼t∈Σk,j,wf(Φx,y(t)).\bar f_{k,j}(x,y)=\mathbb{E}_{t\in\Sigma_{k,j,w}}\,f\big(\Phi_{x,y}(t)\big).(4)✦

For d≤wd\le w, a register rr modulo 2w2^w splits into its low part rmod⁡2dr\bmod 2^d, a register of dd bits, and its high part ⌊r/2d⌋\lfloor r/2^d\rfloor, a register of w−dw-d bits.✦ Splitting the four registers identifies SwS_w with Sd×Sw−dS_d\times S_{w-d}✦, and so Σk,j,w\Sigma_{k,j,w} with Σk,j,d×Sw−d\Sigma_{k,j,d}\times S_{w-d}.✦ Freezing the high bits at z∈Sw−dz\in S_{w-d} gives the export map Φx,y,z:Σk,j,d→Ew\Phi_{x,y,z}\colon\Sigma_{k,j,d}\to E_w, t↦Φx,y(t,z)t\mapsto\Phi_{x,y}(t,z).✦ The panel of ff is the function fz=f∘Φx,y,zf_z=f\circ\Phi_{x,y,z} on Σk,j,d\Sigma_{k,j,d}✦, and the panel mean is μz=𝔼t∈Σk,j,dfz(t)\mu_z=\mathbb{E}_{t\in\Sigma_{k,j,d}}\,f_z(t).

Generators and the Mixing Family

Fix a modulus NN and write a vector of VN=(ℤ/N)4V_N=(\mathbb{Z}/N)^4 as a pair (ξ,η)(\xi,\eta) of faces in TN=(ℤ/N)2T_N=(\mathbb{Z}/N)^2. A command replaces the lead face ξ\xi by its image under a permutation of TNT_N that may depend on η\eta, and keeps η\eta.✦ There are ten commands: four shears, (ξ1,ξ2)↦(ξ1+δξ2,ξ2)(\xi_1,\xi_2)\mapsto(\xi_1+\delta\xi_2,\xi_2) and (ξ1,ξ2)↦(ξ1,ξ2+δξ1)(\xi_1,\xi_2)\mapsto(\xi_1,\xi_2+\delta\xi_1) with δ=±3\delta=\pm3; two translations of ξ\xi, by (1,0)(1,0) and by (0,1)(0,1); and four cross terms, which add η1\eta_1 or η2\eta_2 to ξ1\xi_1 or to ξ2\xi_2.✦

A generator g=(b,κ)g=(b,\kappa) is a bit bb and a command κ\kappa, twenty in all, and GG is their set.✦ The affine action Ag\mathrm{A}_g of a generator g=(b,κ)g=(b,\kappa) on VNV_N is the map that applies κ\kappa when b=0b=0 and, when b=1b=1, swaps the two faces, applies κ\kappa and swaps them back, so that κ\kappa changes η\eta.✦ The linear action Lg\mathrm{L}_g of a generator gg on VNV_N is the map obtained from Ag\mathrm{A}_g by replacing each translation with the identity; the frame permutation of gg is the restriction of Lg\mathrm{L}_g to FnF_n. On a channel or a padded channel, gg acts by g⋅(a,v)=(Lga,Agv)g\cdot(a,v)=(\mathrm{L}_g a,\mathrm{A}_g v), with Lg\mathrm{L}_g taken modulo nn and Ag\mathrm{A}_g modulo the modulus of vv.✦

A family of permutations of a set XX indexed by a set II assigns a permutation of XX to each element of II.✦ The union of a family on XX and a family on YY is the family on X×YX\times Y, indexed by the disjoint union of the two index sets, whose members move their own factor and fix the other.✦ The mixing family on Σk,j,d\Sigma_{k,j,d} is the union of four such families, indexed by the eighty generator choices Γ={1,2,3,4}×G\Gamma=\{1,2,3,4\}\times G, with the salt moved by Ag\mathrm{A}_g modulo 2d2^d: π(i,g)(e1,e2,c,σ)={(g⋅e1,e2,c,σ),i=1,(e1,g⋅e2,c,σ),i=2,(e1,e2,g⋅c,σ),i=3,(e1,e2,c,Agσ),i=4.\pi_{(i,g)}(e_1,e_2,c,\sigma)= \begin{cases} (g\cdot e_1,\,e_2,\,c,\,\sigma), & i=1,\\ (e_1,\,g\cdot e_2,\,c,\,\sigma), & i=2,\\ (e_1,\,e_2,\,g\cdot c,\,\sigma), & i=3,\\ (e_1,\,e_2,\,c,\,\mathrm{A}_g\sigma), & i=4. \end{cases}(5)✦

The Sampled Average

An atom is a pair of a bit and a generator choice✦; the atoms form a set 𝒜\mathcal{A} of 160160 elements, each of weight 1/1601/160. A roller index is a quadruple in 𝒲={0,…,10}4\mathcal{W}=\{0,\dots,10\}^4.✦ Each pair (α,ρ)(\alpha,\rho) of an atom and a roller index determines a roller step, a permutation of EwE_w that depends on kk, jj and dd. Each atom α\alpha and each point u∈Ewu\in E_w determine a winning roller index of α\alpha at uu, an element of 𝒲\mathcal{W} that depends on xx and yy as well. For paths p=(α1,…,αl)∈𝒜lp=(\alpha_1,\dots,\alpha_l)\in\mathcal{A}^l and r=(ρ1,…,ρl)∈𝒲lr=(\rho_1,\dots,\rho_l)\in\mathcal{W}^l, the roller walk Rp,rR_{p,r} applies the roller steps of (α1,ρ1),…,(αl,ρl)(\alpha_1,\rho_1),\dots,(\alpha_l,\rho_l) in this order✦, and (p,r)(p,r) is live at uu when each ρi\rho_i is the winning index of αi\alpha_i at the point that the first i−1i-1 steps reach from uu.✦ The ll-step sampled average of ff is Slf(u)=∑p∈𝒜l∑r∈𝒲l𝟏[(p,r) live at u]160−lf(Rp,r(u)).S_lf(u)=\sum_{p\in\mathcal{A}^l}\,\sum_{r\in\mathcal{W}^l} \mathbf{1}\big[(p,r)\text{ live at }u\big]\,160^{-l}\,f\big(R_{p,r}(u)\big).(6)✦

For a finite alphabet II and a real constant CC, the loss rate is λ(I,C)=116384(C|I|)2.\lambda(I,C)=\frac{1}{16384\,(C\,|I|)^2}.(7)✦ With the threshold τ=2(1−cos⁡(π/8))\tau=2(1-\cos(\pi/8)), the gap constant is C0=6+4/τC_0=6+4/\tau.✦

The Claim

Theorem 1. Let nn be a prime, kk and jj levels, xx and yy identifiers in ℤ/n\mathbb{Z}/n, ww a width, and ff a real function on EwE_w. Then 𝔼u∈Ew[𝟏Hk,j(x,y)(u)f(u)]=pkpjf‾k,j(x,y).\mathbb{E}_{u\in E_w}\big[\mathbf{1}_{H_{k,j}(x,y)}(u)\,f(u)\big]=p_k\,p_j\,\bar f_{k,j}(x,y).(8)✦ If moreover d≤wd\le w, z∈Sw−dz\in S_{w-d} and ll is a number of steps, then, with both fourth moments taken over Σk,j,d\Sigma_{k,j,d} and λ=λ(Γ,C0)\lambda=\lambda(\Gamma,C_0) the loss rate of the eighty generator choices at the gap constant, M4((Slf)∘Φx,y,z−μz)≤16(1−λ)lM4(fz).M_4\big((S_lf)\circ\Phi_{x,y,z}-\mu_z\big)\le 16\,(1-\lambda)^l\,M_4(f_z).(9)✦

In the paper, the result reads: on the product of rank channels conditioned on the retention of one identifier per conditioned channel, with designated free bits and the remaining bits frozen, there is a rational Markov operator KK whose stationary law is the uniform conditional law, with ∥Kl−Π∥Ls→Ls≤Cs2−csl\|K^l-\Pi\|_{L_s\to L_s}\le C_s2^{-c_sl} for each number of steps ll and each fixed 2≤s<∞2\le s<\infty, Π\Pi being the expectation under that law, and with constants independent of the field size, the side lengths, the bit lengths, the identifiers and the frozen bits.

The bound (9) is the fourth-moment form of this estimate, with the sampled average read through the export map in the role of KlK^l and the panel mean in that of Π\Pi.

What Is Checked

The claim is stated over the shared environment EwE_w of three rank channels over a prime nn and a salt, the boxes of levels kk and jj with their fractions pkp_k and pjp_j, the hit set Hk,j(x,y)H_{k,j}(x,y), the slice Σk,j,d\Sigma_{k,j,d} with its opening and export maps, the conditional average (4), the panel fzf_z and its mean μz\mu_z, the sampled average (6) with its atoms, roller steps and live paths, the fourth moment M4M_4, and the loss rate (7) at the gap constant. Beside it the library defines the mixing family (5) on the slice.

The library proves that the shear by −δ-\delta undoes the shear by δ\delta✦, so that every generator acts on VNV_N by a permutation, and that the linear action of a generator maps nonzero vectors to nonzero vectors. It also proves that splitting a register of ww bits into its low dd and high w−dw-d bits is a bijection, inverted by (ℓ,h)↦ℓ+2dh(\ell,h)\mapsto\ell+2^dh.✦