グラハム数

グラハム数（グラハムすう、英: Graham's number）は、ラムゼー理論に関する未解決問題の解の推定値の上限として得られた自然数である。数学の証明で使われたことのある最大の数として1980年にギネスブックに認められた。

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

グラハム問題

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

「

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

」

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

「

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

」

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

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

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

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

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

定義

矢印表記

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

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

[math] x \uparrow y = x ^ y [/math]

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

[math] x \uparrow\uparrow 1 = x[/math]

[math] x \uparrow\uparrow y = x \uparrow \left\{x \uparrow\uparrow \left(y - 1\right)\right\} [/math]

つまり、

[math] x\uparrow\uparrow y =\ \underbrace{x\uparrow x\uparrow \cdots \uparrow x}_y = \underbrace{x^{x^{\cdot^{\cdot^{\cdot^x}}}}}_{y} [/math]

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

[math]\begin{align} 3\uparrow\uparrow2=&3^3=27 \\ 3\uparrow\uparrow3=&3^{3^3}=3^{27}=7625597484987 \\ 3\uparrow\uparrow4=&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{align}[/math]

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

[math] x \uparrow\uparrow\uparrow 1 = x[/math]

[math] x \uparrow\uparrow\uparrow y = x \uparrow\uparrow \left\{x \uparrow\uparrow\uparrow (y - 1)\right\} [/math]

つまり、

[math] x\uparrow\uparrow\uparrow y = \underbrace{x\uparrow\uparrow x\uparrow\uparrow \cdots \uparrow\uparrow x}_{y\text{ copies of }x}[/math]

である。

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

[math] x \uparrow^n 1 = x[/math]

[math] x \uparrow^n y = x \uparrow^{n-1} \left\{x \uparrow^n \left(y - 1 \right)\right\} [/math]

グラハム数

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

[math] G(n) = 3 \uparrow^n 3 = 3 \rightarrow 3 \rightarrow n [/math]

と定義したときの

[math]\begin{align} 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{align}[/math]

をグラハム数といい、その計算法は3の冪乗やテトレーションからの発展を基本としている。

その大きさ

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

[math]= \underbrace{3^{3^{3^{ \cdot ^{ \cdot^ { \cdot^ { \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 3^{ 3^ 3}}}}}}}}}}}}}}}_{7625597484987} [/math]

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

[math]=\underbrace{3\uparrow\uparrow 3\uparrow\uparrow \cdots \uparrow\uparrow 3 \uparrow\uparrow 3 }_{G(3) \text{ copies of }3 }[/math]

• G²(4) = G(G(4)) = 3↑…(G(4) 本)…↑3 = 3→3→G(4) = 3↑^G(4)-13↑^G(4)-2…↑³3↑²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兆6,255億回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能である。G(4) はその十進以下の表記が現実的に不可能な G(3) − 1 の数だけ ↑↑（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっている。

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

この大きさをたとえる話として、「グラハム数を十進記数法を用いて印字しようとした場合（十分に印刷できる面積を持つ物体があるとして）、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。

観測可能な宇宙の素粒子の総数は 10⁸⁰ と考えられているので、このたとえで表せる数は、素粒子1個で1文字を印刷するとしても n 進表記ならせいぜい n¹⁰⁸⁰ に過ぎない。この数は1 < | n | ≤ 10 のときグラハム数どころか G(3) と比較しても圧倒的に小さく（G(3) の遥か手前、[math]3^{3^{3^{3^{3}}}}[/math] が既におよそ [math]{10}^{{10}^{3.6\times{10}^{12}}}[/math] である）、グーゴルプレックス [math]{10}^{{10}^{100}}[/math] にも満たない。

これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。宇宙論で使われた最大の数（複数の宇宙の全質量を1個のブラックホールに圧縮しそれが蒸発した後に、ポアンカレの回帰定理に従い再びブラックホールができる時間）ですら[math]{10}^{{10}^{{10}^{{10}^{{10}^{1.1}}}}}\approx{10}^{{10}^{{10}^{3883775501690}}}[/math]であり、これもグラハム数はおろかG(3) ともとても比較にならない。

近年は巨大数の研究・開発がより進み、現在ではグラハム数を遥かに上回る数も多数登場していて、例えばコンウェイのチェーン表記を用いて、例えば「3→3→3→3」などと書くだけでグラハム数よりも大きな数を表現可能である。

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

[math]3\rightarrow 3\rightarrow 64\rightarrow 2 \lt G \lt 3\rightarrow 3\rightarrow 65\rightarrow 2[/math]

先述の通り、グラハム数自体は桁数を指数で表現することすら不可能なほど大きく、スーパーコンピュータでもG(3)の計算すら望めないが、末尾の数字を計算する方法は確立しており、ある程度の桁数は判明している。

十進法で表したときの末尾10桁は 2,464,195,387 であり、暗黒通信団が末尾100万桁を記した書籍も出版し、その後、暗黒通信団のウェブサイトで末尾1,600万桁を記したPDF形式のファイルも公開している。

表現

グラハム数を表すにはいくつか等価な表現がある。

名称	表記
クヌースの矢印表記	[math]\begin{align}&3 \uparrow^{G^{63}(4)+1} 2 ,~ 3 \uparrow^{G^{62}(3 \uparrow^{5} 2)+1} 2 ,~ 3\uparrow^{G^{63}(4)-1}3\uparrow^{G^{63}(4)-2}\cdots3\uparrow^{5}3\uparrow^{4}3\uparrow^{3}3\uparrow^{2}3\uparrow^{1}\left(3\times\left(3+(3+3)\right)\right),~ 3\uparrow^{G^{63}(4)-1}3\uparrow^{G^{63}(4)-2}\cdots3\uparrow^{5}3\uparrow^{4}3\uparrow^{3}3\uparrow^{2}3\uparrow^{1}27\\ &3\uparrow^{G^{63}(4)-1}\left(3\uparrow^{G^{63}(4)}2\right),~3\uparrow^{G^{63}(4)-2}3\uparrow^{G^{63}(4)-1}\left(3\uparrow^{G^{63}(4)}2-1\right),~3\uparrow\left(3\uparrow^{2}\left(3\uparrow^{3}\left(3\uparrow^{4}\left(\cdots3\uparrow^{G^{63}(4)-2}\left(3\uparrow^{G^{63}(4)-1}\left(3\uparrow^{G^{63}(4)-1}3-1\right)-1\right)\cdots-1\right)-1\right)-1\right)\right),~3\uparrow\left(3\uparrow^{2}\left(3\uparrow^{3}\left(3\uparrow^{4}\left(\cdots3\uparrow^{G^{63}(4)-2}\left(3\uparrow^{G^{63}(4)-1}\left(G\left(G^{63}(4)-1\right)-1\right)-1\right)\cdots-1\right)-1\right)-1\right)\right)\end{align}[/math]
コンウェイのチェーン表記	[math]3 \rightarrow 2 \rightarrow (G^{63}(4)+1),~3 \rightarrow 2 \rightarrow \left(G^{62}\left(3 \rightarrow 2 \rightarrow (5)\right)+1\right)[/math]

小グラハム数

グラハムとロートシルトは1971年に、より小さい上限として小グラハム数 (Little Graham) を示した。この数は関数 F(n) を

[math]F(n) = 2 \uparrow^{n} 3 =2\underbrace{\uparrow \cdots \uparrow}_{n}3 = 2 \rightarrow 3 \rightarrow n[/math]

と定義したときの

[math]\begin{align} F &:= F^{7} (12) = F \left(F \left(F \left (F \left (F \left (F \left(F(12) \right) \right ) \right) \right ) \right ) \right)\\ &=2 \rightarrow 3 \rightarrow\left(2 \rightarrow 3 \rightarrow\left(2 \rightarrow 3 \rightarrow\left(2 \rightarrow 3 \rightarrow\left(2 \rightarrow 3 \rightarrow\left(2 \rightarrow 3 \rightarrow\left(2 \rightarrow 3 \rightarrow 12\right)\right)\right)\right)\right)\right)\\ &= \left. \begin{matrix} 2\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\ 2\underbrace{\uparrow \cdots \cdots \cdots \uparrow}3 \\ \underbrace{\qquad\;\; \vdots \qquad\;\;} \\ 2\underbrace{\uparrow \cdots \cdots \cdots \uparrow}3 \\ 2\uparrow^{12}3 \end{matrix} \right \}7\text{ layers} = 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 12 } 3 } 3 } 3 } 3 } 3 } 3 } 3 = 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow 3 } 3 } 3 } 3 } 3 } 3 } 3\\ &=2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \rightarrow 3 \rightarrow 12 } 3 } 3 } 3 } 3 } 3 } 3\\ &=2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ \operatorname{hyper}({2, 14, 3}) } 3 } 3 } 3 } 3 } 3 } 3\end{align}[/math]

である。これはグラハム数よりは遥かに小さいが、それでもなお非常に大きい数である。

その大きさ

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

• F(1) = 2↑3 = 2→3→1 = 2→3 = 2³ = 8
• F(2) = 2↑↑3 = 2→3→2 = 2↑(2↑2) = 2↑4 = 16
• F(3) = 2↑↑↑3 = 2→3→3 = 2↑↑(2↑↑2) = 2↑↑4 = 2²²² = 2↑F(2) = 65536
• F(4) = 2↑↑↑↑3 = 2→3→4 = 2↑↑↑(2↑↑↑2) = 2↑↑↑4 = 2↑↑2↑↑2↑↑2 = 2↑↑F(3) = 2↑↑65536

[math]= \underbrace{2^{2^{2^{ \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 2^{ 2^ 2}}}}}}}}}}}}_{65536} [/math]

• F(5) = 2↑↑↑↑↑3 = 2→3→5 = 2↑↑↑↑2↑↑↑↑2 = 2↑↑↑↑4 = 2↑↑↑2↑↑↑2↑↑↑2 = 2↑↑↑F(4)

[math]=\underbrace{2\uparrow\uparrow 2\uparrow\uparrow \cdots \uparrow\uparrow 2 \uparrow\uparrow 2 }_{F(4) \text{ copies of }2 }[/math]

：

：

• F(12) = 2↑¹²3 = 2→3→12 = 2↑¹¹2↑¹¹2 = 2↑¹¹4 = 2↑¹⁰2↑¹⁰2↑¹⁰2 = 2↑¹⁰F(11)

[math]=\underbrace{2\uparrow^{9} 2\uparrow^{9} \cdots \uparrow^{9} 2 \uparrow^{9} 2 }_{F(11) \text{ copies of }2 }[/math]

• F²(12) = F(F(12)) = 2↑…(F(12) 本)…↑3 = 2→3→F(12)

• F³(12) = 2↑…(F²(12) 本)…↑3 = 2→3→F²(12)

：

：

• F⁷(12) = 2↑…(F⁶(12) 本)…↑3 = 2→3→F⁶(12)

チェーン表記を用いても F = F⁷(12) を簡潔に表すことはできないが、次の不等式が成立する。

[math]3\rightarrow 2\rightarrow 8\rightarrow 2 \lt F \lt 3\rightarrow 2\rightarrow 9\rightarrow 2[/math]

ラブロフらによる解の上限

ラブロフらは2014年に、多次元三目並べに関するヘイルズ＝ジュエットの定理を応用し、より小さい上限として

[math] N' = 2 \uparrow\uparrow\uparrow 6 = 2 \rightarrow 6 \rightarrow 3 = \operatorname{hyper}(2, 5, 6) [/math]

を示した。これもなお非常に大きい数であるが、グラハム数および小グラハム数と比すると格段に小さい数である。これによりグラハム問題の解 n は

[math]\begin{align} 13 \le n \le 2 \uparrow\uparrow\uparrow 6 =& 2 \rightarrow 6 \rightarrow 3 = \operatorname{hyper}(2, 5, 6) \\ =& 2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2 = {}^{{}^{{}^{{}^{{}^{2}{2}}{2}}{2}}{2}}{2} = {}^{{}^{{}^{{}^{4}{2}}{2}}{2}}{2} = {}^{{}^{{}^{{2}^{{2}^{{2}^{2}}}}{2}}{2}}{2} = {}^{{}^{{}^{65536}{2}}{2}}{2}\end{align}[/math]

の範囲にあることになる。

外部リンク

• Weisstein, Eric W. “Graham's Number”. MathWorld（英語）.