OctoInformBeta

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

Lemma 4.3: An explicit squared ℓ2\ell^2 estimate for central periodic tags, with dependence on difference order and coarse gaps

Bounding mixed positional differences of rank kernels.

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

In a periodic source string, tagged slots can appear at different observed ranks after deletion. The quantity of interest is the squared norm of a mixed positional difference of their conditional rank probabilities, summed over increasing observed-rank tuples. 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\}, denoted qq in the construction theorems. All slot, rank, tag and period indices are zero-based, and [n]0={0,…,n−1}[n]_0=\{0,\ldots,n-1\}.

A finite probability law μ\mu on a finite set AA is a real mass function with nonnegative masses summing to one.✦ A fixed-size subset SS of size ℓ\ell of AA is an ℓ\ell-element subset of AA.✦ For ℓ≤|A|\ell\le |A|, the uniform fixed-size subset law μA,ℓ\mu_{A,\ell} assigns each such subset the mass in (1); write 𝒮n,ℓ\mathcal S_{n,\ell} for these subsets and μn,ℓ\mu_{n,\ell} for this law when A=[n]0A=[n]_0. μA,ℓ(S)=(|A|ℓ)−1(S⊆A,|S|=ℓ).\mu_{A,\ell}(S)=\binom{|A|}{\ell}^{-1} \qquad (S\subseteq A,\ |S|=\ell).(1)✦

For S∈𝒮n,ℓS\in\mathcal S_{n,\ell} and v∈[ℓ]0v\in[\ell]_0, the slot at observed rank vv is the entry sS(v)s_S(v) of the increasing enumeration of SS.✦ Given tagged slots p:[r]0→[n]0p:[r]_0\to[n]_0 and requested ranks v:[r]0→[ℓ]0v:[r]_0\to[\ell]_0, the tagged rank event Ep,vE_{p,v} is the event in (2), and the conditional subset rank kernel Wp(v)W_p(v) is its probability under μn,ℓ\mu_{n,\ell}. Ep,v={S∈𝒮n,ℓ:sS(vh)=ph for every h∈[r]0},Wp(v)=μn,ℓ(Ep,v).E_{p,v}=\{S\in\mathcal S_{n,\ell}:s_S(v_h)=p_h\text{ for every }h\in[r]_0\}, \qquad W_p(v)=\mu_{n,\ell}(E_{p,v}).(2)

An increasing rank tuple v∈ℐr(ℓ)v\in\mathcal I_r(\ell) is a map satisfying (3); all ℓ2\ell^2 norms here use counting measure on these tuples. ℐr(n)={v:[r]0→[n]0:v0<⋯<vr−1}.\mathcal I_r(n)= \{v:[r]_0\to[n]_0:v_0<\cdots<v_{r-1}\}.(3)✦

For uu periods of length mm with offsets ot∈[m]0o_t\in[m]_0, the period defect slot π(t)\pi(t) and the tags selected by j∈ℐr(u)j\in\mathcal I_r(u) are given in (4); WjW_j denotes their periodic rank kernel. π(t)=mt+ot,ph=π(jh),Wj=Wp.\pi(t)=mt+o_t,\qquad p_h=\pi(j_h),\qquad W_j=W_p.(4)

The tuple gap lower and upper bounds Li(p),Ui(p)L_i(p),U_i(p) of a tuple p:[r]0→[n]0p:[r]_0\to[n]_0 are the endpoint sequences in (5), and its open tuple gap gi(p)g_i(p) is their nonnegative difference. For increasing pp, these gaps count the untagged slots outside and between consecutive tags. Li(p)={0,i=0,pi−1+1,1≤i≤r,Ui(p)={pi,0≤i<r,n,i=r,gi(p)=max⁡{Ui(p)−Li(p),0},0≤i≤r.\begin{aligned} L_i(p)&=\begin{cases}0,&i=0,\\p_{i-1}+1,&1\le i\le r,\end{cases} &U_i(p)&=\begin{cases}p_i,&0\le i<r,\\n,&i=r,\end{cases}\\ g_i(p)&=\max\{U_i(p)-L_i(p),0\},&&0\le i\le r. \end{aligned}(5)

The doubled coarse period gap ci=2γic_i=2\gamma_i of an increasing period tuple jj is the natural integer in (6). ci=2γi=2gi(j)+{1,i=0 or i=r,2,0<i<r.c_i=2\gamma_i=2g_i(j)+ \begin{cases}1,&i=0\text{ or }i=r,\\2,&0<i<r.\end{cases}(6)✦

A tuple of separated interior tags p:[r]0→[n]0p:[r]_0\to[n]_0 is a tuple satisfying (7). 1≤ph,ph+1<n(h∈[r]0),pi+3≤pj(0≤i<j<r).1\le p_h,\qquad p_h+1<n\quad(h\in[r]_0),\qquad p_i+3\le p_j\quad(0\le i<j<r).(7)✦

A positional difference choice κ\kappa is the unchanged operator id\mathrm{id}, the centered first difference DD, or the centered second difference VV.✦ Its positional difference coefficients ωκ\omega_\kappa and order are given in (8); coefficient indices a=0,1,2a=0,1,2 correspond to displacements −1,0,1-1,0,1. ωid=(0,1,0),ord⁡(id)=0,ωD=(−1/2,0,1/2),ord⁡(D)=1,ωV=(1/2,−1,1/2),ord⁡(V)=2.\begin{aligned} \omega_{\mathrm{id}}&=(0,1,0),&\operatorname{ord}(\mathrm{id})&=0,\\ \omega_D&=(-1/2,0,1/2),&\operatorname{ord}(D)&=1,\\ \omega_V&=(1/2,-1,1/2),&\operatorname{ord}(V)&=2. \end{aligned}(8)

For separated interior tags pp and displacement assignments a∈{0,1,2}ra\in\{0,1,2\}^r, the displaced tag tuple pap^a and the mixed positional rank difference TκWpT_\kappa W_p are defined by (9), with one choice κh\kappa_h at each tag and total difference order dd. pha=ph+ah−1,d=∑h=0r−1ord⁡(κh),(TκWp)(v)=∑a∈{0,1,2}r(∏h=0r−1ωκh(ah))Wpa(v).\begin{aligned} p_h^a&=p_h+a_h-1,\qquad d=\sum_{h=0}^{r-1}\operatorname{ord}(\kappa_h),\\ (T_\kappa W_p)(v)&= \sum_{a\in\{0,1,2\}^r} \left(\prod_{h=0}^{r-1}\omega_{\kappa_h}(a_h)\right)W_{p^a}(v). \end{aligned}(9)

The Claim

For s≥0s\ge0 and θ∈(0,1)\theta\in(0,1), the length difference smoothing constant Cs(θ)C_s(\theta) is defined in (10); the period rank difference prefactor Au,m,r,d(θ)A_{u,m,r,d}(\theta) is the accompanying expression. Cs(θ)=2s+1θ(1−θ),Au,m,r,d(θ)=144um22rCd(θ)2d+r+2(m/4)dum/(2(r+1))(m/4)r+1.\begin{aligned} C_s(\theta)&=2\sqrt{\frac{s+1}{\theta(1-\theta)}},\\ A_{u,m,r,d}(\theta)&= \frac{144um\,2^{2r}C_d(\theta)^{2d+r+2}} {(m/4)^d\sqrt{um/(2(r+1))}\,\bigl(\sqrt{m/4}\bigr)^{r+1}}. \end{aligned}(10)

Theorem 1. Let u,m,ℓ,ru,m,\ell,r be nonnegative integers with m≥32m\ge32, r≥1r\ge1 and ℓ≤um\ell\le um. Suppose the offsets satisfy |ot−m/2|≤3|o_t-m/2|\le3 for every period tt and |ot−os|≤2|o_t-o_s|\le2 for every pair of periods. Let j∈ℐr(u)j\in\mathcal I_r(u) select separated interior tags ph=mjh+ojhp_h=mj_h+o_{j_h}, and choose a positional difference κh\kappa_h at each tag. Suppose θ∈(0,1)\theta\in(0,1) satisfies umθ=ℓum\theta=\ell and umθ(1−θ)≥1um\theta(1-\theta)\ge1. Then the periodic rank difference bound is (11): ∑v∈ℐr(ℓ)(TκWj)(v)2≤Au,m,r,d(θ)∏i=0rci−1/2.\sum_{v\in\mathcal I_r(\ell)}(T_\kappa W_j)(v)^2 \le A_{u,m,r,d}(\theta)\prod_{i=0}^{r}c_i^{-1/2}.(11)✦

In the paper, the result reads: for 1≤r<R01\le r<R_0, where R0R_0 is the upper cutoff on the number of tags, an admissible central retained count and a tagged tuple in KK periods with coarse gaps γi\gamma_i, disjoint D,V⊆[r]0D,V\subseteq[r]_0 with v′=|D|+2|V|v'=|D|+2|V| satisfy ∥∏h∈DDh∏h∈VVhWj∥22≤δ−Or(1)Kmm−v′∏i=0r(mγi)−1/2\|\prod_{h\in D}D_h\prod_{h\in V}V_h W_j\|_2^2 \le\delta^{-O_r(1)}\sqrt{Km}\,m^{-v'}\prod_{i=0}^r(m\gamma_i)^{-1/2}, with constants depending only on rr.

What Is Checked

The bound (11) is stated over the uniform fixed-size subset law and its tagged rank events, for separated interior tags selected from periods with the stated offset conditions and a retention parameter satisfying the mean and variance conditions of the theorem. For ℓ≤|A|\ell\le |A|, the binomial coefficient (|A|ℓ)\binom{|A|}{\ell} is positive, and the uniform fixed-size subset law has nonnegative masses summing to one.