查看“︁筛法”︁的源代码

'''筛法'''（Sieve Theory）是[[数论]]中的一类基本方法，其研究对象是筛函数，也就是某个被“筛选”过的有限整数子集的元素个数<ref name=HR1974>{{cite book|author=Halberstam, Heini and Richert, Hans-Egon|title=Sieve Methods|series=London Mathematical Society Monographs|volume=4|location=London-New York|publisher=Academic Press|year=1974|isbn=0-12-318250-6}}</ref>{{rp|5}}<ref name=PP1981>{{cite book|author=潘承洞、潘承彪|title=哥德巴赫猜想|series=纯粹数学与应用数学专著|volume=7|location=北京|publisher=科学出版社|year=1981}}</ref>{{rp|10,148-149}}。

[[埃拉托斯特尼筛法]]是一种古典筛法，但由于没有理论价值，在很长时期内都没有发展<ref name=PP1981/>{{rp|10}}；20世纪以来，筛法得到了改进。常见的筛法有[[布朗篩法]]、[[塞尔伯格筛法]]、[[图兰筛法]]和[[大筛法]]等等。另外作為現代篩法始祖的[[勒讓德篩法]]是[[埃拉托斯特尼筛法]]的簡單推廣，且是理解篩法的基礎，但很少有實際應用。

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

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

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

篩法的目標是估計「篩函數」（sifting function）的值，而「篩函數」表記如下：
:<math>S(\mathcal{A},\mathcal{P},z)=\sum\limits_{n\leq x, (n,P(z))=1}a_n.</math>
在<math>a_n=1_{A}(n)</math>的狀況下，這就單純是計算整數子集<math>A_{\operatorname{sift}}\subseteq A</math>中與<math>P(z)</math>的[[質因數]][[互質]]的元素個數。

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

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

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

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

:<math>S(\mathcal{A},\mathcal{P},z)=\sum\limits_{d\mid P(z)}\mu(d)A_d(x)</math>
其中<math>A_d(x)</math>的形式如下：
:<math>A_d(x)=\sum\limits_{n\leq x, n\equiv 0\pmod{d}}a_n.</math>
====範例====
設<math>z=7</math>及<math>\mathcal{P}=\mathbb{P}</math>，由於默比烏斯函數對所有的質數都呈負值之故，因此有下式：
:<math>\begin{align}
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{align}</math>

===同餘和估計===
我們可以假定說<math>A_d(x)</math>可以下式表達：
:<math>A_d(x)=g(d)X+r_d(x)</math>
其中<math>g(d)</math>是一個「密度」（density），也就是有如下形式的[[積性函數]]：
:<math>g(1)=1,\qquad 0\leq g(p)<1 \qquad p\in \mathbb{P}</math>
此外，此處的<math>X</math>是<math>A_1(x)</math>的估計，而<math>r_d(x)</math>則是餘項，因此篩函數可變為以下的形式：
:<math>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)</math>
或簡單地說，
:<math>S(\mathcal{A},\mathcal{P},z)=XG(x,z)+R(x,z).</math>

我們可透過找出<math>S</math>、<math>G</math>及<math>R</math>的[[上下界]]來估計篩函數。

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

另由於<math>g</math>是積性函數之故，因此也可研究下式：
:<math>\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}.</math>

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

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

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

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

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

==参考文献==
{{reflist}}

== 扩展阅读 ==

* {{SpringerEOM | title=Sieve method | id=Sieve_method&oldid=34162 | last=Bredikhin | first=B.M. | author-link= }}
* {{citation | last1= Cojocaru | first1 = Alina Carmen|author1-link= Alina Carmen Cojocaru | last2= Murty | first2= M. Ram | author-link2 = M. Ram Murty | title= An introduction to sieve methods and their applications | publisher= [[Cambridge University Press]] | year= 2006 | isbn= 0-521-84816-4 | series= London Mathematical Society Student Texts | volume= 66 | mr= 2200366 }}
*{{citation | last=Motohashi | first=Yoichi |title=Lectures on Sieve Methods and Prime Number Theory | series=Tata Institute of Fundamental Research Lectures on Mathematics and Physics | volume=72 | publisher=[[Springer-Verlag]] | date=1983 | isbn=3-540-12281-8 | location=Berlin | mr=0735437}}
* {{citation | last=Greaves | first=George | title=Sieves in number theory | series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3) | volume=43 | publisher=[[Springer-Verlag]] | year=2001 | isbn=3-540-41647-1 | location=Berlin | mr=1836967 | doi=10.1007/978-3-662-04658-6}}
* {{cite book | last=Harman | first=Glyn | author-link=Glyn Harman | title=Prime-detecting sieves | series=London Mathematical Society Monographs | volume=33 | publisher=Princeton University Press | year=2007 | isbn=978-0-691-12437-7 | zbl=1220.11118 | mr=2331072 | location=Princeton, NJ}}
* {{cite book | first1=Heini | last1=Halberstam | author-link1=Heini Halberstam | first2=Hans-Egon | last2=Richert | author-link2=Hans-Egon Richert | title=Sieve Methods | publisher=[[Academic Press]] | date=1974 | isbn=0-12-318250-6 | location=London-New York | mr=0424730 | series=London Mathematical Society Monographs | volume=4}} 
* {{citation | last1=Iwaniec | first1=Henryk | author-link1=Henryk Iwaniec | last2=Friedlander |first2= John | author-link2=John Friedlander | title=Opera de cribro | publisher=[[American Mathematical Society]] | date=2010 | isbn=978-0-8218-4970-5 | mr=2647984 | location=Providence, RI | series=American Mathematical Society Colloquium Publications | volume=57}}
* {{citation | last=Hooley | first=Christopher | author-link=Christopher Hooley | title=Applications of sieve methods to the theory of numbers | publisher=[[Cambridge University Press]] | date=1976 | isbn=0-521-20915-3 | series=Cambridge Tracts in Mathematics | volume=70 | location=Cambridge-New York-Melbourne | mr=0404173}}
* {{cite journal | title=Small gaps between primes | url=https://archive.org/details/sim_annals-of-mathematics_2015-01_181_1/page/383 | last=Maynard | first=James | author-link=James Maynard (mathematician) | year=2015 | journal=[[Annals of Mathematics]] | volume=181 | issue=1 | pages=383–413 | mr=3272929 | doi=10.4007/annals.2015.181.1.7 | arxiv=1311.4600 }}
* {{citation | title=Introduction to Analytic and Probabilistic Number Theory | first=Gérald | last=Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | year=1995 | isbn=0-521-41261-7 | pages=56–79 | mr=1342300 | others=Translated from the second French edition (1995) by C. B. Thomas }}
* {{cite journal | title = Bounded gaps between primes | url = https://archive.org/details/sim_annals-of-mathematics_2014-05_179_3/page/1121 | first = Yitang | last = Zhang | author-link=Yitang Zhang | journal = [[Annals of Mathematics]] | year=2014 | volume=179 | issue=3 | pages=1121–1174 | doi=10.4007/annals.2014.179.3.7  | mr=3171761 | doi-access=free }}


[[Category:筛法| ]]