OctoInformBeta

OpenAI preprint, September 2026 · §4. Random routing and independent tests

§4 (setting): full center exposure, first default, and local predicates: Center selector fibers and local selector-terminal tests on nondefault subtrees

A good exposure fixes the first default.

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 point in a dyadic routing construction queries one cell in each selector table. At a decision node, the first successful selector chooses a child; if all selectors vanish, the route takes the default child. The local success test below concerns one nondefault subtree and the terminal table reached inside it.

Let M,d∈ℕM,d\in\mathbb N. The child alphabet is C={0,…,M}C=\{0,\ldots,M\}, with default child MM and nondefault children 0,…,M−10,\ldots,M-1.✦ Thus the paper’s parameter for the total number of children is M+1M+1 in this notation. A decision node is a word PP over CC of length less than dd✦, and a terminal path is a word of length dd.✦ Their sets 𝒩\mathcal N and ℒ\mathcal L are defined in (1); PiPi denotes concatenation with the child ii, and ⌀\varnothing is the empty word. 𝒩=⋃k<dCk,ℒ=Cd.\mathcal N=\bigcup_{k<d}C^k, \qquad \mathcal L=C^d.(1)

The periodic mesh key kq(z)k_q(z), for q,z∈ℝq,z\in\mathbb R, and the finite dyadic key Jb(z)J_b(z), for b∈ℕb\in\mathbb N, are the indices in (2), where {z}=z−⌊z⌋\{z\}=z-\lfloor z\rfloor. At level bb, the periodic grid cells are the half-open intervals [j2−(b+2),(j+1)2−(b+2))[j2^{-(b+2)},(j+1)2^{-(b+2)}) modulo one. kq(z)=⌊q{z}⌋,Jb(z)=k2b+2(z)∈{0,…,2b+2−1}.k_q(z)=\lfloor q\{z\}\rfloor, \qquad J_b(z)=k_{2^{b+2}}(z)\in\{0,\ldots,2^{b+2}-1\}.(2)

Fix selector resolutions bS(P,i)b_S(P,i) for P∈𝒩P\in\mathcal N and i<Mi<M, and terminal resolutions bT(L)b_T(L) for L∈ℒL\in\mathcal L. The selector address set 𝒜S\mathcal A_S and terminal address set 𝒜T\mathcal A_T are the sets of pairs of table labels and grid indices given in (3). A selector table SS and a terminal table TT are Boolean functions on these respective address sets. 𝒜S={((P,i),j):P∈𝒩,i<M,0≤j<2bS(P,i)+2},𝒜T={(L,j):L∈ℒ,0≤j<2bT(L)+2},S:𝒜S→{0,1},T:𝒜T→{0,1}.\begin{aligned} \mathcal A_S &=\{((P,i),j):P\in\mathcal N,\ i<M,\ 0\le j<2^{b_S(P,i)+2}\},\\ \mathcal A_T &=\{(L,j):L\in\mathcal L,\ 0\le j<2^{b_T(L)+2}\},\\ S&:\mathcal A_S\longrightarrow\{0,1\}, \qquad T:\mathcal A_T\longrightarrow\{0,1\}. \end{aligned}(3)

The queried selector and terminal addresses at z∈ℝz\in\mathbb R are qS(P,i,z)q_S(P,i,z) and qT(L,z)q_T(L,z) in (4). qS(P,i,z)=((P,i),JbS(P,i)(z)),qT(L,z)=(L,JbT(L)(z)).q_S(P,i,z)=((P,i),J_{b_S(P,i)}(z)), \qquad q_T(L,z)=(L,J_{b_T(L)}(z)).(4) The extended selector value σS(P,i,z)\sigma_S(P,i,z) is the Boolean function on all words PP in (5). For a Boolean vector v=(vi)i<Mv=(v_i)_{i<M}, the first-success rule cc chooses the least nondefault child with vi=1v_i=1, or MM if there is none.✦ For a center x∈ℝx\in\mathbb R, the pointwise selector choice χS\chi_S and the center choice χx\chi_x are also defined there. σS(P,i,z)={S(qS(P,i,z)),|P|<d,0,|P|≥d,c(v)=min⁡({i<M:vi=1}∪{M}),χS(P,z)=c((σS(P,i,z))i<M),χx(P,S)=χS(P,x).\begin{aligned} \sigma_S(P,i,z)&= \begin{cases} S(q_S(P,i,z)),& |P|<d,\\ 0,& |P|\ge d, \end{cases}\\ c(v)&=\min\bigl(\{i<M:v_i=1\}\cup\{M\}\bigr),\\ \chi_S(P,z)&=c\bigl((\sigma_S(P,i,z))_{i<M}\bigr), \qquad \chi_x(P,S)=\chi_S(P,x). \end{aligned}(5)

For a child-choice map χ(P,z)\chi(P,z), the iterated route Rnχ(P,z)R_n^\chi(P,z) is the word obtained by the recursion in (6). The local routed leaf Λrχ(P,z)\Lambda_r^\chi(P,z) associated to a child-choice map χ\chi, a starting word PP, and a parameter zz is the word Rrχ(P,z)R_r^\chi(P,z) when |P|+r=d|P|+r=d.✦ Write RnS=RnχSR_n^S=R_n^{\chi_S}; the local leaf ℓiS(U,z)\ell_i^S(U,z) starts at the nondefault child UiUi of a decision node UU. R0χ(P,z)=P,Rn+1χ(P,z)=Rnχ(P,z)χ(Rnχ(P,z),z),Λrχ(P,z)=Rrχ(P,z)(|P|+r=d),ℓiS(U,z)=Λd−(|U|+1)χS(Ui,z).\begin{aligned} R_0^\chi(P,z)&=P,\\ R_{n+1}^\chi(P,z)&=R_n^\chi(P,z)\, \chi(R_n^\chi(P,z),z),\\ \Lambda_r^\chi(P,z)&=R_r^\chi(P,z)\quad (|P|+r=d),\\ \ell_i^S(U,z)&=\Lambda_{d-(|U|+1)}^{\chi_S}(Ui,z). \end{aligned}(6)

Fix a center x∈ℝx\in\mathbb R and a Boolean assignment ξ:𝒩×{0,…,M−1}→{0,1}\xi:\mathcal N\times\{0,\ldots,M-1\}\to\{0,1\}. The zero-filled exposure completion Sˆxξ\widehat S_x^\xi is the selector table in (7). Sˆxξ((P,i),j)={ξ(P,i),j=JbS(P,i)(x),0,j≠JbS(P,i)(x).\widehat S_x^\xi((P,i),j)= \begin{cases} \xi(P,i),& j=J_{b_S(P,i)}(x),\\ 0,& j\ne J_{b_S(P,i)}(x). \end{cases}(7)✦

Window Endpoints

An admissible edge path PP over CC is a nonempty word with |P|≤d|P|\le d.✦ Separated window data W=(r,a,b,b*)W=(r,a,b,b^*), with natural parameters M+1,d,g,r0M+1,d,g,r_0, consist of a natural-valued function rr on ℕ\mathbb N and natural-valued assignments a,b,b*a,b,b^* on words satisfying the window conditions in (8) and the separation conditions in (9). Put rP=r(d+1−|P|)r_P=r(d+1-|P|). 1≤rP,r0≤rP,3≤a(P),b(P)+1=a(P)+rP,b*(P)+1≤a(P)+2rP.\begin{gathered} 1\le r_P,\qquad r_0\le r_P,\qquad 3\le a(P),\\ b(P)+1=a(P)+r_P,\qquad b^*(P)+1\le a(P)+2r_P. \end{gathered}(8) For admissible paths P,QP,Q, write P≼QP\preceq Q for the prefix relation and P≺QP\prec Q for a proper prefix. The descendant bounds and prefix separation are the first two conditions of (9). Its last condition is the sibling separation, for words P,VP,V and children i<ji<j whenever PiPi and PjVPjV are admissible. b(P)≤b(Q)≤b*(P)(P≼Q),b(P)+g<a(Q)(P≺Q),b(Pi)+g<a(PjV)(i<j).\begin{aligned} b(P)\le b(Q)\le b^*(P)&\qquad(P\preceq Q),\\ b(P)+g<a(Q)&\qquad(P\prec Q),\\ b(Pi)+g<a(PjV)&\qquad(i<j). \end{aligned}(9) For a decision node PP and a nondefault child ii, the nondefault child edge PiPi is the path obtained by concatenating PP and ii. The selector window endpoints and terminal window endpoints of WW supply the resolutions in (10). bS(P,i)=b(Pi),bT(L)=b(L).b_S(P,i)=b(Pi),\qquad b_T(L)=b(L).(10)

The Claim

Theorem 1 (Center exposure and local tests). For arbitrary selector and terminal resolutions, the full center exposure Ex(S)E_x(S) is the Boolean assignment in (11). The center exposure fiber Ax(ξ)A_x(\xi) of a Boolean assignment ξ\xi at the center xx is the set of selector and terminal table pairs in (12). Ex(S)(P,i)=S(qS(P,i,x))(P∈𝒩,i<M).E_x(S)(P,i)=S(q_S(P,i,x)) \qquad(P\in\mathcal N,\ i<M).(11)✦ Ax(ξ)={(S,T):Ex(S)=ξ}.A_x(\xi)=\{(S,T):E_x(S)=\xi\}.(12)✦ A good exposure ξ\xi at the center xx is a Boolean assignment on 𝒩×{0,…,M−1}\mathcal N\times\{0,\ldots,M-1\} whose completed center route uses a default child, as specified by (13). ξ is good⇔∃k<d:χSˆxξ(RkSˆxξ(⌀,x),x)=M.\xi\text{ is good} \quad\Longleftrightarrow\quad \exists\,k<d: \chi_{\widehat S_x^\xi} \bigl(R_k^{\widehat S_x^\xi}(\varnothing,x),x\bigr)=M.(13)✦ For a child-choice map χ\chi, starting word PP and parameter zz, an index kk is a first default stage when it satisfies (14); write Fd(χ,k,P,z)F_d(\chi,k,P,z) for this condition. k<d,χ(Rkχ(P,z),z)=M,χ(Rlχ(P,z),z)≠M(0≤l<k).\begin{gathered} k<d,\qquad \chi(R_k^\chi(P,z),z)=M,\\ \chi(R_l^\chi(P,z),z)\ne M\qquad(0\le l<k). \end{gathered}(14)✦ If ξ\xi is good, there are an index k<dk<d and a decision node UU with |U|=k|U|=k such that (15) holds for every selector table SS with Ex(S)=ξE_x(S)=\xi. RkS(⌀,x)=U,Fd(χS,k,⌀,x).R_k^S(\varnothing,x)=U, \qquad F_d(\chi_S,k,\varnothing,x).(15)✦ For separated window data WW, tables S,TS,T at the endpoint resolutions (10), a decision node UU, a nondefault child ii, and y∈ℝy\in\mathbb R, the local selector-terminal test QiU,S,T(y)Q_i^{U,S,T}(y) is the Boolean value in (16). QiU,S,T(y)=S(qS(U,i,y))T(qT(ℓiS(U,y),y)).Q_i^{U,S,T}(y) =S(q_S(U,i,y))\,T(q_T(\ell_i^S(U,y),y)).(16)✦

In the paper, the result reads: writing SeS_e for the selector table with label e=(P,i)e=(P,i) and resolution beb_e, and TLT_L for the terminal table with label LL and resolution b(L)b(L), at a fixed center xx, expose Se(Jbe(x))S_e(J_{b_e}(x)) in every selector table, including unvisited subtrees, so that the finite exposure atoms determine the center’s path and, when it exists, its first default node UU; for a nondefault child ii of UU, let Li(z)L_i(z) be the route starting from UiUi and let Qi(z)=SU,i(JbU,i(z))TLi(z)(Jb(Li(z))(z))Q_i(z)=S_{U,i}(J_{b_{U,i}}(z))T_{L_i(z)}(J_{b(L_i(z))}(z)).

What Is Checked

The center exposure fiber and good-exposure condition are stated over arbitrary natural M,dM,d, real centers and Boolean selector assignments; the first default assertion uses a good assignment, while the local test uses separated window data with M+1M+1 total children and both selector and terminal tables.

For a decision node UU and a nondefault child ii, the local routing depth identity is (17). |Ui|+(d−(|U|+1))=d.|Ui|+\bigl(d-(|U|+1)\bigr)=d.(17)✦