Larger sieve


In number theory, the larger sieve is a sieve invented by Patrick X. Gallagher. The name denotes a heightening of the large sieve. Combinatorial sieves like the Selberg sieve are strongest, when only a few residue classes are removed, while the term large sieve means that this sieve can take advantage of the removal of a large number of up to half of all residue classes. The larger sieve can exploit the deletion of an arbitrary number of classes.

Statement

Suppose that is a set of prime powers, N an integer, a set of integers in the interval , such that for there are at most residue classes modulo, which contain elements of.
Then we have
provided the denominator on the right is positive.

Applications

A typical application is the following result, for which the large sieve fails, due to Gallagher:
The number of integers, such that the order of modulo is for all primes is.
If the number of excluded residue classes modulo varies with, then the larger sieve is often combined with the large sieve. The larger sieve is applied with the set above defined to be the set of primes for which many residue classes are removed, while the large sieve is used to obtain information using the primes outside.