インテジャーズ

インテジャーズ

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

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

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

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

解答1

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

0.4522474200410654985065433648322479341732313432398\dots

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

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

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

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

解答2

いわゆるバーゼル問題\displaystyle \sum_{n=1}^{\infty}\frac{1}{n^2} = \frac{\pi^2}{6}に頼った素朴な解答を紹介します。バーゼル問題の証明については
integers.hatenablog.com
を参照してください。

任意の自然数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

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

解答3

もう一つの方法を紹介しましょう。あまり日本語の記事をみかけない気がするのですが、素数ゼータ関数と呼ばれる関数があります。とりあえず\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) – ①

が成り立つことを

integers.hatenablog.com

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

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

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

integers.hatenablog.com

で紹介した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\dotsP(2)の真の値にそれなりに近い値が得られます(解答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

ですが、

\begin{align} \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}}\end{align}

という変形に気づけば①の証明で使った式

\displaystyle \log \zeta (s) = \sum_p\sum_{m=1}^{\infty}\frac{1}{mp^{ms}}

より、

\displaystyle \sum_p\frac{1}{p^2} < \log \frac{\sqrt{10}}{2}=0.4581453\dots

が論証できます。この解法はTwitterで知りました(解答もつぶやかれています):