Fundamental lemma of sieve theory

In number theory, the fundamental lemma of sieve theory is any of several results that systematize the process of applying sieve methods to particular problems. Halberstam & Richert [1]: 92–93  write:

A curious feature of sieve literature is that while there is frequent use of Brun's method there are only a few attempts to formulate a general Brun theorem (such as Theorem 2.1); as a result there are surprisingly many papers which repeat in considerable detail the steps of Brun's argument.

Diamond & Halberstam[2]: 42  attribute the terminology Fundamental Lemma to Jonas Kubilius.

Common notation

edit

We use these notations:

  •   is a set of   positive integers, and   is its subset of integers divisible by  
  •   and   are functions of   and of   that estimate the number of elements of   that are divisible by  , according to the formula
 
Thus   represents an approximate density of members divisible by  , and   represents an error or remainder term.
  •   is a set of primes, and   is the product of those primes  
  •   is the number of elements of   not divisible by any prime in   that is  
  •   is a constant, called the sifting density,[3]: 28  that appears in the assumptions below. It is a weighted average of the number of residue classes sieved out by each prime.

Fundamental lemma of the combinatorial sieve

edit

This formulation is from Tenenbaum.[4]: 60  Other formulations are in Halberstam & Richert,[1]: 82  in Greaves,[3]: 92  and in Friedlander & Iwaniec.[5]: 732–733  We make the assumptions:

  •   is a multiplicative function.
  • The sifting density   satisfies, for some constant   and any real numbers   and   with  :
 

There is a parameter   that is at our disposal. We have uniformly in  ,  ,  , and   that

 

In applications we pick   to get the best error term. In the sieve it is related to the number of levels of the inclusion–exclusion principle.

Fundamental lemma of the Selberg sieve

edit

This formulation is from Halberstam & Richert.[1]: 208–209  Another formulation is in Diamond & Halberstam.[2]: 29 

We make the assumptions:

  •   is a multiplicative function.
  • The sifting density   satisfies, for some constant   and any real numbers   and   with  :

 

  •   for some small fixed   and all  .
  •   for all squarefree   whose prime factors are in  .

The fundamental lemma has almost the same form as for the combinatorial sieve. Write  . The conclusion is:

 

Note that   is no longer an independent parameter at our disposal, but is controlled by the choice of  .

Note that the error term here is weaker than for the fundamental lemma of the combinatorial sieve. Halberstam & Richert remark:[1]: 221  "Thus it is not true to say, as has been asserted from time to time in the literature, that Selberg's sieve is always better than Brun's."

Notes

edit
  1. ^ a b c d Halberstam, Heini; Richert, Hans-Egon (1974). Sieve Methods. London Mathematical Society Monographs. Vol. 4. London: Academic Press. ISBN 0-12-318250-6. MR 0424730.
  2. ^ a b Diamond, Harold G.; Halberstam, Heini (2008). A Higher-Dimensional Sieve Method: with Procedures for Computing Sieve Functions. Cambridge Tracts in Mathematics. Vol. 177. With William F. Galway. Cambridge: Cambridge University Press. ISBN 978-0-521-89487-6.
  3. ^ a b Greaves, George (2001). Sieves in Number Theory. Berlin: Springer. ISBN 3-540-41647-1.
  4. ^ Tenenbaum, Gérald (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge: Cambridge University Press. ISBN 0-521-41261-7.
  5. ^ Friedlander, John; Henryk Iwaniec (1978). "On Bombieri's asymptotic sieve". Annali della Scuola Normale Superiore di Pisa; Classe di Scienze. 4e série. 5 (4): 719–756. Retrieved 2009-02-14.