更大筛法

在数论中，更大筛法（larger sieve）是一个由帕特里克·X·加拉格尔发明的筛法，其名称表明这是一种大筛法。塞尔伯格筛法之类的组合筛法在只移除数个同馀类时能得到最强的结果；而大筛法之名表明了这类的筛法能移除大量、多达半数的同馀类；而更大筛法则是一个可移除任意多同馀类的筛法。

描述

假定${\mathcal {S}}$是一个质数及其幂次所组成的集合、$N$是一个整数、${\mathcal {A}}$是$[1,N]$该区间当中的整数的集合，且对于$q\in {\mathcal {S}}$而言，至多只有$g(q)$个包含${\mathcal {A}}$的元素的模$q$同馀类的话，那么有以下关系式：

$|{\mathcal {A}}|\leq {\frac {\sum _{q\in {\mathcal {S}}}\Lambda (q)-\log N}{\sum _{q\in {\mathcal {S}}}{\frac {\Lambda (q)}{g(q)}}-\log N}},$

上式中，右侧的分母为正数。

应用

根据加拉葛的结果，更大筛法用于下列大筛法失效的状况，尤其适用于$\theta >{\frac {1}{2}}$的状况：

使得对所有质数$p\leq N^{\theta +\epsilon }$而言，$n$模$p$的阶$\leq N^{\theta }$为${\mathcal {O}}(N^{\theta })$的数$n\leq N$的数量。

假若排除掉的模$p$同馀类的数量随$p$变化的话，那么更大筛法常会与大筛法结合使用。其中更大筛法会用于如上定义的${\mathcal {S}}$以做为许多同馀类被移除掉的集合；而大筛法则用套用在落于${\mathcal {S}}$之外的质数上，以得这些质数的资讯。

参考资料

• Gallagher, Patrick. A larger sieve. Acta Arithmetica. 1971, 18: 77–81. doi:10.4064/aa-18-1-77-81 . 
• Croot, Ernie; Elsholtz, Christian. On variants of the larger sieve. Acta Mathematica Hungarica. 2004, 103 (3): 243–254. doi:10.1023/B:AMHU.0000028411.04500.e2 .