素数に関する上からの評価（初等的な証明）

概要

この記事では常に $p$ は素数を表すこととし、$i, k, n$ は整数、$x$ は実数を表すものとします。特に単に $\sum_{p\leq x}$ や $\prod_{p\leq x}$ などと書いて、素数にわたる和や積を表すものとします。

$\pi(x) := \sum_{p\leq x}1$ とします。つまり、$\pi(x)$ は $x$ 以下の素数の個数です。また記事内で、big-O 記号は $x\to \infty$, $N\to\infty$, $n\to\infty$ などに関するものであるとします。

この記事では、次の事実を証明していきます。

なお、さらに詳しく誤差を評価した主張も知られています。

競プロの資料でもこれらの「強い評価」が紹介されていることが多いですが、結果が強いため証明が省略されてしまうことが多く、素数の個数のオーダー評価は難しいらしいという誤解が生まれやすい状況だと思います。しかしながら（競プロ文脈で多くの目的に適合するであろう）「弱い評価」であれば、高校数学レベルで簡単に証明できます。

始めていきましょう。

二項係数と素数

【補題】正の整数 $N$ に対して次が成り立つ：$$\prod_{N < p\leq 2N} p \leq \binom{2N}{N} \leq 2^{2N}$$

【証明】

$\binom{2N}{N} = \frac{(2N)!}{N!N!}$ です。$N < p\leq 2N$ とするとき、$p$ は分子 $(2N)!$ を割り切りますが、分母 $N!$ は割り切りません。$\binom{2N}{N}$ は $p$ の倍数であることが分かります。$N < p\leq 2N$ となる $p$ 同士はどの $2$ つも互いに素であることから、$\binom{2N}{N}$ が $\prod_{N < p \leq 2N} p$ の倍数であることが従い、左側の不等号が示されました。

右側の不等式は、$2^{n} = (1+1)^n = \sum_{k=0}^n \binom{n}{k}$ より任意の $0\leq k\leq n$ に対して $\binom{n}{k}\leq 2^n$ となることから従います。

不等式評価 (1)

上述の不等式より、$\sum_{N < p \leq 2N} \log_2 p\leq 2N$ が成り立ちます。あとは大体やるだけです。一応ちゃんとやっていきましょう。

代数的な式変形と違い、解析的な不等式評価や近似計算の類は、同じものであってもかなり式変形に自由度があるので、あくまでも一例という感じでご覧ください。

---

$N = 2^k$ として、$\sum_{2^k < p \leq 2^{k+1}} \log_2 p\leq 2^{k+1}$ が成り立ちます。範囲内の $p$ に対して $k < \log_2 p$ なので、$\sum_{2^k < p\leq 2^{k+1}}1\leq \frac{2^{k+1}}{k}$ が成り立ちます。$k = 1, 2, \ldots, n$ に対して和をとることで、次の評価が得られます：

$$\pi(2^{n+1}) \leq 1 + \sum_{k=1}^n\frac{2^{k+1}}{k}$$

素数の逆数和についても見ておきましょう。$2^k < p\leq 2^{k+1}$ に対して $\frac{1}{p} \leq \frac{1}{2^{k}}$ なので、$\sum_{2^k < p\leq 2^{k+1}}\frac{1}{p}\leq \frac{1}{2^k}\sum_{2^k < p\leq 2^{k+1}}1\leq \frac{2}{k}$ が成り立ちます。$k = 1, 2, \ldots, n$ に対して和をとることで、次の評価が得られます：

$$\sum_{p\leq 2^{n+1}} \frac{1}{p} \leq \frac12 + \sum_{k=1}^n\frac{2}{k}$$

不等式評価 (2)

調和級数

$\sum_{k=1}^N\frac{1}{k} = \log n + O(1)$ という有名な結果があります。積分を使う方法が簡潔です。ただこれについても、積分を知らないとオーダーが評価できないという誤解がたまにあるので、ここではより初等的な方法で $\sum_{k=1}^N\frac{1}{k} = O(\log N)$ を示しておきます。$2^n\leq N < 2^{n+1}$ となる $n$ をとります。

$2^i\leq k < 2^{i+1}$ に対して $\frac{1}{k}\leq 2^{-i}$ です。よって、$\sum_{k=2^i}^{2^{i+1}-1}\frac{1}{k}\leq \sum_{k=2^i}^{2^{i+1}-1}2^{-i} = 1$ が成り立ちます。$i=0, \ldots, n$ について足し合わせることで、$\sum_{k=1}^{2^{n+1}-1}\frac{1}{k} \leq n+1$ が得られます。

ここから、$\sum_{k=1}^N\frac{1}{k}\leq \sum_{k=1}^{2^{n+1}-1}\frac{1}{k} \leq n + 1\leq \log_2N + 1$ が得られました。特に $\sum_{k=1}^N\frac{1}{k} = O(\log N)$ となります。

素数の逆数和

調和級数の不等式評価を合わせると、

$$\sum_{p\leq 2^{n+1}} \frac{1}{p} \leq \frac12 + \sum_{k=1}^n\frac{2}{k}\leq \frac12 + 2(\log_2n+1)$$

が得られます。さて、$x\in \R$ として、$2^n\leq x < 2^{n+1}$ となる $n$ をとります。すると、

$$\sum_{p\leq x}\frac{1}{p} \leq \sum_{p\leq 2^{n+1}} \frac{1}{p}\leq \frac12 + 2(\log_2n + 1)\leq \frac12 + 2(\log_2\log_2x+1)$$

が得られ、$\sum_{p\leq x}\frac{1}{p} = O(\log_2\log_2 x)$ が示されました。なお、

$$\log_2\log_2x = \log_2\frac{\log x}{\log 2} = \log_2\log x – \log_2\log 2 = \frac{\log\log x}{\log 2} – \log_2\log 2$$

より、今回証明した評価は $\sum_{p\leq x}\frac{1}{p} = \frac{2}{\log 2}\log\log x + O(1) \leq 2.886\cdot\log \log x + O(1)$ と書くこともできます。最善の評価よりも $3$ 倍程度弱い評価ですね。

素数の個数

$\pi(2^{n+1}) \leq 1 + \sum_{k=1}^n\frac{2^{k+1}}{k}$ の右辺を評価します。簡単にいうと、$k = n$ の場合の $\frac{2^{n+1}}{n}$ が和全体の中でも十分大きな割合を占めるという評価をします。$i = n – k$ として、例えば次のようにします。

$$\begin{align*}\sum_{k=1}^n\frac{2^{k+1}}{k} &= \sum_{i=0}^{n-1}\frac{2^{n-i+1}}{n-i} = \frac{2^{n+1}}{n}\sum_{i=0}^{n-1}\frac{n}{n-i}2^{-i}\\&=\frac{2^{n+1}}{n}\left(\sum_{i=0}^{n-1}2^{-i} + \sum_{i=1}^{n-1}\frac{i}{n-i}2^{-i}\right)\\&\leq \frac{2^{n+1}}{n}\left(\sum_{i=0}^{\infty}2^{-i}+\sum_{i=1}^{\infty}i 2^{-i}\right) = \frac{4\cdot 2^{n+1}}{n}\end{align*}$$

したがって、$\pi(2^{n+1})\leq 1 + \frac{4\cdot 2^{n+1}}{n}$ が示されました。

さて、$x\in \R$ として、$2^n\leq x < 2^{n+1}$ となる $n$ をとります。すると、$$\pi(x)\leq \pi(2^{n+1})\leq 1 + \frac{4\cdot 2^{n+1}}{n}\leq 1 + \frac{8x}{\log_2x-1} = \frac{8x}{\log_2 x} + O(1)$$

となって、$\pi(x) \leq \frac{8x}{\log_2x} + O(1)$ 特に $\pi(x) = O(\frac{x}{\log x})$ が示されました。

$\frac{8}{\log_2x} = \frac{8\log 2}{\log x} \leq 5.55\cdot \frac{x}{\log x}$ で、最善の評価よりも $6$ 倍程度弱い評価となっています。

その他コメント

得られた評価は弱い評価ですが、【補題】一発という感じの簡単な証明となっています。式変形の細部で評価を改善できるところもあると思います。

今回は「素数は少ない」という方向の評価を扱いましたが、「素数は多い」つまり $\pi(x)\geq c\cdot \frac{x}{\log x}$ という評価を初等的に行うことも可能です。やはり、例えば $\binom{2N}{N}$ に注目して、$p\leq 2N$ の指数が十分小さいことから評価できて、$\pi(x) = \Theta\left(\frac{x}{\log x}\right)$ や $\sum_{p\leq x} \frac1p = \Theta(\log\log x)$ を証明することが可能です。良ければ考えてみてください。また下からの評価については Euler 積から分かる $\sum_{1\leq n\leq x}\frac{1}{n}\leq \prod_{p\leq x}\left(1-\frac{1}{p}\right)^{-1}$ などを利用する方法もあります。

参考文献

• Introduction to Analytic Number Theory (Tom M. Apostol)

ベースとなるアイデア（$\binom{2N}{N}$ を考える）はここで学びました。細かい式変形は記事を書きながら考えたので、いくらか違う部分があると思います。

素数定理などの「強い評価」についても本書の中で証明されています（二項係数を評価するというアイデアの延長線上ではありません）。数論関数の不等式評価が話題の中心な楽しい本です。高校数学程度の微積分の知識で、大部分を読むことができます。