OctoInform Beta

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

§4 (setting): the global parameters (4.1): Counters for log⁡2s\log_2 s, ss, JJ and 128ns128ns, read from a game’s input code, that with its arena represent the game at width B*B_*

The run computes its global parameters in unary.

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 randomized quasipolynomial-time solver for a mean-payoff game GG with nn vertices runs on a Turing machine with a random tape and calls recursive procedures on boxes in ℤV\mathbb{Z}^V, where VV is the vertex set of GG. It works with the transformed weight t(e)t(e) of each edge ee, an affine function of its weight w(e)w(e), and with the top width B*B_*, a number computed from nn and the largest absolute value of a transformed weight.

From B*B_* and nn the run fixes at the start the global parameters (4.1): an integer gg that grows with the number of binary digits of B*B_*; the sample size ss, a power of two, so that log⁡2s\log_2 s fair bits of the random tape give a uniform index in {0,…,s−1}\{0, \dots, s-1\}; and the number JJ of independent trials. With them comes the basic step budget 128ns128ns.

Before the first call, the machine reads the input code of GG, the fixed encoding of GG as a binary word, and writes these numbers in unary, as counters: a counter is a list of units, and a counter cc of length |c||c| stands for the number |c||c|. The counters for log⁡2s\log_2 s, ss, JJ and 128ns128ns, with the arena of GG, form an environment of the run, as defined below.

The Environment

An environment of the run is a tuple (A,c1,c2,c3,c4)(A, c_1, c_2, c_3, c_4) of an arena AA, with edge weights written as binary words, and four counters.✦

For a width BB, write s(B)s(B) and J(B)J(B) for the parameters ss and JJ of GG computed from BB in place of B*B_*. An environment (A,c1,c2,c3,c4)(A, c_1, c_2, c_3, c_4) represents a game GG with nn vertices and edges e1,…,eme_1, \dots, e_m at width BB when AA is the arena of GG in which each edge eie_i carries a binary word of value t(ei)t(e_i), and the counters have the lengths |c1|=log⁡2s(B),|c2|=s(B),|c3|=J(B),|c4|≥128ns(B).|c_1| = \log_2 s(B), \qquad |c_2| = s(B), \qquad |c_3| = J(B), \qquad |c_4| \ge 128\, n\, s(B).(1)✦

The Claim

Theorem 1. Let GG be a mean-payoff game with nn vertices, top width B*B_* and global parameters gg, ss and JJ. From the input code of GG, the root computation forms the counter cgc_g of the number of binary digits of B*B_* plus two✦, and the argument, the product of a constant counter of length 2172^{17} with cgc_g: ca=217⋅cg.c_a = 2^{17} \cdot c_g.(2)✦ From these it forms the counter cec_e of ⌈log⁡2|ca|⌉\lceil \log_2 |c_a| \rceil✦, the counter csc_s of 2|ce|2^{|c_e|}, computed with ca+cac_a + c_a as its bound, the trial base ct=(cs⋅(n+1))6c_t = (c_s \cdot (n+1))^6, a sixth power taken by repeated multiplication✦, and the counters cJ=ct+ct+1c_J = c_t + c_t + 1✦ and cb=n⋅(128⋅cs)c_b = n \cdot (128 \cdot c_s)✦. Then |cg|=g+1,|c_g| = g + 1,(3)✦ |ce|=log⁡2s,|c_e| = \log_2 s,(4)✦ |cs|=s,|c_s| = s,(5)✦ |cJ|=J,|c_J| = J,(6)✦ |cb|=128ns,|c_b| = 128\, n\, s,(7)✦ and, with AGA_G the arena written from the code of GG, the environment formed by the root computation satisfies (AG,ce,cs,cJ,cb)representsGat widthB*.(A_G, c_e, c_s, c_J, c_b) \ \text{represents}\ G \ \text{at width}\ B_*.(8)✦

In the paper, the result reads: with 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 B*=8nWB_* = 8nW from (2.1), fixed for the whole run, η=4/5\eta = 4/5, g=1+⌈log⁡2(B*+1)⌉g = 1 + \lceil \log_2(B_* + 1) \rceil, s=min⁡{2j:2j≥217(g+1)}s = \min\{2^j : 2^j \ge 2^{17}(g+1)\}, h=1/sh = 1/s, J=2[s(n+1)]6+1J = 2[s(n+1)]^6 + 1 and ε=2−J\varepsilon = 2^{-J}, which only the analysis uses.

What Is Checked

The claim is stated over a mean-payoff game GG with nn vertices and its input code, its top width B*B_* and global parameters gg, ss and JJ, the counters cgc_g, cac_a, cec_e, csc_s, cJc_J and cbc_b that the root computation forms from that code, and the environments of the run with the relation (1) of representing a game at a width.