トゥランふるい

パル・トゥラン

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

説明

篩理論の観点から見ると、トゥラン篩は組合せ型であり、包含・排除原理の基本的な形から派生している。その結果、篩い分けされた集合の大きさの 上限が与えられる。

A をx ≤ の正の整数の集合とし、P を素数の集合とする。Pの各pについて、A _{p を}pで割り切れるAの要素の集合とし、これを拡張して、dがPとは異なる素数の積であるとき、pがdを割り切るA _pの集合をA _dとする。さらに、A _1をA自身とする。z を正の実数とし、P ( z ) をP内のz ≤ の素数の積とする。ふるいの目的は、

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

dが素数pのとき、| A _d |は次のよう に推定できると仮定する。

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

そして、 dが異なる2つの素数の積である場合、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巻 .ケンブリッジ大学出版局. pp.  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).ふるい法の数論への応用. ケンブリッジ大学出版局. p. 21. ISBN 0-521-20915-3。