素数の無限性と素数密度零定理～Eratosthenesの篩～
前回の記事
で、Eratosthenesの篩から
$$
\pi(x)=\pi(\sqrt{x})-1+\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor
\tag{1}
$$
が成り立つことを示しました( \( P(\sqrt{x}) \) のところの記号を前記事から変えてるのでご注意ください)。前回の記事読むのめんどい！って人のために各設定をおさらいしておくと、\( x \) の範囲は \( x\ge1 \) で、\( \pi\colon(0,\infty)\to\mathbb{N} \) は素数計数関数、\( \mu\colon\mathbb{N}\to\{0,\pm1\} \) はMöbius関数、\( \lfloor\cdot\rfloor\colon\mathbb{R}\to\mathbb{Z} \) は床関数、\( P\colon(0,\infty)\to\mathbb{N} \) は
$$
P(x):=\prod_{\substack{p\le x \\ p\colon\mathrm{prime}}}p
$$
です。総和項は \( P(\sqrt{x}) \) の正の約数全体に渡って和をとります。
今回はこの等式を利用して、素数が無限に存在することと、素数密度零定理(正式名称知りません)
$$
\lim_{x\to\infty}\frac{\pi(x)}{x}=0
$$
を証明しようと思います。
以下、基本的に \( x\to\infty \) について考えるので、\( x \) は十分大きい正の実数とします。
まずは素数が無限にあることを示しましょう。背理法を用いて矛盾を導く方針で行きます。
まず \( \pi(x) \)は増加関数なので、\( \pi(x) \) 及び \( \pi(\sqrt{x}) \) は \( x\to\infty \) で共に有限の値に収束するか、もしくは共に正の無限大に発散します(すなわち、前者は素数が有限個であることを指し、後者は素数が無限個であることを指します)。
もし素数が有限個であると仮定すると
$$
\lim_{x\to\infty}\left(\pi(x)-\pi(\sqrt{x})\right)=0
$$
なので、(1)式で \( x\to\infty \) とすれば
$$
\lim_{x\to\infty}\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor=1
\tag{2}
$$
を得ます。
次に、この総和を評価することを考えます。そのために、Möbius関数と床関数について成り立つ不等式
$$
\mu(d)\left\lfloor\frac{x}{d}\right\rfloor\ge\mu(d)\frac{x}{d}-1
$$
を利用します。なぜこの不等式が成立するかというと、\( P(\sqrt{x}) \) の定義から \( P(\sqrt{x}) \) の任意の正の約数 \( d \) に対して \( \mu(d)\in\{\pm1\} \) であり、\( \mu(d)=1 \) なら
$$
\mu(d)\left\lfloor\frac{x}{d}\right\rfloor\ge\mu(d)\frac{x}{d}-1\Longleftrightarrow \left\lfloor\frac{x}{d}\right\rfloor\ge \frac{x}{d}-1\Longleftrightarrow \frac{x}{d}-\left\lfloor\frac{x}{d}\right\rfloor\le 1
$$
\( \mu(d)=-1 \) なら
$$
\mu(d)\left\lfloor\frac{x}{d}\right\rfloor\ge\mu(d)\frac{x}{d}-1\Longleftrightarrow -\left\lfloor\frac{x}{d}\right\rfloor\ge -\frac{x}{d}-1\Longleftrightarrow \frac{x}{d}-\left\lfloor\frac{x}{d}\right\rfloor\ge -1
$$
となって、それぞれ明らかに成り立つことが分かるからです。
これより
$$
\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor\ge \sum_{d\mid P(\sqrt{x})}\left(\mu(d)\frac{x}{d}-1\right)=x\sum_{d\mid P(\sqrt{x})}\frac{\mu(d)}{d}-\sum_{d\mid P(\sqrt{x})}1
$$
と評価できます。さらに、\( p_1,p_2,\ldots,p_n \) を\( \sqrt{x} \) 以下の素数を小さい順に並べたもの(すなわち \( n=\pi(\sqrt{x}) \) )とすると
$$
\begin{align*}
\sum_{d\mid P(\sqrt{x})}\frac{\mu(d)}{d}&=\mu(1)+\sum_{k=1}^{n}\sum_{\substack{I\subset\{1,2,\ldots,n\} \\ |I|=k}}\frac{\displaystyle\mu\left(\prod_{i\in I}p_i\right)}{\displaystyle\prod_{i\in I}p_i} \\
&=1+\sum_{k=1}^{n}\sum_{\substack{I\subset\{1,2,\ldots,n\} \\ |I|=k}}\frac{(-1)^k}{\displaystyle\prod_{i\in I}p_i} \\
&=1+\sum_{k=1}^{n}(-1)^k\sum_{\substack{I\subset\{1,2,\ldots,n\} \\ |I|=k}}\prod_{i\in I}\frac{1}{p_i} \\
&=\prod_{i=1}^{n}\left(1-\frac{1}{p_i}\right) \\
&=\prod_{\substack{p\le\sqrt{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)
\end{align*}
$$
および
$$
\sum_{d\mid P(\sqrt{x})}1=d(P(\sqrt{x}))=2^{n}=2^{\pi(\sqrt{x})}
$$
と計算できる(ただし \( d\colon\mathbb{N}\to\mathbb{N} \) は約数個数関数)ので
$$
\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor\ge x\prod_{\substack{p\le\sqrt{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)-2^{\pi(x)}
$$
が従います。この不等式で \( x\to\infty \) としてみると、素数が有限個であると仮定したことから、\( \displaystyle\lim_{x\to\infty} 2^{\pi(\sqrt{x})} \) と
$$
\lim_{x\to\infty}\prod_{\substack{p\le\sqrt{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)
$$
は共に正の有限値に収束するので
$$
\lim_{x\to\infty}\left(x\prod_{\substack{p\le\sqrt{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)-2^{\pi(x)}\right)=\infty
$$
となり、従って
$$
\lim_{x\to\infty}\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor=\infty
$$
が成り立ちます。
これは、(2)式に明らかに矛盾しています。ゆえに、素数が有限個だと仮定していたので、背理法により素数は無限に存在することが示されました。
なお、この証明は、数学を愛する会さんの選手権で応募させて頂いたものと同じになります。RTして頂いてありがとうございました。(どこでお礼言ってんねん)
さてさて、次に、素数密度が0になることを証明しましょう。実は、証明のために(1)式を少し改変する必要があるのですが、天下り的になることを避けるために、まずはそのままの形で試してみようと思います (つまり、今から書くものは証明ではなく考え方を説明したものです)。
(1)式を用いて \( \pi(x) \) を上から評価してゆきます。\( \pi(x) \) は正値関数なので、その評価式を \( x \) で割ったものが \( x\to\infty \) で0に収束することを言えればよいですね。
さて、まず明らかに \( \pi(x)\le x\) が成り立つので
$$
\pi(x)=\pi(\sqrt{x})-1+\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor\le \sqrt{x}-1+\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor
$$
を得ます。また、上で素数の無限性を示したときと同じ要領で
$$
\mu(d)\left\lfloor\frac{x}{d}\right\rfloor\le\mu(d)\frac{x}{d}+1
$$
が成り立つことが分かるので、総和項は
$$
\begin{align*}
\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor&\le\sqrt{x}-1+\sum_{d\mid P(\sqrt{x})}\left(\mu(d)\frac{x}{d}+1\right) \\
&=x\sum_{d\mid P(\sqrt{x})}\frac{\mu(d)}{d}+\sum_{d\mid P(\sqrt{x})}1 \\
&=x\prod_{\substack{p\le\sqrt{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)+2^{\pi(\sqrt{x})}
\end{align*}
$$
と評価できます。よって
$$
\frac{\pi(x)}{x}\le\frac{1}{\sqrt{x}}-\frac{1}{x}+\prod_{\substack{p\le\sqrt{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)+\frac{2^{\pi(\sqrt{x})}}{x}
$$
となり、\( x\to\infty \) で右辺第一項・第二項は明らかに0に収束、さらに
$$
\lim_{x\to\infty}\prod_{\substack{p\le\sqrt{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)=\frac{1}{\zeta(1)}=0
$$
となるので希望の光が見えてきます。よしっ！っと思って、最後の項を考えます。すると
$$
\lim_{x\to\infty}\frac{2^{\pi(\sqrt{x})}}{x}=\infty
$$
となるなので、証明できねぇじゃん！！！！！！！！！！ということが判明します。。。。。。。(Game Over)
何が問題なのかというと、\( \sqrt{x} \) が大きすぎるために、誤差として出てきた \( 2^{\pi(\sqrt{x})} \) がとても邪魔だということです(Wikiによると、この誤差は(1)式の証明に用いた包除原理によるものらしいです)。
これをどうにかするために(1)式を手直しする必要があるわけです。といっても、式の構造を大幅に変えようとするとEratosthenesの篩の本質を失ってしまう可能性があるので、\( \sqrt{x} \) のみをどうにかしたい気持ちがあります。
そこで、次の不等式に辿り着きます。
$$
\pi(x)\le\pi(f(x))-1+\sum_{d\mid P(f(x))}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor
\tag{3}
$$
ただし、\( f(x) \) は \( f(x)\le\sqrt{x} \) を満たす関数です。この不等式は、前回記事と同様に包除原理を用いた議論をすることによって
$$
\pi(x)-\pi(f(x))+1\le\lfloor x\rfloor-\left|\bigcup_{\substack{p\le f(x) \\ p\colon\mathrm{prime}}}\{m\in p\mathbb{Z}\mid 1\le m\le x\}\right|
$$
と同値であることが分かります。
この不等式の証明も念の為記述しておきましょう。左辺は \( f(x) \) より大きく \( x \) 以下である素数と、素数でも合成数でもない正の整数 \( 1 \) を合わせた整数の個数を表します。対して、右辺は \( x \) 以下の正の整数であって、\( f(x) \) 以下のどの素数でも割り切れないものの個数を表しますが、Eratosthenesの篩の考えから、これは \( f(x) \) より大きい素数のみを素因数としてもつ正の整数と \( 1 \) を合わせた整数の個数に等しいです。
よって、明らかに前者(左辺)より後者(右辺)の方が個数が多いので、不等式の成立を確かめることができました。
さて、この不等式(3)を用いた素数密度零定理の証明を考えると、証明においてネックだった \( 2^{\pi(\sqrt{x})} \) は \( 2^{\pi(f(x))} \) となり、\( 2^{\pi(f(x))}\le2^{f(x)} \) より \( \dfrac{2^{f(x)}}{x} \) が0に収束するような \( f(x) \) をとればよいわけです。
改めてキチンと書きましょう。(3)式において \( f(x)=\log{x} \) としてみると
$$
\begin{align*}
\pi(x)&\le\pi(\log{x})-1+\sum_{d\mid P(\log{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor \\
&\le\log{x}-1+\sum_{d\mid P(\log{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor \\
&\le\log{x}-1+\sum_{d\mid P(\log{x})}\left(\mu(d)\frac{x}{d}+1\right) \\
&=\log{x}-1+x\prod_{\substack{p\le\log{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)+2^{\pi(\log{x})} \\
&\le\log{x}-1+x\prod_{\substack{p\le\log{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)+2^{\log{x}}
\end{align*}
$$
となるので、\( 2^{\log{x}}=e^{\log{2}\log{x}}=x^{\log{2}}<x \) であることに注意すると
$$
\frac{\pi(x)}{x}\le\frac{\log{x}}{x}-\frac{1}{x}+\prod_{\substack{p\le\log{x} \\ p\colon\mathrm{prime}}}\left(1-\frac{1}{p}\right)+\frac{2^{\log{x}}}{x}\to 0\quad(x\to\infty)
$$
が成り立ち
$$
\lim_{x\to\infty}\frac{\pi(x)}{x}=0
$$
が従います。これで証明は完了です。
いかがでしたでしょうか。素数の無限性や素数密度の情報を自明には含まないEratosthenesの篩からこんなに色々証明できて、凄く面白いと僕は思います。
他にも素数の性質を証明できるかもしれませんね。何か証明を発見した方は教えて頂けると幸いです。
Legendreによる素数計数関数の等式を証明～Eratosthenesの篩～
今回は、Legendreが発見した、次の素数計数関数に関する等式を証明しようと思います。
$$
\pi(x)=\pi(\sqrt{x})-1+\sum_{d\mid P_x}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor
$$
ただし、\( x \) は \( 1 \) 以上の実数とし、\( \mu:\mathbb{N}\to\{0,\pm1\} \) はMöbius関数で、\( P_x \) は
$$
P_x:=\prod_{\substack{p\le\sqrt{x} \\ p:\mathrm{prime}}}p
$$
で定めます。なお、\( 1\le x<4 \) では \( P_x:=1 \) とします。また、総和項は \( P_x \) の正の約数全体に渡って和をとることを意味します。
さて、さっそく証明に入りましょう。まず、\( 1\le x<4 \) のときは \( \pi(\sqrt{x})=0 \) より
$$
\pi(x)=\lfloor x\rfloor -1
$$
を示すことになりますが、これは簡単に確認できます。実際
$$
\begin{align*}
1\le x<2&\Longrightarrow \pi(x)=0,\qquad \lfloor x\rfloor -1=1-1=0 \\
2\le x<3&\Longrightarrow \pi(x)=1,\qquad \lfloor x\rfloor -1=2-1=1 \\
3\le x<4&\Longrightarrow \pi(x)=2,\qquad \lfloor x\rfloor -1=3-1=2
\end{align*}
$$
となり成立が示せました。
次に \( x\ge 4 \) のとき、\( P_x \) は定義から
$$
P_x=\prod_{i=1}^{n}p_i
$$
とできます。ここで、\( n=\pi(\sqrt{x}) \) とし、\( p_1,p_2,\ldots,p_n \) は \( \sqrt{x} \) 以下の素数を小さい順に並べたものとします。 すると、\( P_x \) の \( 1 \) でない正の約数 \( d \) は、空でない集合 \( I\subset\{1,2,\ldots,n\} \) を一意に選んで
$$
d=\prod_{i\in I}p_i
$$
と書けるので、\( I \) の元の個数で分けて考えると、示したい等式の総和項は
$$
\begin{align*}
\sum_{d\mid P_x}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor &=\mu(1)\lfloor x\rfloor+\sum_{k=1}^{n}\sum_{\substack{I\subset\{1,2,\ldots,n\} \\ |I|=k}}\mu\left(\prod_{i\in I}p_i\right)\left\lfloor \frac{x}{\displaystyle\prod_{i\in I}p_i}\right\rfloor \\
&=\lfloor x\rfloor+\sum_{k=1}^{n}\sum_{\substack{I\subset\{1,2,\ldots,n\} \\ |I|=k}}(-1)^{k}\left\lfloor \frac{x}{\displaystyle\prod_{i\in I}p_i}\right\rfloor \\
&=\lfloor x\rfloor-\sum_{k=1}^{n}(-1)^{k -1}\sum_{\substack{I\subset\{1,2,\ldots,n\} \\ |I|=k}}\left\lfloor \frac{x}{\displaystyle\prod_{i\in I}p_i}\right\rfloor
\end{align*}
$$
となります。また、この最右辺において
$$
\left\lfloor \frac{x}{\displaystyle\prod_{i\in I}p_i}\right\rfloor=\left|\bigcap_{i\in I}\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}\right|
$$
とできるので、包除原理により
$$
\begin{align*}
\sum_{k=1}^{n}(-1)^{k -1}\sum_{\substack{I\in\{1,2,\ldots,n\} \\ |I|=k}}\left\lfloor \frac{x}{\displaystyle\prod_{i\in I}p_i}\right\rfloor &=\sum_{k=1}^{n}(-1)^{k -1}\sum_{\substack{I\in\{1,2,\ldots,n\} \\ |I|=k}}\left|\bigcap_{i\in I}\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}\right| \\
&=\left|\bigcup_{i=1}^{n}\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}\right|
\end{align*}
$$
が成り立ちます。
以上から
$$
\pi(x)-\pi(\sqrt{x})+1=\lfloor x\rfloor-\left|\bigcup_{i=1}^{n}\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}\right|
$$
を示せばよいことになります。が、これはEratosthenesの篩を考えると成立は明らかです。
すなわち、左辺は \( \sqrt{x} \) より大きく \( x \) 以下である素数と、素数でも合成数でもない正の整数 \( 1 \) を合わせた整数の個数を表します。対して、右辺は \( x \) 以下の正の整数であって、\( \sqrt{x} \) 以下のどの素数でも割り切れないものの個数を表しますが、Eratosthenesの篩で分かるように、ここには \( 1 \) と \( \sqrt{x} \) より大きい素数しか残りません。なぜなら、もし \( x \) 以下の正の合成数 \( m \)であって、\( \sqrt{x} \) 以下のどの素数でも割り切れないものが存在すると仮定すると
$$
x\ge m\ge {p_{n+1}}^{2} >(\sqrt{x})^2=x
$$
となり矛盾するからです。
よって、両者の個数は一致するので、等式の成立が保証され、最初の等式が成り立つことが証明されました。
ちなみに、\( x\ge4 \) では \( 2\lceil \sqrt{x} \rceil \le x \) が成り立つので
$$
\sqrt{x}\le\lceil \sqrt{x} \rceil<2\lceil \sqrt{x} \rceil \le x
$$
であることを考えると、Bertrandの仮説より、\( \sqrt{x}<p\le x \) を満たす素数 \( p \) が必ず存在します。
如何でしたでしょうか。個人的に、\( n \) 個の包除原理を用いたのは初めてだったので、証明を考えてるときとても楽しかったです (安定の小並感)。また、本等式は素数計数関数についてのWikiで見つけたものでしが、最初Eratosthenesの篩が関係してくるとは全然思ってませんでした (ちなみに、その後Eratosthenesの篩についてのWikiを見るとガッツリ等式が載ってました)。
なお、今回の等式を用いて \( \pi(x) \) を適当に評価することにより
$$
\lim_{x\to\infty}\frac{\pi(x)}{x}=0
$$
を示すこともできます (その内この証明も書こうと思います) 。それではこの辺で～。
