89とフィボナッチ数との深い関係がおもしろい

※この記事は、数学 Advent Calendar 2016 1日目の記事です。

タイトルの「89」という数は、一見ただの普通の整数に思われるかもしれません。

ですが、この数にまつわるすごく面白い性質を今年に入って知り、個人的にかなり感動したので、今回はそれを伝えたいと思います。

素数

まず、89は素数です。24番目の素数にあたります。

この記事も素数のTシャツを着て書いている程度に素数大好きな私としては、これだけでも大絶賛に値するのですが、今回はこの件ではありません。

フィボナッチ数

89は、フィボナッチ数列の中にも出現します。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

フィボナッチ数列というのは、前2つの数を足していくことで作られる数列です。

1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21

この数列は、黄金比との関係性など、数々の面白い性質を持っており、数学的にも大変重要な数列で、89はその一員です。

これだけだと、89がたまたまフィボナッチ数の1つだった…といった感じですが、ここからが本題です。

89とフィボナッチ数列

突然ですが、最近個人的に勉強している『コンピュータの数学』の中で、次の興味深い問題が紹介されていました。

以下の数列の和は、いくつになるか。

0.1
0.01
0.002
0.0003
0.00005
0.000008
0.0000013


フィボナッチ数列を、1桁ずつずらしたものを全部足すとどうなるか?ということなのですが…パッと見ただけでは有理数なのか無理数なのか、そもそも収束するのかもイマイチ分かりません。

仮に、求めたい和を S、フィボナッチ数列の一般項を a_n とすると、上の小数列の一般項は

「n桁おとして、n番目のフィボナッチ数を添える」

と捉えると 10^{-n} \cdot a_n になることが分かります。なので、このように書けます。

\displaystyle S = \sum^{\infty}_{n=1} 10^{-n} \cdot a_n = 10^{-1} \cdot a_1 + 10^{-2} \cdot a_2 + 10^{-3} \cdot a_3 + \cdots

いったん和のおさらい

一見難しく思えますので、まずはこれよりも少し分かりやすいものを取り上げてみます。

以下の数列の和はいくつになるでしょうか。

\displaystyle 1, \frac{1}{3}, \frac{1}{9}, \frac{1}{27},

この数列は、前の項を\displaystyle \frac{1}{3}倍ずつしていくことでできる、いわゆる「等比数列」の一種です。等比数列の和には(とても覚えづらいことで悪名高い)公式も存在するので、それに当てはめて計算することもできますが、以下のように、比率の分だけずらして考えるとスッキリします。

progression_sums

2つの式では \displaystyle \frac{1}{3} 以降は全て同じ並びになるので、縦に上から下をごっそり引いてしまうと、

\displaystyle S - \frac{1}{3} S = 1 \Longrightarrow S = \frac{3}{2}

というふうに計算できます。「後半を揃えて、消してしまう」のがポイントですね。

本題を解いてみる

本題についても、この考え方が応用できます。 a_nという数列が入り混じっているぶん複雑ではありますが、a_n はフィボナッチ数列で、これは前2つの数を足していくことでできる数列なので、

\displaystyle a_n = a_{n-1} + a_{n-2} すなわち a_n - a_{n-1} - a_{n-2} = 0 (n \geq 3)

が成り立っています。

ということは、a_n, a_{n-1}, a_{n-2} の3つを同じ列に揃えてしまえば、それを引き合わせて後半の列を消すことが同様にできるはずです。

試しに揃えてみると

fibonacchi_sums

となっているので、縦方向に (1) – (2) – (3) を計算する (辺々引く) と

fibonacchi_sums2

となり、2行目以降は \displaystyle a_n - a_{n-1} - a_{n-2} = 0 なのでキレイに消すことができてしまいます。
a_1 = a_2 = 1 なので、

fibonacchi_sums3

fibonacchi_sums4

こんなにキレイな分数になってしまいました。

しかも、今回の数列は小数点第1位から始めていましたが、小数点第2位から始めると、分子の10まで取れて、こんなふうに書けます。

\displaystyle \sum^{\infty}_{n=1} 10^{-(n+1)} \cdot a_n = \frac{1}{89}

本当にきれいですね…!

まとめ … 1/89 を計算しよう

これはもう、\displaystyle \frac{1}{89} を計算してみるしかないですね! 電卓を少し弾くだけで「ほぼフィボナッチ数列」な小数が現れるわけですから。

1_89_calculation

序盤に現れるフィボナッチ数列を眺めているだけで幸せな気分になれますねw 何回でも電卓を弾きたくなります。

実は、フィボナッチ数列の逆数和

\displaystyle \frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{8} + \frac{1}{13} + \cdots

は無理数であることが証明されているのですが、証明された年が 19『89』 年なのも、もはや単なる偶然には思えなくなってきますね。 …そうでもないですかね?

追記: 和の収束性について

計算の過程で下記の級数どうしを引き算している点について、「そもそも収束することが分かってないと引き算できないのでは?」とのご指摘がありました。ありがとうございます!確かに前提として使ってしまっていましたね。

\displaystyle S = \sum^{\infty}_{n=1} 10^{-n} \cdot a_n

が収束することを見るには、隣り合う項の比率を調べる方法があります。 a_{n+1} = a_n + a_{n-1} \leq 2 a_n (n \geq 2) なので、

\displaystyle 10^{-(n+1)} \cdot a_{n+1} \leq 10^{-1} \cdot 10^{-n} \cdot 2 \cdot a_n = \frac{1}{5} \cdot 10^{-n} \cdot a_n

となります。つまり3番目以降の項は、直前の項の \displaystyle \frac{1}{5} よりも確実に小さくなるんですね。ということは、求める級数は、以下のように公比が \displaystyle \frac{1}{5} の等比級数の和でおさえられるはずです。(n = 1, 2 の場合も左辺が右辺より小さくなるように初期値を調整する必要がありますが、この場合は 10^{-1} を初期値としてOKです)

\displaystyle S = \sum^{\infty}_{n=1} 10^{-n} \cdot a_n \leq \sum^{\infty}_{n=1} 10^{-1} \cdot (\frac{1}{5})^{n-1}

右辺の級数が収束することは、先ほどの公比が \displaystyle \frac{1}{3} の場合と同様に示せます。どちらも正項級数(つまり、負の数がない)であることから、右辺が収束すれば、左辺も何らかの値に収束することになります。(このへんの議論を厳密にやると本題とずれるので割愛します。感覚的には、「収束するときより小さい値を足していってるわけだから、収束はするよね」 という話で、何となく理解できるのではないかと思います)

第6回 プログラマのための数学勉強会 に参加してきた #maths4pg

先日、第6回 プログラマのための数学勉強会に参加してきました。

場所は、イベント検索サービスでもお馴染みのdots.さん。もはや東京周辺に勤務してるITエンジニアで通っていない人はいないですね。

001

004

スペースの雰囲気もさることながら、コーヒーがとてもおいしいです!

030

発表

心地よさと数字

007

 

デザインの領域で様々な活動をされている矢崎裕一さんの発表です。色・形・動きなどから感じる「心地よさ」の裏に潜む様々な話題を、主にデータビジュアライゼーションの考え方を中心に展開されています。

例えば、下記の写真に出ている画像は、日本の都道府県からどのように人口が流入・流出しているかを示したグラフですが、単なる棒グラフに比べて得られる情報量や、おもしろさが変わってきます。いかに「抽象化」して人に伝えるか。「数学をいかに使うか」に頭を割くことの必要性を感じさせてくれます。

個人的には、「既に完成されたものを疑う」ことの大切さに共感したのと、シャボン液に興味を持ちました。「シャボン液+台所用洗剤 最強説」、もっと検証してみたくなります。

ポートフォリオサイトがとってもオシャレです!

矢崎 裕一 / Yuichi YAZAKI

 

数学がデジタルアートに! 高速なシェーダで可視化する数学の世界

009

数学がデジタルアートに – slide

GLSLのスクールで私自身たいへんお世話になった@h_doxasさんの発表です。WebGL/GLSLを使ったプログラミングについて、ライブコーディングも交えて紹介されています。モバイルもGL系のプログラムに耐えられるだけのマシンパワーになってきているので、今後また活用用途が広がりそうですね!

コーディングはGLSL Editorでも試すことができ、つくったものをシェアすることもできます。(書かれたソースコードをURLのクエリに直貼りするゴリ押し仕様だそうです(笑)) ベクトル・三角関数・arctan関数が普通に使えるだけでも、GLSLのかわいさが分かりますよね。GLSLについては、ご本人の書かれたこちらのQiitaの記事もとてもわかりやすく参考になります。

[連載]やってみれば超簡単! WebGL と GLSL で始める、はじめてのシェーダコーディング(1)

こちらのWebサイトでWebGLに関する情報を精力的に発信されています。たいへん面白く、全部は理解できなくても眺めるだけでワクワクしてくるサイトです!

WebGL 総本山

 

Wolfram Language コトハジメ

Wolfram Language ドキュメント

科学技術計算、数値計算に広く利用されるMathematicaというシステムがありますが、それに命令を伝えるための言語にあたるのが、WolframLanguageです。作者はSteven Wolfram という、20歳で博士号取得、その後もセル・オートマトンに関する画期的な研究結果を得るなどの、文字通りの天才です。

スティーブン・ウルフラム – Wikipedia

011

本編では、書き方の事例をPythonと比較しつつ見ていましたが、WolframLanguageの最大の特徴は「関数が非常に多く、そのため簡潔に書ける」というところでしょうか。「頭良ければ関数は覚えられるでしょ」という、天才らしい、一般人置いてけぼり思想でつくられているあたり、さすがです。(いまの時代はいくらでも検索ができるので殆ど問題にはならないでしょうが、できた当時に使いこなすのは苦労したんだろうなぁと…)

ちなみに、WolframAlphaというサービスを使うと、簡単な命令であれば無料で試すことができます。とはいっても、無料でいいんですか!?というぐらい、かなりインタラクティブな検索ができます。実際に「How many baseballs in Boeing 747?」のような問いにも答えが返ってきます!

Wolfram Alpha

 

暗号文のままで計算しよう 準同型暗号入門


 

暗号技術関連の著作などでも知られる光成さんによる発表です。「クラウドを支えるこれからの暗号技術」などを執筆されています。

暗号化されたデータをクラウド上のサーバーに配置してアプリケーションが動いている場合、暗号化されているデータどうしで何もできないと、クラウドが事実上の「データ置き場」と化してしまい、肝心のマシンパワーを有効に利用できません。そこで、「暗号化したまま処理をしたい」という動機が生まれるわけですが、そのような暗号生成を可能にする準同型暗号などの技術について、非常にわかりやすく解説されています。

最近は、和と積の準同型性を併せ持つ、完全準同型暗号についての研究がされているものの、現時点では1Bitの平文に対して1GBの暗号が生成される感じだそうです。何かすごいですね…!

 

圏論とHaskellは仲良し

012


 

まさかの法政大学、大森健児教授の登壇です…! 圏論とはどういったものか、またHaskellが圏論の概念(カテゴリ)をベースにしているプログラミング言語であることを紹介されています。

圏論というと、数学の中でも抽象度が高くて難しい理論という印象があるのですが、教授はそれを68歳から学習されたとのこと(!?)。何をするにも遅すぎることはないのですね。具体例として、「自分の得意分野が圏論でどのように扱われるのか」をみると学びやすい、とのことです。

自己紹介の時に話されていた「課長にだけはなるな」は深いアドバイスでした。笑

HaskellによるFunctional Reactive Programmingで書かれた、ボールの衝突のプログラムは、こちらで参照できます。

BilliardBalls – github

ボールの衝突をFunctional Reactive Programmingで表現する(1) ※ブログ上で全11回の連載になっています。

 

LT

√2をつくる

014

 

この会の主催者の@taketo1024さん。代数拡大の考え方をSwiftのプログラムで表現して、2乗して2になる数(つまり√2)をつくることに成功した物語です。「すごくないですか!!?」を連発する発表には、理解度を差し置いて「すごい!!」となる他ありません(実際、私には分かりやすかったです)

代数拡大をSwiftでどう表現するかは、こちらの力作Qiitaに詳しいです。

Swiftで代数学入門 〜 1. 数とは何か?

 

実践Scalaでペアノの公理

015


 

Scalaの型システムを用いて、ペアノの公理に則って自然数を実装してみた、という話です。勝手にScalaは日本語使えないと思ったので「これ動くんだ!」というのは発見でした笑。また、適切でない計算に対して、実行時に変になるのではなく、コンパイルエラーとして弾き出されるのはとても良いですね!

 

せいほうけい育成日記

016

 

「いま、仕事が、ないですね…!」という絶妙で切実な叫びからスタートした@nekoneneneさんによる発表。相似な図形をどんどん増殖させる(これを「育てる」と呼んでいます)プログラムをつくった結果、せいほうけいを育てるよりも、5角形や9角形などを育てる方がずっとかわいかった、というお話です。めでたいのか、めでたくないのか。Slideにある「お世話になったツール」が個人的に参考になりました。前半の発表であったGLSLなどを用いても書けそうですね。

 

packingにまつわるアレコレ

019


 

我らのアイドル、@simizut22さんによる発表です。大脳皮質のような複雑な平面を一定種数のdisk(より単純な平面)にマッピングしていくにあたって発生する数学的理論がテーマだったようですが、リーマン計量を既知の概念として突き進んだあたりから分からなくなりました…

 

Introducing PONS

022

 
言わずと知れた、404 Blog Not Foundでおなじみ@dankogaiさんがまさかの登壇…!目の前の席に座っていましたが、大変気さくな方でした。Protocol指向でつくられた、型フリーな代数的世界に酔いしれることができるライブラリです。実際すごく便利そうです。どのようなものかは、こちらの記事に詳しく書かれています。文中にある、「すべての型別実装を、生まれる前に消し去りたい」というセリフにぐっと来ます。

Swift – Introducing PONS = Protocol Oriented Number System

 

すべての図形を分類した男

023


 

@matsumoringさんによる発表。StarWarsのプロローグを彷彿とさせるナレーションから始まりました。(スライドの1〜11ページを可能な限り良い声で朗読すると再現されます) 写真のスライドにも映しだされている、ナチュラルにジョジョ立ちする男・ルネ-トムが、コンパクトで境界のない微分可能多様体を分類した男にあたるのですが、彼の提唱したいわゆる「コボルディズム理論」の背景が分かりやすく解説されています。

 

かんたんベジェ曲線

025


 

数学系イベント常連の@butchi_yさんです。この方の発想にはいつも関心させられます。ベジェ曲線が何なのかについては、下記のQiitaの記事にも詳しいのですが、今回はベジェ曲線を陽関数 (y=f(x)の形式) に表現してプロットしてみた、という話題です。

 

ベータ分布の謎に迫る

027


 

(本人曰く)データ分析の裾野広げ担当、@kenmatsu4さん。ベータ分布って公式としては良く見るけど、そもそもどういう事象がベータ分布になるの?という素朴な疑問を解消してくれます。深く関わりのある順序統計量、ベイズ統計周辺の話題についても、「これLT?」というぐらいに広めに解説されていて、参考になります。

 

始代数とCatamorphism

028

 

Ryo Mikami さんによる発表。いわゆるHaskellでいうところのfoldの操作を、「始代数」として表現できる任意のデータ型に対して適用する理論(Catamorphism)について紹介されていました。Catamorphismについて最初に出された論文(?)のタイトルが「Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire」だそうです。普通にBananaって使われる科学系の出版物を私は他に知りません…!Haskellのとあるライブラリが「Reactive-banana」と呼ばれるのも、このせいなのですね。。

Reactive Banana

 

まとめ

私自身、この会に参加するのは3回目ですが、やはり心地が良いです。それは、同じ「数学」という分野に興味がある技術者が集まることで、「数学」の話題が引力になるコミュニティが自然と醸成されているからかなと思います。他のコミュニティだと、「あー、そっすかー、すごいっすねー」程度の反応が関の山だったりするのかなと。それを「いいね、すごいじゃん!」と言い合える心地よさが素晴らしいなぁと改めて感じた次第です。

第4回日曜数学会に参加してきた

先日、第4回 日曜数学会 に参加してきました。

場所は、上野毛のLoopolicというカフェで行われました。なんでも、Loopolic = Loop(人の環)+ holic(夢中)というコンセプトがあるそうで、すごく素敵です。

外観はこんな感じ。ちょっと大通りから隠れたところに佇む、良い雰囲気のお店。機会があったらカフェとしても立ち寄りたいところです。

Loopolic

日曜数学会の本編は、発表(5分)+質疑(5分)からなるLTの集合で構成されており、今回のプログラムは以下の通りでした。

========================================
1.キグロ 江戸時代以前の和算について
2.辻順平 ベルヌーイ数を割る素数
3.ちばまさみ もうとけない(分数編)
4.綾塚祐二 最大公約数に関するささやかな知見
5.高橋俊樹 ポリゴングラフとその応用
6.kuma sinc関数の広義積分について
7.岩淵勇樹 加法よりも低レベルな演算を考える
8.堀川由人 Riemann球面に内接する直方体
9.まこぴ~@Project M 自然数のべき和公式を作ろう
10.素数Tシャツ 寄り道をせずにまっすぐ進む方が道のりは短いという事実から、我々は思いがけず素数に遭遇する
11.三好潤一 幾何学模様三題
12.片桐奏羽 ゲージ理論と時間変数
========================================

特定の分野に偏ることもなく、専門外だった分野の話を多く聞けたので個人的にはとても刺激になりました。間に休憩という名の延長戦も多くあって、深掘って考えたり話し合える時間があって心地良いペースでした。
 

江戸時代以前の和算について

万葉集時期(飛鳥時代)の和歌の中に、九九の読み方を織り交ぜたものが多数含まれているそうです。九九は、算木とともに中国から輸入されていたという説があり、当時としては先端だった九九を使うことが格好良いと考えられていたのでは?という話。いまの最先端の数学を和歌に入れるとどうなるんだろう?みたいな質問もありましたが、何だかとんでもないことになりそうですw
 

ベルヌーイ数を割る素数


ベルヌーイ数に関係する素数としては非正則素数が有名(?)ですが、その中でもB_{p-3}/{p-3} を割り切る素数pをWolstenholme Prime と呼ぶそうです。
まだこれは 10^9 までの範囲で2つしか発見されていないので、なんとか3つめを発見したい!のですが、ベルヌーイ数の計算をすること自体が相当に大変とのことです。3つめ見つけたい…!
 

もうとけない(分数編)


最近の小学生が解く算数事情について。分数の約分で12317/11663を約分しなさい、とか出るんですって。まじ鬼ですね。たぶん最近の小学生はユークリッドの互除法とか知ってて当たり前なのかもしれないです。
分数を単位分数の和に分解するような問題も最近流行っているらしく、10代前半にして単位分数、エジプト分数に思いを馳せる環境がある今の日本の教育環境、実は結構すごいのかもしれません。
 

最大公約数に関するささやかな知見


最大公約数の数表を作って、その大きさを明るさに置き換えたビジュアルに変換してみると、なぜ発生しているのか良く分からない波形が見えてくるという点が印象的でした。波形をなしている数を取り出してみると、何かしら特殊な規則性が見えてくるかもしれないですね。自分でも試してみたいです。
 

ポリゴングラフとその応用

グラフの応用の幅を感じたLT。個人的には、枝刈り法などのプロセスが、長時間使われていないメモリを探して開放するGarbageCollectionのあたりに応用できるという話題に興味を持ちました。実際にGC周辺はコードを読んだことも特にないので、触れてみたい領域です。
「ペースを考えないから残業が多い」は至言でしたw
 

sinc関数の広義積分について


大学院入試を考えていたときに触れていたような話題で非常に懐かしく感じられました。sinc関数というのはsin x/xのことを指しますが、複素積分を使わずにFourrier変換を使って求めることができるんですね。今回の発表で初めて知ったのですが非常に面白かったです。
 

加法よりも低レベルな演算を考える


加算の繰り返しによって乗算ができ、乗算の繰り返しによって累乗ができたように、「繰り返しによって加算ができる」ような演算を考えられないか、という発想での考察をまとめた発表。突き詰めていくと発想の単純さに比して意外と難しいです。発表中もマリオが5〜6機ほど死んでいて大変でしたね。
 

Riemann球面に内接する直方体


これは動画で見てほしいです、とにかく動きが綺麗!アニメーションにはpov-rayというツールを使われているとのことで、ちょっと触ってみましたが、あのレベルの動きを再現するのは大変そうです。。
 

自然数のべき和公式を作ろう


(n+1)^k - n^kの展開式から帰納的にべき和公式が得られ、最終的にはベルヌーイ数とのつながりも導出されるという内容。TeXでつくったPDFはスライドショーにしない方が発表しやすいというのも個人的には密かな発見でした。(何かそういったスライドショーに適したツールがあると良いですよね。TeXきれいだから、そのまま発表したいこともあるし。)
 

寄り道をせずにまっすぐ進む方が道のりは短いという事実から、我々は思いがけず素数に遭遇する

スライドはこちらからダウンロードできます!

要するに「菊池寛は偉大。一方、曽野綾子h (ry 」という話。三角不等式 〜 距離空間 〜 Q上の絶対値 〜 p進数体 〜 Ostrowskiの定理 にまで持っていくというとんでもないスピード感の内容でしたが、これを5分でユーモアも交えて発表してしまうという凄まじさ。素数とは三角不等式、菊池寛はエライ!
 

幾何学模様三題

ここでいう三題とは、ウィア・フェラン構造、Self Tiling Tile Sets、板東秀行の夢のタイル張り定理(という名の予想)のことです。この分野に疎い私にはどれも新鮮でした。ウィア・フェランについては「数学は永遠に」というTEDの講演でも紹介されていましたね。なんでこんな形に行き着くのだろうか。。。
 

ゲージ理論と時間変数

時間を力学変数として考える観点を知ったり、時間の流れ方に依存しない対称性(ゲージ対称性)という概念を知ることができたりと、とても新鮮でした。大学1・2年時代に聞いた物理の話はさっぱりついて来れなかったですが、今になって聞いてみると何となくなら理解できますね。改めて物理を学びなおしても良いかも。
 

補足

素数Tシャツはこちらで販売されているそうです。私は購入します。

パズる会のページはこちらです。参加申し込みは2月10日(水)までとのことなので、興味のある方はお早めに!私も1日参加しようと思います。

ニコニコ学会β データ研究会のイベントについては、こちらで告知されるようです(探し出しましたw)次は第8回になるそうです。これも興味をそそりますねぇ。行きたいものが急に増えてしまいました。

素因数分解の一意性の何がありがたいのか?

この記事は 日曜数学 Advent Calendar 2015 21日目の記事です。

前回はtsunutさんの 食べられる「アレ」の製造シミュレーション(1) でした。

素因数分解の一意性について、ちょっとした発見があったので、その内容を書いてみようと思います。

素因数分解の一意性って?

まず、この定理の内容について簡単に紹介すると、「自然数の素因数分解の方法は、順序を入れ替えれば必ず1通りになるよ」という法則です。

順序を入れ替えれば1通りというのは、例えば 30 の場合

30 = 2 * 3 * 5 = 5 * 3 * 2 = 3 * 5 * 2

のように書けるけど、順番並べかえたらどれも一緒になるよね、ということです。

もう、まさに「自明」と言いたくなってしまうような定理の代表格です。

何がありがたいの?

直感的には当たり前に思えるのですが、「この性質が成り立たない世界」をイメージすると、ありがたさが少し分かるかもしれません。

これはほんの一例なのですが、偶数だけの集合Eに対して、和・差・積の計算をそのまま適用します。

すると、この集合に対する素数(みたいな存在)というのは、「自分以外では割れない数」を指すことになります。

こうしてできるE上の素数を試しに並べてみると

2, 6, 10, 14, 18, 22, 26, 30,

となりますが、この素数の組み合わせは

60 = 2 \times 30 = 6 \times 10

という2通りの分解が見つかってしまいます。(3通り、4通り、… の分解の組み合わせを持つ数字も出てきます)

 

このような、「素因数分解が1通りじゃない世界」があるってことを知っているだけでも、だいぶ見え方が変わります。

実際、この「素因数分解が何通りできるか」という、いわば「分解のしやすさ」が、数学の重要な要素の一つである「類数」と密接に関わっていたりします。難しい分野ですが、深掘ると面白い話題がたくさん出てくるところなので、そのあたりも別の機会に(思い出しながら)書ければと。

まとめ

日曜数学会は行きたいと思いながら一度も行けなかったので、来年こそは参加したいと思います。

グッドスタインの定理 – 数学による突然の裏切り

この記事は、Math Advent Calendar 2015 19日目の記事です。

前の記事は、リングさんの「今年のクリスマスはエキゾチックな球面を作ろう」です。

突然の裏切りとは?

数学をやるには直感が必要、とはよく言われますが、どうしても直感的に受け入れがたい結果というのは、いくつもあるものです。

例えば、誕生日の確率の問題については、聞いたことある方もいるのではないでしょうか。

これは、「クラスメイトが n 人いるとします。n 人の中で、誕生日がかぶるペアが存在する確率はいくらでしょう?」という問題です。あるいは、「誕生日がかぶるペアが存在する確率が50%を超えるのは、クラスが何人以上の時でしょうか?」という問い方をされることもあります。

「1年は365日あるので、直感的には50人とか100人ぐらいいないと50%は超えない気がする・・・」と思ってしまいそうなものですが(私もそうでしたが)、実際は23人の時点で50%を超えてしまいます

このような、直感からは導きにくい結果を返す場面を、数学の「裏切り」と(私が勝手に)呼んでいます。

そして、ときどき思い出したように突然裏切ってくれる数学が、私は大好きです。(Mではありません)

 

ここでは、私がこれまで学んだ中で、「裏切られた!」と感じた定理の一つである「グッドスタインの定理」(Goodstein’s Theorem)を紹介します。

はじめて定理の内容を聞いたとき、何を言っているのか、正直さっぱり分かりませんでした。

グッドスタインの定理とは?

定理の前に、「グッドスタイン列」なる数列G_nを定義します。

これは、初期値 G_1 ( > 0) に対して、以下のような操作を繰り返してできる数列を指します。

  • G_1を、底を2とした指数の和に展開します(このとき、指数部分も含めて展開します。例えば、131 = 2^7 + 2 + 1 の場合、展開した結果は 131 = 2^{2^2 + 2 + 1} + 2 + 1 となります。
  • G_1の展開式から、2を3に変換して、計算した値から1を引いたものをG_2とします。(上の例の場合、 G_2 = (3^{3^3 + 3 + 1} + 3 + 1) - 1 = 3^{31} + 3
  • G_2を、底を3とした指数の和に展開します( G_2 = 3^{3^3 + 3 + 1} + 3
  • G_2の展開式から、3を4に変換して、計算した値から1を引いたものをG_3とします。(上の例の場合、 G_3 = (4^{4^4 + 4 + 1} + 4) - 1 = 4^{261} + 3 )
  • 以下同様に、底を4から5に変換して1を引いてG_4、底を5から6に変換して1を引いてG_5 … と計算していきます。

初期値 131 の場合の例を見てもわかるように、この「グッドスタイン列」は、あっという間に大きな値になり、このまま爆発的に増えることが予想されますが。。。

ここで「グッドスタインの定理」を見てみます。

グッドスタインの定理

任意のグッドスタイン列は、0 に収束する。

 

…どうでしょうか?ちょっと何言ってるか分かりませんよね?

つまり、先ほどの計算をず〜〜っと進めていくと、どんな値から始めたとしても、最終的には必ず 0 に到達すると主張しているわけです。

G_1 = 131 から G_3 =4^{261} + 3 と一気に跳ね上がる数列であるにもかかわらずです。

(たった2項の差で、桁にして150桁以上も跳ね上がっていますw)

証明の着想

この定理、実は証明の着想に関しては、それほど難しくはありません。(厳密にはもう少しステップが要るようですが…)

先ほどのG_1 = 131 の例をもとに、各項の展開式における底をbとすると、以下のように並んでいます。

  • G_1 = b^{b^b + b + 1} + b + 1
  • G_2 = b^{b^b + b + 1} + b
  • G_3 = b^{b^b + b + 1} + 3
  • G_4 = b^{b^b + b + 1} + 2

これをbを変数とする多項式と見ると、この多項式は一般的な多項式の順序のもとで減少列になっています。

(一般的な多項式の順序とは、「次数が大きい方が、大きい多項式である」とか、「同じ次数なら係数の大きい方が、より大きい多項式である」といったルールに基づく順序を指します)

この列はこの後もずっと次数を下げつつ減少していきますが、 0 を下回ることはないため、最終的には 0 に収束する、というのが証明の概要です。

なんだか、わかったような、騙されたような、そんな気持ちにさせられます。

 

ちなみにこの定理、証明の着想自体はさほど難しくないにもかかわらず、ペアノ算術(一般的な数の計算)の範囲内では証明できないことも分かっているようです。どこまで裏切ってくれる気なんですしょうかね。

まとめ

数学は裏切らないと言いますが、たまにはこういう意外性を鑑賞して積極的に裏切られ、ギャップ萌えを味わうのもまた一興です。