グラハム数 グラハム数の概要

ウィキペディア

グラハム数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/07/21 15:21 UTC 版)

極めて巨大な巨大数であり指数で表記するのは事実上不可能なため特別な表記法を用いて表される。

グラハム問題

この数は、1970年のロナルド・グラハムとブルース・リー・ロスチャイルドによる「グラハムの定理」

“

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

”

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

“

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

”

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

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

ただしグラハムらは実際にはこの数を論文では発表しておらず、翌1971年にグラハム数より小さなグラハム問題の解の上限として、小グラハム数という数を発表した。その後、マーティン・ガードナーが1977年にサイエンティフィック・アメリカンでグラハム数を紹介したことによってこの数は広く知られるようになった。

解の上限はのち2014年にミハイル・ラブロフらによってより小さい数が示された。

一方、この問題の解の下限（つまりこの数より小さい数では成り立たないことを示した数）としては、グラハムとロートシルトは1971年の小グラハム数を示したものと同じ論文中で 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、2003年にジェフ・エクスーがより良い下限として 11 を、2008年にはジェローム・バークレーが 13 を与えた。

定義

矢印表記

グラハム数は巨大すぎて、通常の指数では事実上表現不可能である。そのため次のような特殊な関数を用いる。

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

$x\uparrow y=x^{y}$

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

$x\uparrow \uparrow 1=x$

$x\uparrow \uparrow y=x\uparrow \left\{x\uparrow \uparrow \left(y-1\right)\right\}$

つまり、

$x\uparrow \uparrow y=\ \underbrace {x\uparrow x\uparrow \cdots \uparrow x} _{y}=\underbrace {x^{x^{\cdot ^{\cdot ^{\cdot ^{x}}}}}} _{y}$

となる（$\underbrace {} _{y}$ は、x が y 個あることを表す）。ただし演算は右から行う。つまり例えば、x↑x↑x = x↑(x↑x) である。例を挙げると次のようになる。

${\begin{aligned}3\uparrow \uparrow 2=&3^{3}=27\\3\uparrow \uparrow 3=&3^{3^{3}}=3^{27}=7625597484987\\3\uparrow \uparrow 4=&3^{3^{3^{3}}}=3^{7625597484987}\\\approx &1.258\times 10^{3638334640024}\\3\uparrow \uparrow 5=&3^{3^{3^{3^{3}}}}=3^{3^{7625597484987}}\\\approx &3^{1.258\times 10^{3638334640024}}\end{aligned}}$

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

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

$x\uparrow \uparrow \uparrow y=x\uparrow \uparrow \left\{x\uparrow \uparrow \uparrow (y-1)\right\}$

つまり、

$x\uparrow \uparrow \uparrow y=\underbrace {x\uparrow \uparrow x\uparrow \uparrow \cdots \uparrow \uparrow x} _{y{\text{ copies of }}x}$

である。

一般の場合も同様に、「↑…(n 本)…↑」＝「↑ⁿ」を次のように定義する。

$x\uparrow ^{n}1=x$

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

グラハム数

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

$G(n)=3\uparrow ^{n}3=3\rightarrow 3\rightarrow n$

と定義したときの

${\begin{aligned}G&=G^{64}(4)=\underbrace {G(G(\cdots G} _{64}(4)\cdots ))\\&=\underbrace {3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots 3\rightarrow 3\rightarrow } _{64}(4)\cdots ))\\&=\left.{\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\\underbrace {\qquad \;\;\vdots \qquad \;\;} \\3\underbrace {\uparrow \uparrow \cdots \cdots \uparrow } 3\\3\rightarrow 3\rightarrow {4}\end{matrix}}\right\}64{\text{ layers}}=\left.{\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\\underbrace {\qquad \;\;\vdots \qquad \;\;} \\3\underbrace {\uparrow \uparrow \cdots \cdots \uparrow } 3\\\operatorname {hyper} (3,6,3)\end{matrix}}\right\}64{\text{ layers}}\end{aligned}}$

をグラハム数と言う。

その大きさ

G(x) を実際に計算してみると、

• G(1) = 3↑3 = 3→3→1 = 3→3 = 3³ = 27
• G(2) = 3↑↑3 = 3→3→2 = 3↑(3↑3) = 3↑G(1) = 3↑27 = 7625597484987
• G(3) = 3↑↑↑3 = 3→3→3 = 3↑↑(3↑↑3) = 3↑↑G(2) = 3↑↑7625597484987

$=\underbrace {3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3^{3^{3}}}}}}}}}}}}}}}} _{7625597484987}$

• G(4) = 3↑↑↑↑3 = 3→3→4 = 3↑↑↑G(3)

$=\underbrace {3\uparrow \uparrow 3\uparrow \uparrow \cdots \uparrow \uparrow 3\uparrow \uparrow 3} _{G(3){\text{ copies of }}3}$

• G²(4) = G(G(4)) = 3↑…(G(4) 本)…↑3 = 3→3→G(4) = 3↑^G(4)-13↑^G(4)-2…↑³3↑²3↑3

• G³(4) = G(G²(4)) = 3↑…(G²(4) 本)…↑3 = 3→3→G²(4)

：

：

• G⁶⁴(4) = G(G⁶³(4)) = 3↑…(G⁶³(4) 本)…↑3 = 3→3→G⁶³(4) = hyper(3, G⁶³(4)+2, 3) = hyper(3, G⁶²(G(4))+2, 3) = hyper(3, G⁶²(3→2→5)+2, 3) = 3↑^G63(4)-13↑^G63(4)-2…↑³3↑²3↑3↑3

G(2) までは十進法表記で表すことができるが、G(3) ですら既に3の累乗を7兆6000億回以上繰り返した数であるため、現実の何物とも比べられないような巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能である。G(4) はその十進以下の表記が現実的に不可能な G(3) − 1 の数だけ ↑↑（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっている。

次の段階の G²(4) は3と3の間に G(4) 本矢印をおいたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 ($2\left[2[5]\right]=2\left[2[4][4]\right]=2\left[2[3][3][4]\right]=2\left[{2}^{{2}^{2059}}[3]_{254}\right]$)も超える。この操作を63回繰り返した数がグラハム数である。

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

コンウェイのチェーン表記を用いても G = G⁶⁴(4) を簡潔に表すことは出来ないが、次の不等式が成立する。

$3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2$

ちなみに、グラハム数を十進法で表したときの下3桁は387である。末尾100万桁を記した書籍が出版されている。