Larger sieve explained

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

l{S} is a set of prime powers, N an integer, l{A} a set of integers in the interval [1, ''N''], such that for q\in l{S} there are at most g(q) residue classes modulo q , which contain elements of l{A} .

Then we have

| l{A}| \leq (\sum _{q\inl{S})/(Λ (q)) - log N}{\sum _{q\inl{S} } \frac - \log N},provided the denominator on the right is positive.^[1]

Applications

A typical application is the following result, for which the large sieve fails (specifically for

\theta> (1)/(2) ), due to Gallagher:^[2]

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 l{O}(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 l{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 l{S} .^[3]

References

• Patrick . Gallagher . Patrick X. Gallagher . A larger sieve . Acta Arithmetica . 18 . 1971 . 77–81 . 10.4064/aa-18-1-77-81 . free .
• Ernie . Croot . Christian . Elsholtz . Ernie Croot . On variants of the larger sieve . . 103 . 2004 . 3 . 243–254 . 10.1023/B:AMHU.0000028411.04500.e2 . free .

Notes and References

1. Gallagher 1971, Theorem 1
2. Gallagher, 1971, Theorem 2
3. Croot, Elsholtz, 2004