The Setting
Let be a walk in with steps at most , and let be a finite set of rational primes , each with a chosen Gaussian prime of norm . From a time the walk advances a random number of steps, and the displacement is reduced modulo or , landing in one of residue classes. For a threshold , a class is low when its probability is below , and the displacement covers the classes well when few of them are low.
Theorem 5.2 asks how coverage passes back in time. A first random advance is followed by a second, drawn afresh at the time where the first one ends. If the second covers well for most moduli, what must hold of the first for the combined advance to cover well? The answer is phrased through the entropy of the residues of the point that the first advance reaches.
The claim also has an abstract form, in which finite abelian groups , for coordinates of a finite set weighted by a law , stand for the residue rings. A random state has a value in each ; a random step , drawn from a law that depends on , has an image in each ; and further steps , drawn independently from , are continuation data shared by all coordinates. Coverage is asked of , knowing coverage of and how little the entropy of given the shared data falls below .
Laws, Entropy and Low Residues
A finite probability law on a finite set is a function with nonnegative values that sum to ✦; it gives a subset of the probability ✦. The uniform law on a nonempty finite set gives every point the mass , and the proportion of a subset of is its probability under the uniform law.✦ The pushforward of along a map to a finite set is the law of for drawn from : it gives the mass .✦
The joint law of a law on a finite set and laws on a finite set , one for each , is the law on with mass at , the law of when is drawn from and then from .✦ The -fold independent repetition of a law on is the law on with mass at .✦
The entropy of a random variable on a finite set carrying a law is , the sum running over the values of and denoting probability under that law.✦ The conditional entropy of given a second random variable on the same set is .✦
The set of low residues of a law on a finite set at threshold is (1)✦ A law on a residue ring of classes has coverage when it has fewer than low residues. The claim counts low residues against a threshold in place of .
For a finite abelian group , a subset of , reals and , and elements of , the coverage list of is the set of for which few of the shifts land in : (2)✦
Residues Along a Walk
A split prime sieve is a finite set of rational primes together with, for each , a Gaussian prime of norm .✦ The primes of a split prime sieve are listed once and for all as , and the mean of their logarithms is .
A signed prime index of is a pair of a sign vector and a position ; there are of them.✦ For a sign vector , is when and its conjugate when .✦ The prime of is ✦, and its signed factor is ✦. The residue ring at is the quotient of by the multiples of ✦, and is the class of in it✦.
For a random Gaussian integer on a finite set carrying a law, and , the averaged signed residue entropy is the mean, over sign vectors and orderings of the positions, all taken uniformly, of the entropy of the residues of modulo the signed factors at the first positions in the order , all of them when .✦ For , (3)✦
A forward kernel consists of a bound and, for each time , a law on the advances .✦ The composite of forward kernels and is the forward kernel with bound whose law at time is the law of , where is drawn from and then from .✦ For a walk , a forward kernel , a time and a signed index , the relative residue law is the law of for drawn from .✦
The Claim
Theorem 1. Let , , and ; in (a), (b) and (d), let also , and be reals with and . In (a), (b) and (c), is a law on a finite set and a law on a finite set for each ; probabilities are taken with drawn from and then a step from , and conditional entropies with drawn from and then independently from . In (a) and (b), is a law on a finite set , each has a finite abelian group and maps and , and is a real with (4)
Let , and let for with . Suppose that each has a nonempty set with and , a real with , and, for each , a set with off which gives every element probability at least . Then (5)✦
Let be the law of , and let , and be reals with , and for every . If , then (6)✦
Let be a finite abelian group with maps and , let be a nonempty set with , a real and , and for each let be a set with off which gives every element probability at least . If (7)✦ then the shared steps force a deficit , bounded below through the probability that lies in the coverage list (2) of .
Let be a split prime sieve with primes, a walk with steps at most , and forward kernels with , a time, an integer with , and a real with . For each signed index let , and be reals with , and . Suppose that the point , with drawn from , has , and that at every time the signed indices with form a proportion at most . Then (8)✦
In the paper, the result reads: in the experiment with , drawn independently from and , where , , , , and , if at every all but a fraction of the coordinates have coverage for given , and , , , , , and , then all but a fraction of the coordinates have coverage for . The symbols , , , , , , , , , and are the paper’s own.
What Is Checked
The claim is stated over finite probability laws with their probabilities, uniform laws, pushforwards, joint laws and independent repetitions, over entropy and conditional entropy, the low residues (1) and the coverage list (2), and, for the walk, over split prime sieves with their signed prime indices, signed factors, residue rings and mean , the averaged signed residue entropy (3), forward kernels, their composites and their relative residue laws. The library also shows that a split prime sieve with at least one prime has a signed prime index.✦