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

edit

Suppose that   is a set of prime powers, N an integer,   a set of integers in the interval [1, N], such that for   there are at most   residue classes modulo  , which contain elements of  .

Then we have

 

provided the denominator on the right is positive.[1]

Applications

edit

A typical application is the following result, for which the large sieve fails (specifically for  ), due to Gallagher:[2]

The number of integers  , such that the order of   modulo   is   for all primes   is  .

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

Notes

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

References

edit
  • Gallagher, Patrick (1971). "A larger sieve". Acta Arithmetica. 18: 77–81. doi:10.4064/aa-18-1-77-81.
  • Croot, Ernie; Elsholtz, Christian (2004). "On variants of the larger sieve". Acta Mathematica Hungarica. 103 (3): 243–254. doi:10.1023/B:AMHU.0000028411.04500.e2.