OctoInformBeta

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

Lemma 4.2: Squared norms with counting measure for nearby defect offsets and admissible retained counts

A uniform estimate for periodic 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

A periodic source has uu periods of mm slots, with one tagged defect in each period. For a fixed retained count, the observed ranks of tagged defects give rank kernels; summing over choices of distinct periods gives the kernel in Lemma 4.2. For a requested deletion probability q∈(0,1)q\in(0,1), each bit survives with probability 1−q1-q, and the working deletion rate is δ=min⁡{q,1/2}\delta=\min\{q,1/2\}; the construction theorems call this working rate qq.

Write [n]0={0,…,n−1}[n]_0=\{0,\ldots,n-1\} for the zero-based index set of nn source slots. Period indices and observed ranks also start at zero. An increasing rank tuple v∈ℐn,rv\in\mathcal I_{n,r} is a strictly increasing map from [r]0[r]_0 to [n]0[n]_0: ℐn,r={v:[r]0→[n]0:v0<⋯<vr−1}.\mathcal I_{n,r} =\{v:[r]_0\longrightarrow[n]_0:\ v_0<\cdots<v_{r-1}\}.(1)✦ The tuples in (1) specify the distinct ranks of a monomial, or the periods supplying its tagged slots.

Retained Subsets and Rank Kernels

A finite probability law π\pi on a finite outcome set XX is a mass function π:X→[0,∞)\pi:X\to[0,\infty) with ∑x∈Xπ(x)=1\sum_{x\in X}\pi(x)=1.✦ A fixed-size subset S∈ℱl(X)S\in\mathcal F_l(X) is a subset of XX with cardinality ll.✦ For l≤|X|l\le |X|, the uniform fixed-size subset law UX,lU_{X,l} assigns the masses UX,l(S)=(|X|l)−1,S∈ℱl(X).U_{X,l}(S)=\binom{|X|}{l}^{-1}, \qquad S\in\mathcal F_l(X).(2)✦ For retained source slots, take X=[n]0X=[n]_0 in (2).

For a retained subset S∈ℱl([n]0)S\in\mathcal F_l([n]_0) and an observed rank a∈[l]0a\in[l]_0, the slot eS(a)e_S(a) is the source slot at rank aa in the increasing enumeration of SS.✦ For tagged slots p:[r]0→[n]0p:[r]_0\to[n]_0 and requested ranks v:[r]0→[l]0v:[r]_0\to[l]_0, the tagged rank event Ep,vE_{p,v} is the set of retained subsets whose requested ranks contain their corresponding tagged slots.✦ The conditional rank kernel Kn,l(p,v)K_{n,l}(p,v) for tagged slots p:[r]0→[n]0p:[r]_0\to[n]_0 and requested ranks v:[r]0→[l]0v:[r]_0\to[l]_0 is the probability of the tagged rank event Ep,vE_{p,v} under the uniform retained subset law U[n]0,lU_{[n]_0,l}: Ep,v={S∈ℱl([n]0):eS(vi)=pi for every i∈[r]0},Kn,l(p,v)=U[n]0,l(Ep,v),l≤n.\begin{aligned} E_{p,v} &=\{S\in\mathcal F_l([n]_0): e_S(v_i)=p_i \text{ for every }i\in[r]_0\},\\ K_{n,l}(p,v)&=U_{[n]_0,l}(E_{p,v}),\qquad l\le n. \end{aligned}(3)

A period defect offset oo for uu periods of mm slots is a map o:[u]0→[m]0o:[u]_0\to[m]_0. For a period defect offset o:[u]0→[m]0o:[u]_0\to[m]_0, the period defect slot map so:[u]0→[um]0s_o:[u]_0\to[um]_0 is the map that places the defect in each period at so(j)=jm+o(j).s_o(j)=jm+o(j).(4) For n=umn=um, the summed periodic rank kernel Ar,oA_{r,o} is the function on ℐl,r\mathcal I_{l,r} obtained from (3) and (4) by Ar,o(v)=∑J∈ℐu,rKum,l(so∘J,v),∥Ar,o∥ℓ22=∑v∈ℐl,rAr,o(v)2.A_{r,o}(v)=\sum_{J\in\mathcal I_{u,r}}K_{um,l}(s_o\circ J,v), \qquad \|A_{r,o}\|_{\ell^2}^2 =\sum_{v\in\mathcal I_{l,r}}A_{r,o}(v)^2.(5)

The rank Schur constant CRSC_{\mathrm{RS}} is the absolute constant CRS=88473621−exp⁡(−1/1024)exp⁡(1).C_{\mathrm{RS}} =884736\,\frac{2}{1-\exp(-1/1024)}\,\exp(1).(6)✦

The Claim

Theorem 1. Let m≥32m\ge32 and 1≤u≤m1\le u\le m be integers, let 1≤r≤u1\le r\le u, and let l≤uml\le um be a nonnegative integer. Suppose 0<δ≤1/20<\delta\le1/2 and there is a real θ∈[1−δ2,1−δ2/4]\theta\in[1-\delta^2,1-\delta^2/4] such that umθ=lum\theta=l and umθ(1−θ)≥1um\theta(1-\theta)\ge1. Let o:[u]0→[m]0o:[u]_0\to[m]_0 be a period defect offset such that |o(j)−m/2|≤3|o(j)-m/2|\le3 for every period jj and |o(j)−o(k)|≤2|o(j)-o(k)|\le2 for every pair of periods j,kj,k. For the summed kernel in (5) and the constant in (6), ∥Ar,o∥ℓ22≤(3CRSδumr)r.\|A_{r,o}\|_{\ell^2}^2 \le\left(\frac{3C_{\mathrm{RS}}}{\delta} \sqrt{\frac{u}{mr}}\right)^r.(7)✦

In the paper, the result reads: for 1≤u≤m1\le u\le m periods of arbitrary deterministic types bj∈{−1,0,1}b_j\in\{-1,0,1\}, an admissible return count, and every 1≤r≤u1\le r\le u, the summed periodic rank kernel Ar,bA_{r,b} has counting-measure squared norm on increasing rank tuples at most (C3/δ)r(u/m)r/2r−r/2(C_3/\delta)^r(u/m)^{r/2}r^{-r/2}, with C3C_3 absolute and uniform in the types and count.

What Is Checked

The estimate (7) is stated over uniform retained subsets and their tagged rank events, using periodic defect slots subject to the stated offset conditions. For l≤nl\le n, the binomial coefficient (nl)\binom nl in (2) is positive.