OctoInformBeta

OpenAI preprint, September 2026 · §8. Genuine traces, exact lengths, and testing

§8: Multiple gadgets and unrestricted testing: Common-reference testing and independent binary recovery with quantitative exponent margins

Exact-length gadget families bound reconstruction success.

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

Several binary choices can be placed in a word of prescribed length. A reconstruction rule receives independent complete deletion traces and may randomize over all candidate words of that length.

A binary word x∈{0,1}nx\in\{0,1\}^n has zero-based positions 0,…,n−10,\ldots,n-1. For a binary word x∈{0,1}nx\in\{0,1\}^n, a deletion mask a∈{0,1}na\in\{0,1\}^n is a binary sequence that retains position jj when aj=1a_j=1; the retained subsequence t(x,a)t(x,a) is the binary list of those retained bits in their original order. A binary trace is a finite binary list, including its surviving length.✦ The complete trace space and the deletion mask probability at requested deletion rate q∈[0,1]q\in[0,1] are given in (1); a bounded trace of bound nn belongs to this space. 𝒯≤n=⋃j=0n{0,1}j,wq(a)=∏j=0n−1{1−q,aj=1,q,aj=0.\mathcal T_{\le n}=\bigcup_{j=0}^n\{0,1\}^j, \qquad w_q(a)=\prod_{j=0}^{n-1} \begin{cases}1-q,&a_j=1,\\q,&a_j=0.\end{cases}(1)

A finite probability law PP on a finite set 𝒜\mathcal A is a mass function with P(u)≥0P(u)\ge0 and ∑uP(u)=1\sum_uP(u)=1.✦ The deletion mask law has masses wq(a)w_q(a).✦ The complete trace law Tq(x)T_q(x) of a binary word xx of length nn is the probability law on 𝒯≤n\mathcal T_{\le n} with masses given in (2). For a source list xx of length at most MM, the same law is considered on 𝒯≤M\mathcal T_{\le M}.✦ The complete trace expectation ℰq(x;F)\mathcal E_q(x;F) of a real trace test FF for a binary source word xx is its mean under the trace law Tq(x)T_q(x), given in (2). Tq(x)(t)=∑a:t(x,a)=twq(a),ℰq(x;F)=∑tTq(x)(t)F(t).T_q(x)(t)=\sum_{a:\,t(x,a)=t}w_q(a), \qquad \mathcal E_q(x;F)=\sum_tT_q(x)(t)F(t).(2)

For a finite law PP on 𝒜\mathcal A, a real function ff on 𝒜\mathcal A, and a natural sample count mm, the expectation 𝔼P[f]\mathbb E_P[f] is the mean of ff, and the product law P⊗mP^{\otimes m} is the probability law of mm independent samples; their formulas at a sample tuple z∈𝒜mz\in\mathcal A^m are given in (3), with samples indexed by the zero-based slots 0,…,m−10,\ldots,m-1. For a finite law PP on 𝒜\mathcal A and laws KuK_u on a finite set ℬ\mathcal B, indexed by u∈𝒜u\in\mathcal A, the mixture PKP K is a probability law on ℬ\mathcal B with masses given by the last formula in (3). The point mass at v∈ℬv\in\mathcal B assigns mass one to vv and zero elsewhere; for a map f:𝒜→ℬf:\mathcal A\to\mathcal B and a finite law PP on 𝒜\mathcal A, the pushforward f*Pf_*P is the probability law on ℬ\mathcal B obtained by mixing the point masses at f(u)f(u) with weights P(u)P(u). 𝔼P[f]=∑uP(u)f(u),P⊗m(z)=∏j=0m−1P(zj),(PK)(v)=∑uP(u)Ku(v).\mathbb E_P[f]=\sum_uP(u)f(u),\qquad P^{\otimes m}(z)=\prod_{j=0}^{m-1}P(z_j),\qquad (P K)(v)=\sum_uP(u)K_u(v).(3)

For finite probability laws P,QP,Q on a common finite space, their total variation distance TV⁡(P,Q)\operatorname{TV}(P,Q) and probability overlap ov⁡(P,Q)\operatorname{ov}(P,Q) are the real quantities given in (4). The complete trace overlap of two source lists uses their trace laws on the common space with bound equal to the larger source length.✦ TV⁡(P,Q)=12∑u|P(u)−Q(u)|,ov⁡(P,Q)=∑umin⁡{P(u),Q(u)}=1−TV⁡(P,Q).\operatorname{TV}(P,Q)=\frac12\sum_u|P(u)-Q(u)|, \qquad \operatorname{ov}(P,Q)=\sum_u\min\{P(u),Q(u)\} =1-\operatorname{TV}(P,Q).(4)

A randomized reconstruction estimator AA for binary words of length nn, using mm traces, is a rule that assigns every trace tuple zz a probability distribution A(z,⋅)A(z,\cdot) over {0,1}n\{0,1\}^n.✦ The reconstruction success Succ⁡q(A,x)\operatorname{Succ}_q(A,x) of a randomized reconstruction estimator AA on a binary word xx of length nn is the probability of reporting xx, given in (5), where each aja_j is a deletion mask of length nn. For a word length nn, a requested deletion rate qq, and a target success probability ss, a sufficient sample budget for (n,q,s)(n,q,s) is a natural number mm for which some randomized reconstruction estimator using mm traces has success at least ss on every word of length nn.✦ Succ⁡q(A,x)=∑a0,…,am−1(∏j=0m−1wq(aj))A((t(x,aj))j=0m−1,x).\operatorname{Succ}_q(A,x)= \sum_{a_0,\ldots,a_{m-1}} \left(\prod_{j=0}^{m-1}w_q(a_j)\right) A\bigl((t(x,a_j))_{j=0}^{m-1},x\bigr).(5)✦

Gadget and Exponent Parameters

Write ρ\rho for a working deletion rate. The parametrization δ=min⁡(q,1/2)\delta=\min(q,1/2), Λ=δ−3\Lambda=\delta^{-3} for q>0q>0 uses ρ=δ\rho=\delta; the construction theorems call their working rate qq. An approximate trace simulation of a source list xx at rate ρ\rho, with error EE, is a finite law PP on Ω\Omega and a decoder ψ\psi into binary lists satisfying (6) for every trace test FF valued in [0,1][0,1]. |𝔼P[F∘ψ]−ℰρ(x;F)|≤E.\left|\mathbb E_P[F\circ\psi]-\mathcal E_\rho(x;F)\right|\le E.(6)✦

For a finite probability law PP on Ω\Omega, a real function hh on Ω\Omega, and a natural half-order kk, the squared even moment ∥h∥L2k(P)2\|h\|_{L^{2k}(P)}^2 is the probability-weighted quantity in (7). At a zero-based level ii, the corresponding even score exponent is ri=2kr_i=2k. ∥h∥L2k(P)2=(𝔼P[|h|2k])1/k.\|h\|_{L^{2k}(P)}^2 =\left(\mathbb E_P[|h|^{2k}]\right)^{1/k}.(7)✦

A concrete level pair UU at rate ρ∈[0,1]\rho\in[0,1], scale NN, allowance Δ\Delta, decay exponent dd, overlap threshold ω\omega, count multiplier KK, zero-based level ii, and half-order k≥1k\ge1 consists of distinct equal-length binary lists x,yx,y, finite laws P,QP,Q on Ω\Omega, and a common decoder ψ\psi giving approximate trace simulations of x,yx,y with the same error E≥0E\ge0. The likelihood score hh of a concrete level pair UU with finite laws P,QP,Q on Ω\Omega is a real function on Ω\Omega that, together with the natural repetition count ν\nu of UU, satisfies (8), where L=|x|=|y|L=|x|=|y| and xνx^\nu is the concatenation of ν\nu copies of xx. N/2≤L≤N,E/L≤(i+1)Δ,Q(u)=P(u)(1+h(u))(u∈Ω),∥h∥L2k(P)2≤N−d,L≤ν≤KL,ω≤ov⁡(Tρ(xν),Tρ(xν+1)).\begin{gathered} N/2\le L\le N,\qquad E/L\le(i+1)\Delta,\qquad Q(u)=P(u)(1+h(u))\quad(u\in\Omega),\\ \|h\|_{L^{2k}(P)}^2\le N^{-d},\qquad L\le\nu\le KL,\qquad \omega\le\operatorname{ov}\bigl(T_\rho(x^\nu),T_\rho(x^{\nu+1})\bigr). \end{gathered}(8)

For a natural block dimension bb, the block gain G(b)G(b) is given in (9); for a natural block dimension BB and real parameters ζ,H\zeta,H, that display also defines the warmup block count wBw_B, induction depth DBD_B, and final exponent slope σB\sigma_B. Here ⌊⋅⌋+\lfloor\cdot\rfloor_+ is the floor truncated below at zero, and log\log is the natural logarithm. G(b)=b−14−120,wB=5⋅2B,DB(ζ,H)=⌊(1−ζ)log⁡HBlog⁡2⌋+,σB(ζ)=(1−ζ)G(B)Blog⁡2.\begin{gathered} G(b)=\frac{b-1}{4}-\frac1{20},\qquad w_B=5\cdot2^B,\\ D_B(\zeta,H)= \left\lfloor\frac{(1-\zeta)\log H}{B\log2}\right\rfloor_+, \qquad \sigma_B(\zeta)=\frac{(1-\zeta)G(B)}{B\log2}. \end{gathered}(9) The total score exponent TB(D)T_B(D) at natural depth DD is (10), with zero-based block indices jj. TB(D)=115+∑j=0D−1G(bj),bj={2,j<wB,B,j≥wB.T_B(D)=\frac{11}{5}+\sum_{j=0}^{D-1}G(b_j), \qquad b_j=\begin{cases}2,&j<w_B,\\ B,&j\ge w_B.\end{cases}(10)✦

The Claim

Theorem 1. Let q∈[0,1]q\in[0,1] be the requested deletion rate.

Let UU be a concrete level pair as above at a working rate ρ∈[0,q]\rho\in[0,q] with ρ<1\rho<1. For natural g,ng,n satisfying gN≤ngN\le n, there is an injective family W:{0,1}g→{0,1}nW:\{0,1\}^g\to\{0,1\}^n for which (11) holds for every θ∈{0,1}g\theta\in\{0,1\}^g and natural mm; 0g0^g denotes the all-zero choice. TV⁡(Tq(W(θ))⊗m,Tq(W(0g))⊗m)≤mgN−d+2mgE.\operatorname{TV}\!\left(T_q(W(\theta))^{\otimes m}, T_q(W(0^g))^{\otimes m}\right) \le\sqrt{mgN^{-d}}+2mgE.(11)✦

Suppose W:{0,1}g→{0,1}nW:\{0,1\}^g\to\{0,1\}^n is an injective family whose mm-sample trace law at every θ\theta is within ε\varepsilon in total variation of its law at 0g0^g. If mm is a sufficient sample budget for (n,q,s)(n,q,s), then (12) holds. s≤2−g+ε.s\le2^{-g}+\varepsilon.(12)✦

Let P,QP,Q be finite laws on 𝒜\mathcal A, and let A(z,⋅)A(z,\cdot) be a probability distribution on {0,1}g\{0,1\}^g for every z∈𝒜gz\in\mathcal A^g. Set P1=PP_1=P and P0=QP_0=Q. Independent binary recovery satisfies (13). 2−g∑θ∈{0,1}g∑z∈𝒜g(∏j=0g−1Pθj(zj))A(z,θ)≤(1+TV⁡(P,Q)2)g.2^{-g}\sum_{\theta\in\{0,1\}^g}\sum_{z\in\mathcal A^g} \left(\prod_{j=0}^{g-1}P_{\theta_j}(z_j)\right)A(z,\theta) \le\left(\frac{1+\operatorname{TV}(P,Q)}2\right)^g.(13)✦

Suppose the real sequences Nℓ,HℓN_\ell,H_\ell tend to infinity and the sequence dℓd_\ell is real. Suppose c<αc<\alpha, a>0a>0, and eventually dℓ≥αlog⁡Hℓ−K0d_\ell\ge\alpha\log H_\ell-K_0, for a fixed real K0K_0. Then (14) holds for all sufficiently large ℓ\ell. Nℓclog⁡Hℓ≤aNℓdℓ.N_\ell^{\,c\log H_\ell}\le aN_\ell^{\,d_\ell}.(14)✦

Let B≥2B\ge2 be natural and ζ,H\zeta,H real, with wB≤DB(ζ,H)w_B\le D_B(\zeta,H). The score exponent satisfies (15). σB(ζ)log⁡H−(G(B)+wBG(B))<TB(DB(ζ,H)).\sigma_B(\zeta)\log H-\bigl(G(B)+w_BG(B)\bigr) <T_B\bigl(D_B(\zeta,H)\bigr).(15)✦

In the paper, the result reads: choose a fixed number gg of independent hard gadgets with (2/3)g<s(2/3)^g<s, construct them at length ⌊n/g⌋\lfloor n/g\rfloor using the same requested qq, use stronger separated observations and posterior factorization to multiply optimal successes, and use a strict exponent margin to exclude every budget up to nclog⁡(q3log⁡n)n^{c\log(q^3\log n)}.

What Is Checked

The statements concern finite mask and complete trace laws, concrete level pairs with decoded finite experiments, and arbitrary randomized reporting rules, at natural sample counts and exact word lengths.

For q∈[0,1]q\in[0,1], the mask probabilities in (1) are nonnegative✦; their sum over all masks is one for every real qq.✦