OctoInform Beta

OpenAI preprint, September 2026 · §4. Recursive procedures and unconditional termination · §4

§4 (setting): Procedure 4.4 [Orientation]: Base case at small width, else ss center moves by two calls to Ask each, a displacement test and possibly a recursive call

The orientation procedure on a raw stack machine.

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 mean-payoff game GG on a set VV of nn vertices with mm edges, transformed weights t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1, W=max⁡{1,max⁡e|t(e)|}W=\max\{1,\max_e|t(e)|\} and top width B*=8nWB_*=8nW. The randomized solver for GG is run with a global sample count ss, a power of two, and a trial count JJ, both fixed by B*B_*. The randomized solver works on solver inputs (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m): a box with corners a≤ba\le b in ℤV\mathbb Z^V and reference width B≥b−aB\ge b-a, with positive rational support weights α,β\alpha,\beta and budgets k,mk,m. We call θ=(α,β,k,m)\theta=(\alpha,\beta,k,m) the budgets of the input; they give the measure μθ(S)=∑i∈S1αiβi/∑i∈V1αiβi\mu_\theta(S)=\sum_{i\in S}\frac{1}{\alpha_i\beta_i}\big/\sum_{i\in V}\frac{1}{\alpha_i\beta_i} of a set S⊆VS\subseteq V. An orientation for θ\theta is one of the two choices YY and ZZ together with a list of exception sets of vertices.

The procedure Orient maps a solver input to an orientation. On a box with B≤128sB\le 128s it decides from the vector that the basic solver computes on the box. On a wider box it moves a center ss times, each time by two calls to the procedure Ask, and then decides from the displacement of the last center, or calls itself on a smaller box around a center drawn at random.

In the library, Orient runs on a stack machine over raw data, where numbers are binary words and unary counters, a counter of length ℓ\ell standing for ℓ\ell, and where a call leaves on a stack a frame that waits for the answer. One step of the machine is given case by case, one case for each job that can be called and each frame that can receive an answer; the library states Orient as eight such cases, together with the raw operations they use.

The Raw Machine

A register pack zz is a record of eight registers holding raw data: budgets pzp_z, a box bzb_z, a counter tzt_z, two vectors qzq_z and rzr_z, a list vszvs_z of vectors, an orientation ozo_z and a list of orientations.✦ A raw vector is a list of binary words. A raw box Iˆ\hat I is a box whose corners are raw vectors; it has a width w(Iˆ)w(\hat I) and a midpoint mid(Iˆ)\mathrm{mid}(\hat I). A mask is a list of booleans marking a set of vertices, and we use set notation for masks. A raw orientation (χ;H1,…,Hr)(\chi;H_1,\dots,H_r) is a bit χ\chi, true for YY, with a list of masks.✦ We write a pack by the registers it fills, as [p:θˆ,b:Iˆ][p{:}\,\hat\theta,\ b{:}\,\hat I], where a hat marks a raw object, θˆ\hat\theta being raw budgets and Iˆ\hat I a raw box; the other registers hold the zero budget, the zero box, empty counters and lists, and the orientation (Z;)(Z;) with no masks.✦ The pack with every register at its default is the empty pack.✦

A stack cell is a tag with a pack, the tag being a counter whose length names the job or the frame the cell stands for.✦ A machine state is a current cell with a stack, the list of the cells of the pending frames.✦ We write 𝖩(z)∣S\mathsf J(z)\mid S for the state that calls the job 𝖩\mathsf J on the pack zz over the stack SS, 𝗋𝖾𝗍(z)∣S\mathsf{ret}(z)\mid S for the state that returns zz to SS, and 𝖥(z)S\mathsf F(z)\,S for SS with a frame 𝖥\mathsf F holding zz pushed on top; 𝖩[…]\mathsf J[\dots], 𝗋𝖾𝗍[…]\mathsf{ret}[\dots] and 𝖥[…]\mathsf F[\dots] take the pack […][\dots]. The jobs 𝖠𝗌𝗄\mathsf{Ask}, 𝖴𝗉𝖽𝖺𝗍𝖾\mathsf{Update}, 𝖢𝖾𝗇𝗍𝖾𝗋𝗌\mathsf{Centers} and 𝖮𝗋𝗂𝖾𝗇𝗍\mathsf{Orient} have the tags 1,3,4,51,3,4,5, the frames 𝖢𝗈𝗇𝗌\mathsf{Cons}, 𝖥𝗂𝗋𝗌𝗍\mathsf{First}, 𝖲𝖾𝖼𝗈𝗇𝖽\mathsf{Second}, 𝖧𝖾𝖺𝖽\mathsf{Head}, 𝖫𝗈𝗈𝗉\mathsf{Loop} and 𝖳𝖺𝗂𝗅\mathsf{Tail} have the tags 1,3,4,5,6,71,3,4,5,6,7, and a returned pack has the tag 1010.

The environment ℰ\mathcal E is a tuple of the raw arena of the game and four counters: the sample exponent log⁡2s\log_2 s, the sample count ss, the trial count JJ and a step budget for the basic solver.✦ The environment ℰ\mathcal E represents GG at B*B_* when its arena is the vertex code of GG with raw words holding the transformed weights of the edges, its first three counters have the lengths log⁡2s\log_2 s, ss and JJ, and its step budget has length at least 128ns128ns.✦ A machine input x=(ℰ,j,Σ)x=(\mathcal E,j,\Sigma) is an environment, a counter jj, the random index of the step, and a state Σ\Sigma.✦ Of xx the cases use the current pack zz of the current cell, the stack SS, the caller pack z′z' of the frame on top of SS, the empty pack when SS is empty, and the rest σ\sigma of SS below that frame.

Raw data represent the solver’s objects, and we write xˆ⊳x\hat x\triangleright x when xˆ\hat x represents xx. A mask represents the set it marks. A list of raw vectors represents a list of points of a box when its entries represent them one by one.✦ A raw orientation represents an orientation OO for θ\theta when its bit is the choice of OO and its masks represent the exception sets of OO in order.✦

Boxes, Centers and Displacement Sets

Let I=(a,b;B)I=(a,b;B) be a box of the solver at top width B*B_*, with midpoint mIm_I, and write Q(v,D)Q(v,D) for the box of half width DD around v∈ℤVv\in\mathbb Z^V. When B>128sB>128s, the narrowed box of II at vv is Q(v,⌊B/(32s)⌋)Q(v,\lfloor B/(32s)\rfloor) and the widened box is Q(v,⌊B/8⌋)Q(v,\lfloor B/8\rfloor). On raw data, narrow(Iˆ,vˆ)\mathrm{narrow}(\hat I,\hat v) and wide(Iˆ,vˆ)\mathrm{wide}(\hat I,\hat v) are the raw boxes centered at vˆ\hat v whose half width is the width of Iˆ\hat I divided by 2log⁡2s+5=32s2^{\log_2 s+5}=32s, with log⁡2s\log_2 s read from the environment, and by 23=82^3=8.

For a point qq of II, the positive and negative displacement sets of II at qq are PI(q)={i∈V:s(qi−(mI)i)>2B},NI(q)={i∈V:s(qi−(mI)i)<−2B}.P_I(q)=\{\,i\in V: s\,(q_i-(m_I)_i)>2B\,\},\qquad N_I(q)=\{\,i\in V: s\,(q_i-(m_I)_i)<-2B\,\}.(1) The raw masks pos(Iˆ,sˆ,qˆ)\mathrm{pos}(\hat I,\hat s,\hat q) and neg(Iˆ,sˆ,qˆ)\mathrm{neg}(\hat I,\hat s,\hat q) make the two tests of (1) on binary words, with a word sˆ\hat s as the scale, the midpoint of Iˆ\hat I for mIm_I and its width for BB.

For a counter ii, the center lookup ctri(x)\mathrm{ctr}_i(x) is the entry of index ii, counting from 00, of the vector list vszvs_z of the current pack, or the midpoint of the caller’s box bz′b_{z'} when the list has no such entry.✦ The last masks of xx are the displacement masks of the caller’s box at the center of index ss, with the sample count of the environment as the scale: Pˆx=pos(bz′,s,ctrs(x)),Nˆx=neg(bz′,s,ctrs(x)).\hat P_x=\mathrm{pos}\bigl(b_{z'},s,\mathrm{ctr}_s(x)\bigr),\qquad \hat N_x=\mathrm{neg}\bigl(b_{z'},s,\mathrm{ctr}_s(x)\bigr).(2)

Let pIp_I be the exact vector of II in GG, the vector that the basic solver computes on II, and MI={i∈V:B≤2((pI)i−ai)}M_I=\{\,i\in V:B\le 2((p_I)_i-a_i)\,\}. The base orientation of II for the budgets θ\theta is Oθ,Ibase={(Y;V\MI)if μθ(MI)>1/2,(Z;MI)otherwise.O^{\mathrm{base}}_{\theta,I}= \begin{cases} (Y;\,V\setminus M_I) & \text{if } \mu_\theta(M_I)>1/2,\\ (Z;\,M_I) & \text{otherwise.} \end{cases}(3) On raw data, μθˆ(Mˆ)>1/2\mu_{\hat\theta}(\hat M)>1/2 is the test whether the budgets θˆ\hat\theta give the set marked by Mˆ\hat M measure above 1/21/2, and base(θˆ,Iˆ,vˆ)\mathrm{base}(\hat\theta,\hat I,\hat v) makes the choice of (3) with this test, from the mask of the coordinates ii with w(Iˆ)≤2(vi−ai)w(\hat I)\le 2(v_i-a_i), aa the lower corner of Iˆ\hat I.✦ The basic solver call Basic(Iˆ)\mathrm{Basic}(\hat I) runs the raw basic solver on the arena of the environment, the box Iˆ\hat I and the basic step budget, and returns a raw vector.✦

The reduced budgets redk(θˆ)\mathrm{red}_k(\hat\theta) and redm(θˆ)\mathrm{red}_m(\hat\theta) are θˆ\hat\theta with the budget kk, respectively mm, replaced by its reduction ηk\eta k, respectively ηm\eta m, with the reduction factor η=4/5\eta=4/5. For raw vectors uˆ⊳u\hat u\triangleright u and vˆ⊳v\hat v\triangleright v and a raw box Iˆ\hat I with corners a≤ba\le b, the clipped average avgIˆ(uˆ,vˆ)\mathrm{avg}_{\hat I}(\hat u,\hat v) is the raw vector of clip[a,b]⌊(u+v)/2⌋\mathrm{clip}_{[a,b]}\lfloor(u+v)/2\rfloor, where clip[a,b]\mathrm{clip}_{[a,b]} moves each coordinate into the interval between the corresponding coordinates of aa and bb. The extension ext(oˆ,hˆ,hˆ′)\mathrm{ext}(\hat o,\hat h,\hat h') of a raw orientation oˆ\hat o by two masks keeps its bit and appends hˆ\hat h and hˆ′\hat h' to its masks.✦

The Claim

Definition 1 (Orientation on the raw machine). Let xx be a machine input with random index jj, current pack zz, stack SS, caller pack z′z' and rest σ\sigma. The procedure Orient on the raw machine is given by the following cases, each the next state δ(x)\delta(x). On a call of 𝖮𝗋𝗂𝖾𝗇𝗍\mathsf{Orient}, 𝖢𝖾𝗇𝗍𝖾𝗋𝗌\mathsf{Centers} or 𝖴𝗉𝖽𝖺𝗍𝖾\mathsf{Update}: δ𝖮𝗋𝗂𝖾𝗇𝗍(x)={𝗋𝖾𝗍[o:base(pz,bz,Basic(bz))]∣Sif w(bz)≤128s,𝖢𝖾𝗇𝗍𝖾𝗋𝗌[p:pz,b:bz,t:s,q:mid(bz)]∣𝖫𝗈𝗈𝗉(z)Sotherwise;\delta_{\mathsf{Orient}}(x)= \begin{cases} \mathsf{ret}\,[o{:}\,\mathrm{base}(p_z,b_z,\mathrm{Basic}(b_z))]\mid S & \text{if } w(b_z)\le 128s,\\ \mathsf{Centers}\,[p{:}\,p_z,\ b{:}\,b_z,\ t{:}\,s,\ q{:}\,\mathrm{mid}(b_z)] \mid \mathsf{Loop}(z)\,S & \text{otherwise;} \end{cases}(4)✦ δ𝖢𝖾𝗇𝗍𝖾𝗋𝗌(x)={𝗋𝖾𝗍[vs:(qz)]∣Sif tz=0,𝖴𝗉𝖽𝖺𝗍𝖾(z)∣𝖧𝖾𝖺𝖽[p:pz,b:bz,t:tz−1,q:qz]Sotherwise;\delta_{\mathsf{Centers}}(x)= \begin{cases} \mathsf{ret}\,[vs{:}\,(q_z)]\mid S & \text{if } t_z=0,\\ \mathsf{Update}(z)\mid \mathsf{Head}\,[p{:}\,p_z,\ b{:}\,b_z,\ t{:}\,t_z-1,\ q{:}\,q_z]\,S & \text{otherwise;} \end{cases}(5)✦ δ𝖴𝗉𝖽𝖺𝗍𝖾(x)=𝖠𝗌𝗄[p:redk(pz),b:narrow(bz,qz)]∣𝖥𝗂𝗋𝗌𝗍(z)S.\delta_{\mathsf{Update}}(x)= \mathsf{Ask}\,[p{:}\,\mathrm{red}_k(p_z),\ b{:}\,\mathrm{narrow}(b_z,q_z)] \mid \mathsf{First}(z)\,S.(6)✦ On a return to a frame 𝖥𝗂𝗋𝗌𝗍\mathsf{First}, 𝖲𝖾𝖼𝗈𝗇𝖽\mathsf{Second} or 𝖧𝖾𝖺𝖽\mathsf{Head}: δ𝖥𝗂𝗋𝗌𝗍(x)=𝖠𝗌𝗄[p:redm(pz′),b:narrow(bz′,qz′)]∣𝖲𝖾𝖼𝗈𝗇𝖽[b:bz′,r:qz]σ;\delta_{\mathsf{First}}(x)= \mathsf{Ask}\,[p{:}\,\mathrm{red}_m(p_{z'}),\ b{:}\,\mathrm{narrow}(b_{z'},q_{z'})] \mid \mathsf{Second}\,[b{:}\,b_{z'},\ r{:}\,q_z]\,\sigma;(7)✦ δ𝖲𝖾𝖼𝗈𝗇𝖽(x)=𝗋𝖾𝗍[q:avgbz′(rz′,qz)]∣σ;\delta_{\mathsf{Second}}(x)= \mathsf{ret}\,[q{:}\,\mathrm{avg}_{b_{z'}}(r_{z'},q_z)]\mid \sigma;(8)✦ δ𝖧𝖾𝖺𝖽(x)=𝖢𝖾𝗇𝗍𝖾𝗋𝗌[p:pz′,b:bz′,t:tz′,q:qz]∣𝖢𝗈𝗇𝗌[q:qz′]σ.\delta_{\mathsf{Head}}(x)= \mathsf{Centers}\,[p{:}\,p_{z'},\ b{:}\,b_{z'},\ t{:}\,t_{z'},\ q{:}\,q_z] \mid \mathsf{Cons}\,[q{:}\,q_{z'}]\,\sigma.(9)✦ On a return to a frame 𝖫𝗈𝗈𝗉\mathsf{Loop} or 𝖳𝖺𝗂𝗅\mathsf{Tail}, with the last masks Pˆx\hat P_x and Nˆx\hat N_x of (2): δ𝖫𝗈𝗈𝗉(x)={𝗋𝖾𝗍[o:(Y;V\Pˆx)]∣σif μpz′(Pˆx)>1/2,𝗋𝖾𝗍[o:(Z;V\Nˆx)]∣σif not, and μpz′(Nˆx)>1/2,𝖮𝗋𝗂𝖾𝗇𝗍[p:pz′,b:wide(bz′,ctrj(x))]∣𝖳𝖺𝗂𝗅[o:(Z;Pˆx,Nˆx)]σotherwise;\delta_{\mathsf{Loop}}(x)= \begin{cases} \mathsf{ret}\,[o{:}\,(Y;\,V\setminus\hat P_x)]\mid \sigma & \text{if } \mu_{p_{z'}}(\hat P_x)>1/2,\\ \mathsf{ret}\,[o{:}\,(Z;\,V\setminus\hat N_x)]\mid \sigma & \text{if not, and } \mu_{p_{z'}}(\hat N_x)>1/2,\\ \mathsf{Orient}\,[p{:}\,p_{z'},\ b{:}\,\mathrm{wide}(b_{z'},\mathrm{ctr}_j(x))] \mid \mathsf{Tail}\,[o{:}\,(Z;\,\hat P_x,\hat N_x)]\,\sigma & \text{otherwise;} \end{cases}(10)✦ δ𝖳𝖺𝗂𝗅(x)=𝗋𝖾𝗍[o:ext(oz,H1,H2)]∣σ,oz′=(χ;H1,H2,…).\delta_{\mathsf{Tail}}(x)= \mathsf{ret}\,[o{:}\,\mathrm{ext}(o_z,H_1,H_2)]\mid \sigma, \qquad o_{z'}=(\chi;H_1,H_2,\dots).(11)✦

In the paper, the result reads: for (a,b;B,α,β,k,m)(a,b;B,\alpha,\beta,k,m) with R≥1R\ge 1, compute μ\mu; (O1) if B≤128sB\le 128s, compute p=Basic(a,b)p=\mathrm{Basic}(a,b) and P={i:pi≥ai+B/2}P=\{i:p_i\ge a_i+B/2\}, and return YY with the one-entry list (V\P)(V\setminus P) if μ(P)>1/2\mu(P)>1/2, otherwise ZZ with (P)(P); (O2) set q0=⌊(a+b)/2⌋q_0=\lfloor(a+b)/2\rfloor, D=⌊B/(32s)⌋D=\lfloor B/(32s)\rfloor and E0=⌊B/8⌋E_0=\lfloor B/8\rfloor, and for j=0,…,s−1j=0,\dots,s-1 make independent calls r1=Ask(qj−D,qj+D;2D,α,β,ηk,m)r_1=\mathrm{Ask}(q_j-D,q_j+D;2D,\alpha,\beta,\eta k,m) and r2=Ask(qj−D,qj+D;2D,α,β,k,ηm)r_2=\mathrm{Ask}(q_j-D,q_j+D;2D,\alpha,\beta,k,\eta m) and set qj+1=clip[a,b](⌊(r1+r2)/2⌋)q_{j+1}=\mathrm{clip}_{[a,b]}(\lfloor(r_1+r_2)/2\rfloor); (O3) with P={i:(qs)i−(q0)i>2hB}P=\{i:(q_s)_i-(q_0)_i>2hB\} and N={i:(qs)i−(q0)i<−2hB}N=\{i:(q_s)_i-(q_0)_i<-2hB\}, return YY and (V\P)(V\setminus P) if μ(P)>1/2\mu(P)>1/2, else ZZ and (V\N)(V\setminus N) if μ(N)>1/2\mu(N)>1/2; (O4) otherwise draw jj uniformly from {0,…,s−1}\{0,\dots,s-1\} with log⁡2s\log_2 s fresh bits, evaluate (χ,H)=Orient(qj−E0,qj+E0;2E0,α,β,k,m)(\chi,H)=\mathrm{Orient}(q_j-E_0,q_j+E_0;2E_0,\alpha,\beta,k,m) and return χ\chi with the list HH followed by P,NP,N, where ηk\eta k and ηm\eta m are the reduced budgets. Here RR and hh are parameters of the paper, and μ\mu stands for the measure μθ\mu_\theta of the budgets. On the machine, the case of 𝖮𝗋𝗂𝖾𝗇𝗍\mathsf{Orient} makes the test of O1 and starts O2, the cases of 𝖢𝖾𝗇𝗍𝖾𝗋𝗌\mathsf{Centers}, 𝖴𝗉𝖽𝖺𝗍𝖾\mathsf{Update}, 𝖥𝗂𝗋𝗌𝗍\mathsf{First}, 𝖲𝖾𝖼𝗈𝗇𝖽\mathsf{Second} and 𝖧𝖾𝖺𝖽\mathsf{Head} make the ss moves of O2, and the cases of 𝖫𝗈𝗈𝗉\mathsf{Loop} and 𝖳𝖺𝗂𝗅\mathsf{Tail} make O3 and O4.

What Is Checked

The cases are stated over machine inputs with their environment, random index, packs and stack, and the facts below over a game GG at top width B*B_*, a box I=(a,b;B)I=(a,b;B) of the solver at B*B_* with midpoint mIm_I, and a raw box Iˆ⊳I\hat I\triangleright I.

The library shows that the raw operations of the cases represent the solver’s objects. Given budgets θˆ⊳θ\hat\theta\triangleright\theta and a raw vector pˆ⊳pI\hat p\triangleright p_I, the raw base orientation stands for (3): base(θˆ,Iˆ,pˆ)⊳Oθ,Ibase.\mathrm{base}(\hat\theta,\hat I,\hat p)\triangleright O^{\mathrm{base}}_{\theta,I}.(12)✦

Take v∈ℤVv\in\mathbb Z^V with vˆ⊳v\hat v\triangleright v and let B>128sB>128s. If the environment represents GG at B*B_*, the narrowing gives the narrowed box, and the widening gives the widened box with no condition on the environment: narrow(Iˆ,vˆ)⊳Q(v,⌊B/(32s)⌋),\mathrm{narrow}(\hat I,\hat v)\triangleright Q(v,\lfloor B/(32s)\rfloor),(13)✦ wide(Iˆ,vˆ)⊳Q(v,⌊B/8⌋).\mathrm{wide}(\hat I,\hat v)\triangleright Q(v,\lfloor B/8\rfloor).(14)✦

For a point qq of II with qˆ⊳q\hat q\triangleright q and a word sˆ\hat s of value ss, pos(Iˆ,sˆ,qˆ)⊳PI(q),\mathrm{pos}(\hat I,\hat s,\hat q)\triangleright P_I(q),(15)✦ neg(Iˆ,sˆ,qˆ)⊳NI(q).\mathrm{neg}(\hat I,\hat s,\hat q)\triangleright N_I(q).(16)✦

Let xx be a machine input whose caller’s box bz′b_{z'} represents II and whose current vector list vszvs_z represents a list (c0,…,cℓ)(c_0,\dots,c_\ell) of points of II, and put ci=mIc_i=m_I for i>ℓi>\ell. Then for every counter ii ctri(x)⊳ci,\mathrm{ctr}_i(x)\triangleright c_i,(17)✦ and, when the environment of xx represents GG at B*B_*, the last masks (2) mark the displacement sets at csc_s: Pˆx⊳PI(cs),\hat P_x\triangleright P_I(c_s),(18)✦ Nˆx⊳NI(cs).\hat N_x\triangleright N_I(c_s).(19)✦

Last, let oˆ⊳O=(χ;H1,…,Hr)\hat o\triangleright O=(\chi;H_1,\dots,H_r) for an orientation OO for θ\theta, and let hˆ⊳H\hat h\triangleright H and hˆ′⊳H′\hat h'\triangleright H' be masks of two sets that an orientation for θ\theta may have as exceptions. Then ext(oˆ,hˆ,hˆ′)⊳(χ;H1,…,Hr,H,H′).\mathrm{ext}(\hat o,\hat h,\hat h')\triangleright (\chi;H_1,\dots,H_r,H,H').(20)✦