{{Short description|Sieve invented by Patrick X. Gallagher}} 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 <math>\mathcal{S}</math> is a set of prime powers, ''N'' an integer, <math>\mathcal{A}</math> a set of integers in the interval [1,&nbsp;''N''], such that for <math>q\in \mathcal{S}</math> there are at most <math>g(q)</math> residue classes modulo <math>q</math>, which contain elements of <math>\mathcal{A}</math>.

Then we have

:<math>|\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}, </math> provided the denominator on the right is positive.<ref>Gallagher 1971, Theorem 1</ref>

== Applications ==

A typical application is the following result, for which the large sieve fails (specifically for <math>\theta>\frac{1}{2}</math>), due to Gallagher:<ref>Gallagher, 1971, Theorem 2</ref>

{{Math theorem |math_statement = The number of integers <math>n\leq N</math> such that the order of <math>n</math> modulo <math>p</math> is <math>\leq N^\theta</math> for all primes <math>p\leq N^{\theta+\epsilon}</math> is <math>\mathcal{O}(N^\theta)</math>. }}

If the number of excluded residue classes modulo <math>p</math> varies with <math>p</math>, then the larger sieve is often combined with the large sieve. The larger sieve is applied with the set <math>\mathcal{S}</math> 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 <math>\mathcal{S}</math>.<ref>Croot, Elsholtz, 2004</ref>

== Notes ==

{{Reflist|2}}

== References ==

* {{cite journal | first=Patrick | last=Gallagher | author-link=Patrick X. Gallagher | title=A larger sieve | journal=Acta Arithmetica | volume=18 | year=1971 | pages=77–81 | doi=10.4064/aa-18-1-77-81 | doi-access=free }} * {{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 }}

Category:Sieve theory