查看“︁塞尔伯格筛法”︁的源代码

[[File:Atle Selberg.jpg|thumb|阿特勒·塞爾伯格]]
在[[數論]]中，'''塞爾伯格篩法'''（Selberg sieve）是一個用以估計滿足特定條件的「篩選過的」[[正整數]]集大小的技巧，而這些條件一般都以[[同餘]]表示。這篩法由[[阿特勒·塞爾伯格]]於1940年代發展。

==描述==
在[[篩法]]的術語中，塞爾伯格篩法是一種「組合篩法」，也就是一種透過小心應用[[容斥原理]]進行「篩選」的篩法。在此篩法中，塞爾伯格以一組針對問題最佳化的權重取代[[默比烏斯函數]]，而這可給出「篩選過的」的集合大小的上界。

設<math>A</math>為不大於<math>x</math>的正整數的集合，並假定<math>P</math>為質數的集合，然後設<math>A_p</math>是<math>A</math>中可為<math>P</math>中的質數<math>p</math>整除的數組成的集合；此外，可設<math>d</math>為<math>P</math>中的不同質數的乘積，在這種狀況下，可相應地定義<math>A_d</math>為<math>A</math>中可被<math>d</math>整除的數的集合，並定義<math>A_1</math>為<math>A</math>本身。

設<math>z</math>為任意實數，而<math>P(z)</math>為<math>P</math>中不大於<math>z</math>的質數的乘積，那這篩法的目標就是估計下式：

:<math>S(A,P,z) = \left\vert A \setminus \bigcup_{p \mid P(z)} A_p \right\vert . </math>

我們可以假定說<math>\left|A_d\right|</math>可由下式估計：

:<math> \left\vert A_d \right\vert = \frac{1}{f(d)} X + R_d . </math>

其中<math>f</math>是一個[[積性函數]]、<math>X</math>是<math>A</math>的元素個數。

另外，設<math>g</math>是個由對<math>f</math>進行[[默比烏斯反演]]所得到的函數，也就是說，<math> g(n) = \sum_{d \mid n} \mu(d) f(n/d) </math>且<math> f(n) = \sum_{d \mid n} g(d) </math>，其中<math>\mu</math>是[[默比烏斯函數]]。

在這種狀況下，設<math> V(z) = \sum_{\begin{smallmatrix}d < z \\ d \mid P(z)\end{smallmatrix}} \frac{1}{g(d)}. </math>，就可得下列關係式：

:<math> S(A,P,z) \le \frac{X}{V(z)} + O\left({\sum_{\begin{smallmatrix} d_1,d_2 < z \\ d_1,d_2 \mid P(z)\end{smallmatrix}} \left\vert R_{[d_1,d_2]} \right\vert} \right)</math>

其中<math>[d_1,d_2]</math>是<math>d_1</math>及<math>d_2</math>的[[最小公倍數]]。

此外，<math>V(z)</math>的數值可由下式估計：

:<math> V(z) \ge \sum_{d \le z} \frac{1}{f(d)} . \, </math>

==應用==
* [[算數數列中的質數]]相關問題上的[[布朗-第區馬許定理]]。
* 不大於<math>x</math>且與[[歐拉函數]]<math>\varphi(n)</math>互質的<math>n</math>的數量，與<math>\frac{e^{-\gamma}}{\log{\log{\log{(x)}}}}</math>呈現非病態的（asymptotic）關係。

==參考資料==
* {{cite book | first1=Alina Carmen | last1=Cojocaru|author1-link= Alina Carmen Cojocaru | first2=M. Ram | last2=Murty | author2-link=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=Cambridge University Press | isbn=0-521-61275-6 | pages=113–134 | year=2005 | zbl=1121.11063 }}
* {{cite book | last1= Diamond | first1 = Harold G. | last2 = Halberstam | first2 = Heini | authorlink2 = Heini Halberstam | others = With William F. Galway | title = A Higher-Dimensional Sieve Method: with Procedures for Computing Sieve Functions |series= Cambridge Tracts in Mathematics |volume=177 | publisher =Cambridge University Press | location=Cambridge | year=2008 | isbn=978-0-521-89487-6 | zbl=1207.11099 }}
* {{cite book | first=George | last=Greaves | title=Sieves in number theory | publisher=Springer-Verlag | date=2001 | isbn=3-540-41647-1 | zbl=1003.11044 | series=Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge | volume=43 | location=Berlin }}
* {{cite book | first1=Heini | last1=Halberstam | authorlink1 = Heini Halberstam | first2=H.E. | last2=Richert | authorlink2=Hans-Egon Richert | title=Sieve Methods | publisher=Academic Press | date=1974 | isbn=0-12-318250-6 | zbl=0298.10026 | series=London Mathematical Society Monographs | volume=4 }}
* {{cite book | first=Christopher | last=Hooley | authorlink=Christopher Hooley | title=Applications of sieve methods to the theory of numbers | publisher=Cambridge University Press | date=1976 | isbn=0-521-20915-3| pages=7–12 | zbl=0327.10044 | series=Cambridge Tracts in Mathematics | volume=70 }}
* {{cite journal | first=Atle | last=Selberg | authorlink=Atle Selberg | title=On an elementary method in the theory of primes | journal=Norske Vid. Selsk. Forh. Trondheim | volume=19 | year=1947 | pages=64–67 | zbl=0041.01903 | issn=0368-6302 }}

[[Category:篩法]]