The Setting
Let be a rational prime. It splits in as with a Gaussian prime and its complex conjugate, and a Gaussian integer has two residues at , one modulo and one modulo , each in a ring of elements. For a random Gaussian integer with a finite law, each of these residues has entropy at most , the entropy of the uniform law on points.
Take a finite set of such primes. Suppose that the residues of modulo one factor of each of many of these primes, the factor being chosen by a sign (these are the signed residues of ), together carry nearly the largest entropy they can, and that one knows data of small entropy, correlated with . How far can the residue of modulo a single factor, given , fall short of , on average over the prime and over the choice between and ? The library states a bound on that average, alongside a general inequality comparing the entropy of a random prefix of a random vector with the entropies of its coordinates given .
Entropy of Finite Laws
A finite probability law on a finite set is a function that is nonnegative at every point and whose values sum to one.✦ The uniform law on a nonempty finite set is the law that gives each element the mass .✦ Throughout, a mean over a finite set of values of is the mean under the uniform law on that set.
The entropy of a random variable on , with values in any set, is the Shannon entropy of its law, (1)✦ the sum running over the finitely many values that takes. The conditional entropy of given a random variable on is (2)✦ where is the random variable .
A random vector on with coordinates in a set is a random variable with values in . For a permutation of and a natural number , the prefix of of length in the order is the random vector with entries in together with a blank symbol whose entry in position is if and otherwise.✦ The random-order prefix entropy of at is the mean of the entropy of this prefix over the permutations : (3)✦
A sign vector of length is a choice of a sign or in each position, and is the set of them. For a family of random vectors on with coordinates in , the sign-averaged entropy of at is (4)✦
Split Prime Sieves and Residues
A split prime sieve is a finite set of rational primes together with, for each , a Gaussian prime of norm .✦ The prime enumeration of is a fixed listing of its primes✦, and the mean log of its primes is (5)✦
The signed factor of a Gaussian integer with a sign is for the sign and for the sign .✦ A signed index of is a pair of a sign vector and a position .✦ The prime of is , whatever ✦, and the signed factor at is .
The multiples of a Gaussian integer form the subgroup of , the lattice spanned by and .✦ The residue class of a Gaussian integer modulo is its class in the quotient .✦ For a signed index , the residue ring at is ✦, and the residue map sends each Gaussian integer to its residue class modulo .✦
The residue code of modulo is the natural number that labels the residue class of in a fixed numbering of the classes modulo .✦ For a sign vector , the residue vector of a Gaussian integer with signs is the vector of codes (6)✦
A point variable is a random variable on with values in . The averaged signed residue entropy of a point variable at a natural number , for a split prime sieve , is the sign-averaged entropy at of the family of the residue vectors of : (7)✦
The Claim
Theorem 1. Let be a finite probability law on a finite set , let be a random variable on with values in any set, and let be a natural number.
(a) Let be a split prime sieve with primes and , let be a point variable, a Gaussian integer, and , real numbers. If and , then, with the mean over the signed indices of , (8)✦
(b) Let be a split prime sieve with primes and , and let be a point variable. Then, with the means over and , (9)✦
(c) Let be a family of random vectors on with coordinates, and . Then, with the means over and , (10)✦
(d) Let be a random vector on with coordinates, and . Then, with the mean over , (11)✦
In the paper, the result reads: for a point variable and data with a finite joint law, the selection of signs and ordering being made independently of them, if and for a number , then the mean over signed indices of is at most , with , , , , , , and standing for the paper’s , , , , , , and .
What Is Checked
The four inequalities are stated over finite probability laws, the entropy and conditional entropy of random variables, and the random-order and sign-averaged prefix entropies of random vectors. Parts (a) and (b) are stated also over a split prime sieve with its prime enumeration, mean log and signed indices, the uniform law on those indices, the residue maps and residue vectors modulo the signed factors, and the averaged signed residue entropy of a point variable.
Beyond the claim, the library proves that a split prime sieve with at least one prime has a signed index.✦