素数密度零補題

$\displaystyle \pi(x) \sim \frac{x}{\log x},\quad x \to \infty$

は素数分布に関する歴史的定理ですが、これからより定性的な次の結果が従います：

系 (素数密度零補題) 次の極限公式が成り立つ：

$\displaystyle \lim_{x \to \infty}\frac{\pi(x)}{x} = 0.$

integers.hatenablog.com

に書いたように、この結果は素数の関わる問題を解く際などによく使われますが、素数定理という大定理(証明が比較的困難)を経由することなく簡単に証明することができる事実であり、歴史的にはLegendreが証明していました*1。なので、時々見かける「素数密度零補題しか本質的には使わないにもかかわらず、『素数定理を使って〜を証明する』という言明」は数学的には間違ってはいないものの若干ナンセンスな気がしなくもないです。

この記事では素数密度零補題の素数定理を経由しない証明についてまとめておきます。

第一証明

Chebyshevの定理より、或る正の定数 $C$ が存在して

$\displaystyle \pi(x) < C\frac{x}{\log x},\quad x \gg 0$

が初等的に証明されており*2、これから素数密度零補題が導かれます。少しだけ証明の流れを思い出すと、まず

$\displaystyle \frac{\pi(x)\log x}{x} = O\left(\frac{\vartheta(x)}{x}\right)$

を示して、 $\vartheta(x) = O(x)$ に帰着します。 $\binom{2n-1}{n}$ は $n+1 \leq p \leq 2n-1$ なる全ての素数 $p$ で割り切れるような整数であるため、

$\displaystyle \frac{(2n-1)\#}{n\#}\leq \binom{2n-1}{n} < 2^{2n-2}$

が成り立ちますが(左辺は素数階乗の記号を使っています)、これをもとに数学的帰納法によって $\vartheta(n) = O(n)$ が示せます。

素数密度零補題 $\ll$ Chebyshevの定理 $\ll$ 素数定理

という関係にあります。

第二証明

Eulerが証明したように、

$\displaystyle \prod_p\frac{1}{1-\frac{1}{p}} = \sum_{n=1}^{\infty}\frac{1}{n} = \infty$

なので

補題次の極限公式が成り立つ：

$\displaystyle \prod_p\left(1-\frac{1}{p}\right) = 0.$

が成り立ちます。これを使った素数密度零補題の証明を二通りの見せ方で紹介します。ちなみに、Euler積の発散は即座に素数の無限性を導くだけではなく、対数を取れば素数の逆数和の発散を示すことができるのでした(cf. メビウス関数 - INTEGERS)。或いは「無限和 $\sum_{k=1}^{\infty}u_k$ が絶対収束すれば無限積 $\prod_{k=1}^{\infty}(1+u_n)$ も( $0$ でない値に)絶対収束する」という定理の対偶によって補題から素数の逆数和が発散するという見方もできます。

つまり、第二・第三証明は素数の無限性や逆数和の発散性を本質的なエネルギー源として素数密度零補題を証明していますが、第一証明は素数の無限性(と同等以上の事実)は使っていないように見えます。本来、素数密度零補題は「素数は少ない」ことを言うもので、(もし有限個だったら自明な主張になってしまうものの)素数の無限性を導く能力はア・プリオリには持ち合わせていません。

さて、補題を使った一つ目の証明はEratosthenesの篩の考え方によるものです。

命題 (Eratosthenesの篩) $x$ を正の実数とし、 $f(x) \leq \sqrt{x}$ を満たす $f(x)$ を考える。このとき、不等式

$\displaystyle \pi(x) \leq \pi(f(x) )+2^{\pi(f(x) )}+x\prod_{p \leq f(x)}\left(1-\frac{1}{p}\right)$

が成り立つ。

証明. $x$ を固定して、 $\pi(f(x))=n$ とする。 $n=0$ のときは $\prod_{p \leq f(x)}\left(1-\frac{1}{p}\right):=1$ と考えて所望の不等式は自明に成り立っているものとし、 $n \geq 1$ と仮定する。 $p_i$ は $i$ 番目の素数を表すものとする。

$\{x$ 以下の素数達 $\} \subset \{p_1, \dots, p_n\} \cup \{x$ 以下で $p_1, \dots, p_n$ で割り切れない整数達 $\}$

であり、 $x$ 以下で $p_1, \dots, p_n$ で割り切れない整数の個数は包含原理により

$\displaystyle \sum_{d \mid p_1\cdots p_n}\mu(d)\left[\frac{x}{d}\right]$

なので( $\mu$ はMöbius関数)、

$\begin{align} \pi(x) &\leq n+\sum_{d \mid p_1\cdots p_n}\mu(d)\left[\frac{x}{d}\right] \\ &\leq n+\sum_{d \mid p_1\cdots p_n}\left(\mu(d)\frac{x}{d}+1\right)\\ &= n+2^n+x\prod_{i=1}^n\left(1-\frac{1}{p_i}\right)\end{align}$