数論

篩法

概要

目次

1. はじめに

   篩法 (sieve method) は、全体集合から、与えられた条件をすべて満足する（あるいはいずれも満足しない）ものの個数を評価する技法である。 最も古い篩法は、与えられた範囲内の素数をすべて発見するEratosthenesの篩であるが、20世紀になって篩法が素数に関する様々な問題の研究に盛んに用いられるようになり、近年では他の数論や組合せ論の問題への応用も行われるようになっている。本章では篩法の歴史と一般原理について簡単に解説する。

   $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{Arg}[0]{\operatorname{Arg}} \newcommand{BB}[0]{\mathscr{B}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{Ker}[0]{\operatorname{Ker}} \newcommand{mmod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{ord}[0]{\operatorname{ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{rank}[0]{\mathrm{rank}} \newcommand{SS}[0]{\mathscr{S}} \newcommand{TT}[0]{\mathscr{T}} \newcommand{UU}[0]{\mathscr{U}} \newcommand{wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert} \newcommand{Z}[0]{\mathbb{Z}} $$
   1. はじめに
   2. 包含と除去の原理
   3. 篩法の一般原理
   4. 篩密度と篩の次元

2. Eratosthenes-Legendreの篩

   本章では篩法の研究が本格的に進展する以前に論じられた古典的な篩法について解説する。本章で解説する篩法はいわば現代的な篩の前史とよぶべきものである。

   $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{Arg}[0]{\operatorname{Arg}} \newcommand{BB}[0]{\mathscr{B}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{Ker}[0]{\operatorname{Ker}} \newcommand{mmod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{ord}[0]{\operatorname{ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{rank}[0]{\mathrm{rank}} \newcommand{SS}[0]{\mathscr{S}} \newcommand{TT}[0]{\mathscr{T}} \newcommand{UU}[0]{\mathscr{U}} \newcommand{wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert} \newcommand{Z}[0]{\mathbb{Z}} $$
   1. Eratosthenesの篩
   2. Legendreの篩

3. Brunの篩

   $$\newcommand{AA}[0]{\mathscr{A}} \newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{Arg}[0]{\operatorname{Arg}} \newcommand{BB}[0]{\mathscr{B}} \newcommand{C}[0]{\mathbb{C}} \newcommand{CC}[0]{\mathscr{C}} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\operatorname{ind}} \newcommand{Ker}[0]{\operatorname{Ker}} \newcommand{mmod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{Mod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{N}[0]{\mathbb{N}} \newcommand{ord}[0]{\operatorname{ord}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{rank}[0]{\mathrm{rank}} \newcommand{SS}[0]{\mathscr{S}} \newcommand{TT}[0]{\mathscr{T}} \newcommand{UU}[0]{\mathscr{U}} \newcommand{wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert} \newcommand{Z}[0]{\mathbb{Z}} $$
   1. Brunの最初の篩（一般形）
   2. Brunの最初の篩（素数による篩）
   3. Brunの最初の篩（応用）
   4. Brunの篩（一般形）
   5. Brunの篩（素数による篩）
   6. Brunの篩（素数による篩の評価）
   7. Brunの篩（応用）

参考文献