OctoInform Beta

OpenAI preprint, September 2026 · §7. Bit complexity · §7

§7 (proof of Theorem 7.1): integer magnitudes and exact parameters (7.6), (7.7): The post phase costs a polynomial in its input size, the preparation a polynomial in ∥d∥+225000⌈log⁡2(L+2)⌉2\|d\|+2^{25000\lceil\log_2(L+2)\rceil^2}

Bounded growth per step keeps every solver state polynomially small.

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

Take a mean-payoff game on a vertex set VV of nn vertices, given by an input string dd of length LL, and the randomized solver for its zero-threshold winning set, run on a Turing machine with a random tape. The run has two phases. The preparation reads dd and fixes the parameters, among them the number ss of samples, a power of two, and the number 225000λ22^{25000\lambda^2} of steps, where λ=⌈log⁡2(L+2)⌉\lambda=\lceil\log_2(L+2)\rceil. The post phase spends log⁡2s\log_2 s fair bits on each step, which give a uniform sample index in {0,…,s−1}\{0,\dots,s-1\}, runs the solver one step at a time as a stack machine, and writes out the answer. The question is how large the stored numbers, the stored vectors and sets, and the stack become over that many steps, and what each phase costs.

The library bounds the growth in one step and over a run, the size of every state reached, and the cost of the two phases.

The Stack Machine

A register pack is a record of eight registers, stored as bit strings and unary counters: the budgets, holding the positive rational support weights α,β\alpha,\beta and the budgets k,mk,m; a box, given by its reference width BB and its corners aa and bb; a counter; two vectors qq and rr; a list of vectors; an orientation; and a list of orientations.✦ An orientation is a choice of YY or ZZ together with a list of masks, each mask a set of vertices written as a bit string and also called an exception.✦ A stack cell is a pair of a tag, a natural number written as a unary counter, and a register pack.✦

A machine state σ\sigma is a pair of a current cell, which holds the job being called, a task of the solver, or the value being returned, and a stack of cells holding the pending frames, the suspended calls that await the value of a job.✦ The height h(σ)h(\sigma) of a machine state σ\sigma is the number of cells on its stack. The top tag τ(σ)\tau(\sigma) of a machine state σ\sigma is the largest tag among its current cell and the cells of its stack.

An environment η=(G,log⁡2s,s,J,N)\eta=(G,\log_2 s,s,J,N) is a tuple of the arena GG, the game graph with its transformed weights t(e)=(n+1)w(e)+1t(e)=(n+1)w(e)+1, where w(e)w(e) is the weight of the edge ee, and four counters: the sample exponent log⁡2s\log_2 s, the number ss of samples, the number JJ of trials and the step budget NN of the basic solver, the solver that the machine calls on boxes of small width.✦ A control accumulator is a pair (η,σ)(\eta,\sigma) of an environment and a machine state.✦

A step of the machine takes an environment η\eta, a sample index ii and a state σ\sigma to the state Δ(η,i,σ)\Delta(\eta,i,\sigma), chosen by the tag of the current cell.✦ The tags 0,…,90,\dots,9 name the jobs solve, ask, trials, update, centers, orient, orientation trials, orientation plus, tighten and reweight; a job either returns a pack, as a current cell with the return tag 1010, or pushes a frame onto the stack and calls another job. Under any other tag the step resumes the frame on top of the stack, chosen by its tag 0,…,210,\dots,21 among trials head, vector cons, median, first center, second center, centers head, orientation loop, orientation tail, orientation head, orientation cons, combine, first tightening, second tightening, floor and ceiling box passing, solve tight, solve oriented, reweight head, solve reweighted, cap high, cap low and include inner; on an empty stack the state stays as it is.✦

The trials job, started with a counter tt on a budget and a box, runs the solve job on that budget and box tt times in turn and returns the list of the tt vectors obtained; with t=0t=0 it returns the empty list.✦ The ask job on a budget and a box runs the trials job with JJ trials on them and returns the median of the resulting vectors, taken coordinatewise in the box.✦

The basic solver, run on the arena with step budget NN, is called by the solve job on boxes of width at most 128s128s. The update job and the first center frame call the ask job on a box narrowed about a vector to width B/(32s)B/(32s), and the orientation loop uses the sample index ii to pick one of its ss centers, about which it may call the orient job on a box of width B/8B/8. Trials are amplified by medians and majorities: the median frame returns the coordinatewise median of the trial vectors, and the combine frame returns the orientation that chooses YY exactly when a strict majority of the trial orientations do, carrying all their masks.

The update job on a box and a vector qq asks on the box narrowed about qq, first with the budget reduced in kk and then with the budget reduced in mm, and returns the average of the two vectors obtained, clipped to the box. The centers job, started with a counter tt and a vector q0q_0 on a budget and a box, applies the update job tt times in turn, starting from q0q_0, and returns the list q0,q1,…,qtq_0,q_1,\dots,q_t of the vectors obtained, the centers.✦

The grid width δ\delta of a box of width BB is B/2log⁡2s+2=B/(4s)B/2^{\log_2 s+2}=B/(4s).✦ The floor and the ceiling of a box are its lower corner aa and its upper corner bb. The tightening steps test whether a returned vector moves the floor or the ceiling of a box relative to δ\delta. The cap width of a box of width ww is w−δw-\delta.✦

For a box with midpoint mm and width ww, a scale ss and a vector vv, the positive displacement set is the set of coordinates ii with s(vi−mi)>2ws(v_i-m_i)>2w✦, and the negative displacement set is the set of coordinates ii with s(vi−mi)<−2ws(v_i-m_i)<-2w✦. At the ss-th center, with the sample count ss as scale, the orientation loop forms both sets. If, for the support weights, the positive set has measure above one half, it returns the orientation choosing YY with the complement of that set as exception; otherwise, if the negative set has measure above one half, it returns the orientation choosing ZZ with the complement of that set as exception; otherwise it calls the orient job at the center picked by the sample index✦, and the orientation tail frame extends the orientation returned by the two sets✦.

The base orientation of support weights α,β\alpha,\beta, a box with lower corner aa and width ww, and a vector vv is formed from the set MM of coordinates ii with w≤2(vi−ai)w\le 2(v_i-a_i): if MM has measure above one half for the support weights it chooses YY with the complement of MM as exception, and otherwise it chooses ZZ with MM as exception.✦ The orient job returns it on a box of width at most 128s128s, taking for vv the vector of the basic solver on that box.✦

On a box of width above 128s128s, the orient job computes the centers of the box with the centers job, with counter ss and the midpoint of the box as first center, and then continues in the orientation loop.✦ The orientation trials job, started with a counter tt on a budget and a box, runs the orient job on them tt times in turn and returns the list of the tt orientations obtained; with t=0t=0 it returns the empty list.✦

The tighten job on a budget and a box asks on the box with the budget reduced in kk.✦ If the vector qq returned moves the floor of the box relative to δ\delta, it moves the floor to qq and tightens again; otherwise it asks on the same box with the budget reduced in mm✦, and if the vector returned moves the ceiling relative to δ\delta, it moves the ceiling to that vector and tightens again✦. When neither the floor nor the ceiling moves, it returns the box.✦

After tightening, the solve job calls the orientation plus job on the budget and the tightened box, then the reweight job with the orientation returned. The reweight job takes the masks of the orientation one at a time, asks on the box with the budget reweighted by that mask according to the choice YY or ZZ, and returns the list of vectors obtained.✦ The solve job then calls itself on the box capped high for the choice YY and capped low for the choice ZZ, by the cap width✦, and the cap high and cap low frames take the coordinatewise minimum, respectively maximum, of the vector returned and the vectors of that list.

The solve job on a budget and a box first tests the budget: if it is small, it returns the vector prescribed for a small budget on the box; otherwise, on a box of width at most 128s128s it returns the vector of the basic solver, and on a wider box it tightens the box and continues as follows.✦

The control loop runs one step for each index of a list ι=(i1,…,ir)\iota=(i_1,\dots,i_r) of sample indices: from an accumulator (η,σ0)(\eta,\sigma_0) it passes through the accumulators (η,σ1),…,(η,σr)(\eta,\sigma_1),\dots,(\eta,\sigma_r), where σj=Δ(η,ij,σj−1),j=1,…,r.\sigma_j=\Delta(\eta,i_j,\sigma_{j-1}),\qquad j=1,\dots,r.(1)✦

Small States and Their Mass

Fix natural numbers nn, HH and MM. The size ∥x∥\|x\| of a string, a number, a state or an input xx is the size of its encoding. A register pack is (n,H,M)(n,H,M)-small when its budgets, its box, its two vectors and every vector of its list have at most nn entries and every number in them has size at most MM, its counter has length at most HH, and every mask of its orientation and of its list of orientations has at most nn entries.✦ A stack of cells is (n,H,M)(n,H,M)-small when the pack of each of its cells is✦, and a machine state is (n,H,M)(n,H,M)-small when the pack of its current cell and its stack are; 𝒮n,H,M\mathcal S_{n,H,M} is the set of (n,H,M)(n,H,M)-small machine states.✦

The mass of a register pack with list of vectors (v1,…,vp)(v_1,\dots,v_p), orientation oo and list of orientations (o1,…,oℓ)(o_1,\dots,o_\ell) is the natural number p+|o|+ℓ+∑j=1ℓ|oj|,p+|o|+\ell+\sum_{j=1}^{\ell}|o_j|,(2)✦ where |o||o| is the number of masks of an orientation oo. The mass μ(σ)\mu(\sigma) of a machine state σ\sigma is the sum of the masses of the packs of its current cell and of the cells on its stack.✦

The Two Phases

The preparation is a machine with step bound tprep(d)t_{\mathrm{prep}}(d) on the input string dd. It computes 225000λ22^{25000\lambda^2} by repeated doubling of a single unit, parses dd as a game and sets up the root: the top width B*B_*, the number gg equal to the binary length of B*B_* plus one, the sample exponent ⌈log⁡2(217(g+1))⌉\lceil\log_2(2^{17}(g+1))\rceil with ss its power of two✦, J=2(s(n+1))6+1J=2(s(n+1))^6+1✦, N=128nsN=128ns✦, and the initial state, which calls the solve job on the box [0,B*]V[0,B_*]^V with every entry of the support weights α\alpha and β\beta equal to 11 and the budgets k=m=nk=m=n, over an empty stack. It returns the counter (log⁡2s)225000λ2(\log_2 s)\,2^{25000\lambda^2} together with the chunk length log⁡2s\log_2 s, the bound ss, the number 225000λ22^{25000\lambda^2} of chunks into which the post phase cuts its random digits, the width B*B_* and the initial accumulator.✦ The resource R(d)R(d) of an input string dd is the number R(d)=∥d∥+225000λ2.R(d)=\|d\|+2^{25000\lambda^2}.(3)✦

An input zz of the post phase is a string of random digits together with the counter, the chunk length, the bound ss, the number of chunks, the width B*B_* and the initial accumulator that the preparation returns.✦ The sampler cuts the digits into chunks: its state holds the chunk length and the bound, the samples drawn so far and the digits not yet read✦, and each of its steps splits off the next chunk, reverses its digits, reads them as a number and reduces it below ss. The post phase runs the control loop from the initial accumulator over these sample indices and writes out the bit string marking the vertices vv whose coordinate qvq_v, in the vector qq of the final current cell, exceeds half of B*B_*.✦ The cost tpost(z)t_{\mathrm{post}}(z) of the post phase on an input zz is tpost(z)=trun(z)+tout(z)+2,t_{\mathrm{post}}(z)=t_{\mathrm{run}}(z)+t_{\mathrm{out}}(z)+2,(4)✦ where trun(z)t_{\mathrm{run}}(z) is the step bound of the machine that runs the post phase on zz and tout(z)t_{\mathrm{out}}(z) is the cost of writing out its output bits.

The Claim

Theorem 1. Let η=(G,log⁡2s,s,J,N)\eta=(G,\log_2 s,s,J,N) be an environment, ii a sample index and σ\sigma a machine state. Then μ(Δ(η,i,σ))≤μ(σ)+3,h(Δ(η,i,σ))≤h(σ)+2.\mu(\Delta(\eta,i,\sigma))\le\mu(\sigma)+3,\qquad h(\Delta(\eta,i,\sigma))\le h(\sigma)+2.(5)✦ Let nn, HH, MM, EE and DD be natural numbers such that s≤Hs\le H and J≤HJ\le H, every number of the arena GG has size at most EE, and N(E+1)+20≤DN(E+1)+20\le D. If σ\sigma is (n,H,M)(n,H,M)-small, then Δ(η,i,σ)∈𝒮n,H,M+D.\Delta(\eta,i,\sigma)\in\mathcal S_{n,H,M+D}.(6)✦ If moreover TT is a natural number with T≥22T\ge 22 and τ(σ)≤T\tau(\sigma)\le T, the control loop from (η,σ)(\eta,\sigma) over any list of rr sample indices ends in a state σr\sigma_r with σr∈𝒮n,H,M+rD,μ(σr)≤μ(σ)+3r,h(σr)≤h(σ)+2r,τ(σr)≤T.\sigma_r\in\mathcal S_{n,H,M+rD},\quad \mu(\sigma_r)\le\mu(\sigma)+3r,\quad h(\sigma_r)\le h(\sigma)+2r,\quad \tau(\sigma_r)\le T.(7)✦ For any list ι\iota of rr sample indices and any j≤rj\le r, the accumulator (η,σj)(\eta,\sigma_j) reached after the first jj steps of the control loop from (η,σ)(\eta,\sigma) satisfies ∥(η,σj)∥≤240(∥((η,σ),ι)∥+1)12.\|(\eta,\sigma_j)\|\le 2^{40}\bigl(\|((\eta,\sigma),\iota)\|+1\bigr)^{12}.(8)✦ If σ\sigma is (n,H,M)(n,H,M)-small and U≥1U\ge 1 is at least each of nn, HH, MM, τ(σ)\tau(\sigma), μ(σ)\mu(\sigma) and h(σ)h(\sigma), then ∥σ∥≤4096U4.\|\sigma\|\le 4096\,U^4.(9)✦ There is a polynomial PP such that every input string dd satisfies tprep(d)≤P(R(d)),t_{\mathrm{prep}}(d)\le P(R(d)),(10)✦ and there are constants CC and cc such that every input zz of the post phase satisfies tpost(z)≤C(∥z∥+1)c.t_{\mathrm{post}}(z)\le C\,(\|z\|+1)^{c}.(11)✦

In the paper, the result reads: every endpoint, center and returned coordinate lies in [−B*/6,7B*/6][-B_*/6,\,7B_*/6], the reachable support weights are 2−u2^{-u} and the reachable budgets n⋅4u3v/5u+vn\cdot 4^u3^v/5^{u+v} with exponents uu and vv summing to at most D*D_*, so that every number has O(x)O(x) bits and the local work attached to one invocation of the solver is polynomial, where D*D_* and xx are the paper’s parameters.

What Is Checked

The claim is stated over the stack machine of the solver: register packs, orientations, cells and machine states with their height and tags, environments and accumulators, the step Δ\Delta with its ten jobs and twenty-two frames, and the control loop (1); over (n,H,M)(n,H,M)-small packs, stacks and states and the mass (2); and over the two phases, the preparation with its resource (3) and the post phase with its sampler and its cost (4).

Beyond the claim, the library proves two size bounds inside the post phase. After any number of its steps on a counter, the state of the sampler has size at most 5(t+1)25(t+1)^2, where tt is the size of its starting state together with the counter✦; and the coordinatewise minimum or maximum that the cap high and cap low frames take of a vector and the first jj vectors of a list has size at most 20(S+1)220(S+1)^2, where SS is the size of the vector and the list.