OctoInformBeta

OpenAI preprint, September 2026 · §4. An initial pair at the working deletion rate

Proposition 4.1: Explicit overlap and repetition constants at the working deletion rate

Eventual initial pairs with controlled trace error.

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

At the initial scale, the question is whether opposite displacements of sparse defects admit trace simulations with a prescribed error budget. Each source bit is deleted with requested probability qq and survives with probability 1−q1-q. The construction theorems use the working rate δ=min⁡(q,1/2)\delta=\min(q,1/2) and Λ=δ−3\Lambda=\delta^{-3}; their parameter called qq is this working rate.

A finite probability law PP on a finite set Ω\Omega is a nonnegative mass function of total mass one.✦ For a real function ff on Ω\Omega and another law QQ on Ω\Omega, expectation, probability overlap, and total variation distance use the conventions in (1). P(a)≥0,∑a∈ΩP(a)=1,𝔼Pf=∑a∈ΩP(a)f(a),TV⁡(P,Q)=12∑a∈Ω|P(a)−Q(a)|,overlap⁡(P,Q)=∑a∈Ωmin⁡{P(a),Q(a)}=1−TV⁡(P,Q).\begin{gathered} P(a)\ge0,\qquad \sum_{a\in\Omega}P(a)=1,\qquad \mathbb E_P f=\sum_{a\in\Omega}P(a)f(a),\\ \operatorname{TV}(P,Q)=\frac12\sum_{a\in\Omega}|P(a)-Q(a)|,\qquad \operatorname{overlap}(P,Q)=\sum_{a\in\Omega}\min\{P(a),Q(a)\} =1-\operatorname{TV}(P,Q). \end{gathered}(1) A point mass at an outcome aa of a finite set Ω\Omega is a probability law on Ω\Omega that assigns mass one to aa and zero elsewhere. For a family of laws K(a)K(a) on a common finite outcome set, indexed by aa in Ω\Omega, the mixture of PP with this family is the probability law with mass ∑aP(a)K(a)(b)\sum_aP(a)K(a)(b) at each outcome bb; the pushforward f#Pf_\#P is the mixture using the point mass at f(a)f(a) for each aa.✦

A binary word ww of length ℓ\ell is a sequence of bits indexed by the zero-based positions 0,…,ℓ−10,\ldots,\ell-1.✦ A binary trace is a finite bit list whose surviving length is part of the observation; 𝒯\mathcal T denotes the set of all such traces.✦ A deletion mask a∈{0,1}ℓa\in\{0,1\}^{\ell} retains precisely the positions with ai=1a_i=1.✦ The retained subsequence Ta(w)T_a(w), deletion mask law μq\mu_q, and complete trace law 𝖳q(w)\mathsf T_q(w) are specified in (2). For a length bound M≥|w|M\ge|w|, the complete trace space 𝒯≤M\mathcal T_{\le M} contains all traces of length at most MM; a bounded trace is an element of this space.✦ The notation 𝒟q(w;F)\mathcal D_q(w;F) denotes the complete trace expectation of a real test FF. Ta(w)=(wi:ai=1 in increasing order),μq(a)=∏i=0ℓ−1{1−q,ai=1,q,ai=0,𝒯≤M=⋃j=0M{0,1}j,𝖳q(w)=(a↦Ta(w))#μq,𝒟q(w;F)=𝔼𝖳q(w)F.\begin{gathered} T_a(w)=(w_i:a_i=1\text{ in increasing order}),\qquad \mu_q(a)=\prod_{i=0}^{\ell-1} \begin{cases}1-q,&a_i=1,\\q,&a_i=0,\end{cases}\\ \mathcal T_{\le M}=\bigcup_{j=0}^{M}\{0,1\}^j,\qquad \mathsf T_q(w)=(a\mapsto T_a(w))_\#\mu_q,\qquad \mathcal D_q(w;F)=\mathbb E_{\mathsf T_q(w)}F. \end{gathered}(2) The complete trace overlap overlap⁡q(x,y)\operatorname{overlap}_q(x,y) is the overlap of 𝖳q(x)\mathsf T_q(x) and 𝖳q(y)\mathsf T_q(y) on their common space with bound M=max⁡{|x|,|y|}M=\max\{|x|,|y|\}.✦ The repeated word wLw^L is the concatenation of LL copies of ww.✦

Approximate trace simulation Sim⁡δ(P,η;w,E)\operatorname{Sim}_\delta(P,\eta;w,E) is the condition in (3) on a finite law PP and a decoder η\eta into complete traces. For a real score ss on Ω\Omega, a positive integer kk, and a zero-based level index ii, the probability-weighted squared even moment norm in the same display is taken under PP, with even score exponent ri=2kr_i=2k. Sim⁡δ(P,η;w,E):|𝔼P[F∘η]−𝒟δ(w;F)|≤Efor every F:𝒯→[0,1],∥s∥L2k(P)2=(∑a∈ΩP(a)|s(a)|2k)1/k.\begin{gathered} \operatorname{Sim}_\delta(P,\eta;w,E):\quad \bigl|\mathbb E_P[F\circ\eta]-\mathcal D_\delta(w;F)\bigr|\le E \quad\text{for every }F:\mathcal T\longrightarrow[0,1],\\ \|s\|_{L^{2k}(P)}^2= \left(\sum_{a\in\Omega}P(a)|s(a)|^{2k}\right)^{1/k}. \end{gathered}(3) An approximate oracle pair for x,yx,y with parameters (δ,k,E,V)(\delta,k,E,V) is a pair of finite laws P,QP,Q on a common finite outcome set, with a decoder η\eta and a real likelihood score ss satisfying (4). Write 𝒪δ(x,y;k,E,V)\mathcal O_\delta(x,y;k,E,V) for the class of these pairs. Sim⁡δ(P,η;x,E),Sim⁡δ(Q,η;y,E),Q(a)=P(a)(1+s(a)),1+s(a)≥0(a∈Ω),𝔼Ps=0,∥s∥L2k(P)2≤V.\begin{gathered} \operatorname{Sim}_\delta(P,\eta;x,E),\qquad \operatorname{Sim}_\delta(Q,\eta;y,E),\\ Q(a)=P(a)(1+s(a)),\qquad 1+s(a)\ge0\quad(a\in\Omega),\qquad \mathbb E_Ps=0,\qquad \|s\|_{L^{2k}(P)}^2\le V. \end{gathered}(4)✦

A concrete level pair at scale NN, zero-based level ii, and half moment order kk is a pair of distinct binary words x,yx,y, finite laws P,QP,Q with a common decoder η\eta, a real score ss, a nonnegative error EE, and a natural repetition count LL satisfying (5). Its parameters are the error allowance Δ\Delta, decay exponent dd, overlap threshold ω\omega, and count multiplier FF; write ℒδ(N,Δ,d,ω,F;i,k)\mathcal L_\delta(N,\Delta,d,\omega,F;i,k) for this class. x≠y,N/2≤ℓ=|x|=|y|≤N,E≥0,E/ℓ≤(i+1)Δ,Sim⁡δ(P,η;x,E),Sim⁡δ(Q,η;y,E),Q(a)=P(a)(1+s(a))(a∈Ω),∥s∥L2k(P)2≤N−d,ℓ≤L≤Fℓ,overlap⁡δ(xL,xL+1)≥ω.\begin{gathered} x\ne y,\qquad N/2\le\ell=|x|=|y|\le N,\qquad E\ge0,\qquad E/\ell\le(i+1)\Delta,\\ \operatorname{Sim}_\delta(P,\eta;x,E),\qquad \operatorname{Sim}_\delta(Q,\eta;y,E),\qquad Q(a)=P(a)(1+s(a))\quad(a\in\Omega),\\ \|s\|_{L^{2k}(P)}^2\le N^{-d},\qquad \ell\le L\le F\ell,\qquad \operatorname{overlap}_\delta(x^L,x^{L+1})\ge\omega. \end{gathered}(5)✦

The Initial Construction

For a natural number aa, the alternating primitive run RaR_a is the binary word (01)a(01)^a.✦ For natural numbers m,d,um,d,u, the single defect period Dm,dD_{m,d} is the binary word in (6). For defect slots dj∈{0,…,m−1}d_j\in\{0,\ldots,m-1\} indexed by j=0,…,u−1j=0,\ldots,u-1, the concatenated defect periods Per⁡(m,u,(dj))\operatorname{Per}(m,u,(d_j)) form the binary word in the same display. Dm,d=Rd1Rmax⁡{m−1−d,0},Per⁡(m,u,(dj))=Dm,d0⋯Dm,du−1.D_{m,d}=R_d\,1\,R_{\max\{m-1-d,0\}},\qquad \operatorname{Per}(m,u,(d_j))=D_{m,d_0}\cdots D_{m,d_{u-1}}.(6) A Laurent polynomial pp is a finitely supported real coefficient family indexed by ℤ\mathbb Z. For a natural motif order ss, the Prouhet polynomial psp_s and motif support indicator χs\chi_s in (7) specify a signed displacement σ\sigma. For a motif anchor XX, a displacement sign τ\tau, and an interior slot 1≤d1\le d with d+1<md+1<m, the displaced slot djd_j and motif defect word 𝒲(m,u,d,s,X;τ)\mathcal W(m,u,d,s,X;\tau) use the zero-based period index jj. ps(z)=∏v=0s−1(1−z2v),βs(j)=[zj]ps(z),χs(j)=𝟏{0≤j<2s},σ(χ,β,τ)={1,χ=0,2,χ≠0 and βτ=1,0,otherwise,dj=d+σ(χs(j−X),βs(j−X),τ)−1,𝒲(m,u,d,s,X;τ)=Per⁡(m,u,(dj)).\begin{gathered} p_s(z)=\prod_{v=0}^{s-1}(1-z^{2^v}),\qquad \beta_s(j)=[z^j]p_s(z),\qquad \chi_s(j)=\mathbf1_{\{0\le j<2^s\}},\\ \sigma(\chi,\beta,\tau)= \begin{cases}1,&\chi=0,\\2,&\chi\ne0\text{ and }\beta\tau=1,\\0,&\text{otherwise},\end{cases}\\ d_j=d+\sigma\bigl(\chi_s(j-X),\beta_s(j-X),\tau\bigr)-1,\qquad \mathcal W(m,u,d,s,X;\tau)=\operatorname{Per}(m,u,(d_j)). \end{gathered}(7)

Write ⌊⋅⌋+\lfloor\cdot\rfloor_+ and ⌈⋅⌉+\lceil\cdot\rceil_+ for the floor and ceiling truncated below at zero. At scale N≥1N\ge1, the primitives per period mm, buffer count KK, period length ℓper\ell_{\mathrm{per}}, and period capacity UU are given in (8). The base side count hh, block count JJ, and period count pp are given in (8). For m≥4m\ge4, the middle defect slot d*∈{0,…,m−1}d_*\in\{0,\ldots,m-1\} has the value in that display; the zero-based motif anchor XX is an integer. m=⌊N62/125⌋+,K=⌊N123/250⌋+,ℓper=2m−1,U=⌊N/ℓper⌋+,h=⌊δm⌋+,J=⌊U−K2h+1⌋+,p=J(2h+1)+K,d*=max⁡{⌊m/2⌋−1,0},X=⌊p/2⌋−1∈ℤ.\begin{gathered} m=\lfloor N^{62/125}\rfloor_+,\qquad K=\lfloor N^{123/250}\rfloor_+,\qquad \ell_{\mathrm{per}}=2m-1,\qquad U=\lfloor N/\ell_{\mathrm{per}}\rfloor_+,\\ h=\lfloor\delta m\rfloor_+,\qquad J=\left\lfloor\frac{U-K}{2h+1}\right\rfloor_+,\qquad p=J(2h+1)+K,\\ d_*=\max\{\lfloor m/2\rfloor-1,0\},\qquad X=\lfloor p/2\rfloor-1\in\mathbb Z. \end{gathered}(8) The periodic reference word xref(δ,N)x_{\mathrm{ref}}(\delta,N) and signed initial word xτ(δ,N)x_\tau(\delta,N) are defined in (9); the motif order is 300300. xref(δ,N)=Dm,d*p,xτ(δ,N)={𝒲(m,p,d*,300,X;τ),m≥4,empty word,m<4.x_{\mathrm{ref}}(\delta,N)=D_{m,d_*}^{\,p},\qquad x_\tau(\delta,N)= \begin{cases} \mathcal W(m,p,d_*,300,X;\tau),&m\ge4,\\ \text{empty word},&m<4. \end{cases}(9)

The rank Schur constant crc_{\mathrm{r}} and primitive period constant κ\kappa are the absolute constants in (10). The initial overlap lower bound ω0(δ)\omega_0(\delta) and source overlap constant C(δ)C(\delta) depend on the working rate. cr=88473621−exp⁡(−1/1024)exp⁡(1),κ=36cr2,ω0(δ)=11536exp⁡(−32+3κδ3),C(δ)=240δω0(δ).\begin{gathered} c_{\mathrm{r}}=884736\frac{2}{1-\exp(-1/1024)}\exp(1),\qquad \kappa=36c_{\mathrm{r}}^{\,2},\\ \omega_0(\delta)=\frac1{1536} \exp\!\left(-\frac{32+3\kappa}{\delta^3}\right),\qquad C(\delta)=\frac{2^{40}}{\delta\omega_0(\delta)}. \end{gathered}(10) The initial moment ratio ρδ(u,m,w)\rho_\delta(u,m,w) and initial error bound ℰ(J,K,m,k;δ,ω,w)\mathcal E(J,K,m,k;\delta,\omega,w) are the functions in (11). The base primitive score weight wδ,kw_{\delta,k} specializes this bound to the source initial error E0(δ,N,k)E_0(\delta,N,k), using the parameters of (8). ρδ(u,m,w)=w23crδum,wδ,k=6(2k)2δ,ℰ(J,K,m,k;δ,ω,w)=6(4ρδ(K,m,w)1−ρδ(K,m,w))k+2exp⁡(−Kmδ464)+exp⁡(−Jω416),E0(δ,N,k)=ℰ(J,K,m,k;δ,ω0(δ),wδ,k).\begin{gathered} \rho_\delta(u,m,w)=w^2\frac{3c_{\mathrm{r}}}{\delta}\sqrt{\frac um},\qquad w_{\delta,k}=6(2k)\frac2\delta,\\ \mathcal E(J,K,m,k;\delta,\omega,w)= \sqrt{6\left(\frac{4\rho_\delta(K,m,w)}{1-\rho_\delta(K,m,w)}\right)^k} +2\exp\!\left(-\frac{Km\delta^4}{64}\right) +\exp\!\left(-\frac{J\omega^4}{16}\right),\\ E_0(\delta,N,k)= \mathcal E(J,K,m,k;\delta,\omega_0(\delta),w_{\delta,k}). \end{gathered}(11) The initial construction geometry 𝒢δ(N)\mathcal G_\delta(N) is the condition on (δ,N)(\delta,N) given by the inequalities in (12). m≥128,0<K≤m,δ3m≥16,Kmδ2≥8,12(J+2300+1)≤K,2⋅2300<K3(3000+1),N/2≤pℓper≤N.\begin{gathered} m\ge128,\qquad 0<K\le m,\qquad \delta^3m\ge16,\qquad Km\delta^2\ge8,\\ 12(J+2^{300}+1)\le K,\qquad 2\cdot2^{300}<\frac{K}{3(3000+1)},\qquad N/2\le p\ell_{\mathrm{per}}\le N. \end{gathered}(12)✦

The Smallest Scale

For a block size B≥2B\ge2, slack 0<ζ<10<\zeta<1, and problem size nn, the induction depth DD and scale slack ε\varepsilon are defined by (13). H=δ3log⁡n,D=⌊(1−ζ)log⁡HBlog⁡2⌋+,ε=124B+100(D+1).H=\delta^3\log n,\qquad D=\left\lfloor\frac{(1-\zeta)\log H}{B\log2}\right\rfloor_+,\qquad \varepsilon=\frac1{2^{4B+100}(D+1)}.(13) The warmup block count WBW_B, source block dimension bi+1b_{i+1}, block gain g(b)g(b), and scale exponent aj(b,ε)a_j(b,\varepsilon) are given in (14). The block index ii is zero-based, so bi+1b_{i+1} is the dimension of block i+1i+1 in the paper; jj is the zero-based scale index within a block. WB=5⋅2B,bi+1={2,i<WB,B,i≥WB,g(b)=b−14−120,aj(b,ε)=(1+ε)2j2b−ε.\begin{gathered} W_B=5\cdot2^B,\qquad b_{i+1}=\begin{cases}2,&i<W_B,\\B,&i\ge W_B,\end{cases}\\ g(b)=\frac{b-1}{4}-\frac1{20},\qquad a_j(b,\varepsilon)=(1+\varepsilon)\frac{2^j}{2^b}-\varepsilon. \end{gathered}(14) The scale exponent product Πi\Pi_i defines the backwards target scale NiN_i in (15). The total score exponent ADA_D and half moment order kik_i use the same block dimensions. Πi=∏j=iD−1a0(bj+1,ε),Ni=nΠi,AD=115+∑j=0D−1g(bj+1),ki=⌈108210B(AD+B+1)log⁡nlog⁡Ni⌉+.\begin{gathered} \Pi_i=\prod_{j=i}^{D-1}a_0(b_{j+1},\varepsilon),\qquad N_i=n^{\Pi_i},\qquad A_D=\frac{11}{5}+\sum_{j=0}^{D-1}g(b_{j+1}),\\ k_i=\left\lceil 10^8 2^{10B}(A_D+B+1)\frac{\log n}{\log N_i} \right\rceil_+. \end{gathered}(15) A real sequence ff has power law exponent aa relative to a scale sequence NN when it satisfies (16). ft>0 for all sufficiently large t,log⁡ftlog⁡Nt→a.f_t>0\text{ for all sufficiently large }t,\qquad \frac{\log f_t}{\log N_t}\longrightarrow a.(16)✦

The Claim

Theorem 1. Let Nt,nt,At,δtN_t,n_t,A_t,\delta_t be real sequences and ktk_t natural numbers. Suppose Nt,nt→∞N_t,n_t\to\infty, 0<δt≤1/20<\delta_t\le1/2 for every tt, and At≥1A_t\ge1, kt≥1k_t\ge1 for all sufficiently large tt. Assume that kk has power law exponent zero relative to NN, that Λt/log⁡Nt→0\Lambda_t/\log N_t\to0, and that 106Atlog⁡nt≤ktlog⁡Nt10^6A_t\log n_t\le k_t\log N_t eventually. Put Et=E0(δt,Nt,kt)E_t=E_0(\delta_t,N_t,k_t) and abbreviate the signed words by x±,t=x±1(δt,Nt)x_{\pm,t}=x_{\pm1}(\delta_t,N_t) and the reference word by xref,t=xref(δt,Nt)x_{{\mathrm{ref}},t}=x_{\mathrm{ref}}(\delta_t,N_t). The assertions in (17) hold for all sufficiently large tt. 𝒢δt(Nt),Et≤nt−100At,𝒪δt(x−,t,x+,t;kt,Et,Nt−11/5)≠⌀,𝒪δt(xref,t,x+,t;kt,Et,Nt−7/5)≠⌀.\begin{gathered} \mathcal G_{\delta_t}(N_t),\qquad E_t\le n_t^{-100A_t},\\ \mathcal O_{\delta_t}(x_{-,t},x_{+,t};k_t,E_t,N_t^{-11/5})\ne\varnothing,\\ \mathcal O_{\delta_t}(x_{{\mathrm{ref}},t},x_{+,t};k_t,E_t,N_t^{-7/5})\ne\varnothing. \end{gathered}(17)✦

Fix B≥2B\ge2 and 0<ζ<10<\zeta<1. Let nt→∞n_t\to\infty and 0<δt≤1/20<\delta_t\le1/2 for every tt, with Ht=δt3log⁡nt→∞H_t=\delta_t^3\log n_t\to\infty. Evaluate DtD_t, ADtA_{D_t}, N0,tN_{0,t}, and k0,tk_{0,t} at (δt,nt)(\delta_t,n_t) using (13) and (15), and put Δt=nt−100(ADt+B+1)\Delta_t=n_t^{-100(A_{D_t}+B+1)}. The level-zero existence statement (18) holds for all sufficiently large tt. ℒδt(N0,t,Δt,115,ω0(δt),C(δt)2B⋅0+2;0,k0,t)≠⌀.\mathcal L_{\delta_t}\left( N_{0,t},\Delta_t,\frac{11}{5},\omega_0(\delta_t), C(\delta_t)^{2B\cdot0+2};0,k_{0,t}\right)\ne\varnothing.(18)✦

In the paper, the result reads: for the global parameters, a level-zero pair exists with simulation error E0≤ΔE_0\le\Delta and common constants as in Definition 2.2 with MB=1M_B=1, and one may choose ω=exp⁡(−C9Λ)\omega=\exp(-C_9\Lambda) with C9C_9 absolute and C>2C>2 with log⁡C=O(Λ)\log C=O(\Lambda).

What Is Checked

The oracle assertion is stated over the signed initial words and their periodic reference, and the level-zero assertion over distinct equal-length binary words with finite decoded laws satisfying the simulation and score conditions. Deletion mask probabilities are nonnegative for q∈[0,1]q\in[0,1]✦, and their sum is one for every real qq.✦