塞尔伯格筛法

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

阿特勒·塞爾伯格

描述

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

 為不大於 的正整數的集合,並假定 為質數的集合,然後設  中可為 中的質數 整除的數組成的集合;此外,可設  中的不同質數的乘積,在這種狀況下,可相應地定義  中可被 整除的數的集合,並定義  本身。

 為任意實數,而  中不大於 的質數的乘積,那這篩法的目標就是估計下式:

 

我們可以假定說 可由下式估計:

 

其中 是一個積性函數  的元素個數。

另外,設 是個由對 進行默比烏斯反演所得到的函數,也就是說,  ,其中 默比烏斯函數

在這種狀況下,設 ,就可得下列關係式:

 

其中   最小公倍數

此外, 的數值可由下式估計:

 

應用

參考資料