篩法

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

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

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

篩法の現代的理論の当初より目的とされた問題の多くが未解決として残されている中、特に数論の他の方法との併用によって部分的な結果が多く得られている。その一部は以下のものである

1. ブルンの定理；双子素数の逆数の和が収束することを述べた定理（他方素数の逆数の和は発散する）
2. 陳の定理；素数 p で p+2 が素数か、あるいは二つの素数の積となるものが無限に存在することを述べた定理；この陳景潤による密接に関係した今一つの定理に、十分大きな偶数は、素数と、高々素因数が二つの数との和として表される、というものがある。これらは現在、双子素数予想及びゴールドバッハ予想に最も肉薄した結果である。
3. The fundamental lemma of sieve theory；（大雑把に言えば）N 個の数の集合をふるう時、 十分小として、 の反復により篩に残った元を正確に評価できることを述べたもの。この補題は素数をふるい出す際に必要な  の反復と比べても、かなり劣ってはいるが、それでも概素数に関する結果を導くには十分用いることができる。
4. The Friedlander–Iwaniec theorem;  の形に表せる素数が無限に存在することを述べた定理。

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

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

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

特に記載のない限り、コミュニティのコンテンツはCC BY-SAライセンスの下で利用可能です。