塞尔伯格筛法

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

描述

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

設 $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} | .

我們可以假定說 $| A_{d} |$ 可由下式估計：

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

其中 $f$ 是一個積性函數、 $X$ 是 $A$ 的元素個數。

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

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

S (A, P, z) \leq \frac{X}{V (z)} + O (\sum_{\begin{matrix} d_{1}, d_{2} < z \\ d_{1}, d_{2} ∣ P (z) \end{matrix}} | R_{[d_{1}, d_{2}]} |)

其中 $[d_{1}, d_{2}]$ 是 $d_{1}$ 及 $d_{2}$ 的最小公倍數。

此外， $V (z)$ 的數值可由下式估計：

V (z) \geq \sum_{d \leq z} \frac{1}{f (d)} .

應用

算數數列中的質數相關問題上的布朗-第區馬許定理。
不大於 $x$ 且與歐拉函數 $φ (n)$ 互質的 $n$ 的數量，與 $\frac{e^{- γ}}{\log \log \log (x)}$ 呈現非病態的（asymptotic）關係。

參考資料

塞尔伯格筛法

描述

應用

參考資料

导航菜单

搜索