グラハムとギネスブックに載った最大の数「グラハム数」

11月 10, 20175月 16, 2018

はじめに　ロナルド・グラハムのグラハム数　その来歴

ロナルド・グラハムはアメリカで生まれました。１９３５年１０月３１日（木）生まれです。

彼はラムゼー理論に関する未解決問題において推定される解の上限値として「グラハム数」を設定しました。

その数は証明で使用させるどの数値よりも巨大な巨大数であり、指数を用いても事実上の表記が不可能なため、特別な表記法を用いて表されます。

宇宙のすべての物質をインクに変えたとしても、グラハム数を書き表すことはできないと言われています。しかし一方で、そのような巨大数を上限値にしなくとも、その未解決問題は証明できるのではとも考えられています。

グラハム数が生まれた背景として、ロナルド・グラハムとブルース・リー・ロスチャイルドによるグラハム問題があります。

１９７０年の「n次元超立方体の２のn乗個の頂点のそれぞれを互いに結び、２色を用いて連結した線分をいずれかの色に塗り分ける。このとき、nが十分に大きければ、どのような塗り方をしても、同一平面上の４点でそれらを結ぶ線分の色が同一になるものが存在する。」というグラハムの定理に対して、「このnはいくら大きければ良いか。」という問題です。

グラハムの定理により、解の存在は明らかにされていたものの、具体的な数字は得られませんでした。

ロナルド・グラハムとブルース・リー・ロスチャイルドは翌年の１９７１年に「グラハム数」ではなく、より小さな「小グラハム数」という数をグラハム問題の解の上限として発表しました。

一方、この問題の解の下限は、グラハムとロートシルトが６を与えています。

１９７７年にはマーティン・ガードナーがサイエンティフィック・アメリカンでグラハム数を紹介したことで、「グラハム数」は一躍有名になりました。

巨大数を表記するときは指数を使用することをイメージしますが、グラハム数は巨大すぎて、通常の指数では事実上表現不可能です。

というのも、書き切れないというニュアンスで事実上表現できないのです。そのため、まずはクヌースの矢印表現を使った特殊な関数を用いることによって表現します。

クヌースの矢印表現を使ってグラハム数を語るグラハム氏

観測可能な宇宙上の素粒子は１０の８０乗と言われており、粒子１個で１文字を印刷すると見積もっても、グラハム数のn進法表記には到底足りるものではありません。それほど大きすぎる数値をグラハムが発端として開発されました。

しかしながら皮肉なことに、２０１４年、この問題の解の上限は、ミハイル・ラブロフたちによって、さらに小さい数字が示されました。

ちなみにグラハム数を１０進法で表したときの下３桁は３８７と言われ、末尾１００万桁を記した書籍が出版させるほど、現在グラハム数は有名になっています。

ロナルド・グラハムは現在も生存しています。グラハム問題の解の上限として、小グラハム数を発表してから、マーティン・ガードナーがグラハム数を発表しました。

これがきっかけとなり、証明に使われた最も大きな数として、グラハム数はギネスブックに記載されることとなりました。