OctoInformBeta

OpenAI preprint, September 2026 · §12. Derandomization and quantitative consequences · §12

Theorem 12.1 [Fixed inverse-polynomial accuracy]: A function within 1/321/32 of the estimator has evidence within 1/81/8 of the acceptance probability, and comparing integer sums decides the language

A close logspace estimate places bounded-error languages in L\mathrm{L}..

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 probabilistic Turing machine PP that works in logarithmic space within a polynomial clock, and a language AA that PP recognizes with bounded error: it accepts each word of AA with probability at least 2/32/3 and each other word with probability at most 1/31/3. Placing AA in L\mathrm{L} means telling the two cases apart by a deterministic machine in logarithmic space, here by estimating the acceptance probability and comparing the estimate with 1/21/2.

The estimate is built from sampling environments, triples of affine lines in (ℤ/N)4(\mathbb{Z}/N)^4 for a prime NN: a logspace computable function is evaluated on each of them and averaged. The question is how close that function has to come to the estimator of the acceptance probability, a real-valued function of an environment computed on the configuration graph of PP on the input, for the average to separate 2/32/3 from 1/31/3, and how the comparison with 1/21/2 stays within logarithmic space.

Machines, Clocks and Configurations

A probabilistic Turing machine with states 0,…,q0,\dots,q, ww binary work tapes and hh input heads has an initial state, an output at each state (accept, reject or none, the states with an output being the halting ones) and a transition.✦ The transition maps a state, the input symbols under the input heads, the bits under the work heads and a coin bit to a next state, a bit to write on each work tape and a move, left, stay or right, of every head. The input tape holds the word xx, of length nn, between a left and a right endmarker.✦ The run on xx with an infinite coin tape γ\gamma starts in the initial configuration and takes its step at time tt with the coin γ(t)\gamma(t)✦; the space it uses through time tt is the number of distinct cells its work heads have visited by then, summed over the work tapes.✦

A source machine PP is a probabilistic Turing machine together with a space coefficient csc_s and a clock t(x)=c(n+2)kt(x) = c\,(n+2)^k with constants cc and kk.✦ A source machine PP keeps its space bound when on every input xx, with every coin tape and through every time, it uses at most cs⌈log⁡2(n+2)⌉c_s\lceil\log_2(n+2)\rceil cells.✦ The acceptance probability pP(x)p_P(x) of a source machine PP on an input xx is the fraction of the coin sequences of length t(x)t(x) on which the run of PP on xx is in an accepting state at time t(x)t(x): pP(x)=2−t(x)|{β∈{0,1}t(x):P on x with coins β is in an accepting state at time t(x)}|.p_P(x) = 2^{-t(x)}\,\bigl|\{\beta\in\{0,1\}^{t(x)} : P \text{ on } x \text{ with coins } \beta \text{ is in an accepting state at time } t(x)\}\bigr|.(1)✦

A language is a set of binary words.✦ A machine is deterministic when its transition ignores the coin bit✦; it runs in logarithmic space when for some c>0c > 0 it uses at most c⌈log⁡2(n+2)⌉c\lceil\log_2(n+2)\rceil cells on every input, coin tape and time✦; and it decides a language AA when for every input xx there is a time at which, whatever the coins, its state has the output accept if x∈Ax \in A and reject otherwise.✦ The class L\mathrm{L} is the set of languages decided by a deterministic machine that runs in logarithmic space.✦

The configuration graph of a source machine PP on an input xx has the numbered configurations of PP on xx as its nodes. A register record lists a time, a state, the positions of the input heads, and each work tape as two numbers whose binary digits are the cells left of the head and the cells from the head rightward.✦ The node of a register record is the number whose digits in the node radix ρx=q+2+t(x)+(n+2)+2(2(n+2))2cs\rho_x = q + 2 + t(x) + (n+2) + 2\,(2(n+2))^{2c_s} are the registers of the record, and the nodes are the numbers below the node count νx=ρx2w+h+2\nu_x = \rho_x^{\,2w+h+2}. A record is legal when its registers are below ρx\rho_x and its state number is at most qq.✦ The initial node v0v_0 is the node of the start record: time 00, the initial state, every input head on cell 00 and blank work tapes.✦ From a node with a legal record of time below t(x)t(x), the coin bb leads to the node of the record after one step, when that record is legal.✦ The halved edge weight Sx(i,j)S_x(i,j) is half the number of coins that lead from ii to jj✦, and ii is an accepting final node when its record is legal, has time t(x)t(x) and an accepting state.✦ A step of a record increases the time by one, replaces the state by the next state given by the transition, overwrites the cell under each work head and moves that head, and moves each input head in the direction the transition gives, an input head staying on the cells 00 to n+1n+1. When the state has an output, a step changes nothing: the state is kept, the scanned bits are rewritten unchanged and every head stays in place.

Environments and the Evidence

The analytic constants of a source machine PP are an iteration count TT of the estimator that is admissible, a number M>16(T+1)M > 16(T+1) of copies of each vertex, the copies of yy being z+Myz + My for z<Mz < M, two sizes KK and JJ with 128(1+32000(T+1)/δ)≤K+1128\,(1 + 32000\,(T+1)/\delta) \le K+1 and 64M(T+1)2≤δ(J+1)64\,M\,(T+1)^2 \le \delta\,(J+1), where δ=A/400\delta = A/400 and A=1/4096A = 1/4096 is the cutoff scale, and two natural numbers A0A_0 and ℓ\ell. An admissibility certificate for the analytic constants consists of a constant R≥1R \ge 1 that bounds the fourth roots of the cutoff profiles of the estimator and their Lipschitz constants, budget constants that meet the credit condition at A0A_0, and the walk length condition 16ϵℓ≤2−7216\,\epsilon^{\ell} \le 2^{-72}, where ϵ=1−(16384(10g0|𝒞|)2)−1\epsilon = 1 - (16384\,(10\,g_0\,|\mathcal{C}|)^2)^{-1} with the gap constant g0=6+4/τg_0 = 6 + 4/\tau, τ=2(1−cos⁡(π/8))\tau = 2(1-\cos(\pi/8)), and the set 𝒞\mathcal{C} of generator choices of the random walk of length ℓ\ell that the estimator uses.✦ The bank of an admissibility certificate is β=4+2R3(W+1)\beta = 4 + 2R^3(W+1), with the width W=K+128(1+32(128+4(J+1)))W = K + 128\,(1 + 32(128 + 4(J+1))).✦

Fix a source machine PP with analytic constants, an input xx, a natural number BB, the budget, and a prime NN. A channel X=(a,b)X = (a,b) over ℤ/N\mathbb{Z}/N is a pair of a nonzero direction a∈(ℤ/N)4a \in (\mathbb{Z}/N)^4 and an offset b∈(ℤ/N)4b \in (\mathbb{Z}/N)^4✦; its point at y∈ℤ/Ny \in \mathbb{Z}/N is X(y)=b+yaX(y) = b + ya, so that it describes an affine line.✦ An environment is a triple s=(X,Y,Z)s = (X, Y, Z) of channels.✦ The box of level kk is the set QkQ_k of vectors of (ℤ/N)4(\mathbb{Z}/N)^4 whose four coordinates have least nonnegative representatives below mk=⌊(N−1)/2k⌋+1m_k = \lfloor (N-1)/2^k \rfloor + 1.✦

The start vertex is ι=MBv0\iota = M^B v_0, read in ℤ/N\mathbb{Z}/N: the copy of index 00 of the initial node, taken BB times. An environment s=(X,Y,Z)s = (X,Y,Z) retains the start when its first line passes through the box of level BB at the start vertex, X(ι)∈QB,X(\iota) \in Q_B,(2)✦ and ℛ\mathcal{R} is the set of environments that retain the start.

The evidence ℰ(f)\mathcal{E}(f) of a real function ff on environments is its average over the environments whose first channel has a nonzero direction aa and passes through a point uu of QBQ_B at ι\iota: ℰ(f)=avga≠0,u∈QB,Y,Zf((a,u−ιa),Y,Z),\mathcal{E}(f) = \mathop{\mathrm{avg}}\limits_{a \ne 0,\; u \in Q_B,\; Y,\, Z} f\bigl((a,\,u - \iota a),\,Y,\,Z\bigr),(3)✦

For the budget BB and the prime NN, the estimator is a real-valued function of an environment and a vertex, computed on the configuration graph of PP on xx: the nodes below νx\nu_x, weighted by the halved edge weights Sx(i,j)S_x(i,j), with reward 11 at the accepting final nodes and 00 elsewhere. Vˆ(s)\widehat{V}(s) denotes its value on the environment ss at the start vertex ι\iota.

A source machine PP with analytic constants, an input xx, a budget BB and a prime NN are ready for an admissibility certificate with bank β\beta when B≥6,νx≤2B,β≤2B,M<N,2κ(B)≤N,B \ge 6,\qquad \nu_x \le 2^{B},\qquad \beta \le 2^{B},\qquad M < N,\qquad 2^{\kappa(B)} \le N,(4)✦ where the ceiling κ(B)=8((7+M)B+A0(1+(50+8T)B))+(2+M)B+1\kappa(B) = 8\bigl((7+M)B + A_0(1 + (50+8T)B)\bigr) + (2+M)B + 1 is an affine function of BB.

The Threshold Test

With the bit length λ(y)=⌊log⁡2y⌋+1\lambda(y) = \lfloor\log_2 y\rfloor + 1 of a positive integer yy and a padding Δ\Delta, the bit budget of xx is Bx=Δ+λ(νx)+λ(n+2),B_x = \Delta + \lambda(\nu_x) + \lambda(n+2),(5)✦ and the field size NxN_x is the largest prime NN with Λx<N≤2Λx\Lambda_x < N \le 2\Lambda_x, where Λx=2κ(Bx)+M\Lambda_x = 2^{\kappa(B_x)} + M.✦ Vˆx(s)\widehat{V}_x(s) denotes the value of the estimator on an environment ss over ℤ/Nx\mathbb{Z}/N_x at the start vertex, for the budget BxB_x and the prime NxN_x. An environment ss over ℤ/Nx\mathbb{Z}/N_x has the code ⟨s⟩\langle s \rangle, the natural number that lists, in a fixed encoding of tuples, the coordinates of the directions and offsets of its three channels as numbers below NxN_x.✦

A counter program works on registers that hold natural numbers: it moves a register up or down by one, and it branches or loops on the input symbol in the cell a register points to.✦ An expression of a counter program is what the program writes into a register; a map ff from a word and a natural number to a natural number is logspace-computable when, for some exponent dd and read on codes, it carries every such expression, with its registers kept below UdU^{d} whenever they start below some U≥n+2U \ge n+2, to an expression of the same kind.✦ The survey value of such an ff on an environment ss over ℤ/Nx\mathbb{Z}/N_x is the dyadic number svf(x,s)=164min⁡(64,f(x,⟨s⟩)).\mathrm{sv}_f(x,s) = \tfrac{1}{64}\min\bigl(64,\ f(x,\langle s\rangle)\bigr).(6)✦

A natural number ii qualifies at xx when it is the code of a triple of channels, with coordinates below NxN_x and nonzero directions, whose first channel (a,b)(a,b) passes the retention test in integers: every coordinate of (b+MBxv0a)mod⁡Nx(b + M^{B_x} v_0\, a) \bmod N_x is below mBxm_{B_x}.✦ Over the qualifying ii below ωx\omega_x, one more than the code of the triple whose coordinates all equal NxN_x, the census CxC_x counts them✦ and the capped sum of ff adds their capped values: Cx=|{i<ωx:i qualifies}|,Σf(x)=∑i<ωx,i qualifiesmin⁡(64,f(x,i)).C_x = \bigl|\{i < \omega_x : i \text{ qualifies}\}\bigr|, \qquad \Sigma_f(x) = \sum_{i<\omega_x,\ i \text{ qualifies}} \min\bigl(64,\ f(x,i)\bigr).(7)✦ The threshold answer of ff at xx is ansf(x)={1if 32Cx<Σf(x),0otherwise.\mathrm{ans}_f(x) = \begin{cases} 1 & \text{if } 32\,C_x < \Sigma_f(x), \\ 0 & \text{otherwise.} \end{cases}(8)✦

The Claim

Theorem 1 (Fixed inverse-polynomial accuracy). (a) Let PP be a source machine with analytic constants, xx an input, BB a budget and NN a prime. For every real function ff on environments, ∑s∈ℛf(s)=|ℛ|ℰ(f).\sum_{s \in \mathcal{R}} f(s) = |\mathcal{R}|\;\mathcal{E}(f).(9)✦

(b) Suppose moreover that PP keeps its space bound, that the data are ready for an admissibility certificate of the constants, and that ff is a real function on environments with |f(s)−Vˆ(s)|≤1/32|f(s) - \widehat{V}(s)| \le 1/32 for every environment ss that retains the start. Then |pP(x)−ℰ(f)|<1/8.\bigl|p_P(x) - \mathcal{E}(f)\bigr| < 1/8.(10)✦

(c) Let pp and ee be reals with |p−e|<1/8|p - e| < 1/8, let a>0a > 0 and bb be natural numbers with b/64=aeb/64 = ae, and let HH be a statement such that p≥2/3p \ge 2/3 if HH holds and p≤1/3p \le 1/3 if it fails. Then 32a<b⇔H.32a < b \iff H.(11)✦

(d) Let AA be a language and PP a source machine that keeps its space bound, whose analytic constants carry an admissibility certificate with bank β≤2Δ\beta \le 2^{\Delta} for a padding Δ≥6\Delta \ge 6. Let ff be a logspace computable map with |svf(x,s)−Vˆx(s)|≤1/32|\mathrm{sv}_f(x,s) - \widehat{V}_x(s)| \le 1/32 for every input xx and every environment ss over ℤ/Nx\mathbb{Z}/N_x that retains the start. If pP(x)≥2/3p_P(x) \ge 2/3 for every x∈Ax \in A and pP(x)≤1/3p_P(x) \le 1/3 for every x∉Ax \notin A, then A∈L.A \in \mathrm{L}.(12)✦

In the paper, the result reads: for a randomized machine PP with polynomial worst-case running time and work space O(log⁡(n+2))O(\log(n+2)) and an integer d≥1d \ge 1, there is a uniform deterministic transducer that outputs a dyadic zx∈[0,1]z_x \in [0,1] with |zx−pP(x)|≤(n+2)−d|z_x - p_P(x)| \le (n+2)^{-d}, in work space and output length O(log⁡(n+2))O(\log(n+2)) and polynomial time, with constants depending on PP and dd only.

What Is Checked

The claims (9), (10), (11) and (12) are stated over the library’s probabilistic Turing machines, with their acceptance probability (1) within a polynomial clock, their space bound and the class L\mathrm{L}; over the configuration graph and the bit budget (5); over the environments of three channels over ℤ/N\mathbb{Z}/N, the retention test (2), the evidence (3), the readiness conditions (4) and the estimator’s value Vˆ\widehat{V}; and over the survey values (6), the census and capped sums (7) and the threshold answer (8).