OctoInformBeta

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

Lemma 6.3 [Validated walk variants]: A permutation of all channels, independent of yy and picked by a digit guess, moves opened channels as the generator moves padded ones

The guessed variant performs the conditional generator step.

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

The environment is a set of channels, affine lines in (ℤ/n)4(\mathbb{Z}/n)^4 for a prime nn, and a walk moves them by affine maps drawn from a finite alphabet of generators. Fix a level kk and a retained parameter y∈ℤ/ny \in \mathbb{Z}/n, and condition on the line having its point at yy in the box of level kk, a cube of side mm about n/2kn/2^k. Such a line is recorded by a padded channel, whose offset is read modulo mm, and the generator acts on it modulo mm. The question is how to carry out this conditional step by a permutation of the whole environment that never reads yy, taken from a bounded menu by a guess at how the generator wraps around the box.

Channels and Boxes

For a modulus ll, the residue pairs modulo ll form the set Tl=(ℤ/l)2T_l = (\mathbb{Z}/l)^2✦, and the space Vl=Tl×TlV_l = T_l \times T_l is the set of pairs x=(x1,x2)x = (x_1, x_2) of residue pairs, that is (ℤ/l)4(\mathbb{Z}/l)^4.✦ The punctured frame FnF_n of VnV_n is the set of its nonzero vectors.✦ A channel over nn is a pair (a,b)(a, b) of a direction a∈Fna \in F_n and an offset b∈Vnb \in V_n; it describes the affine line y↦b+yay \mapsto b + ya in VnV_n.✦ The channels form the set Cn=Fn×VnC_n = F_n \times V_n.✦

The box side length at level kk over nn is m=⌊(n−1)/2k⌋+1m = \lfloor (n-1)/2^k \rfloor + 1, which equals ⌈n/2k⌉\lceil n/2^k \rceil.✦ A padded channel of level kk is a pair s=(a,w)s = (a, w) of a direction a∈Fna \in F_n and a short offset w∈Vmw \in V_m.✦ The widening wˆ\hat w of w∈Vmw \in V_m is the vector of VnV_n whose entries are the least nonnegative representatives of the entries of ww, read modulo nn; it lies in the box {0,…,m−1}4\{0, \dots, m-1\}^4 of level kk.✦ The opened channel of ss at a parameter y∈ℤ/ny \in \mathbb{Z}/n is the channel openy(s)=(a,wˆ−ya),\mathrm{open}_y(s) = (a,\ \hat w - y a),(1)✦ whose point at yy is wˆ\hat w.

Generators

The command alphabet is the disjoint union of three kinds of letters: shear choices, which are pairs of bits (b1,b2)(b_1, b_2); single bits bb, which select an axial direction; and cross pairs, pairs of bits (i,j)(i, j) that select a cross term.✦ A generator g=(g1,g2)g = (g_1, g_2) is a letter of the generator alphabet: a bit g1g_1, which says whether the two coordinate pairs of VlV_l are exchanged, and a command g2g_2.✦

For a bit bb and a residue dd modulo ll, the shear map shb,d\mathrm{sh}_{b,d} of TlT_l sends u=(u1,u2)u = (u_1, u_2) to (u1+du2,u2)(u_1 + d u_2, u_2) if b=1b = 1 and to (u1,u2+du1)(u_1, u_2 + d u_1) if b=0b = 0✦; as a permutation of TlT_l it is the shear permutation.✦ The shear amount σ(b)\sigma(b) of a bit bb is 33 if b=1b = 1 and −3-3 if b=0b = 0, and the axial unit vector e(b)e(b) of TlT_l is (1,0)(1, 0) if b=1b = 1 and (0,1)(0, 1) if b=0b = 0. For d=(d1,d2)∈Tld = (d_1, d_2) \in T_l and bits i,ji, j, the cross term κi,j(d)\kappa_{i,j}(d) is (t,0)(t, 0) if i=1i = 1 and (0,t)(0, t) if i=0i = 0, where t=d1t = d_1 if j=1j = 1 and t=d2t = d_2 if j=0j = 0.✦

For a flag ϵ∈{0,1}\epsilon \in \{0, 1\}, with ϵ=1\epsilon = 1 allowing translations, a command cc and a parameter d∈Tld \in T_l, the lead coordinate action is the permutation of TlT_l Lc,dϵ(u)={shb1,−σ(b2)(u)if c=(b1,b2) is a shear choice,u+ϵe(b)if c=b is a single bit,u+κi,j(d)if c=(i,j) is a cross pair.L^\epsilon_{c,d}(u) = \begin{cases} \mathrm{sh}_{b_1, -\sigma(b_2)}(u) & \text{if } c = (b_1, b_2) \text{ is a shear choice},\\ u + \epsilon\, e(b) & \text{if } c = b \text{ is a single bit},\\ u + \kappa_{i,j}(d) & \text{if } c = (i, j) \text{ is a cross pair}. \end{cases}(2)✦ The lead coordinate permutation Λcϵ\Lambda^\epsilon_c of VlV_l sends (x1,x2)(x_1, x_2) to (Lc,x2ϵ(x1),x2)(L^\epsilon_{c, x_2}(x_1), x_2)✦, and the face swap ϕb\phi_b of VlV_l sends (x1,x2)(x_1, x_2) to (x2,x1)(x_2, x_1) if b=1b = 1 and is the identity if b=0b = 0.✦ The generator action of gg on VlV_l is αgϵ=ϕg1∘Λg2ϵ∘ϕg1;\alpha^\epsilon_g = \phi_{g_1} \circ \Lambda^\epsilon_{g_2} \circ \phi_{g_1};(3)✦ write αg=αg1\alpha_g = \alpha^1_g for the affine action and λg=αg0\lambda_g = \alpha^0_g for the action without translations. The frame permutation of gg is the restriction of λg\lambda_g to the nonzero vectors FnF_n.✦ The generator permutation of gg acts on Fn×VlF_n \times V_l factor by factor, g⋅(a,w)=(λga,αgw),g \cdot (a, w) = (\lambda_g a,\ \alpha_g w),(4)✦ The conditional generator of gg at level kk is the generator permutation of gg on the padded channels of level kk, where l=ml = m.

Wrap Guesses and Variants

Quadruples of integers or digits are arranged as pairs of pairs, like the vectors of VlV_l✦, and maps and conditions on them apply entrywise. The lift x̃∈ℤ4\tilde x \in \mathbb{Z}^4 of x∈Vlx \in V_l takes each entry to its least nonnegative representative✦, and the reduction zmod⁡n∈Vnz \bmod n \in V_n of z∈ℤ4z \in \mathbb{Z}^4 takes each entry to its residue modulo nn.✦ Over a commutative ring RR, the lowered command action ℓcϵ\ell^\epsilon_c is the map that takes u,d∈R2u, d \in R^2 to the value ℓcϵ(u;d)∈R2\ell^\epsilon_c(u; d) \in R^2 given by the right side of (2) read in RR.✦ The real action of gg on z=(z1,z2)∈R4z = (z_1, z_2) \in R^4 is Pgϵ(z)={(ℓg2ϵ(z1;z2),z2)if g1=0,(z1,ℓg2ϵ(z2;z1))if g1=1,P^\epsilon_g(z) = \begin{cases} (\ell^\epsilon_{g_2}(z_1; z_2),\ z_2) & \text{if } g_1 = 0,\\ (z_1,\ \ell^\epsilon_{g_2}(z_2; z_1)) & \text{if } g_1 = 1, \end{cases}(5)✦ and Pg=Pg1P_g = P^1_g over ℤ\mathbb{Z}.

The roller alphabet W={0,1,…,10}4W = \{0, 1, \dots, 10\}^4 is the set of digit quadruples.✦ At scale mm, the digit chosen for an integer ii is χm(i)=min⁡{10,max⁡{0,5−⌊i/m⌋}},\chi_m(i) = \min\bigl\{10,\ \max\{0,\ 5 - \lfloor i/m \rfloor\}\bigr\},(6)✦ and the guessed digit vector γm(z)∈W\gamma_m(z) \in W of z∈ℤ4z \in \mathbb{Z}^4 applies χm\chi_m entrywise.✦ The guess of gg at a padded channel s=(a,w)s = (a, w) of level kk is γg(s)=γm(Pg(w̃))\gamma_g(s) = \gamma_m(P_g(\tilde w))✦, and the shift vector of ω∈W\omega \in W at scale mm is δm(ω)∈ℤ4\delta_m(\omega) \in \mathbb{Z}^4, with entries m(ωj−5)m(\omega_j - 5).✦ For a level kk, a generator gg and ω∈W\omega \in W, the variant is the permutation of all channels CnC_n Vark,g,ω(a,b)=(λga,αgb+(δm(ω)mod⁡n)).\mathrm{Var}_{k,g,\omega}(a, b) = \bigl(\lambda_g a,\ \alpha_g b + (\delta_m(\omega) \bmod n)\bigr).(7)✦

The Claim

Theorem 1. Let nn be a prime, gg a generator and kk a level, with box side mm.

  1. For every padded channel ss of level kk and every y∈ℤ/ny \in \mathbb{Z}/n, Vark,g,γg(s)(openy(s))=openy(g⋅s).\mathrm{Var}_{k,g,\gamma_g(s)}\bigl(\mathrm{open}_y(s)\bigr) = \mathrm{open}_y(g \cdot s).(8)✦

  2. For every padded channel s=(a,w)s = (a, w) of level kk, αgwˆ+(δm(γg(s))mod⁡n)=αgwˆ.\alpha_g \hat w + \bigl(\delta_m(\gamma_g(s)) \bmod n\bigr) = \widehat{\alpha_g w}.(9)✦

  3. For every positive integer ll and every x∈Vlx \in V_l, −4l≤(Pg(x̃))j<4l(j=1,2,3,4).-4l \le \bigl(P_g(\tilde x)\bigr)_j < 4l \qquad (j = 1, 2, 3, 4).(10)✦

In the paper, the result reads: a walk word of length dd expands into a family of variants over a bounded alphabet, described by O(d)O(d) bits, each acting bijectively and measure-preservingly on the full environment and independently of the indicated identifiers, such that exactly one variant passes the slice and wrap tests and gives the conditional step and the valid variants sum to the conditional average, the tests being done at visits in space O(B)O(B), with BB the paper’s space parameter, in the admissible range. The box treats one generator at a time, with the variants indexed by the digit quadruples of WW.

What Is Checked

The claim is stated over the channels and the padded channels of level kk, with the box side mm, the widening and the opened channel (1); over the generator actions (3), built from shears, axial translations, cross terms and face swaps, with the frame permutation and the conditional generator (4); and over the lift, the real action (5), the guess built from (6), the shift vector and the variant (7). Beyond the claim, the library proves that shearing a residue pair by dd and then by −d-d in the same direction returns it.✦