Rogers sieving theorem
From Wikipedia, the free encyclopedia
The Rogers theorem on excluding congruence classes is an elementary result of C. A. Rogers in number theory from the 1960s, that for many years had the status of a folk theorem not well documented in published literature. After more than half a century, its value as a principle in contemporary sieve theory received recognition.
Arithmetic progressions of integers are sets of the form a + nd where n is any integer, and a (the offset) and d (the difference) are fixed. They can be intersected: the result may be empty, for example even numbers and odd numbers are disjoint. Otherwise, if two progressions have a number in common, there will be an arithmetic progression in common, with a difference that is the least common multiple (lcm) m of the differences in the two progressions.[1] That means that the intersection can be read as a question on integers modulo m.
The intersection of n progressions with differences d1, d2, ..., dn is easiest to understand when the lcm m of the di is their product, or equivalently di and dj have no common factor when i≠j. In that case the Chinese remainder theorem implies that congruences modulo m are the same as simultaneous congruences modulo all the di: the residue numeral system principle. The intersection will be a single progression with difference m.
Sieving
The interest in sieve theory is in simultaneously excluding congruence classes for a number of moduli di. In Boolean algebra terms, one intersects a number of sets of congruence classes defined by complementation. The underlying problem is to understand cases when the Chinese remainder theorem does not apply, because the di are not coprime in pairs. The use of disjunctive normal form is a standard technique for Boolean manipulations.[2] It here allows one to see that the result, at the progression level, is the union of a number of progressions, those resulting from non-empty intersections. These correspond to "surviving" (non-sieved) residue classes modulo m, and there arises the question of how many there might be.
Case when d2 divides d1
A simple situation occurs when d2 divides d1, because then the residue class modulo d1 determines the residue class modulo d2. The progressions P(1) given by r + kd1 and P(2) given by s + ld2 will have a non-empty intersection if and only if
- r ≡ s modulo d2
and then the condition modulo d2 is always satisfied. In other words, the intersection is P(1).
The smallest example not covered in this way, for the prime factors 2 and 3, is with d1 = 12, and d2 = 18. A numerical example is given by Das.[3]