The Setting
The sampler is a random walk whose steps are permutations drawn from a fixed family of twenty, each acting at once on a nonzero vector of , for a prime , and on a vertex of the box , for a positive integer : linearly on the first and affinely on the second, with unit translations besides. For the walk that applies a random member of such a family, or its inverse, a spectral gap is a Poincaré inequality, a bound on the variance of every function by a constant times its energy along the generators.
Theorem 1 gives this inequality for the twenty generators on the product of and and on the box alone, with constants that depend on neither nor , together with an inequality of the same shape on the square for families of functions moved by shears of amount and by unit translations.
Variance and Energy
The average of a real function over a finite set is the sum of its values on divided by ✦; for a function on a finite set , is its average over all of .✦ The variance of a real function on a finite set is the average of its squared deviation from its average, (1)✦
The energy of order of a real function on along a map is .✦ A family of permutations of indexed by a finite set is a map , written ✦, and the total energy of along is (2)✦
A family of permutations of expands with constant , a real number, if every real function on satisfies the Poincaré inequality (3)✦
Shears of the Square
For a positive integer , write for the pairs of residues modulo .✦ For , the upper shear and the lower shear are the maps of given by (4)✦ The lemma uses the four shears of amount , , and the axial unit vectors and .✦ The threshold and the gap constant of the lemma are the real numbers (5)
Let be a finite nonempty set. The mean square of a family of real functions on is .✦ The change of a family under a shear along a permutation of is the family , and its shifted difference along an axial vector is the family , where (6)
The Twenty Generators
Write , a point being a pair of blocks in .✦ A command is one of ten symbols: a shear , an axial vector , or a cross pair .✦ A generator is a pair of a face bit and a command , twenty in all.✦
The affine lead action of a command at a block is the permutation of given by (7)✦ The linear lead action of a command at a block is the permutation of that agrees with , except that each axial command acts as the identity.
The lead permutation of a command is the permutation of .✦ The face swap exchanges the blocks, and is the identity.✦ A generator acts on by (8)✦ The linear action of a generator is with built from the linear lead action, and the affine action of is with built from the affine lead action.
For a set with a zero element, the punctured set is the subset of its elements different from zero.✦ For a prime , the punctured frame is the punctured set of ✦, and the frame permutation of a generator is the restriction of to .✦ For a prime and a positive integer , the slice is , with the box, and the slice generators are the family of twenty permutations of that move a frame vector by the frame permutation and a vertex of the box by the affine action of the same generator: (9)✦
The Claim
Theorem 1 (A uniform affine spectral gap). Let be the gap constant (5).
(i) For a positive integer , a finite nonempty set , a family of real functions on , and a permutation of for each shear , (10)✦
(ii) For a prime and a positive integer , the twenty slice generators expand with constant : every real function on satisfies (11)✦
(iii) For a positive integer , the twenty generators in the affine action on the box expand with constant : every real function on satisfies (12)✦
In the paper, the result reads: for the group with a fixed , there are a fixed finite symmetric generating multiset and a lazy rational random walk on it whose action on every finite transitive -set has spectral gap bounded below by a positive constant depending only on .
What Is Checked
The claim is stated over the average, the variance and the total energy of real functions on finite sets, the Poincaré inequality with a constant, the gap constant built from the threshold , the shears of amount and the axial unit vectors of with the mean squares of the changes and shifted differences they define, and the twenty generators, acting linearly on the punctured frame and affinely on the box .
About these constructions the library proves that the shear by undoes the shear by , ✦, so that each shear is a permutation of .✦