インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

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}
が成り立つ。

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

補題1 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}}) −①

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

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

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

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

と因数分解される(\zeta1の原始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}

と計算でき、①が示された。P(n)=|P(n)|^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.

補題2 自然数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.

integers.hatenablog.com

で紹介したRosser-Schoenfeldの定理よりp_n \leq n^2+1なので*2、補題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}

と変形できます。従って、\displaystyle \pi (m) = \sum_{j=2}^mP(j)であることから、補題1よりSchumacherの素数公式の証明が完了します (n=1のときも成立している)。

*1:integers.hatenablog.com

*2:ここに深い結果を用いる必要があるわけではないのはRegimbalの素数公式の記事で述べた通り。n^2+1で押さえているのはSchumacher氏の好みと思われる。