グラハム数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

グラハム数 (Graham's number) は、ラムゼー理論 (en) に関する未解決問題の解の推定値の上限として得られた自然数である。単なる巨大さ以外で意味のある考察の対象となったことがある最大の数としてギネスブックに認められた。

極めて巨大な数であり指数で表記するのは困難なため特別な表記法を用いて表される。

[編集] グラハム問題

この数は、1970年のグラハム (en) とロートシルト (B. L. Rothschild) による「グラハムの定理」

“

n 次元超立方体の 2ⁿ 個の頂点のそれぞれを互いに全て線で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。
このとき n が十分大きければ、どんな塗り方をしても、同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在する。

”

に関係する。つまり、n が十分大きければというが、

“

n がいくらより大きければ、この関係は常に成立するか

”

ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。

しかし、この関係がグラハム数以上の n について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。グラハム数は現在でもグラハム問題の解の最良の上限である。

グラハムとロートシルトは1971年に解の下限として 6 を与えた。マーティン・ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、Geoff Exoo は2003年により良い下限として 11 を与えた^[1]。

[編集] 定義

[編集] 矢印表記

通常の指数では表現できないので、特殊な関数を用いる。

まず、クヌースの矢印表記を使い、x, y を自然数としたとき、演算子「↑」を次のように定義する。

$x \uparrow y = x ^ y$

さらに「↑↑」を次のように帰納的に定義する。

$x \uparrow\uparrow 1 = x$

$x \uparrow\uparrow y = x \uparrow (x \uparrow\uparrow (y - 1))$

つまり、

$x\uparrow\uparrow y =\ \underbrace{x\uparrow x\uparrow \cdots \uparrow x}_y = \underbrace{x_{}^{x^{{}^{.\,^{.\,^{.\,^x}}}}}}_{y}$ （ $\underbrace{}_y$ は、x が y 個あることを表す）

となる。例を挙げると次のようになる。

$3\uparrow\uparrow2=3^3=27$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987$

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}$

$3\uparrow\uparrow5=3^{3^{3^{3^3}}}$

同様に「↑↑↑」を次のように定義する。

$x \uparrow\uparrow\uparrow 1 = x$

$x \uparrow\uparrow\uparrow y = x \uparrow\uparrow (x \uparrow\uparrow\uparrow (y - 1))$

つまり、

$x\uparrow\uparrow\uparrow y = \underbrace{x\uparrow\uparrow x\uparrow\uparrow \cdots \uparrow\uparrow x}_y$

である。

このようにして、一般に「↑…(n個)…↑」＝「↑ⁿ」を定義する。

$x \uparrow^n 1 = x$

$x \uparrow^n y = x \uparrow^{n-1} (x \uparrow^n (y - 1))$

[編集] グラハム数

これを用いて、関数 G(x) を

$G(x) = 3 \uparrow^x 3$

と定義したときの

$G = G^{64} (4) = \underbrace{G(G(\cdots G}_{64} (4) \cdots ))$

をグラハム数と言う。

[編集] その大きさ

G(x) を実際に計算してみよう。

G(1) = 3↑3 = 3³ = 27
G(2) = 3↑↑3 = 3↑(3↑3) = 3↑G(1) = 3↑27 = 7625597484987
G(3) = 3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑G(2) = 3↑↑7625597484987 = $\underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}_{7625597484987}$
G(4) = 3↑↑↑↑3 = 3↑↑↑G(3) = $\underbrace{3\uparrow\uparrow 3\uparrow\uparrow \cdots \uparrow\uparrow 3}_{G(3)}$

このように急激に大きくなり、G(3) ですらとても計算はできない。G(4) が既に相当な巨大数であることがわかるだろう。次の段階の G²(4) = G(G(4)) = 3↑…(G(4) 個)…↑3 も想像を絶する巨大さであり、ましてグラハム数 G⁶⁴(4) など現実の何物とも比べられない、超巨大な数である。

その大きさをたとえる話として、「グラハム数を十進記数法を用いて印字しようとした場合（十分に印刷できる面積を持つ物体があるとして）、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。しかし、観測可能な宇宙の素粒子の総数は 10⁸⁰ と考えられているので、このたとえで表せる数は、粒子1個で1文字を印刷するとしてもせいぜい $10^{10^{80}}$ に過ぎない。この数はグラハム数どころか G(3) と比較しても圧倒的に小さく（G(3) の遥か手前、 $3^{3^{3^{3^3}}}$ が既に約 $10^{10^{3600000000000}}$ である）、グーゴルプレックスにも満たない。これほど極端な話ですらたとえにもならないほど巨大なのがグラハム数である。