1

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

114
0
$$$$

※本記事は、はてなブログに投稿してたのを統合してMathlogの様式に合わせて移植したものになります。

以下、関数$\pi,\mu,\lfloor\cdot\rfloor$をそれぞれ素数計数関数、Möbius関数、床関数とします。どれも有名な関数なので、それぞれがどのような関数なのかの説明は省略しますが、万が一分からないものがあったらggってWikiとか見てください。
また、関数$P\colon[1,\infty)\to\mathbb{N}$
$$ P(x):= \displaystyle\prod_{\substack{p\le x \\ p\colon\mathrm{prime}}}p $$
で定めます。ただし、$x\in[1,2)$では空積を適用します。

さて今回は、Legendreが発見した、次の素数計数関数に関する等式で遊んでみようと思います。

1以上の実数$x$に対して
$$ \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\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 $$
となり矛盾するからである。

よって、両者の個数は一致するので、等式の成立が保証され、最初の等式が成り立つことが示された。

Eratosthenesの篩の部分の補足

$x\in[1,4)$では$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$が必ず存在する。

証明を読んだら分かると思いますが、実はこの等式(1)はEratosthenesの篩に大きく関係していたのでした。昔初めて篩を習ったときは、単なる素数を見つける手法としか思っていませんでしたが、このように式として表現されると、色々と応用が利きそうに感じます。

というわけで、(1)式を用いて2つの命題を証明します。

素数は無限に存在する。

以下、$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)式に明らかに矛盾する。ゆえに、素数が有限個だと仮定していたので、背理法により素数は無限に存在することが示された。

なんと、素数の無限性を証明できてしまいました。多分あまり知られていない証明法だと思います。

次に、素数密度零定理(正式名称知りません)を証明します。

素数密度零定理

素数は
$$ \lim_{x\to\infty}\frac{\pi(x)}{x}=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 $$
が成り立つので、このままでは冒頭で述べた方針で証明できないことが発覚する。

何が問題なのかというと、$\sqrt{x}$が大きすぎるために、誤差として出てきた$2^{\pi(\sqrt{x})} $がとても邪魔だということです(Wikiによると、この誤差は(1)式の証明に用いた包除原理によるものらしいです)。

これをどうにかするために(1)式を手直しする必要があるわけです。といっても、式の構造を大幅に変えようとするとEratosthenesの篩の本質を失ってしまう可能性があるので、$\sqrt{x}$のみをどうにかしたい気持ちがあります。

そこで、次の不等式に辿り着きます。

$f(x)\le\sqrt{x}$を満たす関数$f(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} $$
が成り立つ。

一応軽く証明しておきましょう。

(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)を用いた素数密度零定理の証明を考えると、証明においてネックだった$2^{\pi(\sqrt{x})}$$2^{\pi(f(x))}$となり、$2^{\pi(f(x))}\le2^{f(x)}$より$\dfrac{2^{f(x)}}{x} $が0に収束するような$f(x)$をとればよいわけです。

改めてキチンと書きましょう。

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

これで証明は完了です。

いかがでしたでしょうか。素数の無限性や素数密度の情報を自明には含まないEratosthenesの篩からこんなに色々証明できて、僕は凄く面白いと思いました。

まだまだ弄れそうな気がするので、もっと色々考えてみたいですね。

投稿日:202182

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

京大理学部B3数理科学系

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中