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

Then we have

:$, \mathcal, \leq \frac,$
provided the denominator on the right is positive.

Applications

A typical application is the following result, for which the large sieve fails (specifically for $\theta>\frac$), 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^$ is $\mathcal(N^\theta)$.

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$ 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$.Croot, Elsholtz, 2004

Notes

References

*
* {{cite journal , first1=Ernie , last1=Croot , first2 = Christian , last2 = Elsholtz , author-link=Ernie Croot , title=On variants of the larger sieve , journal= Acta Mathematica Hungarica , volume=103 , year=2004 , issue=3 , pages=243–254 , doi=10.1023/B:AMHU.0000028411.04500.e2 , doi-access=free

Sieve theory