圖蘭篩法

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

圖蘭·帕爾

描述

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

設${\displaystyle A}$為不大於${\displaystyle x}$的正整數的集合，並假定${\displaystyle P}$為質數的集合，然後設${\displaystyle A_{p}}$是${\displaystyle A}$中可為${\displaystyle P}$中的質數${\displaystyle p}$整除的數組成的集合；此外，可設${\displaystyle d}$為${\displaystyle P}$中的不同質數的乘積，在這種狀況下，可相應地定義${\displaystyle A_{d}}$為${\displaystyle A}$中可被${\displaystyle d}$整除的數的集合，並定義${\displaystyle A_{1}}$為${\displaystyle A}$本身。

設${\displaystyle z}$為任意實數，而${\displaystyle P(z)}$為${\displaystyle P}$中不大於${\displaystyle z}$的質數的乘積，那這篩法的目標就是估計下式：

${\displaystyle S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .}$

我們可以假定說在${\displaystyle d}$為質數${\displaystyle p}$的狀況下，${\displaystyle \left|A_{d}\right|}$可由下式估計：

${\displaystyle \left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}}$

而在${\displaystyle d}$為相異質數${\displaystyle p}$與${\displaystyle q}$的乘積狀況下，${\displaystyle \left|A_{d}\right|}$可由下式估計：

${\displaystyle \left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}}$

其中${\displaystyle X}$是${\displaystyle A}$的元素個數，而${\displaystyle f}$則是一個使得${\displaystyle 0\leq f(d)\leq 1}$的函數。

設${\displaystyle U(z)=\sum _{p\mid P(z)}f(p).}$，可得下式：

${\displaystyle S(A,P,z)\leq {\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 .}$

應用

• 哈代—拉馬努金定理─一個正整數${\displaystyle n}$其相異的質因數個數${\displaystyle \omega (n)}$的正常階（英語：normal order of an arithmetic function）為${\displaystyle \log {\log {(n)}}}$。
• 在高度的階之下，幾乎所有的整係數多項式都是不可約多項式。

參考資料

• Alina Carmen Cojocaru; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts 66. Cambridge University Press. : 47–62. ISBN 0-521-61275-6.
• Greaves, George. Sieves in number theory. Springer-Verlag. 2001. ISBN 3-540-41647-1.
• Halberstam, Heini; Richert, H.-E. Sieve Methods. London Mathematical Society Monographs 4. Academic Press. 1974. ISBN 0-12-318250-6. MR 0424730. Zbl 0298.10026.
• Christopher Hooley. Applications of sieve methods to the theory of numbers. Cambridge University Press. 1976: 21. ISBN 0-521-20915-3.