素数の分布（初等的理論）

$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\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)}$

$\pi(x)$ を $x$ 以下の素数の個数とする。素数の項目で示したように、素数の個数は無限であるから $$\lim_{x\rightarrow +\infty}\pi(x)=+\infty$$ である。より正確に素数定理 $$\pi(x)\sim \frac{x}{\log x}$$ が成り立つことが知られている。

この項目では、素数の個数に関する初等的な結果を証明する。

$$\theta(x)=\sum_{p\leq x}\log p$$ で定義される関数を第一Chebyshev関数という。 また von Mangoldt関数 $\Lambda(n)$ を $n=p^k$ となる素数 $p$ が存在するとき $\log p$, それ以外のとき $0$ をとる関数と定義し、 $$\psi(x)=\sum_{p^k\leq x}\log p=\sum_{n\leq x}\Lambda(n)$$ で定義される関数を第二Chebyshev関数という。

基本的関係

$\pi(x), \theta(x), \psi(x)$ の値は次のように関連付けられる。

定理1.1

• $(1)$ $\psi(x)=\sum_{k=1}^{\infty}\theta(x^{1/k})=\sum_{k=1}^{\floor{\log_2 x}}\theta(x^{1/k})$,
• $(2)$ $\psi(x)=\sum_{k=1}^n \theta(x^{1/k})+O(x^{1/(n+1)}\log x)$,
• $(3)$ $\theta(x)\leq \pi(x)\log x$,
• $(4)$ $\pi(x)=\frac{\theta(x)}{\log x}+\int_2^x\frac{\theta(t)dt}{t\log^2 t}$,
• $(5)$ $\theta(x)=\pi(x)\log x-\int_2^x\frac{\pi(t) dt}{t}$.

Proof.

• $(1)$ $$\psi(x)=\sum_{p^k\leq x}\log p=\sum_{k=1}^\infty \sum_{p\leq x^{1/k}}\log p=\sum_{k=1}^\infty\theta(x^{1/k})$$

となるが、$x^{1/k}<2$ のとき、$\theta(x^{1/k})=\sum_{p\leq x^{1/k}}\log p$ は空和となるので $$\psi(x)=\sum_{k=1}^{\floor{\log_2 x}}\theta(x^{1/k})$$ となる。

• $(2)$ $(1)$ より

$$\psi(x)\geq \sum_{k=1}^n \theta(x^{1/k})$$ が成り立つ。また $y\geq 1$ のとき $\theta(y)\leq y\log y$ となるから $$\begin{split} \psi(x)-\sum_{k=1}^n \theta(x^{1/k}) = & \sum_{k=n+1}^{\floor{\log_2 x}} \theta(x^{1/k}) \\ \leq & \sum_{k=n+1}^{\floor{\log_2 x}} x^{1/k}\log x \\ < & x^{1/(n+1)}\log x+(\log_2 x) x^{1/(n+2)}\log x \end{split}$$ となる。

• $(3)$ 定義より

$$\theta(x)\leq\sum_{p\leq x}\log x=\pi(x)\log x.$$

• $(4)$ $x_0=1$ とし、$a_n (n\geq 2)$ を $n$ が素数のとき $\log n$, それ以外のとき $0$ とし、$f(x)=1/\log x$ とおいて

Abelの総和公式を適用すると $$\pi(x)=\frac{\theta(x)}{\log x}+\int_2^x \theta(t)f^\prime(t) dt=\frac{\theta(x)}{\log x}+\int_2^x\frac{\theta(t)dt}{t\log^2 t}.$$

• $(5)$ $x_0=1$ とし、$a_n (n\geq 2)$ を $n$ が素数のとき $1$, それ以外のとき $0$ とし、$f(x)=\log x$ とおくと

Abelの総和公式から明らか。

□

系

$$\pi(x)<\frac{(K+o(1))x}{\log x}\Longleftrightarrow \theta(x)<(K+o(1))x\Longleftrightarrow \psi(x)<(K+o(1))x$$ かつ $$\theta(x)>(K+o(1))x\Longleftrightarrow \psi(x)>(K+o(1))x\Rightarrow \pi(x)>\frac{(K+o(1))x}{\log x}.$$ また $$\pi(x)=o(x)$$ が成り立つときは最後の矢印の逆も成り立つ。

とくに素数定理は $$\theta(x)\sim x$$ および $$\psi(x)\sim x$$ と同値となる。

Proof.

$(2)$ より $$\psi(x)=\theta(x)+O(x^{1/2}\log x)$$ なので $$\theta(x)<(K+o(1))x\Longleftrightarrow \psi(x)<(K+o(1))x$$ および $$\theta(x)>(K+o(1))x\Longleftrightarrow \psi(x)>(K+o(1))x$$ はすぐにわかる。 $\pi(x)<(K+o(1))x/\log x$ のとき $(3)$ より $\theta(x)<\pi(x)\log x<(K+o(1))x$ となる。

$\theta(x)<(K+o(1))x$ が成り立つとする。とくに $\theta(x)/x$ は上に有界だから $(4)$ より $$\pi(x)<(K+o(1))x+O\left(\int_2^x\frac{dt}{t\log^2 t}\right)$$ となるが、右辺の$O$記号内の積分は $x\rightarrow\infty$ のとき収束するから、 $$\pi(x)<(K+o(1))x$$ が成り立つ。

$\theta(x)>(K+o(1))x$ のとき $(3)$ より $\pi(x)>\theta(x)/\log x>(K+o(1))x/\log x$ となる。 $\pi(x)>(K+o(1))x/\log x$ かつ $\pi(x)=o(x)$ が成り立つとき $(5)$ より $$\theta(x)=\pi(x)\log x-\int_2^{\sqrt{x}}\frac{\pi(t) dt}{t}-\int_{\sqrt{x}}^x\frac{\pi(t) dt}{t}$$ となるが、$\pi(t)/t\leq 1$ かつ $\pi(t)/t\rightarrow 0 (t\rightarrow +\infty)$ だから $$\theta(x)>(K+o(1))x-\sqrt{x}-o(x)=(K+o(1))x$$ となる。

□

Chebyshev関数の初等的評価

Chebyshev関数の値の大きさについて、 $x\geq 2$ のとき $$Ax<\theta(x)<Bx$$ となる定数 $B>A>0$ が存在することが初等的に示せる。

定理2.1

任意の整数 $m\geq 1$ について $$\theta(2m+1)-\theta(m+1)<2m\log 2 \quad\quad (2.1)$$ が成り立つ。

Proof.

$M$ を二項係数 $$M=\binom{2m+1}{m}=\frac{(2m+1)!}{m!(m+1)!}$$ とする。 $m+1<p\leq 2m+1$ のとき、$p$ は $(2m+1)!$ を割り切るが $m!, (m+1)!$ を割り切らないから $p$ は $M$ を割り切る。 よって素数の積 $\prod_{m+1<p\leq 2m+1} p$ も $M$ を割り切るので $$\prod_{m+1<p\leq 2m+1} p\leq M$$ となり $$\theta(2m+1)-\theta(m+1)=\sum_{m+1<p\leq 2m+1} \log p\leq \log M$$ が成り立つ。 $$M=\binom{2m+1}{m}=\binom{2m+1}{m+1}$$ なので $$2M=\binom{2m+1}{m}+\binom{2m+1}{m+1}<\sum_{k=0}^{2m+1}\binom{2m+1}{k}=2^{2m+1}$$ であるから $M<2^{2m}$ となり $$\theta(2m+1)-\theta(m+1)\leq\log M<2m\log 2$$ となることがわかる。

□

定理2.2

任意の整数 $n\geq 1$ について $$\theta(n)<2n\log 2 \quad\quad (2.2)$$ が成り立つ。

Proof.

$n=1$ のときは $\theta(1)=0$, $n=2$ のときは $\theta(2)=\log 2$ だから、$(2.2)$ は成り立つ。 $1\leq n\leq k-1$ のとき、$(2.2)$ が成り立つとする。$n=k=2m+1$ が奇数のとき、定理2.1より $$\theta(2m+1)<\theta(m+1)+2m\log 2$$ なので、帰納法の仮定から $$\theta(2m+1)<2(m+1)\log 2+2m\log 2=2(2m+1)\log 2$$ となり、$(2.2)$は成り立つ。$n=k=2m\geq 4$ が偶数のとき、$k$ は素数ではないので $$\theta(2m)=\theta(2m-1)<2(2m-1)\log 2<4m\log 2$$ となり、$(2.2)$は成り立つ。よって帰納法より$(2.2)$は任意の整数 $n\geq 1$ について成り立つ。

□

定理2.3

任意の整数 $n\geq 3$ について $$\psi(n)>2\floor{\frac{n}{2}}\log 2-\log n \quad\quad (2.3)$$ が成り立つ。

Proof.

整数 $m\geq 2$ に対し、素数 $p$ が二項係数 $$N=\binom{2m}{m}=\frac{(2m)!}{(m!)^2}$$ を割り切る回数を $e(p, m)$ とおくと $$e(p, m)=\sum_{k=1}^\infty\floor{\frac{2n}{p^k}}-2\floor{\frac{n}{p^k}}$$ となる。各被加数は $0$ または $1$ となる。実際 $u=\floor{m/p^k}, m/p^k=u+v$ とおくと $0\leq v<1$ より $$0\leq \floor{\frac{2m}{p^k}}-2\floor{\frac{m}{p^k}}=\floor{2u+2v}-2u\leq 1$$ となる。また $p^k>2m$ ならば被加数は $0$ となるから $$0\leq e(p, m)\leq \floor{\frac{\log (2m)}{\log p}} \quad\quad (2.4) $$ となる。よって $$\begin{split} \log N= & \sum_{p\leq 2m} e(p, m)\log p \\ \leq & \sum_{p\leq 2m}\floor{\frac{\log (2m)}{\log p}}\log p \\ =& \sum_{p\leq 2m} \sum_{1\leq k\leq \log(2m)/\log p} \log p \\ =& \sum_{p^k\leq 2m}\log p \\ =& \psi(2m) \end{split}$$ が成り立つ。

$0\leq k\leq 2m, k\neq m$ のとき $\binom{2m}{m}>\binom{2m}{k}$ となるから $$2m\binom{2m}{m}>2+\sum_{k=1}^{2m-1}\binom{2m}{k}=2^{2m} \quad\quad (2.5) $$ より $$\binom{2m}{m}>\frac{2^{2m}}{2m}$$ となるから $$\psi(2m)\geq\log N>2m\log 2-\log(2m)$$ となる。よって $n=2m\geq 4$ が偶数ならば $(2.3)$ が成り立つ。また $n=2m+1\geq 5$ が奇数のとき $$\psi(2m+1)\geq\psi(2m)>2m\log 2-\log(2m)$$ より $(2.3)$ が成り立つ。最後に $$\psi(3)=\log 6>2\log 2$$ より $n=3$ のときも $(2.3)$ が成り立つ。

□

定理2.4

任意の整数 $n\geq 5$ に対して $$\theta(2n)-\theta(n)>\frac{2}{3}n\log 2-(1+\sqrt{2n})\log(2n)$$ が成り立つ。

ここから、$n\geq 500$ に対して $\theta(2n)-\theta(n)>0$ となる。 $$2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631$$ はいずれも素数だから、$n$ が $2$ 以上の整数のとき、 $n<p<2n$ となる素数 $p$ が存在することがわかる（Betrean-Chebyshevの定理）。

Proof.

$n\geq 5$ とする。 定理2.3の証明と同様に素数 $p$ が二項係数 $$N=\binom{2n}{n}=\frac{(2n)!}{(n!)^2}$$ を割り切る回数を $e(p, n)$ とおく。

$e(p, n)\geq 2$ のとき $p\leq \sqrt{2n}$ となるから $(2.4)$ より $$\sum_{e(p, n)\geq 2} e(p, n)\log p\leq \sum_{p\leq \sqrt{2n}}\log(2n)\leq\sqrt{2n}\log(2n) \quad\quad (2.6)$$ が成り立つ。

$\frac{2}{3}n<p\leq n$ のとき、$p>\frac{2}{3}n>\sqrt{2n}$ より $$e(p, n)=\floor{\frac{2n}{p}}-2\floor{\frac{n}{p}}=2-2=0$$ となる。 よって $$\sum_{e(p, n)=1, p\leq n} e(p, n)\log p\leq \sum_{p\leq \frac{2}{3}n}\log p=\theta\left(\frac{2}{3}n\right) \quad\quad (2.7)$$ となり、定理2.2より $$\sum_{e(p, n)=1, p\leq n} e(p, n)\log p<\frac{4}{3}n\log 2$$ が成り立つ。

$n<p\leq 2n$ のとき $p>n>\sqrt{2n}$ より $e(p, n)=1$ であるから $(2.5), (2.6), (2.7)$ より $$\begin{split} \theta(2n)-\theta(n)=& \sum_{n<p\leq 2n}e(p, n)\log p \\ =& \log N-\sum_{e(p, n)=1, p\leq n} e(p, n)\log p-\sum_{e(p, n)\geq 2} e(p, n)\log p \\ \geq & (2n)\log 2-\log(2n)-\frac{4}{3}n\log 2-\sqrt{2n}\log(2n) \\ = & \frac{2}{3}n\log 2-(1+\sqrt{2n})\log(2n) \end{split}$$ となる。

□

Mertensの定理

p が素数を走るとき、次の評価が成り立つ。

$$\sum_{p\leq n}\frac{\log p}{p}=\log n+O(1),$$ $$\sum_{p\leq n}\frac{1}{p}=\log\log n+b+O\left(\frac{1}{\log n}\right),$$ $$\prod_{p\leq n}\left(1-\frac{1}{p}\right)=\frac{e^{-\gamma}}{\log n}\left(1+O\left(\frac{1}{\log x}\right)\right).$$ これらの不等式を順に、メルテンスの第一定理から第三定理と呼ぶ。 第三定理にあらわれる定数 $\gamma$ は極限 $$\lim_{N\rightarrow\infty} 1+\frac{1}{2}+\cdots +\frac{1}{N}-\log N$$ により定義されるEulerの定数である（詳しくはAbelの総和公式の応用例などを参照）。

また第二定理に現れる定数 b をMeissel-Mertensの定数という。

第一定理の証明

素数 $p$ が $n!$ を割り切る回数を $e(p, n)$ とおくと Legendreの公式 より $$e(n, p)=\sum_{i=1}^{\infty} \left \lfloor \frac{n}{p^i} \right \rfloor$$ であるから $$\floor{\frac{n}{p}}\leq e(n, p)<\frac{n}{p-1}$$ が成り立つ。よって $$\log n!=\sum_p e(n, p)\log p<\sum_{p\leq n}\frac{n\log p}{p-1}$$ となる。 $$\sum_{p\leq n}\frac{\log p}{p(p-1)}<\sum_{k=1}^\infty \frac{\log k}{k(k-1)}<\sum_{k=1}^\infty \frac{2\log k}{k^2}$$ は収束するから $$C_1=\sum_{p\leq n}\frac{\log p}{p(p-1)}$$ とおくと $$\sum_{p\leq n}\frac{\log p}{p}\geq \sum_{p\leq n}\frac{\log p}{p-1}-C_1>\log(n!)-C_1$$ が成り立つ。

Abelの総和公式の応用例から $$\log n!=\sum_{k=1}^n \log k>(n-1)\log n-n$$ がすぐわかるから、 $$\sum_{p\leq n}\frac{\log p}{p}\geq \frac{1}{n}\log n!-C_1\geq\log n-C_2$$ となる定数 $C_2$ が存在する。

また $$\begin{split} \log n!=& \sum_p e(n, p)\log p \\ >& \sum_{p\leq n}\log p\left(\frac{n}{p}-1\right) \\ =& \sum_{p\leq n}\frac{n\log p}{p}-\theta(n) \end{split}$$ となるから定理2.2より $$\log n!>\sum_{p\leq n}\frac{n\log p}{p}-2n\log 2$$ が成り立つ。 再びAbelの総和公式の応用例より $$\log n!=\sum_{k=1}^n \log k<n\log n-n+\log n$$ となるから $$\sum_{p\leq n}\frac{\log p}{p}<\frac{1}{n}\log(n!)+2\log 2<\log n+C_3$$ となる定数 $C_3$ が存在する。

第二定理の証明

$$S(x)=\sum_{p\leq x}\frac{\log p}{p}, \tau(x)=S(x)-\log x$$ とおくと第一定理より $\tau(x)=O(1)$ であることがわかる。 よって積分 $$\int_2^x \frac{\tau(t)dt}{t\log^2 t}$$ は$x\rightarrow\infty$のとき収束するので、Abelの総和公式より $$\begin{split} \sum_{p\leq n}\frac{1}{p} = & \frac{S(x)}{\log x}+\int_2^x \frac{S(t)}{t\log^2 t}dt \\ = & 1+\frac{\tau(x)}{\log x}+\int_2^x \frac{dt}{t\log t}+\int_2^x \frac{\tau(t)dt}{t\log^2 t} \\ = & 1+\log\log x-\log\log 2+\frac{\tau(x)}{\log x}+\int_x^\infty \frac{\tau(t)dt}{t\log^2 t}-\int_x^\infty \frac{\tau(t)dt}{t\log^2 t} \\ = & 1+\log\log x-\log\log 2+\int_2^\infty \frac{\tau(t)dt}{t\log^2 t}+\frac{\tau(x)}{\log x}+O\left(\int_x^\infty \frac{dt}{t\log^2 t}\right) \\ = & 1+\log\log x-\log\log 2+\int_2^\infty \frac{\tau(t)dt}{t\log^2 t}+O\left(\frac{1}{\log x}\right) \end{split}$$ となるので、第二定理は $$b=1-\log\log 2+\int_2^\infty \frac{\tau(t)dt}{t\log^2 t}$$ について成り立つ。

第三定理の証明

$$\sum_{p\leq x} -\log\left(1-\frac{1}{p}\right)=\sum_{p\leq x}\frac{1}{p}+\sum_{p\leq x}\sum_{m\geq 2}\frac{1}{mp^m}$$ および $$\sum_{p>x}\sum_{m\geq 2}\frac{1}{mp^m}=O\left(\sum_{p>x}\frac{1}{p^2}\right)=O\left(\frac{1}{x}\right)$$ から、第二定理より $$\sum_{p\leq x} -\log\left(1-\frac{1}{p}\right)=\log\log x+C_4+O\left(\frac{1}{\log x}\right)$$ となる定数 $C_4$ が存在する。よって $$\prod_{p\leq x} \left(1-\frac{1}{p}\right)=\frac{e^{-C_4}}{\log x}\left(1+O\left(\frac{1}{\log x}\right)\right)$$ となることはすぐにわかる。

定数部分が $e^{-\gamma}$ であることを示す。 $$h(s)=\sum_p \frac{1}{p^s}, g(s)=\sum_p \frac{1}{p^s}+\log\left(1-\frac{1}{p^s}\right), P(x)=\sum_{p\leq x}\frac{1}{p}$$ とおく。 Abelの総和公式より $$h(s)=(s-1)\int_1^{\infty}\frac{P(t)}{t^s}dt$$ が得られる。第二定理より $$P(t)=\log\log t+b+o(1)$$ となるので $$h(s)=(s-1)\int_1^\infty\frac{\log\log t}{t^s}dt+b+O(s-1)$$ が得られる。ここで $t=e^{u/(s-1)}$ とおくとEulerの定数の積分表示 $$\gamma=-\int_0^\infty(\log t)e^{-t} dt$$ から $$(s-1)\int_1^{\infty}\frac{\log\log t}{t^s}dt=\int_0^{\infty}e^{-u}\log\frac{u}{s-1}du=-\gamma-\log (s-1)$$ となる。 $$h(s)=-\gamma-\log(s-1)+b+O(s-1)$$ となるので $$h(s)+\log (s-1)+\gamma-b\rightarrow 0 (s\rightarrow 1+0)$$ が得られる。

ゼータ関数のオイラー積から、$s>1$ のとき $g(s)=h(s)-\log\zeta(s)$ となるが $$(s-1)\zeta(s)\rightarrow 1 (s\rightarrow 1+0)$$ より $$\lim_{s\rightarrow 1+0} g(s)=\lim_{s\rightarrow 1+0} (h(s)-\log \zeta(s))=b-\gamma$$ となる。$g(s)$ は $s_0>1/2$ となる実数 $s_0$ について、$s\geq s_0$ において一様収束するので、 $g(s)$ は $s>1/2$ において連続となる。よって $$\sum_p \frac{1}{p^s}+\log\left(1-\frac{1}{p^s}\right)=g(1)=b-\gamma$$ つまり $$\sum_{p\leq x}\log\left(1-\frac{1}{p}\right)=b-\gamma-P(x)+o(1)$$ である。再び第二定理を用いて $$\sum_{p\leq x}\log\left(1-\frac{1}{p}\right)=-\log\log x-\gamma+o(1)$$ が得られ、第三定理が示される。

参考文献

Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th Ed. revised by D. R. Heath-Brown and J. H. Silverman, Oxford University Press, 2008, Chapter 22.

D. P. Parent, Exercices des théorie des nombres, BORDAS, 1978, English translation: Exercises in Number Theory, Springer-Verlag, 1984, 日本語訳「数論問題ゼミ (1)」（訳：村田玲音）、シュプリンガー・フェアラーク東京、1987, Exercise 1.5 も参照。