Английская Википедия: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]Шаблон:Rp write: Шаблон:Quote Diamond & Halberstam[2]Шаблон:Rp attribute the terminology Fundamental Lemma to Jonas Kubilius.
Common notation
We use these notations:
- <math>A</math> is a set of <math>X</math> positive integers, and <math>A_d</math> is its subset of integers divisible by <math>d</math>
- <math>w(d)</math> and <math>R_d</math> are functions of <math>A</math> and of <math>d</math> that estimate the number of elements of <math>A</math> that are divisible by <math>d</math>, according to the formula
- <math> \left\vert A_d \right\vert = \frac{w(d)}{d} X + R_d . </math>
- Thus <math>w(d)/d</math> represents an approximate density of members divisible by <math>d</math>, and <math>R_d</math> represents an error or remainder term.
- <math>P</math> is a set of primes, and <math>P(z)</math> is the product of those primes <math>\leq z</math>
- <math>S(A, P, z)</math> is the number of elements of <math>A</math> not divisible by any prime in <math>P</math> that is <math>\leq z</math>
- <math>\kappa</math> is a constant, called the sifting density,[3]Шаблон:Rp 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
This formulation is from Tenenbaum.[4]Шаблон:Rp Other formulations are in Halberstam & Richert,[1]Шаблон:Rp in Greaves,[3]Шаблон:Rp and in Friedlander & Iwaniec.[5]Шаблон:Rp We make the assumptions:
- <math>w(d)</math> is a multiplicative function.
- The sifting density <math>\kappa</math> satisfies, for some constant <math>C</math> and any real numbers <math>\eta</math> and <math>\xi</math> with <math>2\leq \eta\leq \xi</math>:
- <math>\prod_{\eta \le p \le \xi} \left( 1 - \frac{w(p)}{p} \right) ^{-1} < \left( \frac{\ln \xi}{\ln \eta} \right) ^\kappa \left( 1 + \frac{C}{\ln \eta} \right). </math>
There is a parameter <math>u\geq 1</math> that is at our disposal. We have uniformly in <math>A</math>, <math>X</math>, <math>z</math>, and <math>u</math> that
- <math>S(a,P,z) = X \prod_{p \le z, p \in P} \left( 1 - \frac{w(p)}{p} \right) \{1 + O(u^{-u/2})\} + O\left(\sum_{d \le z^u, d|P(z)} |R_d| \right).</math>
In applications we pick <math>u</math> 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
This formulation is from Halberstam & Richert.[1]Шаблон:Rp Another formulation is in Diamond & Halberstam.[2]Шаблон:Rp
We make the assumptions:
- <math>w(d)</math> is a multiplicative function.
- The sifting density <math>\kappa</math> satisfies, for some constant <math>C</math> and any real numbers <math>\eta</math> and <math>\xi</math> with <math>2\leq \eta\leq \xi</math>:
<math> \qquad \sum_{\eta \le p \le \xi} \frac{w(p) \ln p}{p} < \kappa \ln \frac{\xi}{\eta} + C. </math>
- <math>\frac{w(p)}{p} < 1-c</math> for some small fixed <math>c</math> and all <math>p</math>.
- <math>|R(d)|\leq w(d)</math> for all squarefree <math>d</math> whose prime factors are in <math>P</math>.
The fundamental lemma has almost the same form as for the combinatorial sieve. Write <math>u = \ln{X} /\ln{z}</math>. The conclusion is:
- <math>S(a,P,z) = X \prod_{p \le z,\ p \in P} \left( 1 - \frac{w(p)}{p} \right) \{1 + O(e^{-u/2})\}.</math>
Note that <math>u</math> is no longer an independent parameter at our disposal, but is controlled by the choice of <math>z</math>.
Note that the error term here is weaker than for the fundamental lemma of the combinatorial sieve. Halberstam & Richert remark:[1]Шаблон:Rp "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
