跳转到内容

塞尔伯格筛法

维基百科,自由的百科全书
阿特勒·塞尔伯格

数论中,塞尔伯格筛法(Selberg sieve)是一个用以估计满足特定条件的“筛选过的”正整数集大小的技巧,而这些条件一般都以同余表示。这筛法由阿特勒·塞尔伯格于1940年代发展。

描述

筛法的术语中,塞尔伯格筛法是一种“组合筛法”,也就是一种透过小心应用容斥原理进行“筛选”的筛法。在此筛法中,塞尔伯格以一组针对问题最佳化的权重取代默比乌斯函数,而这可给出“筛选过的”的集合大小的上界。

为不大于的正整数的集合,并假定为质数的集合,然后设中可为中的质数整除的数组成的集合;此外,可设中的不同质数的乘积,在这种状况下,可相应地定义中可被整除的数的集合,并定义本身。

为任意实数,而中不大于的质数的乘积,那这筛法的目标就是估计下式:

我们可以假定说可由下式估计:

其中是一个积性函数的元素个数。

另外,设是个由对进行默比乌斯反演所得到的函数,也就是说,,其中默比乌斯函数

在这种状况下,设,就可得下列关系式:

其中最小公倍数

此外,的数值可由下式估计:

应用

参考资料