OctoInformBeta

OpenAI preprint, September 2026 · §4. The exact correction and copy hierarchy · §4

Lemma 4.4 [Residual bounds and unsigned-term domination]: For a step matrix CC, D=C−E+ECD=C-E+EC has entries at most (T+1)f(T+1)f, at most f/256f/256 in good columns when TT is admissible, and C+E+EC≤(1+2T/A)DC+E+EC\le(1+2T/A)D

The corrected residual is substochastic and dominates its unsigned terms.

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 randomized machine with a clock moves through its configurations forward in time. Number its configurations so that every transition goes to a larger number, and the transition weights form a substochastic matrix whose positive entries lie strictly above the diagonal. The exact correction and copy hierarchy work with such matrices level by level: at level ii the scale of the entries of the level’s matrix CC is the rate 2−4i2^{-4i}, and CC is corrected by a matrix EE computed from probed values. What is left of the walk is a residual DD, a signed combination of CC, EE and the product ECEC.

The question is whether DD is again strictly forward and substochastic, how large its entries become, in particular in the columns the probed values mark as good, and how DD compares with the unsigned terms CC, EE and ECEC.

Matrices on a Finite Domain

The nodes are the natural numbers, and a finite domain SS is a finite set of nodes.✦ A real vector vv assigns a real number v(x)v(x) to each node xx, and a matrix of reals CC assigns a real entry C(x,y)C(x,y) to each pair of nodes x,yx,y. The product over SS of two matrices of reals FF and CC is the ordinary product with the middle index restricted to SS, (FC)(x,y)=∑z∈SF(x,z)C(z,y),(FC)(x,y)=\sum_{z\in S}F(x,z)\,C(z,y),(1)✦ and the row weight of CC at a node xx over SS is ∑y∈SC(x,y)\sum_{y\in S}C(x,y).✦

Given finite domains SS and S′S' and reals ff and kk, a bounded support matrix over SS with active set S′S', scale ff and bound kk is a matrix of reals CC such that, for all nodes xx and yy, 0≤C(x,y)≤kf,∑z∈SC(x,z)≤k,C(x,y)>0⇒x,y∈S′ and x<y;0\le C(x,y)\le kf,\qquad \sum_{z\in S}C(x,z)\le k,\qquad C(x,y)>0\ \Longrightarrow\ x,y\in S'\text{ and }x<y;(2)✦ we write ℬ(S,S′,f,k)\mathcal{B}(S,S',f,k) for the set of these matrices. A step matrix CC on SS at rate ff is a matrix of reals CC in ℬ(S,S,f,1)\mathcal{B}(S,S,f,1).✦

The Corrected Iteration

Fix a finite domain SS, a scale ff, a real vector gg and a matrix of reals CC, with products taken over SS. The entrywise correction at scale ff with weights gg is the operation that adjusts each entry of a matrix at scale ff according to the weights gg. The corrected iteration of CC at scale ff with weights gg is the sequence of matrices F0,F1,…F_0,F_1,\dots in which F0F_0 is the zero matrix and Ft+1F_{t+1} is the entrywise correction of C+FtCC+F_tC.✦ The residual of CC and FtF_t is Dt=C+FtC−Ft.D_t=C+F_tC-F_t.(3)✦ A column yy is good when g(y)=1g(y)=1.

The cutoff scale is A=1/4096A=1/4096.✦ An iteration count TT is admissible when it is positive and (5/A)TT!≤11024.\frac{(5/A)^T}{T!}\le\frac{1}{1024}.(4)✦

Stages

Parameter constants are four natural numbers: an admissible iteration count TT, a parameter KK, a number of copies MM and a parameter JJ, subject to 128(1+32(T+1)η(δ))≤K+1,16(T+1)<M,64M(T+1)2≤δ(J+1),128\Big(1+\frac{32(T+1)}{\eta(\delta)}\Big)\le K+1,\qquad 16(T+1)<M,\qquad 64\,M\,(T+1)^2\le\delta\,(J+1),(5)✦ where δ=A/400\delta=A/400✦ and η\eta is the map z↦z/1000z\mapsto z/1000.✦ A stage PP consists of parameter constants, a level ii, a finite domain SS of nodes and a matrix of reals CC of transition weights✦; its rate is f=2−4if=2^{-4i}, the retention rate of level ii.✦

Let nn be a prime, the field size of the stage’s channels, which are taken over the group (ℤ/n)4(\mathbb{Z}/n)^4. A pilot pair consists of a real vector VV of probed values and a matrix of reals EE, the correction.✦ The pilot sequence of a stage PP starts from the zero vector and the zero matrix, and each of its terms is obtained from the one before by the update of PP, a map from pilot pairs to pilot pairs; the probed vector VkV_k after kk rounds is the vector of its term of index kk.✦

The cutoff is assembled from the clamp c(u)=min⁡(1,max⁡(0,u))c(u)=\min(1,\max(0,u)) to [0,1][0,1], the smooth fade function ϕ\phi and the smooth rising ramp ρa,b\rho_{a,b} from aa to bb: ϕ(x)=12(c(2x)4+1−c(2−2x)4),ρa,b(x)=ϕ(x−ab−a).\phi(x)=\tfrac12\big(c(2x)^4+1-c(2-2x)^4\big),\qquad \rho_{a,b}(x)=\phi\Big(\frac{x-a}{b-a}\Big).(6) The cutoff function is γ(x)=1−ρ1/2,4/5(x)\gamma(x)=1-\rho_{1/2,4/5}(x); it equals 11 for x≤1/2x\le 1/2 and vanishes for x≥4/5x\ge 4/5.✦

The stage correction after kk steps, EkE_k, is the term FkF_k of the corrected iteration of CC on SS at scale ff with weights g(x)=γ(VT(x))g(x)=\gamma\big(V_T(x)\big), the cutoff of the probed values after TT rounds.✦ The corrected residual of the stage is the residual of CC and E=ETE=E_T: D=C−E+EC.D=C-E+EC.(7)✦

The Claim

Theorem 1. Let SS be a finite domain, f>0f>0 a real number, gg a real vector with values in [0,1][0,1] and CC a matrix of reals, and let FtF_t and DtD_t be the corrected iteration and its residual (3). If C∈ℬ(S,S′,f,1)C\in\mathcal{B}(S,S',f,1) for a finite domain S′S', then for every natural number tt Dt∈ℬ(S,S′,(t+1)f,1).D_t\in\mathcal{B}\big(S,S',(t+1)f,1\big).(8)✦ If CC is a step matrix on SS at rate ff, then for every natural number TT and all nodes xx and yy C(x,y)+FT(x,y)+(FTC)(x,y)≤(1+2TA)DT(x,y),C(x,y)+F_T(x,y)+(F_TC)(x,y)\le\Big(1+\frac{2T}{A}\Big)D_T(x,y),(9)✦ and if moreover TT is admissible and yy is a good column, then for every node xx DT(x,y)≤f256.D_T(x,y)\le\frac{f}{256}.(10)✦ For a stage with domain SS, matrix CC, rate ff and iteration count TT, for every field size nn and every finite domain S′S' with C∈ℬ(S,S′,f,1)C\in\mathcal{B}(S,S',f,1), the corrected residual (7) satisfies D∈ℬ(S,S′,(T+1)f,1).D\in\mathcal{B}\big(S,S',(T+1)f,1\big).(11)✦

In the paper, the result reads: with K*=k*+1K_*=k_*+1, εgood=θ2+q−1/32\varepsilon_{\mathrm{good}}=\theta_2+q^{-1}/32 and cdom=θ1/(2k*)c_{\mathrm{dom}}=\theta_1/(2k_*), the residual DD is nonnegative, strictly forward and substochastic, D(x,y)≤K*fD(x,y)\le K_*f, g(y)=1g(y)=1 implies D(x,y)≤εgoodfD(x,y)\le\varepsilon_{\mathrm{good}}f, D≥cdom(C+E+EC)D\ge c_{\mathrm{dom}}(C+E+EC), every unsigned term of the paper’s level-ii matrices GiG_i and Gi′G'_i is bounded by the input, and R(D)⊆R(C)\mathrm{R}(D)\subseteq\mathrm{R}(C) and T(D)⊆T(C)\mathrm{T}(D)\subseteq\mathrm{T}(C), where R\mathrm{R} and T\mathrm{T} are the paper’s operators on matrices (not the iteration count TT), the paper’s k*k_* is the page’s TT, θ1=A\theta_1=A and θ2=2A\theta_2=2A, and qq is the paper’s parameter occurring in εgood\varepsilon_{\mathrm{good}}.

What Is Checked

The claim is stated over finite domains of natural-number nodes, matrices of reals with their products and row weights over a domain, bounded support and step matrices, the corrected iteration and its residual, the cutoff scale AA and the admissible iteration counts, and, in (11), stages with their parameter constants, rate 2−4i2^{-4i}, pilot sequence and probed vectors, the cutoff γ\gamma built from the clamp, the fade function and the rising ramp, and the stage correction. The library also states that, when CC is a bounded support matrix over SS with active set S′S' at a positive scale ff and the weights gg take values in [0,1][0,1], every term FtF_t of the corrected iteration is substochastic.