OctoInformBeta

OpenAI preprint, September 2026 · §2. The induction and global scales

Definition 2.2: Finite auxiliary laws quantify indistinguishability at a prescribed induction scale

Level pairs with controlled trace simulation.

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

Trace reconstruction compares the laws of the subsequences left after independent bit deletions. The induction measures this comparison at a prescribed word length, with auxiliary observations decoded into traces and with overlap between repeated words. Write q∈[0,1]q\in[0,1] for the requested deletion probability and put δ=min⁡(q,1/2)\delta=\min(q,1/2) and Λ=δ−3\Lambda=\delta^{-3}; the construction theorems call their working deletion rate δ\delta by the name qq.

Finite Laws and Traces

A finite probability law PP on a finite set Ω\Omega is a nonnegative mass function of total mass one.✦ The expectation 𝔼P[f]\mathbb E_P[f] of a real function ff on Ω\Omega under a finite probability law PP on Ω\Omega is the real number in (1). 𝔼P[f]=∑a∈ΩP(a)f(a).\mathbb E_P[f]=\sum_{a\in\Omega}P(a)f(a).(1)✦ The point mass δa\delta_a at an outcome aa of a finite set Ω\Omega is the probability law on Ω\Omega assigning mass one to aa and zero elsewhere. A Markov kernel KK from Ω\Omega to a finite set Ξ\Xi assigns a probability law K(a,⋅)K(a,\cdot) to each aa. For a finite probability law PP on Ω\Omega, a Markov kernel KK from Ω\Omega to Ξ\Xi, and a map f:Ω→Ξf:\Omega\to\Xi, the mixture PKPK and the pushforward f*Pf_*P are the probability laws on Ξ\Xi in (2); the latter uses the point mass δf(a)\delta_{f(a)} at each input. (PK)(b)=∑a∈ΩP(a)K(a,b),f*P=P(a↦δf(a)).(PK)(b)=\sum_{a\in\Omega}P(a)K(a,b), \qquad f_*P=P\bigl(a\mapsto\delta_{f(a)}\bigr).(2)

A binary word ww of length mm is a function assigning a bit to each zero-based position 0,…,m−10,\ldots,m-1.✦ A deletion mask aa for a binary word of length mm is a list of decisions indexed by the positions 0,…,m−10,\ldots,m-1, with a(j)=1a(j)=1 retaining position jj and a(j)=0a(j)=0 deleting it. For a deletion mask aa of a binary word of length mm and a real parameter ρ\rho, the deletion mask weight Wρ,m(a)W_{\rho,m}(a) is the real number in (3). For ρ∈[0,1]\rho\in[0,1] and a word length mm, the deletion mask law 𝖬ρ,m\mathsf M_{\rho,m} is the probability law on deletion masks for a word of length mm that assigns mass Wρ,m(a)W_{\rho,m}(a) to each mask aa.✦ Wρ,m(a)=∏j=0m−1{1−ρ,a(j)=1,ρ,a(j)=0.W_{\rho,m}(a) =\prod_{j=0}^{m-1} \begin{cases} 1-\rho,&a(j)=1,\\ \rho,&a(j)=0. \end{cases}(3)✦ A binary trace is a finite bit list, including its surviving length.✦ For a binary word ww and a deletion mask aa of its positions, the retained subsequence tr⁡(w,a)\operatorname{tr}(w,a) is the binary trace listing, in order, the bits of ww at retained positions.✦ For a nonnegative integer MM, the complete trace space 𝒯M\mathcal T_M is the set of binary traces of length at most MM, and the complete trace law 𝖳ρ(w)\mathsf T_\rho(w) of a binary word ww is the probability law obtained by applying the retained subsequence map to its deletion mask law, as in (4); a bounded trace of bound MM is an element of 𝒯M\mathcal T_M. 𝒯M=⋃ℓ=0M{0,1}ℓ,𝖳ρ(w)=(a↦tr⁡(w,a))*𝖬ρ,|w|,M≥|w|.\mathcal T_M=\bigcup_{\ell=0}^{M}\{0,1\}^{\ell}, \qquad \mathsf T_\rho(w) =\bigl(a\mapsto\operatorname{tr}(w,a)\bigr)_*\mathsf M_{\rho,|w|}, \qquad M\ge |w|.(4)

Trace Comparison

For a binary word ww, a real parameter ρ\rho, and a real function FF on binary traces, the complete trace expectation ℰρ(w,F)\mathcal E_\rho(w,F) is the real number determined recursively by (5). Here ⌀\varnothing is the empty word, and btbt prefixes the bit bb to the list tt. ℰρ(⌀,F)=F(⌀),ℰρ(bw,F)=ρℰρ(w,F)+(1−ρ)ℰρ(w,t↦F(bt)).\begin{aligned} \mathcal E_\rho(\varnothing,F)&=F(\varnothing),\\ \mathcal E_\rho(bw,F) &=\rho\mathcal E_\rho(w,F) +(1-\rho)\mathcal E_\rho(w,t\mapsto F(bt)). \end{aligned}(5)✦ The overlap ov⁡(P,Q)\operatorname{ov}(P,Q) of two finite probability laws P,QP,Q on the same outcome set is the real number in (6), where TV⁡(P,Q)\operatorname{TV}(P,Q) denotes their total variation distance. ov⁡(P,Q)=∑amin⁡{P(a),Q(a)}=1−TV⁡(P,Q),TV⁡(P,Q)=12∑a|P(a)−Q(a)|.\operatorname{ov}(P,Q)=\sum_a\min\{P(a),Q(a)\} =1-\operatorname{TV}(P,Q), \qquad \operatorname{TV}(P,Q)=\frac12\sum_a|P(a)-Q(a)|.(6)✦ The complete trace overlap ov⁡ρ(u,v)\operatorname{ov}_\rho(u,v) of binary words u,vu,v is ov⁡(𝖳ρ(u),𝖳ρ(v))\operatorname{ov}(\mathsf T_\rho(u),\mathsf T_\rho(v)), with both laws on 𝒯max⁡{|u|,|v|}\mathcal T_{\max\{|u|,|v|\}}. For a word ww and a nonnegative integer mm, the repeated word wmw^m is the concatenation of mm copies of ww.✦

The Source Parameters

Let B,DB,D be nonnegative integers and nn a real size parameter. For a zero-based nonnegative integer block index jj, the warmup block count hBh_B and source block dimension bj+1b_{j+1} are the nonnegative integers in (7). The zero-based block index jj corresponds to block number j+1j+1. hB=5⋅2B,bj+1={2,j<hB,B,j≥hB.h_B=5\cdot2^B, \qquad b_{j+1}=\begin{cases}2,&j<h_B,\\B,&j\ge h_B.\end{cases}(7) For a nonnegative integer block dimension bb and a nonnegative integer number of blocks tt, the block gain g(b)g(b) and total score exponent dtd_t are the real numbers in (8). g(b)=b−14−120,dt=115+∑j=0t−1g(bj+1).g(b)=\frac{b-1}{4}-\frac1{20}, \qquad d_t=\frac{11}{5}+\sum_{j=0}^{t-1}g(b_{j+1}).(8) For a nonnegative integer level index ii, a nonnegative integer block dimension bb, and a zero-based nonnegative integer scale index ss, the scale slack ε\varepsilon, scale exponent α(b,s;ε)\alpha(b,s;\varepsilon), scale exponent product AiA_i, and backwards target scale NiN_i are the real numbers defined in (9). ε=124B+100(D+1),α(b,s;ε)=(1+ε)2s2b−ε,Ai=∏j∈[i,D)∩ℕα(bj+1,0;ε),Ni=nAi.\begin{gathered} \varepsilon=\frac{1}{2^{4B+100}(D+1)}, \qquad \alpha(b,s;\varepsilon)=(1+\varepsilon)\frac{2^s}{2^b}-\varepsilon,\\ A_i=\prod_{j\in[i,D)\cap\mathbb N}\alpha(b_{j+1},0;\varepsilon), \qquad N_i=n^{A_i}. \end{gathered}(9) The error allowance Δ\Delta and half moment order kik_i at level ii are respectively the real number and nonnegative integer in (10), with even score exponent ri=2kir_i=2k_i. The notation ⌈⋅⌉+\lceil\cdot\rceil_+ denotes the ceiling truncated below at zero; parameter quotients with denominator zero have value zero. Δ=n−100(dD+B+1),ki=⌈108210B(dD+B+1)log⁡nlog⁡Ni⌉+.\Delta=n^{-100(d_D+B+1)}, \qquad k_i=\left\lceil 10^8\,2^{10B}(d_D+B+1)\frac{\log n}{\log N_i} \right\rceil_+.(10)

For a real parameter ρ\rho, the rank Schur constant κR\kappa_R, primitive period constant κP\kappa_P, initial overlap lower bound ω0(ρ)\omega_0(\rho), and source overlap constant C0(ρ)C_0(\rho) are the real numbers defined in (11). κR=8847362e1−e−1/1024,κP=36κR2,ω0(ρ)=exp⁡(−(32+3κP)/ρ3)1536,C0(ρ)=240ρω0(ρ).\begin{gathered} \kappa_R=884736\,\frac{2e}{1-e^{-1/1024}}, \qquad \kappa_P=36\kappa_R^2,\\ \omega_0(\rho)=\frac{\exp\bigl(-(32+3\kappa_P)/\rho^3\bigr)}{1536}, \qquad C_0(\rho)=\frac{2^{40}}{\rho\omega_0(\rho)}. \end{gathered}(11)

The Definition

Definition 1 (Level pairs). Let ρ∈[0,1]\rho\in[0,1]. For a finite probability law PP on Ω\Omega, a decoder 𝒟:Ω→𝒯\mathcal D:\Omega\to\mathcal T into the set 𝒯\mathcal T of all binary traces, a word ww, and E∈ℝE\in\mathbb R, trace approximation Approx⁡ρ(P,𝒟,w;E)\operatorname{Approx}_\rho(P,\mathcal D,w;E) is the condition (12). |𝔼P[a↦F(𝒟(a))]−ℰρ(w,F)|≤Efor every F:𝒯→[0,1].\left|\mathbb E_P\bigl[a\mapsto F(\mathcal D(a))\bigr] -\mathcal E_\rho(w,F)\right|\le E \qquad\text{for every }F:\mathcal T\to[0,1].(12)✦ For a finite probability law PP on Ω\Omega, a real function ff on Ω\Omega, and a nonnegative integer kk, the even moment quantity Mk(P,f)M_k(P,f) is the real number in (13); for k≥1k\ge1 it is the squared L2k(P)L^{2k}(P) norm, weighted by the probability law PP. Mk(P,f)={(∑a∈ΩP(a)|f(a)|2k)1/k,k≥1,1,k=0.M_k(P,f)= \begin{cases} \displaystyle\left(\sum_{a\in\Omega}P(a)|f(a)|^{2k}\right)^{1/k},&k\ge1,\\ 1,&k=0. \end{cases}(13)✦

Let N,Δ,d,ω,AN,\Delta,d,\omega,A be real parameters, and let i,ki,k be nonnegative integers. A concrete level pair in ℒ(ρ;N,Δ,d,ω,A;i,k)\mathcal L(\rho;N,\Delta,d,\omega,A;i,k) consists of binary words x,yx,y, finite probability laws P,QP,Q on a common finite set Ω\Omega, a common decoder 𝒟:Ω→𝒯\mathcal D:\Omega\to\mathcal T, a real error EE, a real score s:Ω→ℝs:\Omega\to\mathbb R, and an integer repetition count mm satisfying (14), where ℓ\ell is the common word length. |x|=|y|=ℓ,x≠y,N/2≤ℓ≤N,E≥0,E/ℓ≤(i+1)Δ,Approx⁡ρ(P,𝒟,x;E),Approx⁡ρ(Q,𝒟,y;E),Q(a)=P(a)(1+s(a))(a∈Ω),Mk(P,s)≤N−d,m∈ℕ,ℓ≤m≤Aℓ,ov⁡ρ(xm,xm+1)≥ω.\begin{gathered} |x|=|y|=\ell,\qquad x\ne y,\qquad N/2\le\ell\le N,\\ E\ge0,\qquad E/\ell\le(i+1)\Delta,\\ \operatorname{Approx}_\rho(P,\mathcal D,x;E),\qquad \operatorname{Approx}_\rho(Q,\mathcal D,y;E),\\ Q(a)=P(a)(1+s(a))\quad(a\in\Omega),\qquad M_k(P,s)\le N^{-d},\\ m\in\mathbb N,\qquad\ell\le m\le A\ell,\qquad \operatorname{ov}_\rho(x^m,x^{m+1})\ge\omega. \end{gathered}(14)✦ The class 𝒮B,D,n,ρ,i\mathcal S_{B,D,n,\rho,i} of source level pairs at level ii is the class in (15), with parameters from (7) through (11). 𝒮B,D,n,ρ,i=ℒ(ρ;Ni,Δ,di,ω0(ρ),C0(ρ)2Bi+2;i,ki).\mathcal S_{B,D,n,\rho,i} =\mathcal L\bigl(\rho;N_i,\Delta,d_i,\omega_0(\rho), C_0(\rho)^{2Bi+2};i,k_i\bigr).(15)✦

In the paper, the result reads: choose C>2C>2 and 0<ω<1/80<\omega<1/8, depending only on δ\delta, with log⁡C=O(Λ)\log C=O(\Lambda) and log⁡(ω−1)=O(Λ)\log(\omega^{-1})=O(\Lambda), and MB≥0M_B\ge0, depending only on BB, using the same choices at every level; a level-ii pair consists of distinct words xi,yix_i,y_i of common length ℓi∈[Ni/2,Ni]\ell_i\in[N_i/2,N_i], auxiliary laws μi,νi\mu_i,\nu_i, and a common Markov kernel KiK_i approximating both trace laws within Ei≥0E_i\ge0 with Ei/ℓi≤(i+1)ΔE_i/\ell_i\le(i+1)\Delta, where νi≪μi\nu_i\ll\mu_i, the likelihood score dνi/dμi−1d\nu_i/d\mu_i-1 has squared Lri(μi)L^{r_i}(\mu_i) norm at most Ni−diN_i^{-d_i}, and some integer mi∈[ℓi,C2Bi+MBℓi]m_i\in[\ell_i,C^{2Bi+M_B}\ell_i] satisfies ov⁡δ(ximi,ximi+1)≥ω\operatorname{ov}_\delta(x_i^{m_i},x_i^{m_i+1})\ge\omega.

What Is Checked

The level definitions are stated for binary words and finite auxiliary laws with a deterministic decoder, at a deletion rate in [0,1][0,1]. The deletion mask weights satisfy (16). ∑aWρ,m(a)=1(ρ∈ℝ),Wρ,m(a)≥0(ρ∈[0,1]).\sum_a W_{\rho,m}(a)=1\quad(\rho\in\mathbb R), \qquad W_{\rho,m}(a)\ge0\quad(\rho\in[0,1]).(16) For every real deletion parameter, the deletion mask weights sum to one; when the deletion rate lies in [0,1][0,1], every deletion mask weight is nonnegative.