The Setting
Thinning a set of vertex identifiers level by level, keeping each one at level with probability close to , 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 . Here is the size of the field the channels live over, not an input length, and conditions such as refer to it.
Rank Channels and Retention
Fix a prime , let ✦, and let , the vector space over the field .✦ A frame over is a nonzero vector of ; the frames form the punctured space .✦ A rank channel over is a pair of a frame and an offset ✦, and its evaluation at is the vector (1)✦ The channels form the finite set , and the identifiers are the residues .✦
For a natural number , the box side at level is the integer , and the box is the set of vectors of whose four coordinates, each read as an integer in , are less than : (2)✦ A channel retains the identifier at level when .✦ The retention indicator is the function on channels that is on the channels retaining at level and on the others.✦ The retention probability at level is the real number , the share of in ✦, and the rate of level is .✦
For a nonzero , scaling by is the map on frames.✦ For a nonzero and any in , the affine channel map is the map on channels given by (3)✦
Averages and Retained Counts
For a finite set and a real function on , the average of over is .✦ The average of a real function over all channels is written ✦, and its variance is .✦
A padded channel at level is a pair of a frame and a vector .✦ Widening gives the vector whose coordinates are those of , each read as an integer in and then modulo .✦ The opening of a padded channel at an identifier is the channel , whose value at is .✦ The conditional average of a real function on channels, given that is retained at level , is the average of over the padded channels at level opened at : (4)✦
A finite domain is a finite set of natural numbers, each element read as the identifier ✦; it is legal for when .✦ The retained set of at level under a channel is the set of that retains at level ✦, and the retained count is the function on channels giving its size: (5)✦
The Claim
Theorem 1 (Rank-channel estimates). Let be a prime, let and be natural numbers, let be a real function on the channels over , and let be a finite domain with retained count . If , then (6)✦ For every identifier , (7)✦ For distinct identifiers and , (8)✦ The retained count has mean (9)✦ If is legal for , then (10)✦ and if moreover , then for every natural number (11)✦ Let be a nonzero element and any element of . Then for every channel and every identifier , the channel takes at the value (12)✦
In the paper, the result reads: there are constants , , and , depending only on the parameters and of the paper’s setting, such that in every admissible finite range of the paper an identifier is retained at rate with a probability satisfying , for distinct identifiers and admissible rates one has , for a deterministic set of identifiers the count satisfies , and replacing every channel argument by with leaves the joint law unchanged, a rate standing for the page’s and for .
What Is Checked
The claim is stated over the rank channels over a prime , a frame in the punctured space and an offset in , evaluated as in (1); over retention at level in the box of side , with the retention probability and the rate ; 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 in (10) and (11); and over the affine channel map (3). The library also shows that scaling by a nonzero is a permutation of the frames, with inverse , and that is a permutation of the channels, with inverse .