更大篩法

在數論中，更大篩法（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 .