The Setting
Let be a walk in with steps at most , and let be finite sets of nonzero Gaussian integers. Observed at a random time , the walk shows the residues of modulo the elements of each , and the word of its next steps, where are positive lengths. How much does the word tell, per step, about the residues modulo once those modulo are known, and how do these amounts add up along the chain? The item answers this for any random time followed by a uniform offset, among them the terminal time of the common schedule, a random time built from the differences of the walk itself.
Residues and Words
The residue class of a Gaussian integer modulo a Gaussian integer is the coset of in the quotient of by the subgroup of multiples of .✦ For a walk , a finite set of Gaussian integers and a time , the residue vector lists the residue classes of modulo the elements of ; along the chain we write .
The increment word of length at time of a walk is the word of its next steps, (1)✦
The lattice ball of radius is the finite set of Gaussian integers with , and is its number of elements.✦ The norm of a Gaussian integer , with , is the integer .
Laws and Information
A finite probability law on a finite set is a function from to the nonnegative reals whose values, the masses, sum to ; a random variable on is a map from to any set.✦ The uniform law on a nonempty finite set gives every point the mass ✦, and the point mass at gives the mass and every other point the mass ✦. The pushforward of a law on along a map to a finite set is the law on that gives each the mass .✦ The joint law of a law on a finite set and laws on , one for each , is the law on with mass at : the law of drawing from and then from .✦
For a finite probability law on and random variables , , on , with the natural logarithm and the entropy of the pair , the entropy of , the conditional entropy of given and the conditional mutual information of and given are (2) the sum running over the finitely many values of . The binary entropy of is .
Random Times
A time law of last time is a finite probability law on , the law of a random time at most .✦ The exact start at a time is the time law of last time that is the point mass at .✦
The information of a time law , for maps , , on with values in any sets, is the conditional mutual information of , and at a random time of law : (3)✦
A forward kernel of bound is a family of finite probability laws , one for each time , on the advances .✦ The advance of a time law of last time by is the time law of last time that is the pushforward, under , of the joint law of and the laws .✦ The composite of with a forward kernel of bound is the forward kernel of bound whose law at a time is the pushforward, under , of the joint law of and the laws .✦ The smoothing kernel is the forward kernel of bound whose law at every time is the uniform law on .✦
Common Schedules
The difference set of a finite set of Gaussian integers is the set of differences with .✦ The walk segment of length of a walk is the set of its points at the times .✦ For each , a chosen difference pair is a pair of times in with , fixed once and for all✦, and the difference law of on its segment of length is the law of with drawn uniformly from ✦.
The difference kernel of a walk is the forward kernel of bound whose law at a time is that of the following advance: flip a fair coin, draw independently of it from the difference law of the walk on its segment of length , and advance by on heads and by on tails.✦ The common schedule of segment lengths and offset is the forward kernel (4)✦ The terminal time of the common schedule is the random time of law .
The Claim
Theorem 1.
Let be a walk in with steps at most , and let be finite sets of nonzero Gaussian integers. Let and be natural numbers, let be natural numbers with for and for , and let satisfy (5) for every and every integer with . Let be a random time on a finite probability space, with law , and let be the random time of law , the time followed by an independent uniform offset on . Then (6)✦
Under the hypotheses of (a) on , the sets , the lengths , , and , for all segment lengths the terminal time of the common schedule satisfies (7)✦
Let be a natural number and let , and be real numbers with for every and . Then (8)✦
In the paper, the result reads: for every fixed collection of prime choices, , with the paper’s variables and , the sum running over the batches of the primes in and the error tending to uniformly over the choices and the walks as the paper’s parameter tends to infinity.
What Is Checked
Parts (a) and (b) are stated over the residue classes of the walk modulo the multiples of nonzero Gaussian integers, its increment words (1) and the lattice ball of radius , and over the information (3) of a time law, the conditional mutual information (2) of a finite probability law at a random time. The time law is the advance of a law by the smoothing kernel in (a), and in (b) the advance of the exact start by the common schedule (4), built from difference kernels, difference laws and chosen difference pairs on the difference sets of walk segments. Part (c) is stated over real numbers alone.
The library also proves that every element of the difference set of a walk segment is a difference with and in .✦