OctoInformBeta

OpenAI preprint, September 2026 · §5. One amplification block: words and overlap

§5: Nested complementary words and windows: Prouhet cancellation and score exponents fix the parameters of one amplification block

Nested words and rounded reconstruction windows.

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

Nested complementary binary words give the two inputs for one amplification block in trace reconstruction. A Prouhet motif selects old atoms within each new word, while a rounded window schedule assigns an integer width to each nesting level.

Let BB and DD be natural numbers, denoting the block size and depth. The block gain g(b)g(b) is the contribution assigned to a block of dimension bb: g(b)=b−14−120.g(b)=\frac{b-1}{4}-\frac{1}{20}.(1)✦ The warmup count w(B)w(B) determines the dimensions used in the score sum: w(B)=5⋅2B,bi+1={2,0≤i<w(B),B,i≥w(B).w(B)=5\cdot 2^B, \qquad b_{i+1}=\begin{cases} 2,&0\le i<w(B),\\ B,&i\ge w(B). \end{cases}(2)✦ Here the block index ii starts at zero, so its dimension is bi+1b_{i+1}. The total score exponent dDd_D sums the gains in (1) using the dimensions in (2): dD=115+∑i=0D−1g(bi+1).d_D=\frac{11}{5}+\sum_{i=0}^{D-1}g(b_{i+1}).(3)✦ The source slack ε\varepsilon associated with B,DB,D is ε=124B+100(D+1).\varepsilon=\frac{1}{2^{4B+100}(D+1)}.(4)✦

For a natural dimension bb, a natural scale index jj, and a real slack η\eta, the scale exponent aj(b,η)a_j(b,\eta) and window exponent κj(b,η)\kappa_j(b,\eta) are aj(b,η)=(1+η)2j2b−η,κj(b,η)=amax⁡{j−1,0}(b,η)−3(2j−1)η.\begin{aligned} a_j(b,\eta)&=(1+\eta)\frac{2^j}{2^b}-\eta,\\ \kappa_j(b,\eta)&=a_{\max\{j-1,0\}}(b,\eta) -3(2^j-1)\eta. \end{aligned}(5) The scale index in (5) starts at zero; the window indexed by j=0,1,…j=0,1,\ldots belongs to level j+1j+1.

For a pair V=(V+,V−)V=(V^+,V^-) of finite binary words, the complementary-word concatenation 𝒞p,h,ℓ,σ(V)\mathcal C_{p,h,\ell,\sigma}(V) is the pair of binary words obtained from VV using pp slots, motif placement hh, and a Boolean motif σ\sigma of length ℓ\ell. For a natural number ss, write σs\sigma_s for the Boolean Prouhet motif of length 2s2^s. Slot and nesting indices start at zero. For real tt, write ⌊t⌋+=max⁡{0,⌊t⌋}\lfloor t\rfloor_+=\max\{0,\lfloor t\rfloor\} and ⌈t⌉+=max⁡{0,⌈t⌉}\lceil t\rceil_+=\max\{0,\lceil t\rceil\}.

The Definition

Definition 1. Let A=(A+,A−)A=(A^+,A^-) be a pair of finite binary atoms, let ss be a natural number, and let (pj)j≥0(p_j)_{j\ge0} be a sequence of natural trial counts. The recursive source block words Uj=(Uj+,Uj−)U_j=(U_j^+,U_j^-) are defined by (6): U0=A,Uj+1=𝒞pj,max⁡{⌊pj/2⌋−1,0},2s,σs(Uj).\begin{aligned} U_0&=A,\\ U_{j+1}&=\mathcal C_{p_j,\,\max\{\lfloor p_j/2\rfloor-1,0\},\, 2^s,\,\sigma_s}(U_j). \end{aligned}(6)✦ For natural block size BB and depth DD, the source degree cutoff r*r_* is defined by (7), and the source cancellation order s*s_* is defined by (8), with dDd_D and ε\varepsilon as above: r*=210B+40.r_*=2^{10B+40}.(7)✦ s*=⌈100(dD+r*+B+10)ε⌉+.s_*=\left\lceil \frac{100(d_D+r_*+B+10)}{\varepsilon} \right\rceil_+.(8)✦ For a real scale NN, natural dimension bb, real slack η\eta, and zero-based window index jj, the window width Tj+1(N,b,η)T_{j+1}(N,b,\eta) at level j+1j+1 is the integer defined by (9), using (5): Tj+1(N,b,η)=4⌊Nκj+1(b,η)4⌋+.T_{j+1}(N,b,\eta) =4\left\lfloor\frac{N^{\kappa_{j+1}(b,\eta)}}{4}\right\rfloor_+.(9)✦

In the paper, the result reads: put r*=210B+40r_*=2^{10B+40}, s*=⌈100(dD+r*+B+10)/ε⌉s_*=\lceil100(d_D+r_*+B+10)/\varepsilon\rceil, and L=2s*L=2^{s_*}, and take the signed motif with polynomial ∑a=0L−1σaza=∏v=0s*−1(1−z2v)\sum_{a=0}^{L-1}\sigma_a z^a=\prod_{v=0}^{s_*-1}(1-z^{2^v}); starting with U0+=xU_0^+=x and U0−=yU_0^-=y, for each sign τ\tau the word UjτU_j^\tau concatenates PjP_j old atoms, uses the plus atom outside the motif and type τσa\tau\sigma_a at labels ⌊Pj/2⌋+a\lfloor P_j/2\rfloor+a, and has length Sj=PjSj−1S_j=P_jS_{j-1}; the local exponents are aj=(1+ε)2j−b−εa_j=(1+\varepsilon)2^{j-b}-\varepsilon and κj=aj−1−3(2j−1)ε\kappa_j=a_{j-1}-3(2^j-1)\varepsilon, with windows Tj=4⌊Nκj/4⌋T_j=4\lfloor N^{\kappa_j}/4\rfloor; interior paired trial counts are even, while the root count JJ may be odd.

What Is Checked

These definitions are stated over pairs of finite binary words, natural trial counts and nesting parameters, natural block size and depth, and real scale and slack parameters.