mattyuuの数学ネタ集

世界は数式で溢れている

トーナメントは運か実力か(解析解編)

先日の第7回日曜数学会で福原和朗さんが「トーナメントは運か実力か」という大変面白いLTをしておられました。今回は福原さんのLTを受けて、私が見つけた数式について発表させていただきます。

福原さんのLTに関しては下記のリンクのブログにまとめられております。

発表

第7回日曜数学会で発表してきました。 - kazurof weblog

福原さんは後述するある確率の数値解(←コンピュータ等を用いた計算による数値で与えられる解)を発表されたのですが、LTの後に、「必ず確率を文字式で解を表せるよね(つまり解析解(←問題を特徴付ける変数で表された代数的な解)が得られるよね)」と2人で会話させていただきました。先日のMathPowerで行われた素数大富豪のトーナメント表を見てそのことを思い出し、無事に解析解を見つけることができましたので、ここに発表したく思った次第です。

本記事の数学面の説明は、高校レベルの確率(特にコンビネーション\mathrm Cの使い方、赤い玉と白い玉が入っている袋から玉を取り出す系の確率の問題の解き方、何人かを一列に並べて特殊な並べ方の場合の数を求める方法)を習得している人を想定して記載しております。ただ高校確率の知識がない方でも問題の設定は理解していただけると思いますので、こういった現実的な問題を数学を使って解くことができるということ、つまり数学の力を感じていただけたら幸いです。

始まり、始まり
f:id:mattyuu:20161016085420j:plain

「トーナメントは運か実力か(解析解編)」というタイトルで発表させていただきます。

夏の高校野球やリオオリンピックの柔道は負けたら終わりのトーナメント方式ですね(オリンピックの柔道に関しては敗者復活戦があるため完全に負けたら終わりというわけではありませんが)。トーナメントでは第1回戦で実力が1位と2位の人が戦ったら、2位の人は初戦敗退となってしまいます。また、実力がない人でもたまたま対戦相手が自分よりも下の実力であれば、第二回戦、第三回戦と勝ち進むことができます。理不尽だな、と思った経験はないでしょうか。

(余談ですが、駒大苫小牧高校は2004年、2005年と夏の甲子園を連覇しております。そしてなんと2006年の夏も甲子園の決勝まで行っているんです。この2006年の決勝こそ歴史に残る引き分け再試合となった、「ハンカチ王子こと斎藤佑樹」VS「マー君こと田中将大」なんです。夏2連覇して、その翌年の夏も決勝まで進むとは、駒大苫小牧の実力やばいですね。)

数学の確率を使えば理不尽なことがどれほど起こり得るのか、ということを定量的に表すことができます。では問題設定を行います。

f:id:mattyuu:20161016085425j:plain

 nを正の整数として、 2^n人が参加するトーナメントを考えます。ただしトーナメントは上図のような綺麗な形のトーナメントを考え、シードがあったり、参加者によって優勝するまでに必要な勝利数が異なったりしないものとします。

参加者を 2^n人(つまり2人、4人、8人、16人、、、)という人数に縛るのは綺麗な形のトーナメントにするために必要な条件となります。 2^nという制約を課すことで第1回戦、第2回戦、第3回戦、、、という風に第 k回戦終わるごとに勝ち残っている参加者の数が半分になり続け、第 n回戦で1人になる(つまり優勝者が決まる)綺麗な形のトーナメント表を作成することができます。綺麗な形のトーナメントという数学的ではない表現が出てしまっておりますが、その意味するところはわかっていただけると思います(ちなみに数学的には完全2分木という言葉で表します)。

f:id:mattyuu:20161016085429j:plain

参加者には「強さ」を示す数値があらかじめ与えられており、各試合では「強さ」が大きい参加者が必ず勝つものとします。
「強さ」は1から 2^nまでの整数値をとり、参加者の「強さ」はそれぞれ異なるものとします。つまり、1から 2^nまでの各整数値が 2^n人の参加者一人一人に対して重複なく割り振られているものとします。

「強さ」 2^nを持つ参加者はランキング1位、「強さ」 (2^n-1)を持つ参加者はランキング2位、「強さ」1を持つ参加者はランキング 2^n位(つまりビリ)となります。毎回『「強さ」 xを持つ参加者』と書くのは大変ですので、今後は『「強さ」 xを持つ参加者』のことを xさんと呼ぶことにしましょう。

f:id:mattyuu:20161016085449j:plain

上述した設定の元、本記事の問題はこのようになります。

トーナメント表をランダムに組むという意味は、 2^n人の参加者をランダムに一列に並べ、トーナメント表の一番下に据えるということになります。

各試合では「強さ」が大きい参加者が必ず勝つため、 2^nさん(つまり「強さ」 2^nを持つ参加者)が必ず優勝しますし、1さん(つまり「強さ」1を持つビリの参加者)は必ず初戦敗退します。2さんは初戦が1さんでなければ第2回戦に進みますが、第2回戦では必ず負けるでしょう。 P_{a,b} aさんがちょうど b回勝つ確率を表しますから、上で話した簡単な考察ですぐに下記のことがわかります。問題が解けた暁には、下記が成り立っているかを確認することでその妥当性を判定できそうです。

 2^nさんは絶対優勝する。必ずちょうど n回勝つ。逆にちょうど k回( 0\leq k \leq n-1)勝つことはない。
 P_{2^n,n}=1
 P_{2^n,k}=0

1さんは必ず初戦敗退。逆にちょうど k回( 1 \leq k\leq n)勝つことはない。
 P_{1,0}=1
 P_{1,k}=0

2さんは初戦が1さんでなければ第1回戦勝てるが、第2回戦は必ず負ける。初戦の相手が1さんでなければ初戦敗退する。
(トーナメント表はランダムのため、例えば初戦の相手が1さんになる確率は、参加者から2さんを除いた (2^n-1)人のうち1さんだけということで、 1/(2^n-1)となります。)
 P_{2,0}=(2^n-2)/(2^n-1)
 P_{2,1}=1/(2^n-1)

f:id:mattyuu:20161016085452j:plain

具体的な例を見つつ、何が問われているかを確認しましょう。上図は n=3の例になります。

このトーナメントではランキング2位の7さんが初戦敗退している上、ランキング5位の4さんが決勝戦に進んでいるなど、かなり理不尽なことが発生しております。このような理不尽なことがどれほど発生するのかということを、確率という道具を使って評価しよう、ということになります。

以上で問題設定を終わります。イメージは掴めましたでしょうか。

f:id:mattyuu:20161016085456j:plain

 aさんがちょうど b回勝つ確率 P_{a,b}を求めよ」と言われてもどこから手をつけてよいかわかりません。 2^n人が参加するトーナメント表は単純に考えると 2^n!(=2^n \cdot (2^n-1)\cdots3\cdot2\cdot1)通りのパターンがあり、考えようとするだけでも頭がこんがらがりそうです。
今、 aさんがちょうど b回勝つ確率を考えたいので、まずは aさんだけに注目することで考察を始めるための入り口を模索していきたいと思います。

トーナメント表をランダムに組むと aさんの最初の位置は様々です。しかし上図のように aさんを隣の zさんと入れ替えた2つのトーナメント表は本質的に同じものであるといえます。同様に aさんと zさんの2人分の組で構成されたトーナメントのブロックを隣のブロックと入れ替えてもトーナメント表は同じものであると言えるでしょう。トーナメント表は参加者が勝ち進んでいくと、どこを勝ち進んだ勝者と戦うことになるのかを示すものであり、ブロックの左右の入れ替えには影響を受けないため、このような操作をしてもトーナメント表の本質は変わりません。 aさんができるだけ左に行くように各階層でブロックを入れ替えていくと、元のトーナメント表と本質的に同じトーナメント表で aさんが一番左下に配置されているものを得ることが可能になります。つまり aさんは始めからトーナメント表の一番左下に固定してよいということがわかります(数学的にはこのことを「 aさんを左下に固定しても一般性を失わない」と表現します。)。

 aさんを一番左下に置くトーナメント表を考えることで何かいいことがあるでしょうか。まず最初に感じられるメリットは問題のサイズを落とすことができたということになります。元々 2^n!通りのトーナメント表の可能性がありましたが、 aさんを左下に固定することで残りの (2^n-1)人の並べ替えである、 (2^n-1)!通りに問題のサイズを落とすことができました。つまり問題のサイズが 1/2^nになっています。例えば n=5の場合を考えると 1/32の時間で結果を出すことができるわけで、これは数値シミュレーションを行う場合には大変都合の良いメリットになります。

一般性を失わないようにもっと場合の数を減らすことは可能でしょう(例えば第一回戦の対戦では左側に強さが小さい人が来るように配置する等)。ただこれ以上の一般化は数値シミュレーションをする上でメリットになっても、今回のように解析的に解を求めたい場合は必ずしもメリットになりません。場合分けが多く発生し、論理的に考える思考の妨げになるからです。実は今回の一般化は問題のサイズを落とす以上のメリットがあります。 aさんを左下に持っていくことで、 aさんが b回勝つための必要条件を簡単に考察することができるのです。

f:id:mattyuu:20161016085500j:plain

本格的な考察に入る前に、今後の考察、記載を容易にするため、上図のようにトーナメント参加者にラベルをつけておきます。

f:id:mattyuu:20161016085508j:plain

では aさんが b回勝つための必要条件を求めましょう。 aさんをトーナメントの左下に固定した威力が発揮されるときがきました。

必要条件というのは aさんが b回勝つために最低限満たさなければいけない条件となります。つまり必要条件を満たしても aさんがちょうど b回勝つとは限りません。 (b+1)回以上勝つ可能性もあるわけです。「 aさんが b回勝つための必要条件」というのは「 aさんが最低 b回勝つための必要十分条件」ということになります。なおしばらくの間、「 aは1ではない」、かつ「 bは0でない」として話を進めます。 a=1または b=0は、 aさんが初戦敗退するという少し趣が異なる事象になるため、考察がしにくくなります。

まずは aさんが1回勝つ必要条件(つまり初戦突破する条件)を求めましょう。数学では文字式を使った一般的な議論の前に具体的な数値でイメージをつかんで一般化するという手法が有効です。 aさんが1回勝つためには初戦の相手である X_1 aさんよりも弱い(=「強さ」の小さい)1さんから (a-1)さんであることが明らかに必要条件になります。つまり aさんが1回勝つための必要条件は「 X_1が1さんから (a-1)さんのいずれかである。」ということになります。

次に aさんが2回勝つ必要条件を求めましょう。 X_1 aさんよりも弱い参加者であることは明らかに必要ですが、 aさんは第二回戦ですぐ隣のブロックの X_2 X_3の勝者と戦うわけですから、 X_2 X_3のいずれも aさんよりも弱い1さんから (a-1)さんのいずれかであることが必要条件になります。つまり aさんが2回勝つための必要条件は「 X_1 X_2 X_3が1さんから (a-1)さんのいずれかである」ということになります。

同様に考察を行うと aさんが b回勝つための必要条件は「 X_1 X_{2^b-1}が1さんから (a-1)さんのいずれかである」ということが分かるかと思います。

めでたしめでたしとしたいところですが、ここでもう一つ考えないといけない条件があります。例えば5さんは4回勝つことができるでしょうか。5さんが4回勝つためには X_1 X_{2^5-1}(=X_{31})が1さんから4さんである必要があります。 X_1から X_{31}に重複なく1さんから4さんを割り振ることは不可能です。つまり aさんが b回勝つためには a>2^b-1も必要になるわけです。

例えば5さんがb回勝つためには
 5>2^b-1
が満たされる必要がありますから、
 2^b<6
となり、これを満たす bは1、2のみとなります。つまり5さんはどれだけ頑張っても3回以上勝つことができないのです。

以上まとめるとaさんがb回勝つための必要条件は、
 a>2^b-1」 かつ 「 X_1 X_{2^b-1}が1さんから (a-1)さんのいずれかである」
となります。

f:id:mattyuu:20161016085514j:plain

最終的に求めたいものは aさんがちょうど b回勝つ確率の P_{a,b}ですが、その一歩手前として、 aさんが最低 b回勝つ確率 \tau_{a,b}を求めましょう。( \tauという文字に特別の意味はなく、最初に私がノートで計算した際にたまたま用いた文字で、ここでもそのまま使わさせていただきます。)

前章で aさんが b回勝つための必要条件、つまり aさんが最低 b回勝つための必要十分条件が得られております。これを丁寧に確率の計算に当てはめてあげれば良いです。上図に記載した通り、確率の定義を思い出しておきましょう。

まず、求めたい確率の分母である全体の場合の数を求めます。今左下に aさんを固定しているため、トーナメント表の組み合わせとして起こりうる全体の場合の数は、 aさんを除く (2^n-1)人を一列に並べる並べ方の総数である (2^n-1)!に等しくなります。一列に並べて左の人から順に X_1 X_2 X_3、、、 X_{2^n-1}と割り振っていけばよいのです。

f:id:mattyuu:20161016085519j:plain

次に確率の分子になる aさんが最低 b回勝つトーナメントの総数を求めましょう。

まず、 X_1から X_{2^b-1} aさんより弱い1さんから (a-1)さんまでを割り振る場合の数を求めます。これは (a-1)人の中から (2^b-1)人を選出し、選出された (2^b-1)人を一列に並べる場合の数の総数になります。 (a-1)人から (2^b-1)人を選出する組み合わせは {}_{a-1}{\mathrm C}_{2^b-1}通り、その各々に対して選出された (2^b-1)人を一列に並べる総数は (2^b-1)!ですから、この場合の数は {}_{a-1}{\mathrm C}_{2^b-1}\cdot(2^b-1)!となります。
そして、その各々に対し参加者の割り振られていない X_{2^b}から X_{2^n-1} (2^b-1)人に選出されなかった残りの \{(2^n-1)-(2^b-1)\}人、つまり (2^n-2^b)人を割り振ります。この並べ方は aさんが最低 b回勝つという事柄に影響しませんので、単純に一列の並べ方の総数を出せばよく (2^n-2^b)!となります。以上まとめると、 aさんが最低 b回勝つトーナメントの総数は {}_{a-1}{\mathrm C}_{2^b-1}\cdot (2^b-1)!\cdot(2^n-2^b)!となります。

f:id:mattyuu:20161016085524j:plain

確率の分母、分子が求まりましたので、 aさんが最低 b回勝つ確率 \tau_{a,b}は上図の通りとなります。 {}_n{\mathrm C}_r=n!/(n-r)!r!を使うことで、なんともシンプルで綺麗な表記になりました。

なお、最後の \prod \piの大文字であり、高校で習ったシグマ( \sum)の掛け算版の記号として使われます。
つまり、
 \displaystyle
\prod_{k=1}^na_k=a_1a_2\cdots a_n
です。

 a<=2^b-1のときは、 aさんは絶対に b回勝てないので、 \tau_{a,b}=0となります。

今、 a\neq 1で考察していました。 a=1つまり、1さんは最弱のため1回も勝つことができません。つまり b>0となる bに対して、明らかに \tau_{1,b}=0です。
そして b>0なる bに対して、 a=1<=2^b-1ですから、今回求めた \tau_{a,b} a=1に対しても成り立つことがわかります。

f:id:mattyuu:20161016085528j:plain

さて、本題であった aさんがちょうど b回勝つ確率 P_{a,b}を求めましょう。ただし、ここでも b\neq 0とします。 b=0に対しては次章で求めたいと思います。

以前にも注意した通り、 \tau_{a,b} aさんが最低 b回勝つ確率であり、ちょうど b回勝つ確率ではありません。しかし下記の考え方から、 \tau_{a,b}から、簡単に P_{a,b}を求めることができます。

トーナメントが一つ与えられたとき、 aさんが初戦敗退するか、ちょうど1回勝つか、ちょうど2回勝つか、ちょうど3回勝つか、、、ちょうど n回勝つか(つまり、優勝するか)はどの2つの事象も同時に起こることはありません。「ちょうど3回勝つ」と「ちょうど4回勝つ」という事象は同時に起こらないのです。このことを確率の言葉で排反事象といいます。

 aさんが最低 b回勝つトーナメントの総数」は、「 aさんがちょうど b回勝つトーナメントの総数」と「 aさんがちょうど (b+1)回勝つトーナメントの総数」と「 aさんがちょうど (b+2)回勝つトーナメントの総数」、、、「 aさんがちょうど n回勝つトーナメントの総数」の和になります。

このことから(両辺をトーナメントの総数で割ることで)、「 aさんが最低 b回勝つ確率」=「 aさんがちょうど b回勝つ確率」+「 aさんがちょうど (b+1)回勝つ確率」+「 aさんがちょうど (b+2)回勝つトーナメントの確率」+・・・+「 aさんがちょうど n回勝つ確率」となるのです。

今求めたいものは「 aさんがちょうど b回勝つ確率」 P_{a,b}ですが、今具体的に求まっている \tau_{a,b}には、上図の通り邪魔な確率「 aさんが (b+1)回以上勝つ確率」が含まれてしまっております。しかし、「 aさんが (b+1)回以上勝つ確率」= \tau_{a,b+1}ですので、 \tau_{a,b}から邪魔な確率 \tau_{a,b+1}を引いたものが、 P_{a,b}になるのです。

f:id:mattyuu:20161016122736j:plain

これまでは b\neq 0を考えておりました。最後に b=0つまり、 aさんが初戦敗退する確率を求めましょう。これまでの議論に比べればとても簡単なものになります。

上図では少し丁寧に確率を求めましたが、 aさんが初戦敗退する必要十分条件は、「初戦の対戦相手の X_1 aさんより強い」になります。 aさんの初戦の相手となり得る参加者の総数は、 2^n人の参加者から aさんを除いた 2^n-1です。そのうち aさんより強い人は (2^n-a)人おりますし、初戦の相手が誰になるかは aさんを除く参加者全てに対して同様に確からしいため、 aさんが初戦敗退する確率は、
 \displaystyle
 P_{a,0}=\frac{2^n-a}{2^n-1}
になります。

f:id:mattyuu:20161016085537j:plain

以上の議論をまとめると、最終的な解析解は上図の通りになります。誰かが注文したわけではないのに、このような綺麗な形になるところに数学の美しさを感じてしまします。

 a bに具体的な値を入れて計算すると、とてもよくできた数式だと感心します。例えば、1さんが必ず初戦敗退することや、 2^nさんが必ず優勝するということを上記の式から計算して確認してみてください。一体この数式は誰が考え、生み出したのでしょうか。とても神秘的な気持ちになります。

今回の所感として、問題が解けたことに驚きを感じています。この世の中には未だ解けない難問が数多く存在します。一見簡単そうな問題でも、解けていないものが多くあります。今回の問題もたまたま解くことができましたが、解けるという保証はありませんでした。簡単に解ける問題、解けない問題の違いは何か、なぜ今回解けたのか、考えるのも怖いくらい難しい問題な気がします。

今回得られた解析解からどんな面白いことがわかるかという考察はしておりません。それはまた機会があれば考察したいと思います。例えば「一回戦敗けの人の言い訳はどれだけ信用してもよいか?」や「 n\rightarrow \inftyにして、 x=b/n [0,1]区間の連続変数と考えた時の P_a(x)の分布はどうなるか?」等々。後者の分布を出せば、福原さんが日曜数学会で発表されていた、「2位の人は運ゲーである」ということについても目に見える形でわかるのではないかと思います。

f:id:mattyuu:20161016132135j:plain

リーマンゼータ関数のゼロ点を手計算してみた

10/1に第7回日曜数学会で掲題の件でLTをさせていただきました。
拙い発表でしたが、自分の好きな数学に関して発表する機会を作っていただき、日曜数学会の幹事のキグロさん、tsujimotterさん、塩鯖さんに厚く御礼を申し上げます。

また、休憩時間や懇親会にてその他多くの参加者の皆様とも話させていただき、とても有意義な時間が過ごせました。
数学の話題しか出ない懇親会はとてもいいものですね。
皆様ありがとうございました。

私の発表に対してtwitterでつぶやいてくださった方がいらっしゃり大変嬉しかったです。
ありがとうございます。
私はつぶやいたことがなかったのですが、つぶやいてもらえると嬉しいということがわかりましたので、今後日曜数学会に参加した際は全力でつぶやかさせていただきますのでよろしくお願いします。

さて、昨日の発表ですがせっかくなので公開したくブログを作成しました。
日曜数学会のLTは5分という短い時間で伝えたいことを伝えなければいけません。
5分に全力をかける、5分で伝えたいことを凝縮するという点でとても勉強になりましたが、本当は説明したかったところを泣く泣く削ることがありました。
この記事ではそういったところも含めて発表資料のスライドを紙芝居のように使いながら説明させていただこうと思います。
今後リーマンゼータ関数のゼロ点を手計算したい方がいらっしゃいましたら、ぜひ読んでいただけたらと思います。

(本来こういった発表は前提とする数学的知識を明確にすべきなのですが、今回はあまり考えておりませんでした。。。世間一般では複素数とはどれだけ浸透しているのでしょうか。。複素数とは何かといった説明は全くありません。。)
(実際に紙芝居のようにまとめてみると文字数が1万字を超えてしまい、相当のモチベーションがある人じゃないと最後まで読んでもらえないだろうと思います。ただこういう風にまとめておくのは今後の自分のためにもなると思い、公開します。)

始まり、始まり
f:id:mattyuu:20161002134126j:plain

「リーマンゼータ関数のゼロ点を手計算してみた」というタイトルで発表させていただきます。

f:id:mattyuu:20161002134143j:plain

リーマンゼータ関数とは何かというと、18世紀にオイラーが研究し、1859年にリーマンの記念碑的論文「与えられた数より小さい素数の個数について」で{\zeta(s)}という記号で名付けられた関数で、自然数 s乗の逆数の無限和で定義されます。 sが変数で、 \zeta(←ゼータと読みます)が関数名となります。注意したいことはこの関数は通常中学校で学ぶ関数とは異なり、複素変数で複素数値を返す関数になるところです。つまり、変数 s\zeta(s)複素数になります。

例えばs=2とすると、\zeta(2)は平方数の逆数の無限和になりますが、なんとこの無限和は\frac{\pi^2}{6}と等しくなります! これは誠に驚くべきことで、小学生でも理解できて、円とは全く関係のないように見える分数の足し算の先に、\piが現れるのです。この級数が無限大にならず収束することは容易に分かるのですが、誰もその値に辿り着けずにいました。1735年に人類で初めてオイラーがこの級数\frac{\pi^2}{6}と等しくなることを発見、証明しました。とても美しいですね。私は学生時代に学んだ数式の中で2番目にこの数式が好きです(1番はコーシーの積分公式です。)。

関数の記号は\zetaなのに、この関数の名前には"リーマン"もしくは"リーマンの"という風に接頭語がつきます(接頭語という表記が正しいかはわかりませんが。)。これは後の時代に様々な\zeta関数が見つかっているからのようです。私はまだ勉強中の身であるためこれ以上は語ることができません。

f:id:mattyuu:20161002134148j:plain

今回なぜリーマンゼータ関数のゼロ点をテーマに選んだかをお伝えします。
それは、リーマンゼータ関数のゼロ点は、人類が抱える問題の中で間違いなく最難関の部類に入る未解決問題リーマン予想と密接に関係しているためです。リーマンゼータ関数のゼロ点とは\zeta(s)=0となるようなsのことであり、マイナスの偶数がゼロ点になることは容易に証明できます。これは自明なゼロ点と呼ばれます(スライドの水色の点となります。)。

\zeta(-2)=0 ?と不思議になられた方もいらっしゃるかもしれません。それは\zeta(s)自然数の逆数和で表記した時に、明らかにゼロにならないように見えるからです。
{ \displaystyle
\zeta(-2) = \sum_{n=1}^{\infty} \frac{1}{n^{-2}}=1+2^2+3^2+4^2+\cdots = 0  (?)
}
実は\zeta(s)自然数の逆数和で表記できるのは\rm{Re}(s)>1の時だけであり、\rm{Re}(s)\leq1に対しては解析接続という技術を使って関数を表記しなおさなければいけません。ここでは「解析接続が必要なんだよ」というところで説明は省かせていただきます。

さて話を戻すと、マイナスの偶数という自明なゼロ点以外にもリーマンゼータ関数のゼロ点が存在します。それらは非自明なゼロ点と呼ばれます(スライドのピンク色の点となります。)。リーマン予想とは「リーマンゼータ関数の非自明なゼロ点は一直線上に並んでいるはずだ」という予想になり、この一直線とは実部が\frac{1}{2}の直線になります(スライドのピンク色の点線になります)。

リーマン予想が生まれて160年弱、世界中の大天才達が挑み、未だ証明できていません。このことを考えるだけでもゼロ点が凄いものということがわかっていただけると思います。

「天才達が挑んだ歴史なんてどうでもいい、そもそもなぜゼロ点が重要か? ゼロ点がどこかわかって何かいいことある?」と思われる方もいらっしゃるかもしれません。すみません、私の力不足で詳しく色々語ることができないのですが、世の中にはリーマン予想が正しければ正しいという定理が何千もあるようです。それだけリーマン予想は数学の根底に関わる問題なのでしょう。リーマン予想を証明することは多くの数学者が最後のピースを埋められずに証明できていない、数々の定理を証明することになるのです。

f:id:mattyuu:20161002134153j:plain

次に、なぜゼロ点を手計算したくなかったを説明します。
2009年のNHKスペシャル「魔性の難問 リーマン予想・天才たちの闘い」を見たところ、「実際のゼロ点の位置を、まず4つほど求めたリーマンは予想外の事実に気づきます。」というナレーションと共に、リーマンが驚いている描写がされておりました。また当時のリーマンの計算用紙も紹介されておりました。リーマンゼータ関数は無限和や無限区間積分で定義されます。1859年というコンピュータのない時代にどうやってゼロ点を手計算したんだろう? と疑問に思ったことがきっかけです(今回、実際にはリーマンの計算方法ではなくグラームの計算方法で計算しております。)。


f:id:mattyuu:20161002134159j:plain

リーマンゼータ関数のゼロ点を手計算する方法は私が探した限りネット上では見つけることができませんでした。

なお、「リーマン予想 零点 手計算」でgoogle検索を行うと、tsujimotterさんのブログが一番に出てきました。

ジーゲルのZ関数を数値計算する

ジーゲルのZ関数を数値計算する - tsujimotterのノートブック

私がご紹介するのもおこがましいのですが、tsujimotterさんは日曜数学者の生みの親であり、私の憧れであります。数学会では3Dプリンタでリーマンゼータ関数を可視化したことで有名です。ゼロ点がなぜ重要か? ということに関しても、下記の記事にて、リーマンの素数公式の右辺に出てくるためであるという新たな知見を私に与えてくれました。(ここまで不思議と素数について記載していなかったのですが、リーマンゼータ関数のゼロ点は数学者たちが愛してやまない素数の情報をすべて持っているとも言えるのです。)

リーマンの素数公式を可視化する

リーマンの素数公式を可視化する - tsujimotterのノートブック

ただtsujimotterさんのブログではゼロ点をruby(←プログラミング言語)を用いて計算しております。私はコンピュータのない時代にどうやって計算したかを知りたいため、tsujimotterさんのブログだけでは疑問を解消することができませんでした。

f:id:mattyuu:20161002134205j:plain

リーマン予想とゼロ点計算の歴史を簡単に紹介します。リーマン予想が1859年に世に生み出されたことは既にお伝えした通りですが、リーマン予想は1900年のヒルベルトの23の問題、2000年のミレニアム懸賞金問題に選出されております。
ヒルベルトの23の問題とは、1900年にドイツのヒルベルトという有名数学者が20世紀に解くべき数学の23個の未解決問題をまとめたものです。同様にミレニアム懸賞金問題とは、2000年にクレイ研究所が定めた数学上の7つの重要未解決問題のことであり、解決した数学者には100万ドルの懸賞金が与えられるとのことです。1900年、2000年と100年経っても数学会の最重要未解決問題であり続けるリーマン予想のラスボス感を思い知らされます。

驚くことに1900年のヒルベルトの23の問題が発表された当時、人類は非自明なゼロ点に関する数値情報を1つも持っていなかったようです(リーマンただ一人を除いて)。初めて(リーマンを除く)人類が非自明なゼロ点を目にしたのは、1903年グラームの研究結果となります。今回は鹿野健先生編著の「リーマン予想」(日本評論社)を参照して、グラームの方法でゼロ点を手計算しました。

なお、リーマンは研究結果を論文として公表しますが、その結果に至った証明、計算過程のメモを公表することはなかったようです(←リーマン予想に関してだけかもしれません)。そのため1900年代にリーマン予想を証明しようとしてできなかった数学者達に、「リーマン予想は成り立たないのであろう、リーマンは計算していないのだから、リーマン予想は夢想だろう」という風に思われたことがあるようです。1932年ジーゲルというドイツの数学者がその驚くべき洞察力で、リーマンが残した断片的なメモを解読し、リーマンがゼロ点を実際に手計算していたという事実、またゼロ点を計算するのにグラームの方法より有用な公式(←今日ではリーマン・ジーゲルの公式と呼ばれています)を導いていたことを発見します(NHKスペシャルのナレーションには嘘がなかったことになります。)。リーマンは頭脳だけで定理を見つけるような天才ではなく、実際には膨大な手計算を元に定理を導くエレファントな一面もあったわけです。

今回、リーマンが実際に用いたリーマン・ジーゲルの公式は用いず、グラームの方法でゼロ点を計算しています。これはリーマン・ジーゲルの公式がリーマンの天才的頭脳を持ってして思いつく積分路の変更と、エレファントで複雑な計算を経て得られる異形な式であり、ぱっと見なぜこれを計算することでリーマンゼータ関数のゼロ点が計算できるかわからないためです。それに比べグラームの方法は初等的と言え、リーマンゼータ関数を計算しているという実感を得ることができる方法になっており、日曜数学会の発表ではグラームの方法の方が適切と考え、そのようにいたしました。

f:id:mattyuu:20161002134213j:plain

リーマンゼータ関数のゼロ点を計算する中で困難が2つあります。まず1つ目はリーマンゼータ関数は無限個の足し算で定義されていることです。上記のように足し算を\frac{1}{999999999999^s}まで計算したとしても、まだまだ足し算を止めるわけにはいきません。

f:id:mattyuu:20161002134226j:plain

そこでグラームが採用したのがオイラー・マクローリンの和公式です。この公式自体はオイラーが導いたものでリーマンゼータ関数とは直接関係ありません。ここではこういう便利な公式があるというくらいの認識で問題ありません。

f:id:mattyuu:20161002134233j:plain

オイラー・マクローリンの和公式にて、N=\inftyf(z)=1/{z^s}として、
\displaystyle
\zeta(s)=\sum_{n=1}^{M-1}\frac{1}{n^s}+\sum_{n=M}^{\infty}\frac{1}{n^s}
とすることで、上記の式を導くことができます。

まず主要項と呼ばれる部分ではリーマンゼータ関数を最初のM-1まで真面目に計算します。その次の補正項と呼ばれる部分で計算していない残りの部分のk次の近似が与えられます(kを大きくすることで誤差が小さくなります)。近似の精度はMkを大きくすることで上げることができます。スライドでは説明していませんが、誤差項R_{2k}は下記のように上から評価できます(\sigma={\rm Re}(s)です)。

\displaystyle
\left|R_{2k}\right| \leq  \left|\frac{s+2k+1}{\sigma+2k+1}\right|\left|\frac{s(s+1)(s+2)\cdots(s+2k)}{(2k+2)!}\right| \left|B_{2k+2}\right|M^{-\sigma-2k-1}

なお、計算したい非自明なゼロ点(s=1/2+it)tが大きくなるにつれて、十分な精度でゼロ点を計算するためにはMkをどんどん大きくしていく必要があります。例えばt=10であれば、M=10k=10とすることで、誤差項の絶対値を10^{-15}よりも小さくできますが、t=50となると、M=10k=10としても、誤差項の絶対値が10^{-2}程度まで大きくなってしまいます。実際に手計算をやってみればわかりますが、Mkが1大きくなるだけで、計算をする気力がどっと落ちてしまいます。これはグラームの方法の欠点となっています。

とはいえ、オイラー・マクローリンの和公式を使うことで無限個の和という掴みどころのなかったリーマンゼータ関数を、誤差の大きさを評価できる有限回の計算に落とし込むことができました。これは大きな進歩と言えます。

f:id:mattyuu:20161002134240j:plain

ここまで数式のみの続きイメージがしにくかったですが、実際にs=1/2+5i(つまりt=5)、M=5k=3とした場合の展開式を紹介します。式は長いですが、これを実直に計算することで\zeta(1/2+5i)を手計算できるのです。

f:id:mattyuu:20161002134248j:plain

ところで、
\displaystyle
\frac{1}{2^{\frac{1}{2}+5i}}
はどうやって計算するのでしょうか。
実はまたまたオイラーが見つけた公式である、
\displaystyle
e^{i\theta}=\cos{\theta}+i\sin{\theta}
を用いて、上記のように計算できるのです。
なお、オイラーの公式にて\theta=\piとして右辺を左辺に移行した、
\displaystyle
e^{i\pi}+1=0
は、ネイピア数e、円周率\pi虚数単位i、和の単位元0、積の単位元1が1つの式で結ばれており、その美しさから人類の至宝と呼ばれています。

思いがけないところで\sin\cos\logが出てきました。これは簡単には手計算できないぞ、手計算諦めよう、とも考えましたが、コンピュータのなかったリーマンの時代でも数表と呼ばれるものがあり、代表的な関数の値を数表から得ることができます。過去に数表を作ってくださった方々に多大な敬意を払いつつ、発表を続けます。

f:id:mattyuu:20161002134253j:plain

次の困難は複素数値関数であるリーマンゼータ関数では中間値の定理が使えないことです。私はあまり数値計算法に明るくはないのですが、中間値の定理は関数のゼロ点を求めるために、とても重要なものであろうと容易に想像がつきます。例えば上の例のようにf(1)=-1f(2)=1であれば、x1から2まで増加する間にその符号が変わっているため1<\alpha<2となる\alphaが存在して、f(\alpha)=0になるでしょう。f(1)f(2)の符号が異なるだけで、ゼロ点が存在することを知ることができるのです。

f:id:mattyuu:20161002134302j:plain

しかしリーマンゼータ関数は実数値関数ではなく複素数値関数です。実数と違い複素数は2次元の平面と同一視できます。2次元の複素平面上では-110を通らずに結べるため、上記の例のようにf(1)=-1f(2)=1であっても、f(\alpha)\neq 0 (1<\alpha<2)ということも考えられるのです。

f:id:mattyuu:20161002134308j:plain

そこで登場するのが、ジーゲルのZ関数です。複素数値関数で中間値の定理が使えないのであれば、実数値関数にしてしまおうという考えです。ここで細かく説明はできないのですが、{\rm Re}(s)=1/2上で、Z(t)\zeta(1/2+it)はその絶対値が一致します。つまり、
\displaystyle
Z(t)=0 \Longleftrightarrow \zeta(1/2+it)=0
が成り立つのです。複素数値関数で中間値の定理が使えない困った\zeta(1/2+it)ちゃんのゼロ点を計算する代わりに、実数値関数のZ(t)のゼロ点を計算すれば良いということです。これも大きな進歩です。

なお、このZ関数にはジーゲルのZ関数と名付けられておりますが、その存在はリーマンが論文に書いていた関数等式から初等的に導出することができます。また、ジーゲルより前の時代のグラームがゼロ点の計算に用いていることから、ジーゲルはこの関数の発見者ではないと思われます。ジーゲルがリーマンのメモを解読する中で何かこの関数に重大な意味づけした等の功績で名前が付いているものと私は考えております。

f:id:mattyuu:20161002134315j:plain

Z(t)の計算のために必要な\theta(t)もガンマ関数のGaussの公式、
\displaystyle
\Gamma(s)=\lim_{N\rightarrow\infty}\frac{N!N^s}{s(s+1)\cdots(s+N)}
オイラー・マクローリンの和公式を用いることで上記のように近似計算ができます。実際にはその後e^{\theta(t)}=\cos{\theta(t)}+i\sin{\theta(t)}を計算しないといけないのですが、数表を使えばなんとかできそうです。

f:id:mattyuu:20161002134320j:plain

ついに武器は揃いました。tに対して、オイラー・マクローリンの公式から\zeta(1/2+it)を計算し、その後Z(t)を計算します。いくつかのtに対してZ(t)を計算して、例えばZ(t_1)<0Z(t_2)>0であれば、複素平面上でs=1/2+it_1s=1/2+it_2を結ぶ線分上に\zeta(s)=0となるゼロ点が存在するのです。

f:id:mattyuu:20161002134326j:plain

今回はコンピュータのなかった時代にどうやってゼロ点を計算したのかを知りたいため、実際に計算する前に上記のルールを策定しておきます。

f:id:mattyuu:20161002134331j:plain

こちらが私が実際に計算したtになります。最初はt=1,2,3,4,\cdots,20と計算していこう、その後符号が変わったあたりをt=X.1,X.2,\cdots,X.9と計算していき
とゼロ点をそれなりの精度で求めたかったのですが、実際にやってみるとその大変さからたった3つのtに留まってしまいました。。。

なお、それぞれのtに対して、Mkを上記のように選べば、その誤差を10^{-5}程度まで小さくすることができます。

f:id:mattyuu:20161002134337j:plain

計算結果をお伝えする前に白状しないといけないことがあります。計算を進めている中で突然のルール改定が行われました。計算を続け大量の筆算で嫌気がさしてきた頃に、急遽45.9727÷101が現れました。「÷100にしたいよ、÷101とほとんど結果一緒でしょ、、もう嫌だ電卓使っちゃおう」という流れでルール改定を決心しました。電卓を使っていいと言っても1ステップの計算に限ります。そこは譲れません。

「昔の人は偉いな、すごいな。自分たちは便利なものに囲まれて何か大事なものを見失っている気がする。」そういう風に思いました。

f:id:mattyuu:20161002134344j:plain

こちらが最終結果になります。\zeta(1/2+it)Z(t)それぞれに対して、私の手計算の結果と、Wolframというアプリで計算した正確な値を比較しております。自分でも驚くほど計算結果が近いものになっておりました。面白いと感じたのはZ(t)は実数値関数になるため、私の手計算の結果の虚部もかなり小さい値になっていたことです。

計算時間に関してはt=5の途中で突然のルール改定が行われたため、t=10t=15に対しては計算時間が短くなっております。

Z(10)<0Z(15)>0となっていることから、10<\alpha<15となる\alphaが存在して、\zeta(1/2+i\alpha)=0となる非自明なゼロ点が存在することがわかりました!!!!

今回はこれ以上精度を上げて計算はできませんでした。。。
今回はと書きましたが、今後もやりません。こんな計算はコンピュータを使えば一瞬です。便利なものは使います。

f:id:mattyuu:20161002134355j:plain

計算をしていて気づいたことは私の計算用紙とリーマンの計算用紙の見た目がなんとなく似ているということです。リーマンという知の巨人に少し近づけた気がしました。

f:id:mattyuu:20161002134401j:plain

こちらは今回大変参考になった参考文献になります。私が使った式は全てこの参考書からの引用です。

f:id:mattyuu:20161002134409j:plain

お読みいただきありがとうございました。


最後にちょっとした感想です。

実は虚部が一番小さい非自明なゼロ点はs=1/2+14.1\cdots i程度になるのですが、最初のゼロ点が私たち人類が日常的に手の届く範囲に存在していることは奇跡ではないかと思いました。最初のゼロ点の虚部が14程度である必然性はありません(少なくとも私は知りません)。ということは数学の神様がいたずらをして例えば最初のゼロ点が1/2+10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000iであれば、コンピュータを使って計算を続けても非自明なゼロ点を1つも見つけられないということがあり得たのではないかと思います。非自明なゼロ点を具体的に1つも挙げられない中、全ての非自明なゼロ点が一直線上に並んでいることを証明するのは相当心が参るのではないかと。

もう一つ最後に、実は下のようなスライドも用意していました。わかる人にはわかる数学ネタになっております。
f:id:mattyuu:20161002184153j:plain

ありがとうございました。