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 $q\in {𝒮}$ there are at most $g(q)$ residue classes modulo $q$, which contain elements of ${𝒜}$. Then we have

$|{𝒜}|\le \frac{\sum _{q\in {𝒮}}\mathrm{\Lambda }(q)-\log N}{\sum _{q\in {𝒮}}\frac{\mathrm{\Lambda }(q)}{g(q)}-\log N},$

provided the denominator on the right is positive.

Applications

A typical application is the following result, for which the large sieve fails (specifically for $\theta >\frac{1}{2}$), due to Gallagher: The number of integers $n\le N$, such that the order of $n$ modulo $p$ is $\le N^{\theta }$ for all primes $p\le N^{\theta +ϵ}$ is ${𝒪}(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 ${𝒮}$ 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 ${𝒮}$.

References

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