The Setting
Let be a finite set of rational primes , with a chosen Gaussian prime of norm for each, and let be a self-avoiding walk in with steps at most that stays in : none of its points is divisible by or by for . Stop the walk at a random time given by a sampling schedule and record two things there: the residues of modulo the factors and , and the word of the next steps. The question is how much the word must tell about these residues, measured by their conditional mutual information per letter, given the residues of modulo a finite set of nonzero Gaussian integers whose norms have a small sum of logarithms. A walk is a sequence of Gaussian integers; it is self-avoiding when its terms are distinct, and it has steps at most when for every .
A batch certificate records the numerical conditions on the finite set of primes, called the batch, on the schedule and on the word length , for an error and a rate : the error bounds the sum of the logarithms of the norms in , and the rate is the information per letter that the certificate gives.
Batches and Residues
A split prime sieve, or batch, is a finite set of rational primes together with, for each , a Gaussian prime of norm .β¦ The primes of a batch are numbered once and for all as , the prime enumeration of β¦, and the mean log of is .β¦ The avoiding set is the set of divisible by neither nor for any β¦, and the available factors of are the Gaussian integers and for .β¦
A sign pattern gives a sign to each position, and an ordering is a permutation of the positions . A signed index of is a pair of a sign pattern and a position.β¦ The prime of a signed index of is , and its signed factor is if and if β¦. For , the selected factors are the signed factors of the first primes in the order , all of them when .
For a Gaussian integer , the multiples of form the subgroup β¦, and the residue of modulo is its class in the quotient by that subgroupβ¦. The residue ring of a signed index is , a ring with elements.β¦ For a finite set or family of Gaussian integers, is the vector of the residues of modulo the members of . The residue weight of a finite set of Gaussian integers is .β¦
The dyadic batch of index is the set of primes with .β¦ The chosen split factor of such a prime is one fixed choice among the Gaussian primes of norm .β¦ The sieve of a finite set of primes is the batch on that set with the chosen split factorsβ¦, and the dyadic sieve is the sieve of the dyadic batch of index β¦.
Walks and Laws
For , the lattice ball is the set of with ; it has elements.β¦ The increment word of length at time of a walk is β¦; when the steps are at most it is a word of letters in , the bounded increment wordβ¦. The walk segment of length is the set β¦, and the difference set of a finite set is β¦.
A finite probability law on a finite set gives each point a nonnegative mass, the masses summing to .β¦ The uniform law on is the law that gives all points the same massβ¦, and the point mass at is the law that gives the mass β¦. The probability of an event is the total mass of the points where it holdsβ¦, and the pushforward of a law along a map gives each value the mass of its preimageβ¦. The joint law of a law on and laws on is the law on with mass at : draw from , then from .β¦
A random time on is a map from to . For random variables , , on , is the Shannon entropy of the law of β¦, is the conditional entropyβ¦, and the conditional mutual information is (1)β¦
For a sign pattern , the residue vector of is .β¦ Under a law on , the random-order prefix entropy at of a random vector with coordinates indexed by the positions is the mean, over the orderings , of the entropy of its coordinates at β¦, and the sign-averaged entropy of a family of random vectors indexed by sign patterns is the mean over of their random-order prefix entropies.β¦ The point entropy at of a random Gaussian integer is the sign-averaged entropy of its residue vectors: (2)β¦
Schedules
A forward kernel of bound is a family of laws , one for each time , on the advances .β¦ The composite of forward kernels of bounds and is the forward kernel of bound that advances from by drawn from and then by drawn from : its law at is the pushforward of the joint law along .β¦ The smoothing kernel is the forward kernel of bound whose law at every time is the uniform law on .β¦
Let be a walk, and a time, and let . For , the chosen difference pair is a pair of advances in with , fixed once and for allβ¦, and the difference law is the law of for uniform on β¦. The difference kernel is the forward kernel of bound whose law at is the law of or , chosen by an independent fair coin.β¦ The common sampling schedule of a sequence of phase lengths with smoothing length is the composite (3)β¦ which is for the empty sequence; denotes the concatenation of two sequences, and .
A time law is a law on for some , the law of a random time.β¦ The advance of a time law by a forward kernel is the time law of with drawn from and then from , and is the time law with point mass at β¦. The terminal time is the random time with the law of advanced by . The information of a time law about functions , , of time is for drawn from it.β¦
Let be a forward kernel of bound , a time and , and let the walk have steps at most . The walk package at an advance is the pair of a displacement in and a word of letters in β¦, and the package law of at is the law of for drawn from β¦. The relative residue law is the law on of the class of for drawn from .β¦ The low residues of a law on a finite set at a level are the elements of probability less than ; on they are the classes of probability below , and is their number.β¦
Certificates
For reals , and , the band scale is β¦ and the band length is β¦; the band size of index for a batch is β¦.
Let be a batch, a step bound, a schedule, a smoothing length, a number of primes and a deficit. An entropy band for these data consists of a ratio with , a scale , a number of bands and a cost rate such that is a prefix followed by and then a suffix , is the band size for , , and (4)β¦
Fix a batch , a step bound and a smoothing length . A threshold function gives a real number to each signed index . The coverage derivation relation , between a schedule , a floor , a threshold function and an exception rate , is defined inductively by two rules. By the base rule, it holds when there are with , a real with an entropy band for , , and , and a real such that (5)β¦ By the step rule, holds when there are , reals and threshold functions and with the following properties: there is an entropy band for , smoothing length , and ; holds; , , , , , and ; (6) and every signed index has , , , and .
Let be a step bound, a schedule, a smoothing length, a batch, a word length, an error and a rate. A batch certificate for consists of a splitting , a scale , a number of primes, a number of repetitions, a floor , a gain , an exception rate , a deficit and a threshold function with the following properties: is nonempty, for every , , , , , and ; there are an entropy band for , smoothing length , and , and a coverage derivation ; every signed index satisfies the smoothing conditions (7) and the list bound (8) and the rate bound (9)β¦ holds with . The set of batch certificates for is denoted .
The Window Schedule
The top parameter is .β¦ For and , the top block is the sequence of the band lengths β¦, twenty being the top iteration countβ¦, and for a finite set the top blocks are the concatenation of the , , in decreasing order of β¦. For the accurate grid is β¦, and for a real number the accurate block is the sequence of the band lengths for β¦, the accurate iteration count being β¦. For and finite sets , the window blocks are followed by , for from down to β¦, and the common block list is the window blocks followed by : (10)β¦ The window smoothing length is β¦, the word length of the dyadic batch of index is β¦, and the top coefficient of is β¦.
The Claim
Theorem 1. In (a) to (e), is a batch and is a self-avoiding walk with steps at most whose points all lie in , with in (a) to (c) and in (d) and (e).
(a) Suppose a batch certificate for exists, and let be a finite set of nonzero Gaussian integers of residue weight at most . Then there is a finite set of Gaussian integers with such that, for the terminal time , (11)β¦
(b) Suppose the splitting together with , , , , , , and forms a batch certificate for , and let be a family of Gaussian integers with for the terminal time . Then there are a sign pattern and an ordering such that, for , (12)β¦
(c) Let be nonempty, a law on a finite set , a random time on , a family of Gaussian integers and a forward kernel of bound , and write for . Let , , , , , , , , , and a threshold function satisfy (7) and (8) at every signed index and (9) with . Suppose that, under , , , and the mean over the signed indices of is at most . Then there are and such that (13)β¦ where is drawn from , then from , and .
(d) Let , , and be as in (c) and a random variable on with values in a finite set, and let , , , , , , and a threshold function satisfy (7) and (8) at every signed index. Suppose that, under , , , and the mean over the signed indices of is at most . Then (14)β¦ where is drawn from , then from the package law of at for words of length , , and and are uniform.
(e) Let be a law on a finite set , a random time on , a forward kernel and a random variable on with values in a finite set, and let be signed indices with factors . Let , , , reals and and thresholds satisfy (7) and (8) at each with . Suppose that, under , and . Then, with , and as in (d), (15)β¦
(f) Let , , and with , and let be natural numbers. Then for all sufficiently large the following holds. If are finite sets of natural numbers such that every , for every , satisfies and , and any two distinct elements of differ by at least , then for every and every (16)β¦
In the paper, the batch consists of the primes in . In the paper, the result reads: there is , depending only on the fixed schedule parameters, such that for all sufficiently large and every batch , , uniformly over all infinite self-avoiding walks with steps at most in .
The library states the bound in existential form, for one set of factors, and on the dyadic sieves in place of the batches .
What Is Checked
The claim is stated over batches of split primes with their signed factors, residues and avoiding set, self-avoiding walks with steps at most in that set and their increment words, the entropy and conditional mutual information of finite probability laws, forward kernels with the common sampling schedules and terminal times built from them, entropy bands, coverage derivations and batch certificates, and, in (16), the dyadic sieves and the window schedule (10).
Of these constructions the library also proves that every element of the difference set of a walk segment is for some times .β¦