查看“︁更大篩法”︁的源代码

在數論中，'''更大篩法'''（larger sieve）是一個由{{link-en|帕特里克·X·加拉格尔|Patrick X. Gallagher}}發明的[[篩法]]，其名稱表明這是一種[[大篩法]]。[[塞爾伯格篩法]]之類的組合篩法在只移除數個同餘類時能得到最強的結果；而大篩法之名表明了這類的篩法能移除大量、多達半數的同餘類；而更大篩法則是一個可移除任意多同餘類的篩法。

==描述==

假定<math>\mathcal{S}</math>是一個質數及其冪次所組成的集合、<math>N</math>是一個整數、<math>\mathcal{A}</math>是<math>[1,N]</math>該區間當中的整數的集合，且對於<math>q\in \mathcal{S}</math>而言，至多只有<math>g(q)</math>個包含<math>\mathcal{A}</math>的元素的模<math>q</math>同餘類的話，那麼有以下關係式：

:<math>|\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},
</math>
上式中，右側的分母為正數。<ref>Gallagher 1971, Theorem 1</ref>

==應用==
根據加拉葛的結果，更大篩法用於下列大篩法失效的狀況，尤其適用於<math>\theta>\frac{1}{2}</math>的狀況：<ref>Gallagher, 1971, Theorem 2</ref>

:使得對所有質數<math>p\leq N^{\theta+\epsilon}</math>而言，<math>n</math>模<math>p</math>的階<math>\leq N^\theta</math>為<math>\mathcal{O}(N^\theta)</math>的數<math>n\leq N</math>的數量。

假若排除掉的模<math>p</math>同餘類的數量隨<math>p</math>變化的話，那麼更大篩法常會與大篩法結合使用。其中更大篩法會用於如上定義的<math>\mathcal{S}</math>以做為許多同餘類被移除掉的集合；而大篩法則用套用在落於<math>\mathcal{S}</math>之外的質數上，以得這些質數的資訊。<ref>Croot, Elsholtz, 2004</ref>

==註解==

{{Reflist|2}}

==參考資料==

* {{cite journal | first=Patrick | last=Gallagher | author-link=Patrick X. Gallagher | title=A larger sieve | journal=Acta Arithmetica  | volume=18 | year=1971 | pages=77–81 | doi=10.4064/aa-18-1-77-81 | doi-access=free }}
* {{cite journal | first1=Ernie | last1=Croot | first2 = Christian | last2 = Elsholtz | author-link=Ernie Croot | title=On variants of the larger sieve | journal=[[Acta Mathematica Hungarica]] | volume=103 | year=2004 | issue=3 | pages=243–254 | doi=10.1023/B:AMHU.0000028411.04500.e2 | doi-access=free }}

[[Category:篩法]]