グラハム数

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

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

## グラハム問題

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

に関係する。つまり、*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 }

**G*2(4) = *G*(*G*(4)) = 3&uarr;…(*G*(4) 本)…&uarr;3 = 3→3→*G*(4) = 3&uarr;3&uarr;…&uarr;3&uarr;3&uarr;3&uarr;3

**G*3(4) = *G*(*G*2(4)) = 3&uarr;…(*G*2(4) 本)…&uarr;3 = 3→3→*G*2(4)
:：
:：
**G*64(4)  *G*(*G*63(4))  3&uarr;…(*G*63(4) 本)…&uarr;3  3→3→*G*63(4) = hyper(3, *G*63(4)+2, 3) = 3&uarr;…((*G*63(4)+1) 本)…&uarr;2 = 3→2→(*G*63(4)+1) = hyper(3, *G*63(4)+3, 2) = hyper(3, *G*(*G*(4))+2, 3) = hyper(3, *G*(3→2→5)+2, 3) = 3&uarr;3&uarr;…&uarr;3&uarr;3&uarr;3&uarr;3
*G*(2) までは関数電卓やパソコンでも普通に計算できるが、*G*(3) ですら既に3の累乗を7兆6,255億回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、の方が遥かに大きい（しかし3↑↑↑4よりは遥かに小さい）。*G*(4) はその十進以下の表記が現実的に不可能な *G*(3) &minus; 1 の数だけ &uarr;&uarr;（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっている。

次の段階の *G*2(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>](https://ja.wikipedia.org/wiki/%E5%A4%9A%E8%A7%92%E5%BD%A2%E8%A1%A8%E8%A8%98)も超える。この操作を63回繰り返した数がグラハム数である。

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

観測可能な宇宙の素粒子の総数は 1080 と考えられているので、このたとえで表せる数は、素粒子1個で1文字を印刷するとしても *n* 進表記ならせいぜい *n*1080 に過ぎない。この数は1 3^{3^{3^{3^{3}}}} が既におよそ {10}^} である）。16進表記ではアルファベットの大文字と小文字を区別しないが、Unicodeでは区別されている。現在Unicodeで使用されている文字の総数は13万7468個であり、未使用領域が全て埋め尽くされると *n* = 1114112となるが、 *n* が1億まで拡張されたとしても108×1080 であり、グーゴルプレックス <math>{10}^</math> にも満たない。

これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。宇宙論で使われた最大の数（複数の宇宙の全質量を1個のブラックホールに圧縮しそれが蒸発した後に、ポアンカレの回帰定理に従い再びブラックホールができる時間）をaとすると、aですら{10}^_{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↑3 = 2→3→12 = 2↑2↑2 = 2↑4 = 2↑2↑2↑2 = 2↑*F*(11)
::=\underbrace{2\uparrow^{9} 2\uparrow^{9} \cdots \uparrow^{9} 2 \uparrow^{9} 2 }_{F(11) \text{ copies of }2 }

**F*2(12) = *F*(*F*(12)) = 2&uarr;…(*F*(12) 本)…&uarr;3 = 2→3→*F*(12)

**F*3(12) = 2&uarr;…(*F*(12) 本)…&uarr;3 = 2→3→*F*(12)
:：
:：
**F*7(12) = 2&uarr;…(*F*(12) 本)…&uarr;3 = 2→3→*F*(12)

*F*(3) までは関数電卓やパソコンでも普通に計算できるが、*F*(4) ですら十進法以下の表記で表すことすら現実的には不可能である（ただしよりは遥かに小さい）。同様の操作を繰り返した*F*(12)も同様に巨大数である。

次の段階の *F*2(12) は2と3の間に *F*(12) 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、[モーザー数 (<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>)](https://ja.wikipedia.org/wiki/%E5%A4%9A%E8%A7%92%E5%BD%A2%E8%A1%A8%E8%A8%98)も超える。この操作を6回繰り返した数が小グラハム数である。

グラハム数の大きさの議論と同様に、log10F≒Fと見做せる。

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

:3\rightarrow 2\rightarrow 8\rightarrow 2 
小グラハム数もグラハム数と同様に末尾の数字を計算する方法は確立しており、ある程度の桁数は判明している。

 を十進法で表したときの末尾3桁は  である。

### 表現
小グラハム数を表すにはいくつか等価な表現がある。
*クヌースの矢印表記
: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), 
: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(4 \uparrow \left(2 + \left(2 + 4\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(4 \uparrow 8\right)\right)\right)\right)\right)\cdots\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 4 \rightarrow 11\right)\right)\right)\right)\right)\right)

これはどちらも 2\rightarrow 3 \rightarrow 12 = 2\rightarrow 4 \rightarrow 11 を根拠としている。

## ラブロフらによる解の上限
ラブロフらは2014年に、多次元三目並べに関するを応用し、より小さい上限として
: N' = 2 \uparrow\uparrow\uparrow 6 = 2 \rightarrow 6 \rightarrow 3 =
\operatorname{hyper}(2, 5, 6) 
を示した。これでもなお十進表記が事実上不可能なほど非常に大きい数であるが、グラハム数および小グラハム数と比較すると格段に小さい数である。これによりグラハム問題の解 *n* は
:\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\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow4 = 2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow65536 \\
=& {}^{2} = {}^{2} = {}^{{}^{2} = {}^{2}\end{align}
の範囲にあることになる。

## 出典


## 関連項目
*グラハム数を超える巨大数の一覧

## 外部リンク
*