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 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

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

  1. Gallagher 1971, Theorem 1
  2. Gallagher, 1971, Theorem 2
  3. Croot, Elsholtz, 2004
gollark: We implemented it.
gollark: Macron 3.
gollark: Ugh, `await irc.psend(&"MODE {ev.prefix} +o")` you.
gollark: `→ :osmarks-stats LUSERS test.apionet.irc test.apionet.irc (prefix: "osmarks-stats", command: "LUSERS", params: @["test.apionet.irc", "test.apionet.irc"])`
gollark: This annoying IRC user keeps calling me `LUSERS`.

References

  • Gallagher, Patrick (1971). "A larger sieve". Acta Arithmetica. 18: 77–81.
  • Croot, Ernie; Elsholtz, Christian (2004). "On variants of the larger sieve". Acta Mathematica Hungarica. 103: 243–254.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.