The Setting
Each rational prime is the norm of a Gaussian prime , and , so a Gaussian integer has two residues above : one modulo and one modulo . For a random Gaussian integer and a finite set of such primes, the question is how much these residues reveal about , and how that information accumulates as the primes are taken one at a time, each through one of its two factors.
The item also concerns a walk in and a way to move a random time forward along it by at most steps, steered by the differences between the points of a stretch of the walk.
The library defines these objects and states a concavity result for the entropy of the first coordinates of a random vector.
Laws, Residues and Times
A finite probability law on a finite set is a nonnegative function on whose values sum to one.✦ The uniform law on a nonempty finite set gives each element the mass ✦, and the pushforward of along a map from to a finite set is the law on with .✦ Given a law on a finite set and, for each , a law on , the joint law on gives the mass .✦ A random variable on , with values in any set, has entropy in natural logarithms, the sum running over the finitely many values of .✦
Let be a random vector on with coordinates in a set . For a permutation of and , the prefix of of length in the order is the random vector of its first coordinates in that order, (1)✦
A split prime sieve is a finite set of rational primes together with a Gaussian prime of norm for each ✦; its primes are listed once and for all as .✦ A sign vector is an element of . The signed factor of with sign is , and with sign its conjugate .✦ The residue class of a Gaussian integer modulo a Gaussian integer is the set of Gaussian integers that differ from by a multiple of , an element of .✦
A time law of last time is a finite probability law on , the law of a random time at most .✦ A forward kernel of bound assigns to each time a finite probability law on the advances , an advance being a number of steps taken forward from .✦ For a statement , write for when holds and otherwise.
The Claim
Definition 1. Let be a split prime sieve with primes , and a finite probability law on a finite set . The residue vector of with signs is (2)✦ For a random vector on with coordinates and , the random-order prefix entropy of at is the mean, over the permutations of , of the entropy of the prefix of length in the order , (3)✦ and is the ordered entropy profile of . For a family of such random vectors, one for each sign vector, the sign-averaged entropy at is (4)✦ The point entropy of a random Gaussian integer on , its averaged signed residue entropy, is the sign-averaged entropy of the family of its residue vectors: (5)✦ For a walk in and , the walk segment of length is (6)✦ and the difference set of a finite set is (7)✦ Each difference has a representative, a pair of times of the segment fixed once and for all with (8)✦ and the difference law is the law on of the representative of a difference drawn uniformly from : (9)✦ For a time , the shifted walk is , with segment . The difference transition takes a time law of last time to its step, the time law of last time given by (10)✦ The difference kernel of the walk and the bound , the difference transition as a forward kernel, is the forward kernel of bound that assigns to each time the law on given by (11)✦
Theorem 1. Let be a finite probability law on a finite set and a random vector on with coordinates in a set . Then the ordered entropy profile of is concave on : for every with , (12)✦
What Is Checked
The definitions and the theorem are stated over an arbitrary split prime sieve, finite probability laws on finite sets, random vectors with coordinates in any set, any walk in , any segment length and any time law.