图兰筛法

在數論中，圖蘭篩法（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) = | A ∖ ⋃_{p ∣ P (z)} A_{p} | .

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

| A_{p} | = \frac{1}{f (p)} X + R_{p}

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

| A_{p q} | = \frac{1}{f (p) f (q)} X + R_{p, q}

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

設 $U (z) = \sum_{p ∣ P (z)} f (p) .$ ，可得下式：

S (A, P, z) \leq \frac{X}{U (z)} + \frac{2}{U (z)} \sum_{p ∣ P (z)} | R_{p} | + \frac{1}{U (z)^{2}} \sum_{p, q ∣ P (z)} | R_{p, q} | .

應用

哈代—拉馬努金定理─一個正整數 $n$ 其相異的質因數個數 $ω (n)$ 的Template:Link-en為 $\log \log (n)$ 。
在高度的階之下，幾乎所有的整係數多項式都是不可約多項式。

參考資料

图兰筛法

描述

應用

參考資料

导航菜单

搜索