Larger sieve

Sieve invented by Patrick X. Gallagher

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 S {\displaystyle {\mathcal {S}}} is a set of prime powers, N an integer, A {\displaystyle {\mathcal {A}}} a set of integers in the interval [1, N], such that for q ∈ S {\displaystyle q\in {\mathcal {S}}} there are at most g ( q ) {\displaystyle g(q)} residue classes modulo q {\displaystyle q} , which contain elements of A {\displaystyle {\mathcal {A}}} .

Then we have

| A | ≤ ∑ q ∈ S Λ ( q ) − log ⁡ N ∑ q ∈ S Λ ( q ) g ( q ) − log ⁡ N , {\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]

Applications

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

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

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

Notes

  1. ^ Gallagher 1971, Theorem 1
  2. ^ Gallagher, 1971, Theorem 2
  3. ^ Croot, Elsholtz, 2004

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.