The Setting
Fix a prime and let .✦ A rank channel over is a pair of a direction in the punctured frame and an offset ✦; its point at a residue modulo is . Write for the set of rank channels and for the salts of width , four registers of bits each. The shared environment of width is (1)✦
Retention is membership in a small box. At level the box side length is ✦, the box is the set of vectors whose four coordinates have least nonnegative representatives below ✦, and fills the fraction (2)✦ of , close to . A residue modulo is called an identifier; a channel retains the identifier at level when . For identifiers and levels , the hit set is the set of environments in which retains at level and retains at level .✦
Two questions are asked of this set: what the mean of a function over it is, and how fast a random walk on it, driven by affine maps of the channels and the salt, forgets its starting point when the high salt bits are frozen.
Averages and the Slice
For a finite set and a real function on , is the sum of the values of divided by ✦, and the fourth moment of is .✦
A padded channel of level is a pair of a direction and a short offset ; is the set of them.✦ The widening of replaces each coordinate by its least nonnegative representative, read modulo .✦ Opening at gives the rank channel , whose point at is , a vector of .✦
The slice of levels and width is the set (3)✦ of two padded channels, a rank channel and a salt. The opening map opens the first padded channel at and the second at , and keeps the rank channel and the salt.✦ For a real function on , the conditional average of at is (4)✦
For , a register modulo splits into its low part , a register of bits, and its high part , a register of bits.✦ Splitting the four registers identifies with ✦, and so with .✦ Freezing the high bits at gives the export map , .✦ The panel of is the function on ✦, and the panel mean is .
Generators and the Mixing Family
Fix a modulus and write a vector of as a pair of faces in . A command replaces the lead face by its image under a permutation of that may depend on , and keeps .✦ There are ten commands: four shears, and with ; two translations of , by and by ; and four cross terms, which add or to or to .✦
A generator is a bit and a command , twenty in all, and is their set.✦ The affine action of a generator on is the map that applies when and, when , swaps the two faces, applies and swaps them back, so that changes .✦ The linear action of a generator on is the map obtained from by replacing each translation with the identity; the frame permutation of is the restriction of to . On a channel or a padded channel, acts by , with taken modulo and modulo the modulus of .✦
A family of permutations of a set indexed by a set assigns a permutation of to each element of .✦ The union of a family on and a family on is the family on , indexed by the disjoint union of the two index sets, whose members move their own factor and fix the other.✦ The mixing family on is the union of four such families, indexed by the eighty generator choices , with the salt moved by modulo : (5)✦
The Sampled Average
An atom is a pair of a bit and a generator choice✦; the atoms form a set of elements, each of weight . A roller index is a quadruple in .✦ Each pair of an atom and a roller index determines a roller step, a permutation of that depends on , and . Each atom and each point determine a winning roller index of at , an element of that depends on and as well. For paths and , the roller walk applies the roller steps of in this order✦, and is live at when each is the winning index of at the point that the first steps reach from .✦ The -step sampled average of is (6)✦
For a finite alphabet and a real constant , the loss rate is (7)✦ With the threshold , the gap constant is .✦
The Claim
Theorem 1. Let be a prime, and levels, and identifiers in , a width, and a real function on . Then (8)✦ If moreover , and is a number of steps, then, with both fourth moments taken over and the loss rate of the eighty generator choices at the gap constant, (9)✦
In the paper, the result reads: on the product of rank channels conditioned on the retention of one identifier per conditioned channel, with designated free bits and the remaining bits frozen, there is a rational Markov operator whose stationary law is the uniform conditional law, with for each number of steps and each fixed , being the expectation under that law, and with constants independent of the field size, the side lengths, the bit lengths, the identifiers and the frozen bits.
The bound (9) is the fourth-moment form of this estimate, with the sampled average read through the export map in the role of and the panel mean in that of .
What Is Checked
The claim is stated over the shared environment of three rank channels over a prime and a salt, the boxes of levels and with their fractions and , the hit set , the slice with its opening and export maps, the conditional average (4), the panel and its mean , the sampled average (6) with its atoms, roller steps and live paths, the fourth moment , and the loss rate (7) at the gap constant. Beside it the library defines the mixing family (5) on the slice.
The library proves that the shear by undoes the shear by ✦, so that every generator acts on by a permutation, and that the linear action of a generator maps nonzero vectors to nonzero vectors. It also proves that splitting a register of bits into its low and high bits is a bijection, inverted by .✦