Eratosthenesの篩から素数の無限性と密度を暴く

まず、$x\in [1,4)$のときは$\pi (\sqrt{x})=0,P(\sqrt{x})=1$より
$$\pi (x)=\lfloor x\rfloor -1$$
を示すことになるが、これは
$$\begin{array}{rl}x\in [1,2)& ⟹\pi (x)=0,\lfloor x\rfloor -1=1-1=0\\ x\in [2,3)& ⟹\pi (x)=1,\lfloor x\rfloor -1=2-1=1\\ x\in [3,4)& ⟹\pi (x)=2,\lfloor x\rfloor -1=3-1=2\end{array}$$
より成立する。

次に $x\in [4,\mathrm{\infty })$のとき、$P(\sqrt{x})$は定義から
$$P(\sqrt{x})=\prod _{i=1}^n{p}_i$$
と書ける。ここで、$n:=\pi (\sqrt{x})$であり、$p_1,p_2,\dots ,p_n$は$\sqrt{x}$以下の素数を小さい順に並べたものとする。
すると、$P(\sqrt{x})$の1でない正の約数$d$は、空でない集合$I\subset \{1,2,\dots ,n\}$を一意に選んで
$$d=\prod _{i\in I}{p}_i$$
と書けるので、$I$の元の個数で分けて考えると、示したい等式の総和項は
$$\begin{array}{rl}\sum _{d\mid P_x}\mu (d)\lfloor \frac{x}{d}\rfloor & =\mu (1)\lfloor x\rfloor +\sum _{k=1}^n\sum _{\begin{array}{c}I\subset \{1,2,\dots ,n\}\\ |I|=k\end{array}}\mu \left(\prod _{i\in I}{p}_i\right)\lfloor \frac{x}{{\displaystyle \prod _{i\in I}{p}_i}}\rfloor \\ & =\lfloor x\rfloor +\sum _{k=1}^n\sum _{\begin{array}{c}I\subset \{1,2,\dots ,n\}\\ |I|=k\end{array}}(-1{)}^k\lfloor \frac{x}{{\displaystyle \prod _{i\in I}{p}_i}}\rfloor \\ & =\lfloor x\rfloor -\sum _{k=1}^n(-1{)}^{k-1}\sum _{\begin{array}{c}I\subset \{1,2,\dots ,n\}\\ |I|=k\end{array}}\lfloor \frac{x}{{\displaystyle \prod _{i\in I}{p}_i}}\rfloor \end{array}$$
となる。また、この最右辺において
$$\lfloor \frac{x}{{\displaystyle \prod _{i\in I}{p}_i}}\rfloor =|\bigcap _{i\in I}\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}|$$
とできるので、包除原理により
$$\begin{array}{rl}\sum _{k=1}^n(-1{)}^{k-1}\sum _{\begin{array}{c}I\in \{1,2,\dots ,n\}\\ |I|=k\end{array}}\lfloor \frac{x}{{\displaystyle \prod _{i\in I}{p}_i}}\rfloor & =\sum _{k=1}^n(-1{)}^{k-1}\sum _{\begin{array}{c}I\in \{1,2,\dots ,n\}\\ |I|=k\end{array}}|\bigcap _{i\in I}\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}|\\ & =|\bigcup _{i=1}^n\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}|\end{array}$$
が成り立つ。

以上から
$$\pi (x)-\pi (\sqrt{x})+1=\lfloor x\rfloor -|\bigcup _{i=1}^n\{m\in p_i\mathbb{Z}\mid 1\le m\le x\}|$$
を示せばよいことになるが、これは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$を十分大きい正の実数とする。

まず$\pi$は増加関数なので、$\pi (x)$及び$\pi (\sqrt{x})$は$x\to \mathrm{\infty }$で共に有限の値に収束するか、もしくは共に正の無限大に発散する(すなわち、前者は素数が有限個であることを指し、後者は素数が無限個であることを指す)。

もし素数が有限個であると仮定すると
$$\underset{x\to \mathrm{\infty }}{lim}(\pi (x)-\pi (\sqrt{x}))=0$$
なので、(1)式で$x\to \mathrm{\infty }$とすれば
$$\begin{array}{}\text{(2)}& \underset{x\to \mathrm{\infty }}{lim}\sum _{d\mid P(\sqrt{x})}\mu (d)\lfloor \frac{x}{d}\rfloor =1\end{array}$$
を得る。

次に、この総和を評価することを考える。そのために、Möbius関数と床関数について成り立つ不等式
$$\mu (d)\lfloor \frac{x}{d}\rfloor \ge \mu (d)\frac{x}{d}-1$$
を利用する。なぜこの不等式が成立するかというと、$P(\sqrt{x})$の定義から$P(\sqrt{x})$の任意の正の約数$d$に対して$\mu (d)\in \{\pm 1\}$であり、$\mu (d)=1$なら
$$\mu (d)\lfloor \frac{x}{d}\rfloor \ge \mu (d)\frac{x}{d}-1⟺\lfloor \frac{x}{d}\rfloor \ge \frac{x}{d}-1⟺\frac{x}{d}-\lfloor \frac{x}{d}\rfloor \le 1$$
$\mu (d)=-1$なら
$$\mu (d)\lfloor \frac{x}{d}\rfloor \ge \mu (d)\frac{x}{d}-1⟺-\lfloor \frac{x}{d}\rfloor \ge -\frac{x}{d}-1⟺\frac{x}{d}-\lfloor \frac{x}{d}\rfloor \ge -1$$
となって、それぞれ明らかに成り立つことが分かるからである。

これより
$$\sum _{d\mid P(\sqrt{x})}\mu (d)\lfloor \frac{x}{d}\rfloor \ge \sum _{d\mid P(\sqrt{x})}(\mu (d)\frac{x}{d}-1)=x\sum _{d\mid P(\sqrt{x})}\frac{\mu (d)}{d}-\sum _{d\mid P(\sqrt{x})}1$$
と評価できる。さらに
$$\begin{array}{rl}\sum _{d\mid P(\sqrt{x})}\frac{\mu (d)}{d}& =\mu (1)+\sum _{k=1}^n\sum _{\begin{array}{c}I\subset \{1,2,\dots ,n\}\\ |I|=k\end{array}}\frac{{\displaystyle \mu \left(\prod _{i\in I}{p}_i\right)}}{{\displaystyle \prod _{i\in I}{p}_i}}\\ & =1+\sum _{k=1}^n\sum _{\begin{array}{c}I\subset \{1,2,\dots ,n\}\\ |I|=k\end{array}}\frac{(-1{)}^k}{{\displaystyle \prod _{i\in I}{p}_i}}\\ & =1+\sum _{k=1}^n(-1{)}^k\sum _{\begin{array}{c}I\subset \{1,2,\dots ,n\}\\ |I|=k\end{array}}\prod _{i\in I}\frac{1}{p_i}\\ & =\prod _{i=1}^n(1-\frac{1}{p_i})\\ & =\prod _{\begin{array}{c}p\le \sqrt{x}\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})\end{array}$$
および
$$\sum _{d\mid P(\sqrt{x})}1=d(P(\sqrt{x}))=2^n=2^{\pi (\sqrt{x})}$$
と計算できる(ただし$d:\mathbb{N}\to \mathbb{N}$は約数個数関数)ので
$$\sum _{d\mid P(\sqrt{x})}\mu (d)\lfloor \frac{x}{d}\rfloor \ge x\prod _{\begin{array}{c}p\le \sqrt{x}\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})-2^{\pi (\sqrt{x})}$$
が従う。この不等式で$x\to \mathrm{\infty }$としてみると、素数が有限個であると仮定したことから
$$\underset{x\to \mathrm{\infty }}{lim}{2}^{\pi (\sqrt{x})},\underset{x\to \mathrm{\infty }}{lim}\prod _{\begin{array}{c}p\le \sqrt{x}\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})$$
は共に正の有限値に収束するので
$$\underset{x\to \mathrm{\infty }}{lim}(x\prod _{\begin{array}{c}p\le \sqrt{x}\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})-2^{\pi (\sqrt{x})})=\mathrm{\infty }$$
となり、従って
$$\underset{x\to \mathrm{\infty }}{lim}\sum _{d\mid P(\sqrt{x})}\mu (d)\lfloor \frac{x}{d}\rfloor =\mathrm{\infty }$$
が成り立つ。

これは、(2)式に明らかに矛盾する。ゆえに、素数が有限個だと仮定していたので、背理法により素数は無限に存在することが示された。

(1)式を用いて$\pi (x)$を上から評価する。$\pi (x)$は正値関数なので、その評価式を$x$で割ったものが$x\to \mathrm{\infty }$で0に収束することを言えばよい。

さて、まず明らかに$\pi (x)\le x$が成り立つので
$$\pi (x)=\pi (\sqrt{x})-1+\sum _{d\mid P(\sqrt{x})}\mu (d)\lfloor \frac{x}{d}\rfloor \le \sqrt{x}-1+\sum _{d\mid P(\sqrt{x})}\mu (d)\lfloor \frac{x}{d}\rfloor$$
を得る。また、素数の無限性の証明と同じ要領で
$$\mu (d)\lfloor \frac{x}{d}\rfloor \le \mu (d)\frac{x}{d}+1$$
が成り立つことが分かるので、総和項は
$$\begin{array}{rl}\sum _{d\mid P(\sqrt{x})}\mu (d)\lfloor \frac{x}{d}\rfloor & \le \sqrt{x}-1+\sum _{d\mid P(\sqrt{x})}(\mu (d)\frac{x}{d}+1)\\ & =x\sum _{d\mid P(\sqrt{x})}\frac{\mu (d)}{d}+\sum _{d\mid P(\sqrt{x})}1\\ & =x\prod _{\begin{array}{c}p\le \sqrt{x}\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})+2^{\pi (\sqrt{x})}\end{array}$$
と評価できる。よって
$$\frac{\pi (x)}{x}\le \frac{1}{\sqrt{x}}-\frac{1}{x}+\prod _{\begin{array}{c}p\le \sqrt{x}\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})+\frac{2^{\pi (\sqrt{x})}}{x}$$
となり、$x\to \mathrm{\infty }$で右辺第一項・第二項は明らかに0に収束、さらに
$$\underset{x\to \mathrm{\infty }}{lim}\prod _{\begin{array}{c}p\le \sqrt{x}\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})=\frac{1}{\zeta (1)}=0$$
となる。しかし
$$\underset{x\to \mathrm{\infty }}{lim}\frac{2^{\pi (\sqrt{x})}}{x}=\mathrm{\infty }$$
が成り立つので、このままでは冒頭で述べた方針で証明できないことが発覚する。

(3)式は、定理1と同様に包除原理を用いた議論をすることによって
$$\begin{array}{}\text{(4)}& \pi (x)-\pi (f(x))+1\le \lfloor x\rfloor -|\bigcup _{\begin{array}{c}p\le f(x)\\ p:\mathrm{prime}\end{array}}\{m\in p\mathbb{Z}\mid 1\le m\le x\}|\end{array}$$
と同値であることが分かる。

(4)式について、左辺は$f(x)$より大きく$x$以下である素数と、素数でも合成数でもない正の整数1を合わせた整数の個数を表す。対して、右辺は$x$以下の正の整数であって、$f(x)$以下のどの素数でも割り切れないものの個数を表すが、Eratosthenesの篩の考えから、これは$f(x)$より大きい素数のみを素因数としてもつ正の整数と1を合わせた整数の個数に等しい。

よって、明らかに前者(左辺)より後者(右辺)の方が個数が多いので、(4)式は成立し、ゆえに(3)式が示された。

(3)式において$f(x)=\log x$としてみると、
$$\begin{array}{rl}\pi (x)& \le \pi (\log x)-1+\sum _{d\mid P(\log x)}\mu (d)\lfloor \frac{x}{d}\rfloor \\ & \le \log x-1+\sum _{d\mid P(\log x)}\mu (d)\lfloor \frac{x}{d}\rfloor \\ & \le \log x-1+\sum _{d\mid P(\log x)}(\mu (d)\frac{x}{d}+1)\\ & =\log x-1+x\prod _{\begin{array}{c}p\le \log x\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})+2^{\pi (\log x)}\\ & \le \log x-1+x\prod _{\begin{array}{c}p\le \log x\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})+2^{\log x}\end{array}$$
となるので、$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 _{\begin{array}{c}p\le \log x\\ p:\mathrm{prime}\end{array}}(1-\frac{1}{p})+\frac{2^{\log x}}{x}\to 0(x\to \mathrm{\infty })$$
が成り立ち
$$\underset{x\to \mathrm{\infty }}{lim}\frac{\pi (x)}{x}=0$$
が従う。