在數論中，塞爾伯格篩法（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) = \left\vert A \setminus \bigcup_{p \mid P(z)} A_p \right\vert .
我們可以假定說\left|A_d\right|可由下式估計：
: \left\vert A_d \right\vert = \frac{1}{f(d)} X + R_d .
其中f是一個積性函數、X是A的元素個數。
另外，設g是個由對f進行默比烏斯反演所得到的函數，也就是說， g(n) = \sum_{d \mid n} \mu(d) f(n/d) 且 f(n) = \sum_{d \mid n} g(d) ，其中\mu是默比烏斯函數。
在這種狀況下，設 V(z) = \sum_{\begin{smallmatrix}d ，就可得下列關係式：
: S(A,P,z) \le \frac{X}{V(z)} + O\left({\sum_{\begin{smallmatrix} d_1,d_2
其中[d_1,d_2]是d_1及d_2的最小公倍數。
此外，V(z)的數值可由下式估計：
: V(z) \ge \sum_{d \le z} \frac{1}{f(d)} . \,
應用
- 算數數列中的質數相關問題上的布朗-第區馬許定理。
- 不大於x且與歐拉函數\varphi(n)互質的n的數量，與\frac{e^{-\gamma}}{\log{\log{\log{(x)}}}}呈現漸近（asymptotic）關係。
參考資料
*
*
*
*
*
*
评论 (0)