Top Qs
Timeline
Chat
Perspective

Larger sieve

Sieve invented by Patrick X. Gallagher From Wikipedia, the free encyclopedia

Remove ads

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.

Remove ads

Statement

Summarize
Perspective

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]

Remove ads

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]

Remove ads

Notes

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads