筛法基本引理

在数论上，筛法基本引理（fundamental lemma of sieve theory）指的是数个对于把筛法套用到特定问题上的过程进行系统化结果。哈巴施潭与理希 写道：

筛法文献一个引人好奇的特性是尽管人们常用布朗筛法，但仅有少数人尝试为布朗‘定理’（如定理2.1）给出一个一般公式；而这结果就是，有令人惊讶多的论文不断地在许多细节上，重复布朗的论证。

贾盟（Diamond）与哈巴施潭认为“基本引理”一词源自约拿·古必柳。

共通符号

此条目中，我们使用以下的符号：

• $A$是一个有$X$个正整数的集合，而$A_{d}$则是由可被$d$除尽的正整数组成的子集。
• $w(d)$及$R_{d}$是$A$与$d$的函数，这些函数可用以估计$A$中可被$d$除尽的元素的个数。而我们有以下的公式：

$\left\vert A_{d}\right\vert ={\frac {w(d)}{d}}X+R_{d}.$

因此，$w(d)/d$表示能被$d$除尽的元素的大致密度；而$R_{d}$则表示剩余项或误差。

• $P$是一个质数的集合，而$P(z)$则是所有不大于$\leq z$的质数的乘积。
• $S(A,P,z)$是$A$中不为任何$P$中不大于$\leq z$的质数除尽的元素的数量。
• $\kappa$是一个常数，又称作筛选密度（sifting density）。这筛选密度会出现在以下的假设中，表示被每个质数筛掉的同余类数量的加权平均。

组合筛法基本引理

以下公式表示取自太能保母（Tenenbaum）。，其他的公式表示则可见于哈巴施潭与理希、、葛里维斯（Greaves）及及弗里兰与伊万尼兹等人的著作。

我们首先作出如下假设：

• $w(d)$是一个积性函数。
• 对于某个常数$C$及任意满足$2\leq \eta \leq \xi$的实数$\eta$及$\xi$而言，筛选密度$\kappa$满足如次条件：$\prod _{\eta \leq p\leq \xi }\left(1-{\frac {w(p)}{p}}\right)^{-1}<\left({\frac {\ln \xi }{\ln \eta }}\right)^{\kappa }\left(1+{\frac {C}{\ln \eta }}\right).$

对于$A$、$X$、$z$及$u$而言，我们有以下等式。此公式中的$u\geq 1$由使用者自行决定其数值：

$S(A,P,z)=X\prod _{p\leq z,p\in P}\left(1-{\frac {w(p)}{p}}\right)\{1+O(u^{-u/2})\}+O\left(\sum _{d\leq z^{u},d|P(z)}|R_{d}|\right).$

在实际应用中，可对$u$进行选取已得到最佳的结果。在这筛法中，其数值取决于容斥原理的使用层级数。

塞尔伯格筛法基本引理

以下公式表示取自哈巴施潭与理希的结果；另一个公式表示可见于贾盟（Diamond）与哈巴施潭的结果。

我们首先作出如下假设：

• $w(d)$是一个积性函数。
• 对于某个常数$C$及任意满足$2\leq \eta \leq \xi$的实数$\eta$及$\xi$而言，筛选密度$\kappa$满足如次条件：$\qquad \sum _{\eta \leq p\leq \xi }{\frac {w(p)\ln p}{p}}<\kappa \ln {\frac {\xi }{\eta }}+C.$
• 对于一些小且固定的$c$及所有的$p$而言，${\frac {w(p)}{p}}<1-c$。
• 对于所有无平方因子、且质因数位于$P$中的$d$而言，$|R(d)|\leq w(d)$。

使用上述的假定，塞尔伯格筛法基本引理跟组合筛法基本引理几乎相同。设$u=\ln {X}/\ln {z}$，则有如次结论：

$S(A,P,z)=X\prod _{p\leq z,\ p\in P}\left(1-{\frac {w(p)}{p}}\right)\{1+O(e^{-u/2})\}.$

应当注意的是，在我们的处理中，$u$不再是一个独立参数，而是一个取决于$z$的参数。

另外值得注意的是，此处的误差项弱于上述组合筛法基本引理的误差项；而哈巴施潭与理希对此写道说：“因此一直以来许多文献假定的‘塞尔伯格筛法总是比布朗筛法还要好’的这说法不全然为真。”