Larger sieve

In number theory, the larger sieve is a sifting device invented by P. X. Gallagher. The name denotes a heightening of the large sieve. In fact, 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 ${\mathcal {S}}$ is a set of prime powers, N an integer, ${\mathcal {A}}$ a set of integers in the interval [1, N], such that for $q\in {\mathcal {S}}$ there are at most $g(q)$ residue classes modulo $q$ , which contain elements of ${\mathcal {A}}$ .

Then we have

|{\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}},

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

Applications

A typical application is the following result 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 ${\mathcal {O}}(N^{\theta })$ .

The large sieve cannot prove this statement for $\theta >{\frac {1}{2}}$ .

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 ${\mathcal {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 ${\mathcal {S}}$ .^[3]

Notes

↑ Gallagher 1971, Theorem 1
↑ Gallagher, 1971, Theorem 2
↑ Croot, Elsholtz, 2004

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 - version of the 3/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.