篩法(ふるいほう)、または単に篩(ふるい)とは、数論でよく使う技法の総称である。
整数をふるった集合 (sifted set) の元の個数を数えたり、その大きさを評価したりする。篩の操作によって得られる集合の例として、ある数を超えない素数の集合が挙げられる。つまりいにしえのエラトステネスの篩、あるいは一般にルジャンドルの篩と呼ばれるものである。しかしこれらの篩を直接用いた素数分布の定量的研究は、誤差項の累積というどうしようもない困難に直面した。20世紀に入り、双子素数予想やゴールドバッハ予想などの研究の中でこれらの困境を克服する方法が見いだされ、現在ではブルンの篩をはじめ、セルバーグの篩、大きな篩といったものが編み出されている。
これらの原始的なエラトステネスの篩の発展形においては、ふるわれた(評価されるべき)集合を、他の解析しやすいより単純な集合によって近似することや、sieving function などとよばれる関数の巧みな構成、等の改良が含まれる。
篩法の現代的理論の当初より目的とされた問題の多くが未解決として残されている中、特に数論の他の方法との併用によって部分的な結果が多く得られている。その一部は以下のものである
ブルンの定理;双子素数の逆数の和が収束することを述べた定理(他方素数の逆数の和は発散する)
陳の定理;素数 p で p+2 が素数か、あるいは二つの素数の積となるものが無限に存在することを述べた定理;この陳景潤による密接に関係した今一つの定理に、十分大きな偶数は、素数と、高々素因数が二つの数との和として表される、というものがある。これらは現在、双子素数予想及びゴールドバッハ予想に最も肉薄した結果である。
The fundamental lemma of sieve theory
上のような問題において、篩法はほとんど唯一の攻略法として非常に強力なものとなっているが、parity problem として知られている障害により本質的に有効範囲が制限されていると考えられている。これは篩が、ある数の、素因数を偶数個持つか奇数個持つかを判別するのに重大な困難があるという内容であるが、いまだ解明されてはいない。
篩法は比較的初等的であり、代数的や解析的整数論のような難しい概念がない。篩法はその発展に伴いさらに複雑かつ微妙になり(特に、他理論の方法と組み合わされた場合)、専門書も出版されている。古典的な文献は (Halberstam & Richert(1974)) によるもの。
上記の篩法は、素因数分解における二次篩法(quadratic sieve)や一般数体篩法といった篩法とはあまり関係がない。これらの方法はエラトステネスの篩のアイデアは用いているが、効率的に素因数分解を行うことを目的としている。 出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。(2024年3月)
参考文献.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%;font-size:90%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}
Motohashi, Yoichi, Sieve Methods and Prime Number Theory, Tata Institute of Fundamental Research 1983. ⇒http://www.math.tifr.res.in/~publ/ln/tifr72.pdf
本橋洋一『解析的整数論』1 (素数分布論)、朝倉書店〈朝倉数学大系 ; 1〉、2009年。国立国会図書館書誌ID:.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}000010611029
本橋洋一「‘篩法’概観」『数学』第57巻第2号、日本数学会、2005年、138-163頁、doi:10.11429/sugaku1947.57.138。
本橋洋一「 ⇒素数の翼に乗って」(PDF)『数学通信』第10巻第1号、東京 : 日本数学会、2005年5月、4-19頁、CRID 1520572358126328192、ISSN 13421387。
Cojocaru, Alina Carmen; Murty, M. Ram (2006), An introduction to sieve methods and their applications, London Mathematical Society Student Texts, 66, Cambridge University Press, ISBN 0521848164, MR2200366
Greaves, George (2001), Sieves in number theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge), 43, Springer-Verlag, ISBN 3-540-41647-1
Halberstam, Heini; Richert, H.E. (1974), Sieve Methods, Academic Press, ISBN 0-12-318250-6
Hooley, Christopher (1976), Applications of sieve methods to the theory of numbers, Cambridge University Press, ISBN 0-521-20915-3
Tenenbaum, Gerald (1995), Introduction to Analytic and Probabilistic Number Theory, Cambridge studies in advanced mathematics, 46, Cambridge University Press, pp. 56-79, ISBN 0-521-41261-7
外部リンク
⇒Notes on sieve theory
⇒Small Sieves, Part I: The Brun Sieve
⇒Sieve Methods
⇒An Overview of the Sieve Method and its History
⇒Lectures on sieves