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

[[File:Bundesarchiv Bild 183-33149-0001, Leipzig, Universität, Professor Turan.jpg|thumb|圖蘭·帕爾]]

在[[數論]]中，'''圖蘭篩法'''（Turán sieve）是一個用以估計滿足特定條件的「篩選過的」[[正整數]]集大小的技巧，而這些條件一般都以[[同餘]]表示。這篩法由[[圖蘭·帕爾]]於1934年發展。

==描述==
在[[篩法]]的術語中，圖蘭篩法是一種「組合篩法」，也就是一種透過小心應用[[容斥原理]]進行「篩選」的篩法。此種篩法可給出「篩選過的」的集合大小的上界。

設<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>d</math>為質數<math>p</math>的狀況下，<math>\left|A_d\right|</math>可由下式估計：

:<math> \left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p  </math>

而在<math>d</math>為相異質數<math>p</math>與<math>q</math>的乘積狀況下，<math>\left|A_d\right|</math>可由下式估計：

:<math> \left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q}  </math>

其中<math>X</math>是<math>A</math>的元素個數，而<math>f</math>則是一個使得<math>0 \le f(d) \le 1</math>的函數。

設<math> U(z) = \sum_{p \mid P(z)} f(p) . </math>，可得下式：

:<math> S(A,P,z) \le \frac{X}{U(z)} + \frac{2}{U(z)} \sum_{p \mid P(z)} \left\vert R_p \right\vert +\frac{1}{U(z)^2} \sum_{p,q \mid P(z)} \left\vert R_{p,q} \right\vert . </math>

==應用==
* [[哈代—拉馬努金定理]]─一個正整數<math>n</math>其相異的質因數個數<math>\omega(n)</math>的{{link-en|算術函數的正常階|normal order of an arithmetic function|正常階}}為<math>\log{\log{(n)}}</math>。
* 在高度的階之下，幾乎所有的整係數多項式都是[[不可約多項式]]。

==參考資料==
* {{cite book | author=Alina Carmen Cojocaru |author2=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=47&ndash;62 }}
* {{cite book | first=George | last=Greaves | title=Sieves in number theory | url=https://archive.org/details/sievesinnumberth0000grea_k2q7 | publisher=Springer-Verlag | date=2001 | isbn=3-540-41647-1}}
* {{cite book | last1= Halberstam | first1=Heini |author1-link=Heini Halberstam | author2-link=Hans-Egon Richert | first2=H.-E. | last2=Richert | title=Sieve Methods | series=London Mathematical Society Monographs | volume=4 | publisher=[[Academic Press]] | date=1974 | isbn=0-12-318250-6 | mr=424730 | zbl=0298.10026 }}
* {{cite book | author= Christopher 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=21}}

{{DEFAULTSORT:Turan sieve}}
[[Category:篩法]]