Larger sieve - Alchetron, The Free Social Encyclopedia

In number theory, the larger sieve is a sifting device invented by P. X. Gallagher. The name denotes a heightening of the large sieve. In fact, 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 S is a set of prime powers, N an integer, A a set of integers in the interval [1, N], such that for q ∈ S there are at most g ( q ) residue classes modulo q , which contain elements of A .

Then we have

| A | ≤ ∑ q ∈ S Λ ( q ) − log ⁡ N ∑ q ∈ S Λ ( q ) g ( q ) − log ⁡ N ,

provided the denominator on the right is positive.

Applications

A typical application is the following result due to Gallagher.

The number of integers n ≤ N , such that the order of n modulo p is ≤ N θ for all primes p ≤ N θ + ϵ is O ( N θ ) .

The large sieve cannot prove this statement for θ > 1 2 .

If the number of excluded residue classes modulo p varies with p , then the larger sieve is often combined with the large sieve. The larger sieve is applied with the set S 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 S .

References

Larger sieve Wikipedia

(Text) CC BY-SA

Contents

Statement

Applications

References