1 - Σ1/p^2 > 0.54 素数と量子計算

せきゅーんです。「素数と量子計算」という大それたタイトルですが、これらが関係あるのかは私は知りません。というか、量子計算の勉強は私はしたことがありません。

今回の記事の目的は、次の不等式を証明することです：

次の不等式を示せ： $\ \ \displaystyle 1-\sum_{\substack{p: \text{素数}}}\frac{1}{p^2} > 0.54.$

この問題は物理学を学んでいる後輩から質問を受けたものなのですが、どうやら量子計算・量子コンピュータに関する論文中に出てきたとのこと。該当の論文は

R. Cleve, A. Ekert, C. Macchiavello, Quantam Algorithms Revisited, http://arxiv.org/pdf/quant-ph/9708016.pdf

で式(6.3)に先ほどの不等式が現れています。
f:id:integers:20160604030234p:plain

ちゃんと読んではいないですが、二つの整数が互いに素であることが効いてくる場面があるらしく、確率計算の過程で用いるようです。

とにかく、後輩の質問に答えましょう。

解答１

示すべきことは $\displaystyle \sum_{p}\frac{1}{p^2} < 0.46$ です。ちなみに、この和は

$0.4522474200410654985065433648322479341732313432398\dots$

なる値に収束しますので、確かに所望の不等式が成り立っていることが分かります。

これでは当然不満が残るでしょう。2003年の東大の入試問題

円周率が $3.05$ より大きいことを証明せよ。

の解答として、「 $\pi = 3.141592653589\dots$ なので。」と書いてあっても、それではペケを付けざるを得ない採点者の気持ちです。もう少し論証っぽく見える証明を模索しましょう(何らかのレベルで計算に頼ることになりますが。この記事では「円周率」および「自然対数」の数値計算は満足にできるものと仮定します)。

解答２

いわゆるバーゼル問題 $\displaystyle \sum_{n=1}^{\infty}\frac{1}{n^2} = \frac{\pi^2}{6}$ に頼った素朴な解答を紹介します。バーゼル問題の証明についてはバーゼル問題の高校数学範囲内で分かる証明 - INTEGERSを参照してください。

任意の自然数 $k$ に対して

$\displaystyle \sum_p\frac{1}{p^2} < \frac{\pi^2}{6} - 1 - \sum_{\substack{n=2 \\ n:\text{合成数}}}^k\frac{1}{n^2}$

が成り立つため、所望の不等式が得られるまで $k$ を大きくしていって素朴に計算するという証明法です。この方法を手持ちの関数電卓で試したところ、

$\displaystyle \frac{\pi^2}{6}-1-\sum_{\substack{n=2 \\ n:\text{合成数}}}^{108}\frac{1}{n^2} = 0.45992494594\dots < 0.46$

と比較的少量の計算で証明できました。

解答３

もう一つの方法を紹介しましょう。あまり日本語の記事をみかけない気がするのですが、素数ゼータ関数と呼ばれる関数があります。とりあえず $\mathrm{Re}(s) > 1$ なる複素数 $s$ に対しては絶対収束級数

$\displaystyle P(s) := \sum_{p:\text{素数}}\frac{1}{p^s}$

と定義されます。つまり、素数ゼータ関数の $s=2$ における特殊値 $P(2)$ こそが今計算したい値なのです。

素数ゼータ関数に関する基本的性質として

$\displaystyle P(s) = \sum_{n=1}^{\infty}\frac{\mu (n)}{n}\log \zeta (ns)$ – ①

が成り立つことをメビウス関数 - インテジャーズ

で証明しました。ここで、 $\mu (n)$ は同じ記事で定義したMöbius関数です。この公式より、

$\displaystyle P(2) = \sum_{n=1}^{\infty}\frac{\mu (n)}{n}\log \zeta (2n)$ – ②

が成り立つため、Riemannゼータの偶数での値 $\zeta (2n)$ を計算できれば $P(2)$ の値も計算できることが分かります。ところが、リーマンゼータ関数 - INTEGERS

で紹介したEulerの公式によって円周率(と関-Bernoulli数)を使って $\zeta (2n)$ を計算することができます。この方針で $P(2) < 0.46$ を証明してみましょう。

Möbius関数の定義より無平方であるような $n$ のみを考えれば十分であることに注意しておきます。とりあえず、

$\begin{align} \zeta (2) &= \frac{\pi^2}{6} \\ \zeta (4) &= \frac{\pi^4}{90}\\ \zeta (6) &= \frac{\pi^6}{945}\\ \zeta (10) &= \frac{\pi^{10}}{93555}\\ \zeta (12) &= \frac{691\pi^{12}}{638512875}\\ \zeta (14) &= \frac{2\pi^{14}}{18243225}\\ \zeta (20) &= \frac{174611\pi^{20}}{1531329465290625}\\ \zeta (22) &= \frac{155366\pi^{22}}{13447856940643125}\\ \zeta (26) &= \frac{1315862\pi^{26}}{11094481976030578125}\end{align}$

を用いて

$\begin{equation}\begin{split}\log \zeta (2)&-\frac{\log \zeta (4)}{2}-\frac{\log \zeta (6)}{3}-\frac{\log \zeta (10)}{5}+\frac{\log \zeta (12)}{6}\\ &-\frac{\log \zeta (14)}{7}+\frac{\log \zeta (20)}{10}-\frac{\log \zeta (22)}{11}-\frac{\log \zeta (26)}{13}\end{split}\end{equation}$

を計算すると $0.4522474197\dots$ と $P(2)$ の真の値にそれなりに近い値が得られます(解答２の方法より優秀)。ここまで計算しておけば、かなりいい加減な評価で $0.46$ で押さえられることを論証できます(いい加減にせず同じ計算を $n \geq 14$ で続ければどんどん真の値に近づきます)。

$\displaystyle \zeta (28)=\frac{6785560294\pi^{28}}{564653660170076273671875}$

を用いると、

$\displaystyle \frac{\log \zeta (28)}{14} < 2.667\cdot 10^{-10}$

が得られます。 $n \geq 14$ では $\mu (n) = +1$ となる $n$ だけをピックアップして、 $n=65$ までは全て上記値で計算することにより上から評価しましょう( $\log \zeta (2n)/n$ は単調減少であることに注意)。なお、 $n=14$ から $65$ までに $\mu (n) = +1$ となるようなものは

$14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65$

の $17$ 個あります。 $n \geq 69$ については次の極めて粗い評価を行います( $65$ の次に $\mu (n)=+1$ となるのが $n=69$ )。Riemannゼータの記事で証明した不等式により、

$\displaystyle \zeta (2n) < 1+\frac{1}{2n-1}$

が成り立つので、 $x > 0$ に対して成立する不等式 $\log (1+x) < x$ を用いると、

$\begin{equation}\begin{split}\sum_{n=69}^{\infty}\frac{\mu (n)}{n}\log \zeta (2n) &< \sum_{n=69}^{\infty}\frac{\log \zeta (2n)}{n} < \sum_{n=69}^{\infty}\frac{\log \left ( 1+\frac{1}{2n-1} \right)}{n} < \sum_{n=69}^{\infty}\frac{1}{n(2n-1)} \\ &< \frac{1}{2}\sum_{n=69}^{\infty}\frac{1}{n(n-1)} = \frac{1}{136} \end{split}\end{equation}$

と評価できます。以上により、

$\displaystyle P(2) < 0.4522474198 + 17\times 2.667\cdot 10^{-10} + \frac{1}{136}=0.45960046\dots < 0.46$

を得ます。

追記

②の最初の二項の和は

$\displaystyle \log \zeta(2)-\frac{1}{2} \log \zeta(4) = \log \frac{\sqrt{10}}{2}=0.4581453\dots$

ですが、

$\displaystyle \sum_p\frac{1}{p^2} < \sum_p\sum_{m=1, \ \text{奇数}}^{\infty}\frac{1}{mp^{2m}}= \sum_p\sum_{m=1}^{\infty}\frac{1}{mp^{2m}}-\sum_p\sum_{m=1, \ \text{偶数}}^{\infty}\frac{1}{mp^{2m}}$