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

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

ロナルド・グラハムはアメリカで生まれました。1935年10月31日(木)生まれです。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

グラハム問題における未解決問題に対して、書き切れないような大きすぎる巨大数を使って、証明しようとしたアイデアに途方もない奇怪さを感じるとともに感銘を受けます。

そのような巨大数を作成するにはどのようにすれば良いのか、作成基準となる関数も巨大化させれば良いという考えにまたひとつ、奥ゆかしさを感じることができます。