Larger sieve

Suppose that ${\displaystyle {\mathcal {S}}}$ is a set of prime powers, N an integer, ${\displaystyle {\mathcal {A}}}$ a set of integers in the interval [1, N], such that for ${\displaystyle q\in {\mathcal {S}}}$ there are at most ${\displaystyle g(q)}$ residue classes modulo ${\displaystyle q}$, which contain elements of ${\displaystyle {\mathcal {A}}}$.

Then we have

${\displaystyle |{\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]

A typical application is the following result, for which the large sieve fails (specifically for ${\displaystyle \theta >{\frac {1}{2}}}$), due to Gallagher:[2]

The number of integers ${\displaystyle n\leq N}$, such that the order of ${\displaystyle n}$ modulo ${\displaystyle p}$ is ${\displaystyle \leq N^{\theta }}$ for all primes ${\displaystyle p\leq N^{\theta +\epsilon }}$ is ${\displaystyle {\mathcal {O}}(N^{\theta })}$.

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

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