Schumacherの素数公式

素数公式記事第三弾。

定理 (Schumacher, 2015) $n$ 番目の素数を $p_n$ とする。このとき、

$\begin{align} p_n = \frac{1}{4} \sum_{m=1}^{n^2+1}&\Biggl\{ 1-(-1)^{2^{\left( \displaystyle n-\sum_{j=2}^m\left(\frac{2^{j-1}}{j^2}\right)^{j-1}\prod_{k=1}^{j-1}\prod_{l=1}^{j-1}\left( 1-\cos \frac{2\pi kl}{j}\right) \right)^2}} \Biggr\}\\ &\times \Biggl\{ 1+(-1)^{2^{\left( \displaystyle n-\sum_{j=2}^{m-1}\left(\frac{2^{j-1}}{j^2}\right)^{j-1}\prod_{k=1}^{j-1}\prod_{l=1}^{j-1}\left( 1-\cos \frac{2\pi kl}{j}\right) \right)^2}} \Biggr\}m\end{align}$

が成り立つ。

数式の正確な読み方は証明を見れば分かります。

補題１ $n \geq 2$ に対して、

$\displaystyle P(n)= \left( \frac{2^{n-1}}{n^2}\right)^{n-1} \prod_{k=1}^{n-1}\prod_{l=1}^{n-1}\left( 1-\cos \frac{2\pi kl}{n} \right)$

が成り立つ。ここで、 $P(n)$ は素数判定関数*1。

証明. まず、

$\displaystyle P(n) = \frac{1}{n^{n-1}}\prod_{k=1}^{n-1}\prod_{l=1}^{n-1}(1-e^{\frac{2\pi \sqrt{-1}kl}{n}}) \tag{1}$

が成り立つことを示す。 $n$ が合成数ならば、整数 $a, b$ を用いて $n=ab$ と書ける( $2 \leq a, b \leq n-1$ )。このとき、(1)の右辺の二重積の中に

$1-e^{\frac{2\pi \sqrt{-1}ab}{n}} = 1-e^{2\pi \sqrt{-1}}=0$

が現れるから、(1)の右辺は $0$ となる。次に、 $n$ が素数であるとしよう。このとき、

$\displaystyle x^{n-1}+x^{n-2}+\cdots +1 = \prod_{\zeta}(x-\zeta)$

と因数分解される( $\zeta$ は $1$ の原始 $n$ 乗根全体を走る)ので、

$\displaystyle \prod_{\zeta}(1-\zeta)=n$

を得る。各 $k \in \{1, \dots, n-1\}$ に対して、

$\{ e^{\frac{2\pi \sqrt{-1}kl}{n}}\mid l=1, \dots, n-1\}$

は $1$ の原始 $n$ 乗根全体に一致する。従って、

$\displaystyle \prod_{k=1}^{n-1}\prod_{l=1}^{n-1}(1-e^{\frac{2\pi \sqrt{-1}kl}{n}}) = \prod_{k=1}^{n-1}\prod_{\zeta}(1-\zeta)=\prod_{k=1}^{n-1}n=n^{n-1}$

と計算でき、(1)が示された。 $P(n)=\left|P(n)\right|^2$ であることと、

$\displaystyle \left|1-e^{\frac{2\pi \sqrt{-1}kl}{n}}\right|^2 = 2\left( 1-\cos \frac{2\pi kl}{n}\right)$

に注意すれば、所望の等式が得られる。 Q.E.D.

補題２ 自然数 $n, m$ に対してKroneckerのデルタ $\delta_{n, m}$ は

$\delta_{n, m}=\frac{1}{2}\left\{ 1-(-1)^{2^{(n-m)^2}}\right\}$

と表示できる。また、

$\delta_{p_n, m}=\delta_{n, \pi (m)}(1-\delta_{n, \pi (m-1)})$

が成立する。

証明. 一つ目の式は自明。二つ目は

$\displaystyle \delta_{n, \pi (m)} = \begin{cases}0 & (m < p_n), \\ 1 & (p_n \leq m < p_{n+1}), \\ 0 & (m \geq p_{n+1})\end{cases}$

および

$\displaystyle \delta_{n, \pi (m-1)} = \begin{cases}0 & (m < p_n+1), \\ 1 & (p_n+1 \leq m < p_{n+1}+1), \\ 0 & (m \geq p_{n+1}+1)\end{cases}$

が成り立つことから分かる。 Q.E.D.

Rosser-Schoenfeldの定理より $p_n \leq n^2+1$ なので*2、補題２より

$\begin{align} p_n &= \sum_{m=1}^{n^2+1}\delta_{p_n, m}m \\ &= \sum_{m=1}^{n^2+1}\delta_{n, \pi (m)}(1-\delta_{n, \pi (m-1)})m \\ &= \frac{1}{4}\sum_{m=1}^{n^2+1}\left\{ 1-(-1)^{2^{(n-\pi (m) )^2}}\right\} \left\{ 1+(-1)^{2^{(n-\pi (m-1) )^2}}\right\} m \end{align}$