筛法基本引理

在数论上，筛法基本引理（fundamental lemma of sieve theory）指的是数个对于把筛法套用到特定问题上的过程进行系统化结果。哈巴施潭（英语：Heini Halberstam）与理希（英语：Hans-Egon Richert） ^[1]:92–93写道：

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

贾盟（Diamond）与哈巴施潭（英语：Heini Halberstam）^[2]:42认为“基本引理”一词源自约拿·古必柳（英语：Jonas Kubilius）。

共通符号

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

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

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

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

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

组合筛法基本引理

以下公式表示取自太能保母（Tenenbaum）。^[4]:60，其他的公式表示则可见于哈巴施潭（英语：Heini Halberstam）与理希（英语：Hans-Egon Richert）、^[1]:82、葛里维斯（Greaves）及^[3]:92及弗里兰（英语：John Friedlander）与伊万尼兹等人的著作。^{[5]:732–733}

我们首先作出如下假设：

• ${\displaystyle w(d)}$是一个积性函数。
• 对于某个常数${\displaystyle C}$及任意满足${\displaystyle 2\leq \eta \leq \xi }$的实数${\displaystyle \eta }$及${\displaystyle \xi }$而言，筛选密度${\displaystyle \kappa }$满足如次条件：${\displaystyle \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).}$

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

${\displaystyle 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).}$

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

塞尔伯格筛法基本引理

以下公式表示取自哈巴施潭（英语：Heini Halberstam）与理希（英语：Hans-Egon Richert）的结果^{[1]:208–209}；另一个公式表示可见于贾盟（Diamond）与哈巴施潭（英语：Heini Halberstam）的结果。^[2]:29

我们首先作出如下假设：

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

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

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

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

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