Rogers sieving theorem

The Rogers theorem on excluding congruence classes is an elementary result of C.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

Background

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. That means that the intersection can be read as a question on integers modulo m. The intersection of n progressions with differences d 1 , d 2 , ..., 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.

Sieving

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. 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 d 2 divides d 1

A simple situation occurs when d 2 divides d 1 , because then the residue class modulo d 1 determines the residue class modulo d 2 . The progressions P(1) given by r + kd 1 and P(2) given by s + ld 2 will have a non-empty intersection if and only if r ≡ s modulo d 2 and then the condition modulo d 2 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 1 = 12, and d 2 = 18. A numerical example is given by Das.

Statement of the theorem

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. This approach looks at the complemented situation: the minimum union corresponds to the maximum non-sieved set.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1350101824 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001350101824 · captured 2026-04-20 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Rogers sieving theorem”, snapshot enwiki-001350101824. https://encyclopegia.org/a/rogers-sieving-theorem

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.