インテジャーズ

INTEGERS

数、特に整数に関する記事。

素数密度零補題

素数定理

\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. メビウス関数 - インテジャーズ)。或いは「無限和\sum_{k=1}^{\infty}u_kが絶対収束すれば無限積\prod_{k=1}^{\infty}(1+u_n)も(0でない値に)絶対収束する」という定理の対偶によって補題から素数の逆数和が発散するという見方もできます。

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

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

命題 (Eratosthenesの篩) xを正の実数とし、関数 f(x)f(x) \leq \sqrt{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_ii番目の素数を表すものとする。

\{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]

なので(\muMö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}

と評価できる。 Q.E.D.

素数密度零補題の証明. x \gg 0とする。命題において f(x) = \log xとすることによって

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

と評価でき、補題より右辺は x \to \infty0に収束する。 Q.E.D.

第三証明

Eulerのトーシェント関数を用いた証明です。

素数密度零補題の証明. \varepsilon > 0を任意にとる。補題より

\displaystyle \prod_{i=1}^n\left(1-\frac{1}{p_i}\right) < \varepsilon

が成り立つようなnが存在し、一つとって固定する。N:=\prod_{i=1}^np_iとおく。トーシェント関数の公式より

\displaystyle \varphi(N) = N\prod_{i=1}^n\left(1-\frac{1}{p_i}\right)

なので、\displaystyle \frac{\varphi(N)}{N} < \varepsilonである。正整数パラメータkに対してk=qN+r, \ (0 \leq r < N)と割り算を行い、区間の分割

\displaystyle [1, k] = \bigcup_{j=1}^q[(j-1)N+1, jN] \cup [qN+1, k]

を考える。まず、N以下の素数はp_1, \dots, p_nのいずれかであるか、Nと互いに素なN以下の整数なので

[1, N]に含まれる素数の個数\ =\pi(N) \leq n+\varphi(N)

がわかる。j \geq 2に対して区間[(j-1)N+1, jN]に属する素数の個数はその区間に属するNと互いに素な整数の個数で押さえられるが、平行移動を考えればそれは\varphi(N)個ある。以上の考察により、

\pi(k) \leq n+q\varphi(N)+r

なる評価を得る。よって、

\displaystyle \frac{\pi(k)}{k} \leq \frac{n+q\varphi(N)+r}{k} \leq \frac{n+r}{k}+\frac{\varphi(N)}{N} < \frac{n+N}{k}+\varepsilon

であり、n, N固定なので \displaystyle \lim_{k \to \infty}\frac{\pi(k)}{k} \leq \varepsilonが従う。\varepsilon > 0は任意であったので証明が完了する。 Q.E.D.

*1:山田先生に教えていただきました。Eulerに帰す書き方をしている文献もありますが、Eulerがこの定理を明言している文献があるかは現段階で調査できておりません。

*2:必要な分だけ証明を抜き出せば(第二・第三証明と比較しても)相当に簡単であることがわかります。思いつくかは別として。