素数計数関数の恒等式
はじめに
はじめまして！与えられた非負の実数$N$以下の素数の個数を数える関数は素数計数関数と呼ばれ、$\pi(N)$で表されます。私は高校生の時に、素数計数関数の恒等式を考えました。まだ素数定理も証明できていませんが、素数の持つ美しい構造を感じて頂ければ幸いです。
この記事の主な目標は、次の恒等式を証明することです。
与えられた2以上の実数$N$について
\begin{equation}
\lfloor N \rfloor-1=\displaystyle \sum_{\ell=1}^{\lfloor \log_2{N} \rfloor} \sum_{m=1}^{\lfloor N/2^\ell \rfloor} \eta_{\ell m}\pi \Bigl( \sqrt[\ell]{N/m} \Bigr), \eta_{\ell m}=\frac{1}{\Omega(m)+\ell},
\end{equation}
が成り立つ。ここで、$\lfloor N \rfloor$は床関数と呼ばれ、$N$以下の最大の整数を与える。また$\Omega(n)$は、与えられた自然数$n$の重複を含めた素因数の個数を返す。
恒等式の証明
はじめに素数計数関数を拡張する。$k$-概素数を重複を含めた$k$個の素数の積と定義する。[1]では、$N$以下の2-概素数の計数関数を$\pi^{(2)}(N)$と表記している。そのため、$N$以下の$k$-概素数の個数を数える関数を$\pi^{(k)}(N)$と表記する。
2以上の実数$N$に対し、次の恒等式が成り立つ。
\begin{equation}
\lfloor N \rfloor = 1+ \displaystyle \sum_{k=1}^{\lfloor \log_2{N} \rfloor}\pi^{(k)}(N).
\end{equation}
$N$以下の自然数の個数は、1と全ての$k$-概素数の個数の総和と等しい。最小の$k$-概素数は$2^k$であり、$N\geq2^k$のとき$k$-概素数は存在する。$k$は自然数なので、$1 \leq k \leq \lfloor \log_2{N} \rfloor$と$N \geq 2$を得る。
$\pi^{(k)}(N)$を$\pi(N)$だけで表そうと試みる。
[1]より、$k=2$のとき
\begin{equation}
\pi^{(2)}(N) =\Biggl(\pi \bigl(\sqrt{N} \bigr)+\displaystyle \sum_{i=1}^{\pi(N/2)}\pi(N/p_i) \Biggr)/2,
\end{equation}
が成り立つ。ここで$p_i$は$i$番目の素数である。
任意の相異なる素数を$p_1$,$p_2$と置くと、2-概素数は全て${p_1}^2$か$p_1p_2$で表される。
・$N ={p_1}^2$に対し、$\pi \bigl(\sqrt{N} \bigr)$と$\pi(N/p_1)$は互いに1増加する。
・$N = p_1p_2$に対し、$\pi(N/p_1)$と$\pi(N/p_2)$は互いに1増加する。
これらの合計を2で割ったものは$\pi^{(2)}(N)$と等しい。
この計算を表1にする。
| $\pi \bigr( \sqrt{N} \bigl)$ | ${\displaystyle \sum_{i=1}^{\pi(N/2)}\pi(N/p_i)}$ | 合計 | 合計/2 | |
|---|---|---|---|---|
| ${p_1}^2$ | +1 | +1 | +2 | +1 |
| $p_1p_2$ | 0 | +2 | +2 | +1 |
表1: $\pi^{(2)}(N)$の計算
補題2を基に、$k=3$のとき
\begin{equation*}
\pi^{(3)}(N) = \Biggl( \pi \bigl( \sqrt[3]{N} \bigr) + {\displaystyle \sum_{i=1}^{p_i=\lfloor N/4\rfloor} \pi \Bigl( \sqrt{N/p_i} \Bigr)}+
{\displaystyle \sum_{\substack{{i_1},{i_2}=1\\{i_1}={i_2}}}^{p_{i_1}p_{i_2} \leq \lfloor N/2 \rfloor }\pi(N/p_{i_1} p_{i_2})} \Biggr)/3,
\end{equation*}
が成り立つ。ここで$\displaystyle \sum_{\substack{{i_1},{i_2}=1\\{i_1}={i_2}}}^{p_{i_1}p_{i_2} \leq \lfloor N/2 \rfloor}$は$\lfloor N/2 \rfloor$以下の重複を含む全ての$p_{i_1}p_{i_2}$について総和を取ることを意味する。
任意の相異なる素数を$p_1$,$p_2$,$p_3$と置くと、3-概素数は全て${p_1}^3$,${p_1}^2p_2$,$p_1p_2p_3$のいずれかで表される。
・$N = {p_1}^3$に対し、$\pi \bigl(\sqrt[3]{N} \bigr)$,$\pi \bigl( \sqrt{N/p_1} \bigr)$,$\pi(N/{p_1}^2)$はそれぞれ1増加する。
・$N = {p_1}^2p_2$に対し、$\pi \bigl( \sqrt{N/p_2} \bigr)$,$\pi(N/{p_1}^2)$,$\pi(N/p_1p_2)$はそれぞれ1増加する。
・$N = p_1p_2p_3$に対し、$\pi(N/p_1p_2)$,$\pi(N/p_1p_3)$,$\pi(N/p_2p_3)$はそれぞれ1増加する。
これらの合計を3で割ったものは$\pi^{(3)}(N)$と等しい。
この計算を表2に示す。
| $\pi \bigl(\sqrt[3]{N} \bigr)$ | ${\displaystyle \sum_{i=1}^{p_i= \lfloor N/4 \rfloor}\pi \Bigl( \sqrt{N/p_i} \Bigr)}$ | ${\displaystyle \sum_{\substack{{i_1},{i_2}=1\\{i_1}={i_2}}}^{p_{i_1}p_{i_2} \leq \lfloor N/2 \rfloor}\pi(N/p_{i_1} p_{i_2})}$ | 合計 | 合計/3 | |
|---|---|---|---|---|---|
| ${p_1}^3$ | +1 | +1 | +1 | +3 | +1 |
| ${p_1}^2p_2$ | 0 | +1 | +2 | +3 | +1 |
| $p_1p_2p_3$ | 0 | 0 | +3 | +3 | +1 |
表2: $\pi^{(3)}(N)$の計算
次に$\pi(N)$の性質からいくつか補題を導く。
与えられた実数$N$以下の$mp$で表される数の個数は$\pi(N/m)$と等しい。
ここで$m$はある自然数、$p$は任意の素数とする。
$m=1$のとき、定義より明らか。
$m=2$のとき、$\pi(N/2)=n$とする。$N/2$を超えない素数を$p_1 , \dots , p_n$と列挙できる。ここで$p_k$は$k$番目の素数である。また$N$を超えない$2p$は$2p_1, \dots, 2p_n$と列挙できる。したがって、$\pi(N/2)$は$N$を超えない$2p$で表される数の個数と等しい。
2を$m$に置き換えることで、任意の自然数$m$について成り立つ。
与えられた実数$N$以下の$p^\ell$で表される数の個数は$\pi\bigl(\sqrt[\ell]{N}\bigr)$と等しい。
ここで$\ell$はある自然数、$p$は任意の素数とする。
$\ell=1$のとき、定義より明らか。
$\ell=2$のとき、$\pi\bigl(\sqrt{N}\bigr)=n$とする。$\sqrt{N}$を超えない素数を$p_1 , \dots , p_n$と列挙できる。ここで$p_k$は$k$番目の素数である。また$N$を超えない$p^2$は${p_1}^2, \dots, {p_n}^2$と列挙できる。したがって、$\pi\bigl(\sqrt{N}\bigr)$は$N$を超えない$p^2$で表される数の個数と等しい。
2を$\ell$に置き換えることで、任意の自然数$\ell$について成り立つ。
与えられた実数$N$以下の$mp^\ell$で表される数の個数は$\pi \bigl( \sqrt[\ell]{N/m} \bigr)$と等しい。
補題5より、$\pi \bigl( \sqrt[\ell]{N/m} \bigr)$は$N/m$以下の$p^\ell$の個数と等しい。補題4は$N/m$以下の素数の個数は$N$以下の$mp$の個数と等しいことを意味する。それゆえ、$N/m$以下の$p^\ell$の個数は$N$以下の$mp^\ell$の個数と等しい。
これらの補題を使って次の命題を示す。
$k$を2以上の自然数とすると、
\begin{equation} \label{eq:k-almostcountingfunction}
\pi^{(k)}(N) = \Biggl( \pi \bigl( \sqrt[k]{N} \bigr) + \displaystyle \sum_{j=1}^{k-1} \sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}^{p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor }\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr) \Biggr)/k,
\end{equation}
となり、ここで$\displaystyle \sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}^{p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor }$は$\lfloor N/2^{(k-j)}\rfloor$以下の重複を含む全ての$p_{i_1}\cdots p_{i_j}$について総和を取ることを意味する。
補題6より$\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr)$は、任意の素数$p$に対して、$N$以下の$p_{i_1}\cdots p_{i_j}p^{k-j}$の個数を数える関数である。$p_{i_1}$から$p_{i_j}$は重複を含み、総和を取ることで$p_{i_1}\cdots p_{i_j}$は全ての$j$-概素数となる。そのため$N$が$k$-概素数のとき、$\sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr)$は$k$-概素数の内の$p^{k-j}$で表される素数の個数と等しい。
$x \geq 2$に対し$\pi(x)$は正である。よって$\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr)$が正となるためには、$\sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \geq 2$を満たす必要がある。両辺を$k-j$乗し、分母を移項する。$p_{i_1} \dotsm p_{i_j}$が整数であることを考慮すれば、上限$p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor$を得る。
1から$k-1$までの$j$の総和$\displaystyle \sum_{j=1}^{k-1} \sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}^{p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor }\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr)$は$k$-概素数の内$p^1,p^2, \dots ,p^{k-1}$で表される素数の個数を数える。同様に、$\pi \bigl( \sqrt[k]{N} \bigr)$は$p^k$で表される素数の個数を数える。これらの総和は$N$が$k$-概素数のとき、$k$増加する。したがって、これらの総和を$k$で割ったものは$\pi^{(k)}(N)$と等しい。
与えられた2以上の実数$N$について、次の恒等式が成り立つ。
\begin{equation}
\lfloor N \rfloor =1+\displaystyle \sum_{\ell=1}^{\lfloor \log_2{N} \rfloor} \sum_{m=1}^{\lfloor N/2^\ell \rfloor} \frac{\pi \bigl(\sqrt[\ell]{N/m} \bigr)}{\Omega(m)+\ell},
\end{equation}
ここで、$\lfloor N \rfloor$は床関数と呼ばれ、$N$以下の最大の整数を与える。また$\Omega(n)$は、与えられた自然数$n$の重複を含めた素因数の個数を返す。
命題7で得られた$\pi^{(k)}(N)$の公式を補題1の恒等式に代入して
\begin{equation}
\begin{split}
\lfloor N \rfloor &= 1 + \pi(N) \\
&+\displaystyle \sum_{k=2}^{\lfloor \log_2{N} \rfloor}\Biggl( \pi \bigl(\sqrt[k]{N} \bigr) + \displaystyle \sum_{j=1}^{k-1} \sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}^{p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor }\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr) \Biggr)/k
\end{split}
\end{equation}
を得る。計算しやすくするため、任意の自然数$m,\ell$として$\pi \bigl( \sqrt[\ell]{N/m} \bigr)$に分け、$m,\ell$の昇順に並び替えた。
\begin{equation}
\begin{split}
\lfloor N \rfloor &= 1 + \pi(N) + \frac{\pi(N/2)}{2} + \cdots + \frac{\pi(N/\lfloor N/2 \rfloor)}{\Omega (\lfloor N/2 \rfloor) +1} \\
&+\frac{\pi \bigl( \sqrt{N} \bigr)}{2}+\frac{\pi \bigl( \sqrt{N/2} \bigr)}{3}+\cdots +\frac{\pi \bigl( \sqrt{N/\lfloor N/2^2 \rfloor} \bigr)}{\Omega (\lfloor N/2^2 \rfloor) +2}+\cdots \\
&+\frac{\pi \bigl(\sqrt[\ell]{N} \bigr)}{\Omega(1)+\ell}+ \cdots +\frac{\pi \bigl(\sqrt[\ell]{N/m} \bigr)}{\Omega(m)+\ell}+\cdots + \frac{\pi \bigl( \sqrt[\ell]{N/\lfloor N/2^\ell \rfloor} \bigr)}{\Omega (\lfloor N/2^\ell \rfloor)+\ell}+\cdots \\
&+\frac{\pi \bigl(\sqrt[\lfloor \log_2{N} \rfloor]{N} \bigr)}{\Omega(1)+\lfloor \log_2{N} \rfloor}.
\end{split}
\end{equation}
この式より$\pi \bigl( \sqrt[\ell]{N/m} \bigr)$の係数は$1/(\Omega(m)+\ell)$で表せられる。$\ell$の上限は$k$の上限と等しい。$x\geq2$のとき、$\pi(x)$は正である。よって$\pi \bigl( \sqrt[\ell]{N/m} \bigr)$が正となるためには、$\sqrt[\ell]{N/m} \geq 2$を満たす必要がある。$m$が整数であることを考慮して、$m$の上限$\lfloor N/2^\ell \rfloor$を得る。
他の数論的関数との繋がり(追記)
得られた恒等式は$\lfloor N \rfloor-1$を$\pi \bigl(\sqrt[\ell]{N/m}\bigr)$で展開したとも捉えられる。展開係数$\eta_{\ell m}$は$1/(\Omega(m)+\ell)$である。他の数論的関数に対し、$\pi \bigl(\sqrt[\ell]{N/m}\bigr)$での展開を考える。
与えられた2以上の実数$N$について、次の恒等式が成り立つ。
$\displaystyle\sum_{n=2}^N\Omega(n)=\displaystyle \sum_{\ell=1}^{\lfloor \log_2{N} \rfloor} \sum_{m=1}^{\lfloor N/2^\ell \rfloor}\eta_{\ell m}\pi\Bigl( \sqrt[\ell]{N/m} \Bigr)$, $\eta_{\ell m}=1.$
命題7より、$2$以上の自然数$k$に対して、
$\pi \bigl( \sqrt[k]{N} \bigr) + \displaystyle \sum_{j=1}^{k-1} \sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}^{p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor }\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr)$
は、$N$が$k$-概素数のとき$k$増加する。これは$N$が$k$-概素数のときの$\Omega(N)$と等しい。$k=1$のときは$\pi(N)$となるため、全ての$k$-概素数の総和を取ると
$\displaystyle\sum_{n=2}^N\Omega(n)=\pi(N)+\sum_{k=2}^{\lfloor \log_2{N} \rfloor}\biggl( \pi \bigl( \sqrt[k]{N} \bigr) + \sum_{j=1}^{k-1} \sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}^{p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor }\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr) \biggr),$
を得る。任意の自然数$m,\ell$として$\pi \bigl( \sqrt[\ell]{N/m} \bigr)$に分け、$m,\ell$の昇順に並び替えた。
\begin{equation}
\begin{split}
\displaystyle\sum_{n=2}^N\Omega(n)&=\pi(N) + \pi(N/2) + \cdots + \pi(N/\lfloor N/2 \rfloor)\\
&+\pi \bigl( \sqrt{N} \bigr)+\pi \Bigl( \sqrt{N/2} \Bigr)+\cdots +\pi \Bigl( \sqrt{N/\lfloor N/2^2 \rfloor} \Bigr)+\cdots \\
&+\pi \bigl(\sqrt[\ell]{N} \bigr)+ \cdots +\pi \Bigl(\sqrt[\ell]{N/m} \Bigr)+\cdots + \pi \Bigl( \sqrt[\ell]{N/\lfloor N/2^\ell \rfloor} \Bigr)+\cdots \\
&+\pi \bigl(\sqrt[\lfloor \log_2{N} \rfloor]{N} \bigr).
\end{split}
\end{equation}
この式より展開係数$\eta_{\ell m}=1$と分かる。$\ell,m$の条件は定理8と同じである。
与えられた2以上の実数$N$について、次の恒等式が成り立つ。
$\displaystyle\sum_{n=2}^N\omega(n)=\displaystyle \sum_{m=1}^{\lfloor N/2 \rfloor}\eta_{1m}\pi(N/m)$,$\eta_{1m}=1.$
ここで$\omega(n)$は、与えられた自然数$n$の相異なる素因数の個数を返す。
命題7より、$2$以上の自然数$k$に対して、$\displaystyle \sum_{\substack{i_1, \dots , i_j=1\\i_1= \dots =i_j}}^{p_{i_1} \dotsm p_{i_j} \leq \lfloor N/2^{(k-j)} \rfloor }\pi \Bigl( \sqrt[k-j]{N/p_{i_1} \dotsm p_{i_j} } \Bigr)$は$k$-概素数の内$p^{k-j}$で表される素数の個数を数える。特に$j=k-1$のとき、$p$で表される素数の個数を数える。これは$N$が$k$-概素数のときの$\omega(N)$と等しい。$k=1$のときは$\pi(N)$となるため、全ての$k$-概素数の総和を取ると
$\displaystyle\sum_{n=2}^N\omega(n)= \pi(N)+\sum_{k=2}^{\lfloor \log_2{N} \rfloor}\Biggl( \sum_{\substack{i_1, \dots , i_{k-1}=1\\i_1= \dots =i_{k-1}}}^{p_{i_1} \dotsm p_{i_{k-1}} \leq \lfloor N/2 \rfloor }\pi (N/p_{i_1} \dotsm p_{i_{k-1}}) \Biggr),$
を得る。任意の自然数$m$として$\pi(N/m)$に分け、$m$の昇順に並び替えた。
\begin{equation}
\displaystyle\sum_{n=2}^N\omega(n)=\pi(N) + \pi(N/2) + \cdots + \pi(N/\lfloor N/2 \rfloor).
\end{equation}
この式より展開係数$\eta_{1 m}=1$と分かる。$m$の条件は定理8と同じである。
与えられた2以上の実数$N$について、次の恒等式が成り立つ。
\begin{equation}
\displaystyle\sum_{n=2}^N \frac{\omega(n)}{\Omega(n)}= \sum_{m=1}^{\lfloor N/2 \rfloor} \eta_{1 m}\pi(N/m), \eta_{1 m}=\frac{1}{\Omega(m)+1}.
\end{equation}
例2と同様に、$2$以上の自然数$k$に対して、$\displaystyle\sum_{\substack{i_1, \dots , i_{k-1}=1\\i_1= \dots =i_{k-1}}}^{p_{i_1} \dotsm p_{i_{k-1}} \leq \lfloor N/2 \rfloor }\pi( N/p_{i_1} \dotsm p_{i_{k-1}})$は、$N$が$k$-概素数のときの$\omega(N)$に等しい。これを$k$で割ったものは、$N$が$k$-概素数のときの$\omega(N)/\Omega(N)$と等しい。$k=1$のときは$\pi(N)$となるため、全ての$k$-概素数の総和を取ると
$\displaystyle\sum_{n=2}^N\frac{\omega(n)}{\Omega(n)}= \pi(N)+\sum_{k=2}^{\lfloor \log_2{N} \rfloor}\Biggl( \sum_{\substack{i_1, \dots , i_{k-1}=1\\i_1= \dots =i_{k-1}}}^{p_{i_1} \dotsm p_{i_{k-1}} \leq \lfloor N/2 \rfloor }\pi \Bigl( N/p_{i_1} \dotsm p_{i_{k-1}} \Bigr) \Biggr)/k,$
を得る。任意の自然数$m$として$\pi(N/m)$に分け、$m$の昇順に並び替えた。
\begin{equation}
\displaystyle\sum_{n=2}^N\frac{\omega(n)}{\Omega(n)}= \pi(N) + \frac{\pi(N/2)}{2} + \cdots + \frac{\pi(N/\lfloor N/2 \rfloor)}{\Omega (\lfloor N/2 \rfloor) +1}.
\end{equation}
この式より展開係数$\eta_{1 m}=1/(\Omega(m)+1)$と分かる。$m$の条件は定理8と同じである。
おわりに
素数計数関数$\pi(N)$の性質から恒等式を導いた。それを$\lfloor N \rfloor-1$の$\pi \bigl(\sqrt[\ell]{N/m}\bigr)$での展開と見なし、数論的関数$\Omega(n),\omega(n)$へ応用した。次は$s$を複素数とし、$\lfloor N \rfloor$を自然数の$s$乗の逆数和、$\pi(N)$を素数の$s$乗の逆数和へと一般化する。
