OctoInformBeta

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

Lemma 2.1: Lower bounds and exponential absorption along the joint asymptotic regime

Target scales absorb deletion losses uniformly.

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 recursive trace reconstruction construction assigns a target size to each block level, starting from a problem size nn. The relevant budget is the logarithm of that target size multiplied by the scale slack. Deletion losses depend on the working deletion rate and on the number of block levels.

For a requested deletion probability q∈(0,1)q\in(0,1), each bit survives with probability 1−q1-q. The working deletion rate is δ=min⁡{q,1/2}\delta=\min\{q,1/2\}, and its loss parameter is Λ=δ−3\Lambda=\delta^{-3}. The construction theorems call their working rate qq. Write Hdel=δ3log⁡nH_{\mathrm{del}}=\delta^3\log n for the deletion parameter.

Fix an integer block size B≥2B\geq2 and a real parameter ζ\zeta. The warmup block count WBW_B and the block dimension bi+1b_{i+1} at zero-based block index ii are defined by (1); index ii corresponds to block number i+1i+1 in the paper. WB=5⋅2B,bi+1={2,0≤i<WB,B,i≥WB.W_B=5\cdot2^B, \qquad b_{i+1}= \begin{cases} 2,&0\leq i<W_B,\\ B,&i\geq W_B. \end{cases}(1) For a block dimension b∈ℕb\in\mathbb N, a zero-based scale index j∈ℕj\in\mathbb N, and real slack uu, the scale exponent ab,j(u)a_{b,j}(u) is the real number in (2). ab,j(u)=(1+u)2j2b−u.a_{b,j}(u)=(1+u)\frac{2^j}{2^b}-u.(2)✦

For a positive real parameter HH, the induction depth D(H)D(H) is the floor truncated below at zero, and the scale slack ε(H)\varepsilon(H) is the reciprocal prescribed in (3). D(H)=max⁡{0,⌊(1−ζ)log⁡HBlog⁡2⌋},ε(H)=124B+100(D(H)+1).D(H)=\max\left\{0, \left\lfloor\frac{(1-\zeta)\log H}{B\log2}\right\rfloor\right\}, \qquad \varepsilon(H)=\frac{1}{2^{4B+100}(D(H)+1)}.(3) The scale exponent product Pi(H)P_i(H) is the product of the scale-zero exponents over block indices in [i,D(H))[i,D(H)).✦ The backwards target scale Ni(n,H)N_i(n,H) for problem size nn is the real power defined together with that product in (4). Pi(H)=∏i≤j<D(H)abj+1,0(ε(H)),Ni(n,H)=nPi(H).P_i(H)=\prod_{i\leq j<D(H)}a_{b_{j+1},0}\bigl(\varepsilon(H)\bigr), \qquad N_i(n,H)=n^{P_i(H)}.(4) The empty product is 11. For fixed parameters, abbreviate D=D(H)D=D(H), ε=ε(H)\varepsilon=\varepsilon(H) and Ni=Ni(n,H)N_i=N_i(n,H); along parameter sequences, write Dk=D(Hk)D_k=D(H_k), εk=ε(Hk)\varepsilon_k=\varepsilon(H_k) and Ni,k=Ni(nk,Hk)N_{i,k}=N_i(n_k,H_k).

The Claim

Theorem 1. Let B≥2B\geq2 be an integer, let ζ≤1\zeta\leq1, and suppose that H≥1H\geq1 and n>1n>1. Every nonnegative integer index ii satisfies the logarithmic bound (5). log⁡n2H1−ζ≤log⁡Ni.\frac{\log n}{2H^{1-\zeta}}\leq\log N_i.(5)✦ If Λ>0\Lambda>0 and log⁡n=ΛH\log n=\Lambda H, the scale margin satisfies (6) for every such ii. ΛHζ2⋅24B+100(D+1)≤εlog⁡Ni.\frac{\Lambda H^\zeta}{2\cdot2^{4B+100}(D+1)} \leq\varepsilon\log N_i.(6)✦

Suppose now that 0<ζ<10<\zeta<1, and fix a nonnegative integer hh. Let (nk)(n_k) be a real sequence tending to infinity, and let (tk)(t_k) be any positive real sequence such that Hk=tk3log⁡nkH_k=t_k^3\log n_k tends to infinity. For every sequence (ik)(i_k) of nonnegative integer indices, the deletion loss has the limit (7). (Dk+1)htk−3εklog⁡Nik,k→0(k→∞).\frac{(D_k+1)^h t_k^{-3}} {\varepsilon_k\log N_{i_k,k}} \longrightarrow0 \qquad(k\longrightarrow\infty).(7)✦

Let C≥0C\geq0 and η>0\eta>0. For real sequences nk→∞n_k\to\infty and Hk→∞H_k\to\infty, and positive real numbers Λk\Lambda_k satisfying log⁡nk=ΛkHk\log n_k=\Lambda_kH_k for every kk, the bound (8) holds for all sufficiently large kk, simultaneously for every nonnegative integer ii. exp⁡(C(Dk+1)hΛk)≤Ni,kηεk.\exp\!\bigl(C(D_k+1)^h\Lambda_k\bigr) \leq N_{i,k}^{\eta\varepsilon_k}.(8)✦

In the paper, the result reads: for the preceding deletion parameters, with dDd_D denoting the terminal dimension, log⁡N0≳B(log⁡n)2−BD\log N_0\gtrsim_B(\log n)2^{-BD} and log⁡N0≳B(log⁡n)Hdel−(1−ζ)≳BΛHdelζ\log N_0\gtrsim_B(\log n)H_{\mathrm{del}}^{-(1-\zeta)}\gtrsim_B\Lambda H_{\mathrm{del}}^\zeta, while εlog⁡N0≳B(log⁡n)ζ/(1+log⁡log⁡n)\varepsilon\log N_0\gtrsim_B(\log n)^\zeta/(1+\log\log n) dominates log⁡log⁡n+log⁡(dD+B+1)\log\log n+\log(d_D+B+1), and, for every fixed nonnegative integer hh, uniformly for 0≤i≤D0\leq i\leq D, (D+1)hΛ=o(εlog⁡N0)(D+1)^h\Lambda=o(\varepsilon\log N_0) and exp⁡(OB((D+1)hΛ))=Nio(ε)\exp\!\bigl(O_B((D+1)^h\Lambda)\bigr)=N_i^{o(\varepsilon)} in the joint asymptotic regime.

What Is Checked

The claims concern the block dimensions and scale exponents in (1) and (2), the deterministic depth and slack in (3), and the backwards target scales in (4), with the stated real parameter bounds and sequences indexed by nonnegative integers.