Rogers sieving theorem

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 d₁, d₂, ..., d_n is easiest to understand when the lcm m of the d_i is their product, or equivalently d_i and d_j 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 d_i: the residue numeral system principle. The intersection will be a single progression with difference m.

The interest in sieve theory is in simultaneously excluding congruence classes for a number of moduli d_i. 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 d_i 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.

A simple situation occurs when d₂ divides d₁, because then the residue class modulo d₁ determines the residue class modulo d₂. The progressions P(1) given by r + kd₁ and P(2) given by s + ld₂ will have a non-empty intersection if and only if

r ≡ s modulo d₂

and then the condition modulo d₂ 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 d₁ = 12, and d₂ = 18. A numerical example is given by Das.^[3]

The result of Rogers states that number of surviving residue classes is bounded above by the number when the congruence conditions are t ≡ 0 modulo d_i for all i. In other words, when the "simple situation" cannot exclude anything because 0 ≡ 0 is automatic, the surviving classes are at a maximum.

It is possible to count those classes, in the special case. In fact the system of congruences is then equivalent to a system where the d_i are replaced by the powers of primes in the prime factorisation of the lcm m; and in this case the Chinese remainder theorem applies.

The original statement by Rogers, as modified by Heini Halberstam and Klaus Roth in their 1966 book Sequences, concerned minimising the natural density of the union of sets of progressions, when the offsets are varied. The minimum is attained for the offsets all set to 0.^[4] This approach looks at the complemented situation: the minimum union corresponds to the maximum non-sieved set.

• "Rogers' theorem on sieving". terrytao.wordpress.com. 19 January 2026.