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

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

次に $x\in[4,\infty)$のとき、$P(\sqrt{x})$は定義から
$$ P(\sqrt{x})=\prod_{i=1}^{n}p_i $$
と書ける。ここで、$n:=\pi(\sqrt{x})$であり、$p_1,p_2,\ldots,p_n$は$\sqrt{x}$以下の素数を小さい順に並べたものとする。
すると、$P(\sqrt{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$を十分大きい正の実数とする。

まず$\pi$は増加関数なので、$\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 $$
と評価できる。さらに
$$ \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(\sqrt{x})} $$
が従う。この不等式で$x\to\infty$としてみると、素数が有限個であると仮定したことから
$$ \lim_{x\to\infty} 2^{\pi(\sqrt{x})},\quad\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(\sqrt{x})}\right)=\infty $$
となり、従って
$$ \lim_{x\to\infty}\sum_{d\mid P(\sqrt{x})}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor=\infty $$
が成り立つ。

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

(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 $$
が成り立つので、このままでは冒頭で述べた方針で証明できないことが発覚する。

(3)式は、定理1と同様に包除原理を用いた議論をすることによって
$$ \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|\tag{4} $$
と同値であることが分かる。

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

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

(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 $$
が従う。