The Setting
A rational prime splits in into two conjugate Gaussian primes, , and modulo either factor the residue classes of form a group of elements. For a finite set of such primes, a sign for each prime picks one of its two factors, and a random Gaussian integer has a residue modulo each factor picked. The question is how evenly the law of such a residue spreads over its classes, and in particular how many classes it leaves with much less than the fair share .
Split Prime Sieves
A split prime sieve is a finite set of rational primes together with a choice, for each , of a Gaussian prime of norm .✦ The enumeration of is a fixed bijection from onto , where .✦
For a Gaussian integer and a sign , the signed factor is the Gaussian integer given by (1)✦
Residue Classes
For a Gaussian integer , the multiples of , the products with , form the subgroup of .✦
For Gaussian integers and , the residue class of modulo is the element of the quotient group given by (2)✦
Finite Probability Laws
A finite probability law on a finite set is a function with for every and .✦
The Definition
Definition 1. Let be a split prime sieve with primes , listed by its enumeration. A signed index of is a pair of a sign pattern , one sign for each position, and a position ; the signed indices of form the set (3)✦ The prime of is ✦, and its factor is the signed factor ✦. The residue group at is the group of residue classes modulo , (4)✦ and the residue map at sends each Gaussian integer to its class (2) modulo : (5)✦ For a finite probability law on a finite set and a real number , the set of low residues of is (6)✦
In the paper, the result reads: a signed coordinate comes with a homomorphism from a lattice to a finite abelian group of order , and a random variable on an alphabet of size has coverage when .
For a finite probability law on a finite set , a real number and a threshold , the law has coverage at threshold when its set (6) of low residues has fewer than elements; the library counts the low residues against in place of .
What Is Checked
The definition is stated over a split prime sieve, with its primes , its Gaussian primes of norm and its enumeration; over the signed factors (1), the multiples of a Gaussian integer and the residue classes (2); and over finite probability laws on a finite set.
The library also establishes that taking coordinates in the basis of is a -linear isomorphism of onto .