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 $$

を示すこともできます (その内この証明も書こうと思います) 。それではこの辺で～。