lemmaroutine

Rank channel retention estimates

Retention rates πa≍a\pi_a\asymp a, pair inflation ≤ constant, counts concentrate
probability toolkit for retained vertex sets
Lemma·lem:env-ranks·§3 Rank channels for retained vertex sets

Statement (paper)

There are positive constants cπ,Cπ,Cpair,Cvarc_\pi,C_\pi,C_{\rm pair},C_{\rm var}, depending only on H,h0H,h_0, with the following properties in every admissible finite range. \begin{enumerate} \item A specified identifier is retained at rate aa with probability πa\pi_a, where cπa≤πa≤Cπac_\pi a\le\pi_a\le C_\pi a. \item For distinct identifiers x,yx,y and any admissible rates u,au,a, Pr⁡{Xa(y)=1∣Xu(x)=1}≤Cpaira. \Pr\{X_a(y)=1\mid X_u(x)=1\}\le C_{\rm pair}a. \item If A0A_0 is a deterministic set of qq distinct identifiers and Ta=∑y∈A0Xa(y)T_a=\sum_{y\in A_0}X_a(y), then Pr⁡{Ta<qπa/2}≤Cvarqπa(q>0). \Pr\{T_a<q\pi_a/2\}\le \frac{C_{\rm var}}{q\pi_a} \quad(q>0). \item Replacing every channel argument yy by the same injective affine map αy+β\alpha y+\beta leaves the joint law of all evaluations unchanged, provided α≠0\alpha\ne0 in FP\mathbb F_P. In particular, a common fixed padding suffix leaves their law unchanged. \end{enumerate}

In plain English

Retention indicators Xa(y)X_a(y) for identifiers at admissible rates aa have probability πa≍a\pi_a\asymp a, conditioning on another identifier being retained inflates the retention probability by at most a constant factor (≤Cpaira\le C_{\rm pair}a), and the count TaT_a over qq fixed identifiers is at least qπa/2q\pi_a/2 except with probability O(1/(qπa))O(1/(q\pi_a)). The joint law is also unchanged if every channel argument yy is replaced by αy+β\alpha y+\beta with α≠0\alpha\ne0 in FP\mathbb F_P, so a fixed common padding suffix changes nothing.

Why it's here

This is the basic probability toolkit for retained vertex sets: single-point rates, near-independence of pairs, and concentration of retained counts via a variance (Chebyshev-type) bound. The later lemmas on column tests, atom identities, sample means and heavy-count rarity cite these bounds, and the affine-invariance part lets identifiers be re-encoded or padded without changing the analysis. The constants depend only on H,h0H,h_0, so they stay uniform across admissible ranges.
Classified routine:
These are standard pairwise-independence estimates for hash-based sampling over a prime field: single-point rates, bounded pairwise correlation, a Chebyshev second-moment bound on the retained count, and affine invariance of a uniformly random affine/polynomial hash family. They are adapted here to the paper's rank channels.

Uses

Nothing else in the paper

Used by

lemColumn test separates heavy and light columnslemDense-bin atom table is bounded and unbiasedlemTrue tables yield prescribed sample meanslemBuffer overflow events are rarethmDeterministic logspace approximation of acceptance probabilityclaimPrecision choice beats coordinate factor N

Sources

PaperOpen
Section
§3 Rank channels for retained vertex sets
Page
—
Label
lem:env-ranks
Line
sections/environment.tex:44
Leannot aligned

Phase 2 aligns this node to a Lean declaration.