篩法のソースを表示

'''篩法'''（ふるいほう）、または単に'''篩'''（ふるい）とは、[[数論]]でよく使う技法の総称である。

[[整数]]をふるった[[集合]] (sifted set) の元の個数を数えたり、その大きさを評価したりする。篩の操作によって得られる集合の例として、ある数を超えない素数の集合が挙げられる。つまりいにしえの[[エラトステネスの篩]]、あるいは一般に[[アドリアン＝マリ・ルジャンドル|ルジャンドル]]の篩と呼ばれるものである。しかしこれらの篩を直接用いた[[素数]]分布の定量的研究は、誤差項の累積というどうしようもない困難に直面した。[[20世紀]]に入り、[[双子素数予想]]や[[ゴールドバッハ予想]]などの研究の中でこれらの困境を克服する方法が見いだされ、現在では[[ブルンの篩]]をはじめ、[[アトル・セルバーグ|セルバーグ]]の篩、大きな篩といったものが編み出されている。

これらの原始的な[[エラトステネスの篩]]の発展形においては、ふるわれた（評価されるべき）集合を、他の解析しやすいより単純な集合によって近似することや、sieving function などとよばれる[[関数 (数学)|関数]]の巧みな構成、等の改良が含まれる。

篩法の現代的理論の当初より目的とされた問題の多くが未解決として残されている中、特に数論の他の方法との併用によって部分的な結果が多く得られている。その一部は以下のものである
# ''[[ブルンの定理]]''；[[双子素数]]の逆数の和が収束することを述べた定理（他方[[素数]]の逆数の和は発散する）
# ''[[陳の定理]]''；素数 ''p'' で ''p''+2 が素数か、あるいは二つの素数の積となるものが無限に存在することを述べた定理；この[[陳景潤]]による密接に関係した今一つの定理に、十分大きな偶数は、素数と、[[高々 (数学)|高々]][[素因数]]が二つの数との和として表される、というものがある。これらは現在、[[双子素数予想]]及び[[ゴールドバッハ予想]]に最も肉薄した結果である。
# The ''[[fundamental lemma of sieve theory]]''；（大雑把に言えば）''N'' 個の数の集合をふるう時、<math>\epsilon</math> を十分小として、<math>N^\epsilon</math> の反復により篩に残った元を正確に評価できることを述べたもの。この補題は素数をふるい出す際に必要な <math>N^{1/2}</math> の反復と比べても、かなり劣ってはいるが、それでも[[概素数]]に関する結果を導くには十分用いることができる。
# The ''Friedlander–Iwaniec theorem''; <math>a^2 + b^4</math> の形に表せる素数が無限に存在することを述べた定理。

上のような問題において、篩法はほとんど唯一の攻略法として非常に強力なものとなっているが、parity problem として知られている障害により本質的に有効範囲が制限されていると考えられている。これは篩が、ある数の、[[素因数]]を偶数個持つか奇数個持つかを判別するのに重大な困難があるという内容であるが、いまだ解明されてはいない。

篩法は比較的初等的であり、[[代数的整数論|代数的]]や[[解析的整数論]]のような難しい概念がない。篩法はその発展に伴いさらに複雑かつ微妙になり（特に、他理論の方法と組み合わされた場合）、専門書も出版されている。古典的な文献は {{harv|Halberstam & Richert(1974)}} によるもの。

上記の篩法は、[[素因数分解]]における[[二次篩法]](quadratic sieve)や[[一般数体篩法]]といった篩法とはあまり関係がない。これらの方法はエラトステネスの篩のアイデアは用いているが、効率的に素因数分解を行うことを目的としている。

== 参考文献 ==
{{参照方法|date=2024年3月|section=1}}
* Motohashi, Yoichi, Sieve Methods and Prime Number Theory, Tata Institute of Fundamental Research 1983. http://www.math.tifr.res.in/~publ/ln/tifr72.pdf
* {{cite book|和書|author=本橋洋一 |title=解析的整数論 |series=朝倉数学大系 ; 1 |issue=1 (素数分布論) |publisher=朝倉書店 |year=2009 |id={{国立国会図書館書誌ID|000010611029}} |url=https://ndlsearch.ndl.go.jp/books/R100000002-I000010611029 |quote=第2刷 2012：加筆含む |ref=harv}}
* {{Cite journal|和書|author=本橋洋一 |year=2005 |url=https://doi.org/10.11429/sugaku1947.57.138 |title=&lsquo;篩法&rsquo;概観 |journal=数学 |volume=57 |issue=2 |pages=138-163 |doi=10.11429/sugaku1947.57.138 |publisher=日本数学会 |ref=harv}}
* {{Cite journal|和書|author=本橋洋一 |date=2005-05 |url=http://mathsoc.jp/publication/tushin/1001/motohashi.pdf |format=PDF |title=素数の翼に乗って |journal=数学通信 |ISSN=13421387 |publisher=東京 : 日本数学会 |volume=10 |issue=1 |pages=4-19 |CRID=1520572358126328192 |ref=harv}}
* {{citation | last1= Cojocaru | first1 = Alina Carmen | last2= Murty | first2= M. Ram | authorlink2 = M. Ram Murty | title= An introduction to sieve methods and their applications | publisher= [[Cambridge University Press]] | year= 2006 | isbn= 0521848164 | id= {{MR|2200366}} | series= London Mathematical Society Student Texts | volume= 66 }}
* {{citation | last=Greaves | first=George | title=Sieves in number theory | series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge) | volume=43 | publisher=[[Springer-Verlag]] | date=2001 | isbn=3-540-41647-1}}
* {{citation | last1=Halberstam | first1=Heini | authorlink1=Heini Halberstam | last2=Richert |first2=H.E. | title=Sieve Methods | publisher=[[Academic Press]] | date=1974 | isbn=0-12-318250-6 |ref={{harvid|Halberstam & Richert(1974)}}}}
* {{citation | last=Hooley | first=Christopher | authorlink=Christopher Hooley | title=Applications of sieve methods to the theory of numbers | publisher=Cambridge University Press | date=1976 | isbn=0-521-20915-3}}
* {{citation | title=Introduction to Analytic and Probabilistic Number Theory | first=Gérald | last=Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | year=1995 | isbn=0-521-41261-7 | pages=56-79 }}

== 外部リンク ==
* [http://www.dpmms.cam.ac.uk/~bjg23/expos.html Notes on sieve theory]
* [http://www.math.uga.edu/~lyall/Analysis/brunsieve.pdf Small Sieves, Part I: The Brun Sieve]
* [http://pages.cs.wisc.edu/~cdx/Sieve.pdf Sieve Methods]
* [https://arxiv.org/abs/math/0505521 An Overview of the Sieve Method and its History]
* [https://arxiv.org/abs/math/0209360 Lectures on sieves]

{{DEFAULTSORT:ふるいほう}}
[[Category:数論]]
[[Category:解析的整数論]]
[[Category:組合せ論]]
[[Category:数学に関する記事]]