グラハム数
グラハム数(グラハムすう、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 を自然数としたとき、演算子「↑」を次のように定義する。
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{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}\\
\approx &10^{6.0022\times 10^{3638334640023}\end{align}
同様に「↑↑↑」を次のように再帰的に定義する。
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 本)…↑」=「↑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 \mathbin{\underbrace{\uparrow\cdots\uparrow}_{n\ \textrm{arrows}}3
\begin{align}
G &= G^{64} (4) = \underbrace{G(G(\cdots G}_{64} (4) \cdots ))\\
&= \left.
\begin{matrix}
3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots\cdots\cdots\cdots \cdots \cdots\cdots\cdots \uparrow \uparrow \uparrow}3 \\
\qquad\quad3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow \uparrow \uparrow}3\text{ arrows} \\
\vdots \\
\qquad\quad3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots\cdots \uparrow \uparrow \uparrow}3\text{ arrows} \\
3 \uparrow\uparrow\uparrow\uparrow 3 \text{ arrows}
\end{matrix}
\right \} 64 \text{ layers}
\end{align}
をグラハム数といい、その計算法は3の冪乗やテトレーションからの発展を基本としている。
G(x) を実際に計算してみると、
G(1) = 3↑3 = 3→3→1 = 3→3 = 33 = 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↑↑3) = 3↑↑G(2) = 3↑↑7625597484987(トリトリ)
= \underbrace{3^{3^{3^{ \cdot ^{ \cdot^ { \cdot^ { \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 3^{ 3^ 3}}}}}}}}_{\text{高 さ }7625597484987} = 3^{\underbrace{3^{3^{3^{ \cdot ^{ \cdot^ { \cdot^ { \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 3^{ 3^ 3}}}}}}}}_{\text{高 さ }7625597484986} \approx \exp_{10}^{7,625,597,484,986}(1.09902)
G(4) = 3↑↑↑↑3 = 3→3→4 =3↑↑↑↑3 = 3↑↑↑G(3)(グラハル)
=\underbrace{3\uparrow\uparrow 3\uparrow\uparrow \cdots \uparrow\uparrow 3 \uparrow\uparrow 3 }_{G(3) \text{ copies of }3 }
G2(4) = G(G(4)) = 3↑…(G(4) 本)…↑3 = 3→3→G(4) = 3↑G(4)-13↑G(4)-2…↑33↑23↑3↑3
G3(4) = G(G2(4)) = 3↑…(G2(4) 本)…↑3 = 3→3→G2(4)
:
:
G64(4)  G(G63(4))  3↑…(G63(4) 本)…↑3  3→3→G63(4) = hyper(3, G63(4)+2, 3) = 3↑…((G63(4)+1) 本)…↑2 = 3→2→(G63(4)+1) = hyper(3, G63(4)+3, 2) = hyper(3, G62(G(4))+2, 3) = hyper(3, G62(3→2→5)+2, 3) = 3↑G63(4)-13↑G63(4)-2…↑33↑23↑3↑3
G(2) までは関数電卓やパソコンでも普通に計算できるが、G(3) ですら既に3の累乗を7兆6,255億回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、16$Pickoverの方が遥かに大きい(しかし3↑↑↑4よりは遥かに小さい)。G(4) はその十進以下の表記が現実的に不可能な G(3) − 1 の数だけ ↑↑(二重矢印)を繰り返した数であるため、想像を絶する大きさとなっている。
次の段階の G2(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[3]_{258} \right]=2\left[4[4][3]_{253}\right])も超える。この操作を63回繰り返した数がグラハム数である。
この大きさをたとえる話として、「グラハム数を十進記数法を用いて印字しようとした場合(十分に印刷できる面積を持つ物体があるとして)、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。しかし、その例えを使ったとしてもG(3)にすら満たない。
観測可能な宇宙の素粒子の総数は 1080 と考えられているので、このたとえで表せる数は、素粒子1個で1文字を印刷するとしても n 進表記ならせいぜい n1080 に過ぎない。この数は1 < | n | ≤ 16 のときグラハム数や16$Pickoverどころか G(3) と比較しても圧倒的に小さい(G(3) の遥か手前、3^{3^{3^{3^{3}} が既におよそ {10}^10}^{3.6\times{10}^{12} である)。16進表記ではアルファベットの大文字と小文字を区別しないが、Unicodeでは区別されている。現在Unicodeで使用されている文字の総数は13万7468個であり、未使用領域が全て埋め尽くされると n = 1114112となるが、 n が1億まで拡張されたとしても108×1080 であり、グーゴルプレックス {10}^10}^{100 にも満たない。
これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。宇宙論で使われた最大の数(複数の宇宙の全質量を1個のブラックホールに圧縮しそれが蒸発した後に、ポアンカレの回帰定理に従い再びブラックホールができる時間)をaとすると、aですら{10}^& \underbrace{3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2}\cdots \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3}_{G(n - 1)\text{個の}3}\\ =& 3 \uparrow^{n - 2} \underbrace{3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2}\cdots \uparrow^{n - 2} 3 \uparrow^{n - 2} 3 \uparrow^{n - 2} 3}_{\left(G(n - 1)-1\right)\text{個の}3}\\ =& 3 \uparrow^{n - 2} \left(3 \uparrow^{n - 1} \left(G(n - 1)-1\right)\right)
\end{align}\right)
3 \rightarrow 2 \rightarrow \left(G^{63}(4)+1\right),~3 \rightarrow 2 \rightarrow \left(G^{62}\left(3 \rightarrow 2 \rightarrow (5)\right)+1\right)
3 \left[G^{63}(3 [6] 3)+2\right] 3 ,~ 3 \left[G^{63}(3 [6] 3)+3\right] 2 ,~ 3 \left[G^{63}(3 [7] 2)+2\right] 3 ,~ 3 \left[G^{63}(3 [7] 2)+3\right] 2 ,~ H_{G^{63}(H_{6}(3, 3))+2}(3, 3),~ H_{G^{63}(H_{6}(3, 3))+3}(3, 2),~ H_{G^{63}(H_{7}(3, 2))+2}(3, 3),~ H_{G^{63}(H_{7}(3, 2))+3}(3, 2) \operatorname{hyper}(3, G^{63}(\operatorname{hyper}(3, 6, 3))+2, 3) ,~ \operatorname{hyper}(3, G^{63}(\operatorname{hyper}(3, 6, 3))+3, 2) ,~ \operatorname{hyper}(3, G^{63}(\operatorname{hyper}(3, 7, 2))+2, 3),~ \operatorname{hyper}(3, G^{63}(\operatorname{hyper}(3, 7, 2))+3, 2)
グラハムとロートシルトは1971年に、より小さい上限として小グラハム数 (Little Graham) を示した。この数は関数 F(n) を
F(n) = 2 \uparrow^{n} 3 =2\underbrace{\uparrow \cdots \uparrow}_{n}3 = 2 \rightarrow 3 \rightarrow n
\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}
である。これはグラハム数よりは遥かに小さいが、それでもなお非常に大きい数である。
F(x) を実際に計算してみると、
F(1) = 2↑3 = 2→3→1 = 2→3 = 23 = 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 = 2222 = 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
= \underbrace{2^{2^{2^{ \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 2^{ 2^ 2_{65536}
F(5) = 2↑↑↑↑↑3 = 2→3→5 = 2↑↑↑↑2↑↑↑↑2 = 2↑↑↑↑4 = 2↑↑↑2↑↑↑2↑↑↑2 = 2↑↑↑F(4)
=\underbrace{2\uparrow\uparrow 2\uparrow\uparrow \cdots \uparrow\uparrow 2 \uparrow\uparrow 2 }_{F(4) \text{ copies of }2 }
:
:
F(12) = 2↑123 = 2→3→12 = 2↑112↑112 = 2↑114 = 2↑102↑102↑102 = 2↑10F(11)
=\underbrace{2\uparrow^{9} 2\uparrow^{9} \cdots \uparrow^{9} 2 \uparrow^{9} 2 }_{F(11) \text{ copies of }2 }
F2(12) = F(F(12)) = 2↑…(F(12) 本)…↑3 = 2→3→F(12)
F3(12) = 2↑…(F2(12) 本)…↑3 = 2→3→F2(12)
:
:
F7(12) = 2↑…(F6(12) 本)…↑3 = 2→3→F6(12)
F(3) までは関数電卓やパソコンでも普通に計算できるが、F(4) ですら既に2の累乗を6万回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、9$Pickoverよりは遥かに小さい。F(5) はその十進以下の表記が現実的に不可能な F(4) − 1 の数だけ↑↑(二重矢印)を繰り返した数であるため、想像を絶する大きさとなっており、ましてやそれと同様の操作を繰り返したF(12)はなおさらである。
次の段階の F2(12) は2と3の間に F(12) 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 (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])も超える。この操作を6回繰り返した数がリトル・グラハム数である。
この大きさをたとえる話として、「リトル・グラハム数を十進記数法を用いて印字しようとした場合(十分に印刷できる面積を持つ物体があるとして)、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。しかし、その例えを使ったとしてもF(4)にすら満たず、F(4)の時点で、グラハム数の大きさを例えるのに使用した、Unicodeや宇宙論を用いた例えがそのまま適用され、log10F≒Fと見做せる。
チェーン表記を用いても F = F7(12) を簡潔に表すことはできないが、次の不等式が成立する。
3\rightarrow 2\rightarrow 8\rightarrow 2 < F < 3\rightarrow 2\rightarrow 9\rightarrow 2
先述の通り、リトル・グラハム数自体は桁数を指数で表現することすら不可能なほど大きく、スーパーコンピュータでもF(4)の計算すら望めないが、末尾の数字を計算する方法は確立しており、ある程度の桁数は判明している。
2→3→F5(2→3→12) を十進法で表したときの末尾3桁は 736 である。
小グラハム数を表すにはいくつか等価な表現がある。
2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 } 3,
2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -1} 4,
2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -2} \left(2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -1} 3\right),
2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -2} \left(2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -3} \left(2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -4} \left(2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -5} \left(\cdots 2 \uparrow^{6} \left(2 \uparrow^{5} \left(2 \uparrow^{4} \left(2 \uparrow^{3} \left(2 \uparrow^{2} \left(2 \uparrow \left(2 \cdot \left(2 + \left(2 + 4\right)\right)\right)\right)\right)\right)\right)\right)\cdots\right)\right)\right)\right),
2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -2} \left(2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -3} \left(2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -4} \left(2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -5} \left(\cdots 2 \uparrow^{6} \left(2 \uparrow^{5} \left(2 \uparrow^{4} \left(2 \uparrow^{3} \left(2 \uparrow^{2} \left(\left(2 \uparrow 2\right) \uparrow \left(2 + \left(2 + 4\right)\right)\right)\right)\right)\right)\right)\cdots\right)\right)\right)\right),