The Setting
The environment is a set of channels, affine lines in for a prime , and a walk moves them by affine maps drawn from a finite alphabet of generators. Fix a level and a retained parameter , and condition on the line having its point at in the box of level , a cube of side about . Such a line is recorded by a padded channel, whose offset is read modulo , and the generator acts on it modulo . The question is how to carry out this conditional step by a permutation of the whole environment that never reads , taken from a bounded menu by a guess at how the generator wraps around the box.
Channels and Boxes
For a modulus , the residue pairs modulo form the set ✦, and the space is the set of pairs of residue pairs, that is .✦ The punctured frame of is the set of its nonzero vectors.✦ A channel over is a pair of a direction and an offset ; it describes the affine line in .✦ The channels form the set .✦
The box side length at level over is , which equals .✦ A padded channel of level is a pair of a direction and a short offset .✦ The widening of is the vector of whose entries are the least nonnegative representatives of the entries of , read modulo ; it lies in the box of level .✦ The opened channel of at a parameter is the channel (1)✦ whose point at is .
Generators
The command alphabet is the disjoint union of three kinds of letters: shear choices, which are pairs of bits ; single bits , which select an axial direction; and cross pairs, pairs of bits that select a cross term.✦ A generator is a letter of the generator alphabet: a bit , which says whether the two coordinate pairs of are exchanged, and a command .✦
For a bit and a residue modulo , the shear map of sends to if and to if ✦; as a permutation of it is the shear permutation.✦ The shear amount of a bit is if and if , and the axial unit vector of is if and if . For and bits , the cross term is if and if , where if and if .✦
For a flag , with allowing translations, a command and a parameter , the lead coordinate action is the permutation of (2)✦ The lead coordinate permutation of sends to ✦, and the face swap of sends to if and is the identity if .✦ The generator action of on is (3)✦ write for the affine action and for the action without translations. The frame permutation of is the restriction of to the nonzero vectors .✦ The generator permutation of acts on factor by factor, (4)✦ The conditional generator of at level is the generator permutation of on the padded channels of level , where .
Wrap Guesses and Variants
Quadruples of integers or digits are arranged as pairs of pairs, like the vectors of ✦, and maps and conditions on them apply entrywise. The lift of takes each entry to its least nonnegative representative✦, and the reduction of takes each entry to its residue modulo .✦ Over a commutative ring , the lowered command action is the map that takes to the value given by the right side of (2) read in .✦ The real action of on is (5)✦ and over .
The roller alphabet is the set of digit quadruples.✦ At scale , the digit chosen for an integer is (6)✦ and the guessed digit vector of applies entrywise.✦ The guess of at a padded channel of level is ✦, and the shift vector of at scale is , with entries .✦ For a level , a generator and , the variant is the permutation of all channels (7)✦
The Claim
Theorem 1. Let be a prime, a generator and a level, with box side .
For every padded channel of level and every , (8)✦
For every padded channel of level , (9)✦
For every positive integer and every , (10)✦
In the paper, the result reads: a walk word of length expands into a family of variants over a bounded alphabet, described by bits, each acting bijectively and measure-preservingly on the full environment and independently of the indicated identifiers, such that exactly one variant passes the slice and wrap tests and gives the conditional step and the valid variants sum to the conditional average, the tests being done at visits in space , with the paper’s space parameter, in the admissible range. The box treats one generator at a time, with the variants indexed by the digit quadruples of .
What Is Checked
The claim is stated over the channels and the padded channels of level , with the box side , the widening and the opened channel (1); over the generator actions (3), built from shears, axial translations, cross terms and face swaps, with the frame permutation and the conditional generator (4); and over the lift, the real action (5), the guess built from (6), the shift vector and the variant (7). Beyond the claim, the library proves that shearing a residue pair by and then by in the same direction returns it.✦