在數論中，圖蘭篩法（Turán sieve）是一個用以估計滿足特定條件的「篩選過的」正整數集大小的技巧，而這些條件一般都以同餘表示。這篩法由圖蘭·帕爾於1934年發展。
描述
在篩法的術語中，圖蘭篩法是一種「組合篩法」，也就是一種透過小心應用容斥原理進行「篩選」的篩法。此種篩法可給出「篩選過的」的集合大小的上界。
設A為不大於x的正整數的集合，並假定P為質數的集合，然後設A_p是A中可為P中的質數p整除的數組成的集合；此外，可設d為P中的不同質數的乘積，在這種狀況下，可相應地定義A_d為A中可被d整除的數的集合，並定義A_1為A本身。
設z為任意實數，而P(z)為P中不大於z的質數的乘積，那這篩法的目標就是估計下式：
:S(A,P,z) = \left\vert A \setminus \bigcup_{p \mid P(z)} A_p \right\vert .
我們可以假定說在d為質數p的狀況下，\left|A_d\right|可由下式估計：
: \left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p
而在d為相異質數p與q的乘積狀況下，\left|A_d\right|可由下式估計：
: \left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q}
其中X是A的元素個數，而f則是一個使得0 \le f(d) \le 1的函數。
設 U(z) = \sum_{p \mid P(z)} f(p) . ，可得下式：
: 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 .
應用
- 哈代—拉馬努金定理─一個正整數n其相異的質因數個數\omega(n)的為\log{\log{(n)}}。
- 在高度的階之下，幾乎所有的整係數多項式都是不可約多項式。
參考資料
*
*
*
*
评论 (0)