篩法

提供: Mathpedia


$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$ \newcommand{\relmid}[1]{\mathrel{}\middle|\mathrel{}}


篩法 (sieve method)は、全体集合から、与えられた条件をすべて満足する（あるいはいずれも満足しない）ものの個数を評価する技法である。

たとえば、与えられた実数 $X>0$ について $$\sqrt{X}<p\leq X$$ の範囲にある素数 $p$ 全体は、後述のように $X$ 以下の整数で、$\sqrt{X}$ 以下のいずれの素数でも割り切れないもの全体と一致する。 また、$p, p+2$ が双子素数の対で、$p$ が上記の範囲にあるための必要十分条件は、$p+2$ が素数の平方でなく、かつ $p$ を $\sqrt{X}$ 以下のどの素数で割っても余りが $0, p-2$ とはならないことである。

最も古い篩法は、与えられた範囲内の素数をすべて発見するEratosthenesの篩である。LegendreはEratosthenesの篩をもとに集合の数え上げとして定量化することで、与えられた数 $X$ 以下の素数の個数 $\pi(X)$ の $X$ に対する比 $\pi(X)/X$ は $0$ に近づくことを示した。

本格的な篩法の発展は1910年代に始まる。1911年にMerlinがEratosthenesの篩を拡張することで双子素数問題やGoldbach予想の研究に利用できるかも知れないと主張したが、Merlinは第一次世界大戦で戦死してしまった。 BrunはMerlinの議論に触発され、本格的に篩法を研究し、組合せ論的な議論を工夫することで1915年に双子素数の逆数の和が収束することを証明し、さらに1920年に次の一連の定理を証明した。

  1. $n, n+2$ がどちらも重複も含めて$9$個以下の素因数しかもたない整数 $n$ が無限に多く存在する。
  2. $X$ が大きいとき、$X$ 以下の双子素数の個数は $100X/\log^2 X$ より小さい。
  3. $n$ が十分大きい偶数のとき、$n$ は重複も含めて$9$個以下の素因数しかもたない$2$つの整数の和としてあらわされる。
  4. $n$ が大きいとき、$n$ と $n+\sqrt{n}$ の間には、重複も含めて$11$個以下の素因数しかもたない整数が存在する。

その後、Selbergが $\lambda^2$ 法を用いて、より単純な篩法を構成した。Selbergの篩は当初は個数の上からの評価しか得られなかったが、その後、下からの評価が得られるようになり、 Jing-run Chen（陳景潤）はこの方法により、十分大きな偶数が素数と、$2$個以下の素因数しかもたない整数の和としてあらわされること、および $p+2$ が$2$個以下の素因数しかもたない素数 $p$ が無限に多く存在することを示した。

一方、RosserとIwaniecはBrunとは別の組合せ論的な構成法を用いて特殊な場合に上からの評価と下からの評価を改良し、Iwaniecはこの方法を用いて $x^2+y^2+1$ の形の素数が無限に多く存在することを示した。 Iwaniecはさらに誤差項を詳しく調べることで、$n^2+1$ の形の、$2$個以下の素因数しかもたない整数が無限に多く存在することを示した。

また、Goldston, Pintz, YıldırımはSelbergの$\lambda^2$法を変形した新しい篩の議論を導入し、$n$ 番目の素数 $p_n$ と $n+1$ 番目の素数 $p_{n+1}$ の間隔について $$\liminf \frac{p_{n+1}-p_n}{\log p_n}=0$$ となることを示し、Yitang Zhang（張益唐）はこの方法を改良して $$\liminf p_{n+1}-p_n<7\times 10^7$$ を示した。その後Polymath projectが $$\liminf p_{n+1}-p_n\leq 246$$ を示した。

Eratosthenes-Legendreの篩

Eratosthenesは、ある範囲の素数をすべて列挙する方法を与えた。

  • $p_1=2$ は素数である。一方で $2$ 自身を除く $2$ の倍数はすべて合成数だから、取り除く。
  • $2$ から先の数で、残った数の中で最小のものである $p_2=3$ は素数である。一方で $3$ 自身を除く $3$ の倍数はすべて合成数だから、取り除く。
  • 以下同様に、 $p_k$ 自身を除く $p_k$ の倍数を取り除いた後に残った数の中で、$p_k$ から先の数で最小のものを $p_{k+1}$ とおいて、

$p_{k+1}$ 自身を除く $p_{k+1}$ の倍数を取り除く。

このようにして、与えられた $k$ に対して、最初の $k$ 個の素数 $p_1=2, p_2=3, \ldots, p_k$ を得る。

LegendreはEratosthenesの篩を次のように変形することで、素数の個数を数えることを試みた。 $X$ までの正の整数 $$1, 2, \ldots, X$$ から $z$ 以下の素数 $p$ で割り切れるものをすべて取り除く。 $p$ が $z<p\leq X$ となる素数ならば、$p$ より小さい素数、とくに $z$ 以下の素数で割れないから取り除かれずに残る。 $A_d$ を、$X$ までの正の整数のうち $d$ の倍数となるものの集合、$P(z)$ を $z$ 以下の素数すべての積とおくと 包含と除去の原理より、このようにして残る数を $S(z)$ とおくと $$S(z)=\sum_{d\mid P(z)}(-1)^\mu(d) \#A_d=\sum_{d\mid P(z)}(-1)^\mu(d)\floor{\frac{X}{d}}$$ となる。 $$0\leq \frac{X}{d}-\floor{\frac{X}{d}}<1$$ となることから、 $$S<\sum_{d\mid P(z)}\left((-1)^\mu(d)\frac{X}{d}+1\right)$$ となるが、$P(z)$ の約数の個数は $$2^{\omega(P(z))}=2^{\pi(z)}<2^z$$ で $$\sum_{d\mid P(z)}\frac{(-1)^\mu(d)}{d}=\prod_{p\leq z}\left(1-\frac{1}{p}\right)$$ となる。さらに $$\prod_{p\leq z}\left(1-\frac{1}{p}\right)^{-1}\geq \sum_{n\leq z}\frac{1}{z}>\log z$$ なので $$S(z)<\frac{X}{\log z}+2^z$$ となる。$z=(\log X-\log\log X)/\log 2$ とおくと、 $$\pi(X)\leq z+S(z)<\frac{X(1+o(1))}{\log\log X}$$ となることがわかる。 とくに、 $$\frac{\pi(X)}{X}\rightarrow 0\ (X\rightarrow\infty)$$ となることが示される。

これは、素数定理はもちろん、初等的かつ比較的容易に得られる結果、たとえば素数の分布（初等的理論）:定理1.1および定理2.2から得られる $$\pi(X)=O\left(\frac{X}{\log X}\right)$$ よりも弱い。和の中の項の個数が $2^z$ 個となって $z$ に比べて大きすぎるためである。

篩法の一般原理

一般の有限集合において、包含と除去の原理はつぎのようにして証明される。 $A$ が有限集合で、$A_i (i=1, 2, \ldots, n)$ がその部分集合とし、 $I\subset\{1, 2, \ldots, n\}$ に対して、$A_I=\cap_{i\in I}A_i$ と定める。 このとき、 $$\mu(I)=(-1)^{\# I}$$ と定義すると、 $$\sum_{J\subset I}\mu(J)=(1-1)^{\# I}=\left\{\begin{array}{cl} 1 & (I=\emptyset), \\ 0 & (I\neq\emptyset) \end{array}\right.$$ となる。よって $x\in A_i$ となる $i$ 全体の集合を $J(x)$ とおくと $$\sum_{I\ni x}\mu(I)=\sum_{I\subset J(x)}\mu(I)=\left\{\begin{array}{cl} 1 & (J(x)=\emptyset), \\ 0 & (J(x)\neq\emptyset) \end{array}\right.$$ となるから $$S=A\setminus\left(\bigcup_{i=1}^n A_i\right)$$ を $A$ の要素のうち、どの $A_i$ にも属さないもの全体の集合とすると $$\#S = \sum_{I\subset J(x)}\mu(I)= \sum_{x\in A} \sum_{I\ni x}\mu(I)=\sum_{I\subset\{1, 2, \ldots, n\}}\mu(I) \#A_I$$ となる。

ここで、ある実数 $X$ が存在し、さらに各 $i=1, 2, \ldots, n$ に対して実数 $\delta_i$ が対応し、$\delta(I)=\prod_{i\in I} \delta_i$, $\delta(\emptyset)=1$ とおくと、各 $I\subset \{1, 2, \ldots, n\}$ について $$\# A_I=\frac{\delta(I)}X+R_I$$ となるとする。それで $\abs{R_I}$ が小さいとき、$A_I$ は $X\delta(I)=X\prod_{i=1}^r \delta_i$ で近似されるといえる。確率論的には $A$ の要素が $A_I$ に属する確率が $\delta(I)=\prod_{i=1}^r \delta_i$ で近似されている（よって $A$ の要素が $A_i$ に属する事象は異なる $i$ についてほぼ独立である）といえる。

$A_1, A_2, \ldots, A_k$ に属する要素をすべて $A$ から取り除いた集合の要素の個数を $$S(A, k)=\# \left[A\setminus\left(\bigcup_{i=1}^n A_i\right)\right]$$ とおくと、包含と除去の原理から $$S(A, k)=\sum_{I\subset \{1, 2, \ldots, k\}} (-1)^{\# I} \#A_d=X\prod_{i=1}^k (1-\delta_i)+\sum_{I\subset\{1, 2, \ldots, k\}} (-1)^{\# I}R_I$$ となる。

Eratosthenes-Legendreの篩はこれをそのまま用いるものであったが、誤差項となる右辺の和は大きなものになりうる。 Brun以降の篩法の出発点は、$\mu(d)$ を別の関数 $\lambda(I)$ で置き換えるところにある。一般的には次の定理が成り立つ。

定理 1

$\lambda^+(I)$ が $\{1, 2, \ldots, n\}$ の部分集合に関する関数で、すべての $I\subset \{1, 2, \ldots, n\}$ について $$\sum_{J\subset I}\mu(J) \leq \sum_{J\subset I}\lambda^+(J)$$ が成り立つとき、 $$\# S \leq \sum_{I\subset\{1, 2, \ldots, n\}}\lambda^+(I) \#A_I$$ が成り立つ。同様に $\lambda^-(I)$ が $\{1, 2, \ldots, n\}$ の部分集合に関する関数で、すべての $I\subset \{1, 2, \ldots, n\}$ について $$\sum_{J\subset I}\mu(J) \geq \sum_{J\subset I}\lambda^-(J)$$ が成り立つとき、 $$\# S \geq \sum_{I\subset\{1, 2, \ldots, n\}}\lambda^+(I) \#A_I$$ が成り立つ。

Proof.

各 $x$ について $$\sum_{I\subset J(x)}\mu(I) \leq \sum_{I\subset J(x)}\lambda^+(I)$$ が成り立つから $$\# S \leq \sum_{x\in A} \sum_{I\subset J(x)}\lambda^+(I)=\sum_{I\subset\{1, 2, \ldots, n\}}\lambda^+(I) \# A_I$$ となる。同様に各 $x$ について $$\sum_{I\subset J(x)}\mu(I) \geq \sum_{I\subset J(x)}\lambda^-(I)$$ だから $$\# S \geq \sum_{x\in A} \sum_{I\subset J(x)}\lambda^-(I)=\sum_{I\subset\{1, 2, \ldots, n\}}\lambda^-(I) \# A_I$$ となる。

□

整数論において篩法を用いる場合の多くは素数を法とする剰余類を取り除く。このことはつぎのようにあらわすことができる。 $A$ をものの集まりとし、各素数 $p$ に対して $A$ の部分集合 $A_p$ が与えられ、 相異なる素数の積 $d=p_1 p_2 \cdots p_r$ について $A_d=\cap_{i=1}^r A_p$ と定め、$A_1=A$ と定める。 一方、各素数 $p$ に対して実数（整数でなくてもよい） $\rho(p)$ が対応し、相異なる素数の積 $d=p_1 p_2 \cdots p_r$ について $$\rho(d)=\prod_{i=1}^r \rho(p), \rho(1)=1$$ と定める。 そして各 $d$ について $$\# A_d=\frac{\rho(d)}{d}X+R_d=X\prod_{p\mid d}\frac{\rho(p)}{p}+R_d$$ となるとする（先述の $\delta_i$ に対して $\rho(p)/p$ が対応している）。 このとき $z$ よりも小さい素数 $p$ に対する $A_p$ をすべて $A$ から取り除いた集合の要素の個数を $$S(A, z)=\# \left(A\setminus \bigcup_{p<z} A_p\right)$$ とおくと、包含と除去の原理から $$S(A, z)=\sum_d \mu(d)\#A_d=X\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)+\sum_d \mu(d)R_d$$ となる。

この場合も、誤差項となる右辺の和は大きなものになりうるので、$\mu(d)$ を別の関数 $\lambda(d)$ で置き換えることが Brun以降の篩法の出発点であることは先の一般的な場合と同様である。

一方、右辺に現れる積 $$\prod_{p<z}\left(1-\frac{\rho(p)}{p}\right)$$ の大きさも知る必要がある。Legendreの篩の場合はすべての素数に対して $\rho(p)=1$ であったから Mertensの第3定理より $$\prod_{p<z}\left(1-\frac{1}{p}\right)^{-1}=\frac{e^{-\gamma}}{\log z}\left(1+O\left(\frac{1}{\log z}\right)\right)$$ となることがわかる。このことから $z>w>1$ のとき $$\prod_{w\leq p<z}\left(1-\frac{1}{p}\right)=\frac{\log w}{\log z}\left(1+O\left(\frac{1}{\log w}\right)\right)$$ となることもわかる。ただし、この右辺の $O$ 記号における定数は $w$ にも $z$ にも依存しない絶対定数である。

さらに、 $$\log\prod_{w\leq p<z}\left(1-\frac{k}{p}\right)=\sum_{w\leq p<z}\log\left(1-\frac{k}{p}\right)=-k\sum_{w\leq p<z}\frac{1}{p}+O\left(\frac{1}{p^2}\right)$$ となるから、有限個の素数を除いて $\rho(p)=k$ となるとき $$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}=(1+o(1))\left(\frac{\log z}{\log w}\right)^k$$ となる（この右辺の $o(1)$ は $w\rightarrow +\infty$ のとき $0$ に近づく）。とくに $$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}=O\left(\left(\frac{\log z}{\log w}\right)^k\right)$$ が成り立つ。ただし、この右辺の $O$ 記号における定数は $w$ にも $z$ にも依存しない絶対定数である。

一般に、実数（整数でなくてもよい） $k$ に対して上記の式が成り立つとき、$k$ を篩密度 (sifting density) という。この場合の篩を $k$ 次元の篩 ($k$-dimensional sieve) という。

定理 2

与えられた定数 $k$ について、つぎの $(1)$ が成り立つとき $(2)$ が成り立ち、$(2)$ が成り立つとき $(3)$ が成り立つ。

$(1)$ $$\sum_{w\leq p<z}\rho(p)\leq k\int_w^z\frac{dt}{\log t}+A_0$$ となる定数 $A_0$ が存在する。

$(2)$ $$\sum_{w\leq p<z}\frac{\rho(p)\log p}{p}\leq k\log\left(\frac{z}{w}\right)+A_1$$ となる定数 $A_1$ が存在する。

$(3)$ $$\sum_{w\leq p<z}\frac{\rho(p)}{p}\leq k(\log\log z-\log\log w)+\frac{A_2}{\log w}$$ となる定数 $A_2$ が存在する。

さらに、$(3)$ が成り立つとき $$\sum_{p<z}\rho(p)\leq (k+A_2)\mathrm{Li} z+\frac{2A_2}{\log 2}$$ となる。かつ、このとき $$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1} <\left(\frac{\log z}{\log w}\right)^k\left(1+\frac{A_3}{\log w}\right)$$ となる定数 $A_3$ が存在する。なお、対数積分と指数積分で定めたように、 $$\mathrm{Li} z=\int_2^z \frac{dt}{\log t}$$ である。

Proof.

$(1)$ が成り立つとして、左辺を $$S_1(w, z)=\sum_{w\leq p<z}\rho(p)$$ とおく。Abelの総和公式より $$\begin{split} \sum_{w\leq p<z}\frac{\rho(p)\log p}{p}= & \frac{S_1(w, z)\log z}{z}+\int_w^z \frac{S_1(w, t)(1+\log t)}{t^2}dt \\ < & \frac{\log z}{z}\left(A_0+k\int_w^z\frac{dt}{\log t}\right)-\int_w^z\left(k\int_w^t\frac{du}{\log u}+A_0\right)\frac{1+\log t}{t^2}dt \\ = & \frac{\log z}{z}\left(A_0+k\int_w^z\frac{dt}{\log t}\right)-\frac{S_1(w, z)\log z}{z}+\int_w^z\frac{kdt}{t} \\ < & k\left(\log\frac{z}{w}\right)+\frac{\log z}{z}\left(A_0+k\int_w^z\frac{dt}{\log t}\right) \end{split}$$ となるが、対数積分と指数積分:定理1より $$\int_w^z\frac{dt}{\log t}<\frac{z}{\log z}+\sqrt{z}+\frac{4z}{\log^2 z}$$ となるので $$\sum_{w\leq p<z}\frac{\rho(p)\log p}{p}\leq k\log\left(\frac{z}{w}\right)+A_1$$ となる定数 $A_1$ がとれるので、 $(2)$ が成り立つ。

つぎに $(2)$ が成り立つとして、左辺を $$S_2(w, z)=\sum_{w\leq p<z}\frac{\rho(p)\log p}{p}$$ とおくと、先と同様に、 $$\begin{split} \sum_{w\leq p<z}\frac{\rho(p)}{p}= & \frac{S_2(w, z)}{\log z}+\int_w^z\frac{S_2(w, t)}{t\log^2 t}dt \\ < & \frac{k\log (z/w)}{\log z}+\frac{A_1}{\log z}+\int_w^z \frac{k}{t\log t}+\frac{A_1-k\log w}{t\log^2 t}dt \\ = & k(\log\log z-\log\log w)+\frac{A_1}{\log w}+\frac{k\log (z/w)}{\log z}-k\left(1-\frac{\log w}{\log z}\right) \\ = & k(\log\log z-\log\log w)+\frac{A_1}{\log w} \end{split}$$ となるので、$(3)$ が成り立つ。

$(3)$ が成り立つとして、左辺を $$S_3(z)=\sum_{w\leq p<z}\frac{\rho(p)}{p}$$ とおく。 $$\begin{split} \int_2^z S_3(w, z)dw= & \sum_{w\leq p<z}\left(\int_2^p\frac{\rho(p)}{p} dt\right) \\ = & \sum_{w\leq p<z}\frac{\rho(p)(p-2)}{p} \\ = & S_1(2, z)-2S_3(2, z) \end{split}$$ なので、 $$\begin{split} S_1(2, z)= & 2S_3(2, z)+\int_2^z S_3(w, z)dw \\ \leq & 2k(\log\log z-\log\log 2)+\frac{2A_2}{\log 2}+\int_2^z k(\log\log z-\log\log t)+\frac{A_2}{\log t}dt \end{split}$$ となる。ここで $$\int_2^z \log\log tdt=z\log\log z-2\log\log 2-\int_2^z \frac{dt}{\log t}$$ であるから $$\begin{split} \int_2^z k(\log\log z-\log\log t)+\frac{A_2}{\log t}dt = & k((z-2)\log\log z-z\log\log z+2\log\log 2)+\int_2^z \frac{k+A_2}{\log t}dt \\ = & 2k(\log\log 2-\log\log z)+(k+A_2)\mathrm{Li} z \end{split}$$ となるので、 $$S_1(2, z)\leq (k+A_2)\mathrm{Li} z+\frac{2A_2}{\log 2}$$ となることがわかる。

また、$(3)$ が成り立つとき $$\frac{\rho(p)}{p}\leq -\log (1-\frac{\rho(p)}{p})\leq \frac{\rho(p)}{p}+\frac{\rho(p)}{2p^2}+\frac{\rho(p)}{3p^3}+\cdots\leq \frac{\rho(p)}{p}+\frac{\rho(p)}{p^2}$$ となるから $$\exp \sum_{w\leq p<z}\frac{\rho(p)}{p}<\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}<\exp\left(\sum_{w\leq p<z}\frac{\rho(p)}{p}+\frac{\rho(p)}{p^2}\right)$$ が成り立つ。ここで、 $$\begin{split} \sum_{w\leq p<z}\frac{\rho(p)}{p^2}= & \frac{S_3(w, z)}{z}+\int_w^z \frac{S_3(w, t)}{t^2}dt \\ < & \frac{k(\log\log z-\log\log w)}{z}+\frac{A_2}{z\log w}+\int_w^z \frac{k(\log\log t-\log\log w)}{t^2}+\frac{A_2}{t^2\log w} dt \\ < & \frac{k\log\log z}{z}+\frac{A_2}{z\log w}+\int_w^z \frac{k\log t}{t^2}+\frac{A_2}{t^2\log w} dt \\ < & \frac{k\log\log z}{z}+\frac{k(1+\log w)}{w}+\frac{A_2}{w\log w}　\\ < & \frac{A_4}{\log w} \end{split}$$ となる定数 $A_4$ が存在するので、 $$\prod_{w\leq p<z}\left(1-\frac{\rho(p)}{p}\right)^{-1}<\exp\left(k(\log\log z-\log\log w)+\frac{A_2+A_4}{\log w}\right)<\left(\frac{\log z}{\log w}\right)^k\left(1+\frac{A_3}{\log w}\right)$$ となることがわかる。

□

Brunの篩

篩の方法を本格的に進展させたBrunの最初の考えは、$\mu(I)$ において $I$ の個数を与えられた個数以下に制限した関数 $$\mu_k(I)=\left\{\begin{array}{cl} (-1)^{\# I} & (\# I\leq k), \\ 0 & (\# I>k) \end{array}\right.$$ を利用するものである。

たとえば $k=1$ のとき、$\mu_1(\emptyset)=1$, $\mu_1(\{i\})=-1$ でそれ以外の $I$ については $\mu_1(I)=0$ となるので $$\sum_{I\subset\{1, 2, \ldots, n\}}\mu_1(I) \# A_I=\# A-\sum_{i=1}^n\# A_i\leq \# S$$ が明らかに成り立つ。Brunの最初の篩（Brun's pure sieveと呼ばれる）の基本原理はこれを次のように一般化したものである。

定理 3

$k$ が奇数のとき $$\# S\geq \sum_{I\subset\{1, 2, \ldots, n\}}\mu_k(I) \# A_I$$ となり、$k$ が偶数のとき $$\# S\leq \sum_{I\subset\{1, 2, \ldots, n\}}\mu_k(I) \# A_I$$ となる。

Brunはこの原理に基づいて、双子素数の逆数の和が収束することを証明した。 その後、Brunは篩法をさらに拡張し、冒頭に記した一連の結果を得た。この拡張された篩法を単にBrunの篩 (Brun's sieve)と呼ぶ。 Brunの篩は次の事実に依拠している。

定理 4

$0$ 以上の整数列 $b_k$ を任意にとる。 $I\subset \{1, 2, \ldots, n\}$ に対して $0$ または $1$ をとる関数 $\chi_0(I), \chi_1(I)$ を $I=\{a_1, a_2, \ldots, a_r\}, 1\leq a_1<a_2<\cdots a_r\leq n$ の形の表示に対して $$\chi_i(\{a_1, a_2, \ldots, a_r\})=1\Longleftrightarrow [a_{2k+i}\geq b_k\ (1\leq 2k+i\leq r)]\ \ (3.1)$$ により定めると、 $$\sum_{I\subset\{1, 2, \ldots, n\}}\chi_0(I)\mu(I) \# A_I\leq\# S\leq \sum_{I\subset\{1, 2, \ldots, n\}}\chi_1(I)\mu(I) \# A_I \ \ \ (3.2)$$ が成り立つ。

これは、つぎのように言い換えられる。$T_i\ (i=0, 1)$ を $$T_1=\{\{a_1, a_2, \ldots, a_r\}: 1\leq a_1<a_2<\cdots a_r\leq n, a_{2k+1}\geq b_k\ (1\leq 2k+1\leq r)\}$$ および $$T_0=\{\{a_1, a_2, \ldots, a_r\}: 1\leq a_1<a_2<\cdots a_r\leq n, a_{2k}\leq b_k\ (2\leq 2k\leq r)\}$$ と定め、 $\lambda_i(I)$ をそれぞれ $\mu(I)$ の $T_i$ への制限とする。このとき $$\sum_{I\subset\{1, 2, \ldots, n\}}\lambda_0(I) \# A_I\leq\# S\leq \sum_{I\subset\{1, 2, \ldots, n\}}\lambda_1(I) \# A_I$$ つまり $$\sum_{I\in T_0}(-1)^{\# I} \# A_I\leq\# S\leq \sum_{I\in T_1}(-1)^{\# I} \# A_I$$ が成り立つ。

この事実は、次のような補助関数を導入することで証明できる（この論法については Greaves, Chap. 3 を参照）。

補題 5

$I\subset \{1, 2, \ldots, n\}$ に対して $0$ または $1$ をとる関数 $\bar\chi_0(I), \bar\chi_1(I)$ を $I=\{a_1, a_2, \ldots, a_r\}, 1\leq a_1<a_2<\cdots a_r\leq n$ の形の表示に対して $$\bar\chi_i(\{a_1, a_2, \ldots, a_r\})=1\Longleftrightarrow r=2k+i\land a_r<b_k\land [j<k\Longrightarrow a_{2j+i}\geq b_j]$$ により定める。また $\bar\chi_0(\emptyset)=\bar\chi_1(\emptyset)=0$ と定める。

このとき空でない集合 $I=\{a_1, a_2, \ldots, a_m\}, 1\leq a_1<a_2<\cdots a_m\leq n$ に対して $$\chi_i(I)=1-\sum_j \bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})\ \ (3.3)$$ が成り立つ。

Proof.

$i$ を $0$ か $1$ の一方に定める。 空でない集合 $I=\{a_1, a_2, \ldots, a_m\}, 1\leq a_1<a_2<\cdots a_m\leq n$ について $\chi_i(I)=0$ とすると $(3.1)$ より $a_{2j+i}<b_j$ となる $j$ が存在するのでそのような $j$ で最小のものを $k$ とおくと、 $$\bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=1\Longleftrightarrow j=k$$ となるので、$\sum_j \bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=1$ となる。 一方、$\chi_i(I)=1$ とすると $(3.1)$ より、今度は $a_{2j+i}<b_j$ となる $j$ は存在しないので $$\forall j[\bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=0]$$ となり、$\sum_j \bar\chi_i(\{a_1, a_2, \ldots, a_{2j+i}\})=0$ となる。

□

ここで、$I=\{a_1, a_2, \ldots, a_m\}, 1\leq a_1<a_2<\cdots a_m\leq n$ について $J=\{a_1, a_2, \ldots, a_k\}$ となる $k$ が存在することを $J\Subset I$ とあらわすと $(3.3)$ は $$\chi_i(I)=1-\sum_{J\Subset I} \bar\chi_i(J) (3.4)$$ とあらわすことができる。

このことから、 $$\begin{split}\sum_{J\subset I} \chi_i(J)\mu(J) = & \sum_{J\subset I} \left(\mu(J)-\sum_{K\Subset J} \mu(J)\bar\chi_i(K)\right) \\ = & \sum_{J\subset I}\mu(J)-\sum_K\bar\chi_i(K)\sum_{K\Subset J\subset I} \mu(J) \end{split} \ \ (3.5)$$ となる。

ここで定理 4の証明に戻る。 $$L(K)=\{i:\max K<i\leq n\}$$ とおくと、 $$K\Subset J\subset I\Longleftrightarrow J=K\cup H, H\subset L(K)$$ となり、右辺において $H$ は $J$ により一意に定まり、かつ $K$ と共通部分をもたないから、 $$\sum_{K\Subset J\subset I} \mu(J)=\mu(K)\sum_{H\subset L(K)}\mu(H)$$ となる。これを $(3.5)$ に代入し $$\sum_{J\subset I} \chi_i(J)\mu(J)=\sum_{J\subset I}\mu(J)-\sum_K\bar\chi_i(K)\mu(K)\sum_{H\subset L(K)}\mu(H)$$ が得られるが、$L(K)=\emptyset\Longleftrightarrow \max K=n$ なので $$\sum_{J\subset I} \chi_i(J)\mu(J)=\sum_{J\subset I}\mu(J)-\sum_{\max K=n}\bar\chi_i(K)\mu(K)$$ となる。 $\bar\chi_0(K)=1$ のとき $\#K$ は偶数なので $\mu(K)=1$ となるので、右辺の $K$ に関する和はつねに $0$ 以上、 $\bar\chi_1(K)=1$ のとき $\#K$ は奇数なので $\mu(K)=-1$ となるので、右辺の $K$ に関する和はつねに $0$ 以下である。よって $$\sum_{J\subset I} \chi_0(J)\mu(J)\leq \sum_{J\subset I}\mu(J)\leq \sum_{J\subset I} \chi_1(J)\mu(J)$$ が成り立つ。よって$\lambda^-(I)=\chi_0(I)\mu(I), \lambda^+(I)=\chi_1(I)\mu(I)$ に対して定理 1を適用することで定理 4が示される。


参考文献

  • George Greaves, Sieves in Number Theory, Springer-Verlag, 2001, doi:10.1007/978-3-662-04658-6.
  • Heini Halberstam and Hans Egon-Richert, Sieve Methods, 2nd edition, Dover publications, 2011.
  • Glyn Harman, Prime-Detecting Sieves, Princeton University Press, 2007.
  • Melvyn B. Nathanson, Additive Number Theory: The Classical Bases, Graduate Texts in Math. 164, Springer-Verlag, 19996, doi:10.1007/978-1-4757-3845-2.
「https://math.jp/w/index.php?title=篩法&oldid=11449」から取得