ブルンの篩

ブルンの篩（ブルンのふるい、英: Brun(’s pure) sieve、ブルンの純正篩とも^[1]）は、数学の整数論における手法で、整数の集合から与えられた合同条件を満たすものを篩って残った集合の大きさを評価するもの。ヴィーゴ・ブルンによって創められた^[2]^[3]。

ブルンの篩は、包除原理を基礎としたものであることから、篩法では組合せ型（combinatorial type）に分類される。

定式化

A を x 以下のいくつかの正の整数からなる集合、P を（必ずしも全てではない）素数の集合（A も P もいづれも元に重複はないものとする）とし、正の実数 z に対し P(z) を P の z 以下の元から成る集合とする。

P の元 p に対し A_p を A の要素で p の倍数でもある元の集合、更に P に含まれる異なる素数の積として表される任意の d に対し A_d を、d の全ての素数の約数 p に関する A_p の共通部分とする；A₁は A 自身を表すものとする：

A の P(z) によって篩われて残った集合を S で表す：

$S(A,P,z):=\left\vert A\setminus \bigcup _{p\in P(z)}A_{p}\right\vert .$

A_d について、ある乗法的関数 w が存在して以下が成り立つとする；ここで $X:=|A|$ $X:=|A|$ .
- $\left\vert A_{d}\right\vert ={\frac {w(d)}{d}}X+R_{d}$ ,
- $|R_{d}|\leq w(d)$ .

更に、ある定数C, D, Eに対し以下を仮定する。
- P の任意の元 p について $w(p)<C$ ,
- $\sum _{p\in P_{z}}{\frac {w(p)}{p}}<D\log \log z+E$ .

このとき以下が成り立つ^[4]：

$S(A,P,z)=X\cdot W(z)\cdot \left({1+O\left((\log z)^{-b\log b}\right)}\right)+O\left(z^{b\log \log z}\right)$ .

ここで、

$W(z)=\prod _{p\in P(z)}\left(1-{\frac {w(p)}{p}}\right)$

で、b は任意の正の整数である。特に十分小さな c に対して x を log z < c log x / log log x を満たすように取れば以下が成り立つ：

$S(A,P,z)=X\cdot W(z)(1+o(1)).$

現在は陳の定理等、これらより強い結果が知られている。