トゥランふるい

数論において、トゥランの篩は、合同式で表される一連の条件を満たす正の整数の「篩分けされた集合」の大きさを推定するための手法である。これは1934年にパール・トゥランによって開発された。

篩理論の観点から見ると、トゥランの篩は組み合わせ論的なものであり、包含排除原理の基本的な形式から導き出される。この結果は、篩分け後の集合のサイズの上限を与える。

A をx 以下の正の整数の集合とし、 Pを素数の集合とする。Pの各pについて、A _{p を}pで割り切れるAの要素の集合とし、これを拡張して、d がPの異なる素数の積である場合に、pがdを割り切るA _pの共通部分をA _dとする。さらに、A _1をA自体とする。zを正の実数とし、P ( z ) をz以下のPの素数の積とする。篩の目的は、推定することである。

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

dが素数pの場合、 | Ad |は次のように推定できると仮定します_。

$\displaystyle \left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}}$

dが異なる素数の積である場合、d = p qは

${\displaystyle \left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}}$

ここで、X  =  | A | であり、f は0 ≤ f ( d ) ≤ 1という性質を持つ関数である。

${\displaystyle U(z)=\sum _{p\mid P(z)}f(p).}$

それから

$${\displaystyle S(A,P,z)\leq {\frac {X}{U(z)}}+{\frac {2}{U(z)}}\sum _{p\mid P(z)}\left\vert R_{p}\right\vert +{\frac {1}{U(z)^{2}}}\sum _{p,q\mid P(z)}\left\vert R_{p,q}\right\vert .}$$

• ハーディ・ラマヌジャンの定理によれば、数nの異なる素因数の数であるω ( n )の正規位数はlog(log( n )) である。
• ほぼすべての整数多項式（高さの順に）は既約である。

• Alina Carmen Cojocaru; M. Ram Murty. 『ふるい法とその応用入門』ロンドン数学会学生テキスト 第 66巻ケンブリッジ大学出版局47–62頁ISBN  0-521-61275-6。
• グリーブス、ジョージ（2001）。数論における篩。シュプリンガー・フェルラーク。ISBN 3-540-41647-1。
• ハルバースタム、ハイニ；リチャート、H.-E. (1974).篩法. ロンドン数学会モノグラフ. 第 4巻.アカデミックプレス. ISBN 0-12-318250-6。MR 0424730。Zbl 0298.10026。  
• クリストファー・フーレイ（1976）。『篩法の数論への応用』ケンブリッジ大学出版局、 21ページ。ISBN 0-521-20915-3。