Larger sieve

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 $\mathcal{S}$ is a set of prime powers, N an integer, $\mathcal{A}$ a set of integers in the interval [1, N], such that for $q\in \mathcal{S}$ there are at most $g(q)$ residue classes modulo $q$, which contain elements of $\mathcal{A}$.

Then we have

$|\mathcal{A}| \leq \frac{\sum_{q\in\mathcal{S}} \Lambda(q) - \log N}{\sum_{q\in\mathcal{S}} \frac{\Lambda(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\leq N$, such that the order of $n$ modulo $p$ is $\leq N^\theta$ for all primes $p\leq N^{\theta+\epsilon}$ is $\mathcal{O}(N^\theta)$.

The large sieve cannot prove this statement for $\theta>\frac{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 $\mathcal{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 $\mathcal{S}$.