篩法

篩法（Sieve Theory）是數論中的一類基本方法，其研究對象是篩函數，也就是某個被「篩選」過的有限整數子集的元素個數。

埃拉托斯特尼篩法是一種古典篩法，但由於沒有理論價值，在很長時期內都沒有發展；20世紀以來，篩法得到了改進。常見的篩法有布朗篩法、塞爾伯格篩法、圖蘭篩法和大篩法等等。另外作為現代篩法始祖的勒讓德篩法是埃拉托斯特尼篩法的簡單推廣，且是理解篩法的基礎，但很少有實際應用。

直接對質數集合進行研究的效果不佳，因此研究者常常會改成估計與特定目標集合（如質數的集合）類似但較簡單的集合（如殆質數的集合）的元素個數，而通常這樣的集合其大小會稍微大於目標集合，但也較好分析。更加細緻的篩法也不直接研究集合本身，而是透過精心挑選的、對各集合的權重（也就是給部分集合較高的權重等作法）來計算集合元素個數；此外，在部分當代的研究中，研究者以篩法構造一個在集合中很大、但在集合外很小、且比集合本身的特徵函數還容易分析的函數，而非直接估計「被篩選」集合的元素個數。

基本篩法

首先我們從非負數的有限序列${\mathcal {A}}=(a_{n})$開始。在最基本的狀況中，這序列就只是我們要篩選的集合$A=\{s:s\leq x\}$的指示函數$a_{n}=1_{A}(n)$；然而，這樣的抽象化可套用在更一般的情境中。

接著我們引入一個稱為「篩選範圍」（sifting range）的質數集合${\mathcal {P}}\subseteq \mathbb {P}$，及這「篩選範圍」中不大於$z$的質數的乘積$P(z)=\prod \limits _{p\in {\mathcal {P}},p<z}p$，此處$P(z)$可視為一個對$z$的函數。

篩法的目標是估計「篩函數」（sifting function）的值，而「篩函數」表記如下：

$S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n\leq x,(n,P(z))=1}a_{n}.$

在$a_{n}=1_{A}(n)$的狀況下，這就單純是計算整數子集$A_{\operatorname {sift} }\subseteq A$中與$P(z)$的質因數互質的元素個數。

相關表記

下為此文表記的注意事項：

在文獻中，人們常將序列集合${\mathcal {A}}$與$A$本身等同，也就是說，可以將${\mathcal {A}}$表示成${\mathcal {A}}=\{s:s\leq x\}$以定義序列${\mathcal {A}}=(a_{n})$；

此外，在文獻中$A_{d}(x)$這和有時以集合$A_{d}(x)$的元素個數$|A_{d}(x)|$表示；然而此處我們因為已經將$A_{d}(x)$定義為元素個數之故，因此此處我們以 $\mathbb {P}$表示質數的集合，並以$(a,b)$表示$a$與$b$的最大公因數。

勒讓德等式

我們可透過默比烏斯函數及一組由${\mathcal {P}}$中的元素生成的函數$A_{d}(x)$，將篩選函數表述為一個稱為「勒讓德等式」（Legendre's identity）的函數：

$S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{d\mid P(z)}\mu (d)A_{d}(x)$

其中$A_{d}(x)$的形式如下：

$A_{d}(x)=\sum \limits _{n\leq x,n\equiv 0{\pmod {d}}}a_{n}.$

範例

設$z=7$及${\mathcal {P}}=\mathbb {P}$，由於默比烏斯函數對所有的質數都呈負值之故，因此有下式：

${\begin{aligned}S({\mathcal {A}},\mathbb {P} ,7)&=A_{1}(x)-A_{2}(x)-A_{3}(x)-A_{5}(x)+A_{6}+A_{10}+A_{15}-A_{30}.\end{aligned}}$

同餘和估計

我們可以假定說$A_{d}(x)$可以下式表達：

$A_{d}(x)=g(d)X+r_{d}(x)$

其中$g(d)$是一個「密度」（density），也就是有如下形式的積性函數：

$g(1)=1,\qquad 0\leq g(p)<1\qquad p\in \mathbb {P}$

此外，此處的$X$是$A_{1}(x)$的估計，而$r_{d}(x)$則是餘項，因此篩函數可變為以下的形式：

$S({\mathcal {A}},{\mathcal {P}},z)=X\sum \limits _{d\mid P(z)}\mu (d)g(d)+\sum \limits _{d\mid P(z)}\mu (d)r_{d}(x)$

或簡單地說，

$S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R(x,z).$

我們可透過找出$S$、$G$及$R$的上下界來估計篩函數。

篩函數的部分和會交替性地大於跟小於集合大小本身，而其餘項最終會變得非常大。瑋哥·布朗解決這問題的方法，是將篩函數中的$\mu (d)$以一個包含受限默比烏斯函數的權重序列$(\lambda _{d})$取代。透過選取兩個適當的序列$(\lambda _{d}^{-})$及$(\lambda _{d}^{+})$並將篩函數以$S^{-}$及$S^{+}$表示，可得到原始篩函數的下界與上界：

$S^{-}\leq S\leq S^{+}.$

另由於$g$是積性函數之故，因此也可研究下式：

$\sum \limits _{d\mid n}\mu (d)g(d)=\prod \limits _{\begin{array}{c}p|n;\;p\in \mathbb {P} \end{array}}(1-g(p)),\quad \forall \;n\in \mathbb {N} .$

篩法種類

當代的篩法包括了布朗篩法、塞爾伯格篩法、圖蘭篩法、大篩法、更大篩法以及GPY篩法等；而篩法的一個原始目的，就是嘗試證明孿生質數猜想等數論的問題。盡管篩法原始的目標依舊未達成，透過篩法學界依舊達成了部分目標，尤其在將此篩法與其他數論工具混合時更是如此。一些篩法取得的重要成果如下：

1. 布朗定理，這定理指出所有的孿生質數的倒數之和收斂（但所有質數的倒數之和發散）
2. 陳氏定理, 這定理指出，存在無限多的質數$p$，使得$p+2$要不就是質數，要不就是殆質數；而一個緊密相關的定理指出，任何一個充分大的偶數都可以表示成兩個質數的和或者一個質數及一個半質數（2次殆質數）的和。這兩個定理可分別視為與孿生質數猜想和哥德巴赫猜想最接近的定理。
3. 篩法基本引理，這引理指出如果要對一個有N個元素的整數集合進行篩選，那在$\varepsilon$（像是1/10之類的分數常用於此情況）足夠小的狀況下，經過$N^{\varepsilon }$個步驟後就能得到精確的估計；然而，盡管這引理在篩出質數方面太弱（一般而言，這需要大約$N^{1/2}$個步驟），但依舊足以證明殆質數方面的結果。
4. 弗里蘭-伊萬尼茲定理，這定理指出有無限多的質數可表成$a^{2}+b^{4}$的形式。
5. 張益唐定理，(Zhang 2014)這定理指出有無限多對的質數，其彼此的間隔是有限的；而梅那–陶定理（Maynard–Tao theorem）(Maynard 2015)將之推廣為存在任意長度的質數序列。

篩法技巧

篩法是一個相當強力的技巧，但這技巧受限於奇偶性問題（parity problem）；而粗略地說，奇偶性問題指的是篩法在辨別有奇數個質因數的數及有偶數個質因數的數方面極為困難。截至目前為止，學界對奇偶性問題尚未有充分的了解。

跟其他數論方法相比，篩法是一個相對「初等」的技巧，而之所以會說篩法「初等」，是因為篩法不需要用到諸如解析數論或代數數論等其他更為進階的理論的觀念；然而，更加進階的篩法也可變得非常複雜且細緻，尤其在與其他數論技巧混合時更是如此；此外，目前也有專門介紹篩法的教科書，其中一個經典著作是(Halberstam & Richert 1974)；而一個更為現代的著作則是(Iwaniec & Friedlander 2010)。

另外，本文中介紹的篩法與二次篩選法和普通數域篩選法等等作為整數質因數分解方法的篩選法並不密切相關，而這些質因數分解方法大多是利用埃拉托斯特尼篩法來有效率地決定一個數是否可以完全分解成小質數的演算法。

擴展閱讀

• Bredikhin, B.M., Sieve method, Hazewinkel, Michiel (編), 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4 
• Cojocaru, Alina Carmen; Murty, M. Ram, An introduction to sieve methods and their applications, London Mathematical Society Student Texts 66, Cambridge University Press, 2006, ISBN 0-521-84816-4, MR 2200366 
• Motohashi, Yoichi, Lectures on Sieve Methods and Prime Number Theory, Tata Institute of Fundamental Research Lectures on Mathematics and Physics 72, Berlin: Springer-Verlag, 1983, ISBN 3-540-12281-8, MR 0735437 
• Greaves, George, Sieves in number theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 43, Berlin: Springer-Verlag, 2001, ISBN 3-540-41647-1, MR 1836967, doi:10.1007/978-3-662-04658-6 
• Harman, Glyn. Prime-detecting sieves. London Mathematical Society Monographs 33. Princeton, NJ: Princeton University Press. 2007. ISBN 978-0-691-12437-7. MR 2331072. Zbl 1220.11118. 
• Halberstam, Heini; Richert, Hans-Egon. Sieve Methods. London Mathematical Society Monographs 4. London-New York: Academic Press. 1974. ISBN 0-12-318250-6. MR 0424730. 
• Iwaniec, Henryk; Friedlander, John, Opera de cribro, American Mathematical Society Colloquium Publications 57, Providence, RI: American Mathematical Society, 2010, ISBN 978-0-8218-4970-5, MR 2647984 
• Hooley, Christopher, Applications of sieve methods to the theory of numbers, Cambridge Tracts in Mathematics 70, Cambridge-New York-Melbourne: Cambridge University Press, 1976, ISBN 0-521-20915-3, MR 0404173 
• Maynard, James. Small gaps between primes. Annals of Mathematics. 2015, 181 (1): 383–413. MR 3272929. arXiv:1311.4600 . doi:10.4007/annals.2015.181.1.7. 
• Tenenbaum, Gérald, Introduction to Analytic and Probabilistic Number Theory, Cambridge studies in advanced mathematics 46, Translated from the second French edition (1995) by C. B. Thomas, Cambridge University Press: 56–79, 1995, ISBN 0-521-41261-7, MR 1342300 
• Zhang, Yitang. Bounded gaps between primes. Annals of Mathematics. 2014, 179 (3): 1121–1174. MR 3171761. doi:10.4007/annals.2014.179.3.7 .