OctoInformBeta

OpenAI preprint, September 2026 · §3. Rank channels for retained vertex sets · §3

Lemma 3.1 [Rank-channel estimates]: For prime nn and 2k≤n2^k\le n, an identifier is retained at level kk with probability between 2−4k2^{-4k} and 16⋅2−4k16\cdot 2^{-4k}

Retention estimates for rank channels.

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

Thinning a set of vertex identifiers level by level, keeping each one at level kk with probability close to 2−4k2^{-4k}, needs random choices short enough for a logspace machine to store. It also needs control over several identifiers at once: how the retention of one identifier changes the odds for another, and how far the number retained from a fixed set strays from its mean. Rank channels make these choices from eight residues modulo a prime nn. Here nn is the size of the field the channels live over, not an input length, and conditions such as 2k≤n2^k\le n refer to it.

Rank Channels and Retention

Fix a prime nn, let Tn=(ℤ/n)2T_n=(\mathbb{Z}/n)^2✦, and let Vn=Tn×TnV_n=T_n\times T_n, the vector space (ℤ/n)4(\mathbb{Z}/n)^4 over the field ℤ/n\mathbb{Z}/n.✦ A frame over nn is a nonzero vector of VnV_n; the frames form the punctured space Fn=Vn\{0}F_n=V_n\setminus\{0\}.✦ A rank channel over nn is a pair s=(d,b)s=(d,b) of a frame d∈Fnd\in F_n and an offset b∈Vnb\in V_n✦, and its evaluation at y∈ℤ/ny\in\mathbb{Z}/n is the vector s(y)=b+yd∈Vn.s(y)=b+y\,d\in V_n.(1)✦ The channels form the finite set Cn=Fn×VnC_n=F_n\times V_n, and the identifiers are the residues y∈ℤ/ny\in\mathbb{Z}/n.✦

For a natural number kk, the box side at level kk is the integer ℓk=⌊(n−1)/2k⌋+1\ell_k=\lfloor (n-1)/2^k\rfloor+1, and the box BkB_k is the set of vectors of VnV_n whose four coordinates, each read as an integer in {0,…,n−1}\{0,\dots,n-1\}, are less than ℓk\ell_k: Bk={0,1,…,ℓk−1}4⊆Vn.B_k=\{0,1,\dots,\ell_k-1\}^4\subseteq V_n.(2)✦ A channel ss retains the identifier yy at level kk when s(y)∈Bks(y)\in B_k.✦ The retention indicator Xk(y)X_k(y) is the function on channels that is 11 on the channels retaining yy at level kk and 00 on the others.✦ The retention probability at level kk is the real number πk=(ℓk/n)4\pi_k=(\ell_k/n)^4, the share of BkB_k in VnV_n✦, and the rate of level kk is 2−4k2^{-4k}.✦

For a nonzero u∈ℤ/nu\in\mathbb{Z}/n, scaling by uu is the map d↦udd\mapsto u\,d on frames.✦ For a nonzero uu and any tt in ℤ/n\mathbb{Z}/n, the affine channel map σu,t\sigma_{u,t} is the map on channels given by σu,t(d,b)=(ud,b+td).\sigma_{u,t}(d,b)=(u\,d,\;b+t\,d).(3)✦

Averages and Retained Counts

For a finite set SS and a real function ff on SS, the average of ff over SS is 𝔼a∈Sf(a)=|S|−1∑a∈Sf(a)\mathbb{E}_{a\in S}f(a)=|S|^{-1}\sum_{a\in S}f(a).✦ The average of a real function ff over all channels is written 𝔼f\mathbb{E}f✦, and its variance is Var⁡f=𝔼(f−𝔼f)2\operatorname{Var}f=\mathbb{E}\,(f-\mathbb{E}f)^2.✦

A padded channel at level kk is a pair (d,w)(d,w) of a frame dd and a vector w∈(ℤ/ℓk)4w\in(\mathbb{Z}/\ell_k)^4.✦ Widening ww gives the vector w‾∈Bk\bar w\in B_k whose coordinates are those of ww, each read as an integer in {0,…,ℓk−1}\{0,\dots,\ell_k-1\} and then modulo nn.✦ The opening of a padded channel (d,w)(d,w) at an identifier yy is the channel (d,w‾−yd)(d,\,\bar w-y\,d), whose value at yy is w‾\bar w.✦ The conditional average 𝔼k,yf\mathbb{E}_{k,y}f of a real function ff on channels, given that yy is retained at level kk, is the average of ff over the padded channels at level kk opened at yy: 𝔼k,yf=𝔼(d,w)∈Fn×(ℤ/ℓk)4f(d,w‾−yd).\mathbb{E}_{k,y}f=\mathbb{E}_{(d,w)\in F_n\times(\mathbb{Z}/\ell_k)^4}\,f(d,\,\bar w-y\,d).(4)✦

A finite domain A0A_0 is a finite set of natural numbers, each element ii read as the identifier imod⁡ni\bmod n✦; it is legal for nn when A0⊆{0,…,n−1}A_0\subseteq\{0,\dots,n-1\}.✦ The retained set of A0A_0 at level kk under a channel ss is the set of i∈A0i\in A_0 that ss retains at level kk✦, and the retained count TkT_k is the function on channels giving its size: Tk(s)=|{i∈A0:s(i)∈Bk}|.T_k(s)=\bigl|\{\,i\in A_0:\ s(i)\in B_k\,\}\bigr|.(5)✦

The Claim

Theorem 1 (Rank-channel estimates). Let nn be a prime, let jj and kk be natural numbers, let ff be a real function on the channels over nn, and let A0A_0 be a finite domain with retained count TkT_k. If 2k≤n2^k\le n, then 2−4k≤πk≤16⋅2−4k.2^{-4k}\le\pi_k\le16\cdot2^{-4k}.(6)✦ For every identifier yy, 𝔼[fXk(y)]=πk𝔼k,yf.\mathbb{E}\bigl[f\,X_k(y)\bigr]=\pi_k\,\mathbb{E}_{k,y}f.(7)✦ For distinct identifiers xx and yy, 𝔼k,xXj(y)≤2πjand𝔼k,xXk(y)≤πk.\mathbb{E}_{k,x}X_j(y)\le2\,\pi_j \quad\text{and}\quad \mathbb{E}_{k,x}X_k(y)\le\pi_k.(8)✦ The retained count has mean 𝔼Tk=|A0|πk.\mathbb{E}\,T_k=|A_0|\,\pi_k.(9)✦ If A0A_0 is legal for nn, then Var⁡Tk≤|A0|πk,\operatorname{Var}T_k\le|A_0|\,\pi_k,(10)✦ and if moreover 2k≤n2^k\le n, then for every natural number x<nx<n 𝔼j,xTk≤1+32|A0|2−4k.\mathbb{E}_{j,x}T_k\le1+32\,|A_0|\,2^{-4k}.(11)✦ Let uu be a nonzero element and tt any element of ℤ/n\mathbb{Z}/n. Then for every channel ss and every identifier yy, the channel σu,t(s)\sigma_{u,t}(s) takes at yy the value σu,t(s)(y)=s(t+yu).\sigma_{u,t}(s)(y)=s(t+y\,u).(12)✦

In the paper, the result reads: there are constants cπc_\pi, CπC_\pi, CpairC_{\mathrm{pair}} and CvarC_{\mathrm{var}}, depending only on the parameters HH and h0h_0 of the paper’s setting, such that in every admissible finite range of the paper an identifier is retained at rate aa with a probability πa\pi_a satisfying cπa≤πa≤Cπac_\pi a\le\pi_a\le C_\pi a, for distinct identifiers x,yx,y and admissible rates a,a′a,a' one has Pr⁡{Xa(y)=1∣Xa′(x)=1}≤Cpaira\Pr\{X_a(y)=1\mid X_{a'}(x)=1\}\le C_{\mathrm{pair}}\,a, for a deterministic set A0A_0 of qq identifiers the count Ta=∑y∈A0Xa(y)T_a=\sum_{y\in A_0}X_a(y) satisfies Pr⁡{Ta<qπa/2}≤Cvar/(qπa)\Pr\{T_a<q\pi_a/2\}\le C_{\mathrm{var}}/(q\pi_a), and replacing every channel argument yy by αy+β\alpha y+\beta with α≠0\alpha\ne0 leaves the joint law unchanged, a rate aa standing for the page’s 2−4k2^{-4k} and πa\pi_a for πk\pi_k.

What Is Checked

The claim is stated over the rank channels (d,b)(d,b) over a prime nn, a frame dd in the punctured space Vn\{0}V_n\setminus\{0\} and an offset bb in Vn=(ℤ/n)4V_n=(\mathbb{Z}/n)^4, evaluated as in (1); over retention at level kk in the box BkB_k of side ℓk\ell_k, with the retention probability πk\pi_k and the rate 2−4k2^{-4k}; over averages and variances on channels and the conditional average (4) through padded channels; over the retained count (5) of a finite domain, legal for nn in (10) and (11); and over the affine channel map (3). The library also shows that scaling by a nonzero uu is a permutation of the frames, with inverse d↦u−1dd\mapsto u^{-1}d, and that σu,t\sigma_{u,t} is a permutation of the channels, with inverse (d,b)↦(u−1d,b−tu−1d)(d,b)\mapsto(u^{-1}d,\,b-t\,u^{-1}d).