ルジャンドルふるい

数学において、アドリアン＝マリー・ルジャンドルにちなんで名付けられたルジャンドル篩は、現代の篩理論における最も単純な手法です。これはエラトステネスの篩の概念を応用し、与えられた整数集合内における素数の上限または下限を求めます。エラトステネスの考えを単純に拡張したものであるため、ルジャンドル・エラトステネス篩と呼ばれることもあります。^[1]

ルジャンドルの正体

この方法の中心的な考え方は、ルジャンドル恒等式と呼ばれることもある次の恒等式によって表現されます。

${\displaystyle S(A,P)=\sum _{a\in A}\sum _{d\mid a;\,d\mid P}\mu (d)=\sum _{d\mid P}\mu (d)|A_{d}|,}$

ここで、 Aは整数の集合、Pは異なる素数の積、はメビウス関数、はA内のdで割り切れる整数の集合であり、S(A, P)は次のように定義されます。 ${\displaystyle \mu}$ ${\displaystyle A_{d}}$

${\displaystyle S(A,P)=|\{n:n\in A,\gcd(n,P)=1\}|}$

つまり、S ( A、  P ) は、 Pと共通する因数を持たないAの数値の数です。

最も一般的なケースでは、Aはある実数X以下のすべての整数、Pはある整数z  <  X以下のすべての素数の積であり、ルジャンドル恒等式は次のようになることに注意してください。

${\displaystyle {\begin{aligned}S(A,P)={}&\sum _{d\mid P}\mu (d)\left\lfloor {\frac {X}{d}}\right\rfloor \\[6pt]={}&\lfloor X\rfloor -\sum _{p_{1}\leq z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor \\[4pt]&{}-\sum _{p_{1}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots +\mu (P)\left\lfloor {\frac {X}{P}}\right\rfloor \end{aligned}}}$

（ここで は床関数を表します）。この例では、ルジャンドル恒等式がエラトステネスの篩から導かれるという事実は明らかです。第1項はXより小さい整数の数、第2項はすべての素数の倍数を消去し、第3項は2つの素数の倍数（「2回消された」ために誤って数えられた）を加算し直すだけでなく、3つの素数の倍数を1回多く加算し直し、これをすべての（ここで はzより小さい素数の個数を表します ）素数の組み合わせがカバーされるまで繰り返します。 ${\displaystyle \lfloor X\rfloor }$ ${\displaystyle 2^{\pi (z)}}$ ${\displaystyle \pi (z)}$

この特別なケースについてS ( A ,  P )が計算されると、次の式を使って 境界値を求めることができる。${\displaystyle \pi (X)}$

${\displaystyle S(A,P)\geq \pi (X)-\pi (z)+1,\,}$

これはS ( A ,  P )の定義から直ちに導かれる 。

制限事項

ルジャンドル篩は、項の小数部分が累積して大きな誤差を生じるという問題を抱えており、ほとんどの場合、非常に弱い境界しか与えません。このため、ルジャンドル篩は実際にはほとんど使用されず、ブルン篩やセルバーグ篩といった他の手法に取って代わられました。しかし、これらのより強力な篩はルジャンドル篩の基本的な考え方を拡張したものであるため、まずルジャンドル篩の仕組みを理解しておくことは有益です。

参考文献

1. イワニエツ、ヘンリク。エラトステネス＝ルジャンドルのふるい。ピサの高等師範学校 – 科学教室、Sér. 4、4いいえ。 2 (1977)、257–268 ページ MR 453676