グラハム数

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

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

グラハム問題

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

「

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

」

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

「

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

」

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

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

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

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

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

定義

矢印表記

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

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

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

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

${\displaystyle x\uparrow \uparrow 1=x}$

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

つまり、

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

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

${\displaystyle {\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}}\\\approx &10^{6.0022\times 10^{3638334640023}}\end{aligned}}}$

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

${\displaystyle x\uparrow \uparrow \uparrow 1=x}$

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

つまり、

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

である。

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

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

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

グラハム数

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

${\displaystyle G(n)=3\uparrow ^{n}3=3\mathbin {\underbrace {\uparrow \cdots \uparrow } _{n\ {\textrm {arrows}}}} 3}$

と定義したときの

${\displaystyle {\begin{aligned}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 \quad 3\underbrace {\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow \uparrow \uparrow } 3{\text{ arrows}}\\\vdots \\\qquad \quad 3\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{aligned}}}$

をグラハム数といい、その計算法は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↑↑3) = 3↑↑G(2) = 3↑↑7625597484987（トリトリ）

${\displaystyle =\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)（グラハル）

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

次の段階の G²(4) は3と3の間に G(4) 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 (${\displaystyle 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)にすら満たない。

観測可能な宇宙の素粒子の総数は 10⁸⁰ と考えられているので、このたとえで表せる数は、素粒子1個で1文字を印刷するとしても n 進表記ならせいぜい n¹⁰⁸⁰ に過ぎない。この数は1 < | n | ≤ 16 のときグラハム数や16$_Pickoverどころか G(3) と比較しても圧倒的に小さい（G(3) の遥か手前、${\displaystyle 3^{3^{3^{3^{3}}}}}$ が既におよそ ${\displaystyle {10}^{{10}^{3.6\times {10}^{12}}}}$ である）。16進表記ではアルファベットの大文字と小文字を区別しないが、Unicodeでは区別されている。現在Unicodeで使用されている文字の総数は13万7468個であり、未使用領域が全て埋め尽くされると n = 1114112となるが、 n が1億まで拡張されたとしても10^8×1080 であり、グーゴルプレックス ${\displaystyle {10}^{{10}^{100}}}$ にも満たない。

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

レオナルド・サスキンドは宇宙の直径を${\displaystyle 10^{10^{10^{122}}}}$と推定しているが、この値をbとすると、bもaと同様に桁数が大きすぎて単位が考慮されていない。しかし、1辺がbヨタパーセクの立方体に1辺が1プランク長の立方体が隙間なく詰め込まれ、それらの立方体がa千年紀に渡って1プランク時間ごとに1種類の文字を生成し、作業完了時点で完全に重複する文字が1種類も存在しない場合ですら、生成された文字をc種類とし、c-1を表現する文字をc個並べた数をdとした場合、dはグラハム数はおろかG(3) ともとても比較にならない。

なお、強いて「グラハム数を十進法で表した時の桁数」を考えるなら、log₁₀Gとなるが、Gは十分な巨大数なので、この場合にあってはlog₁₀という関数で厳密には元の数より小さくなるものの、巨大数としては無視できるレベルでしかなく、近似に吸収されてしまう。すなわち、log₁₀G≒Gである。

近年は巨大数の研究・開発がより進み、現在ではグラハム数を遥かに上回る数も多数登場していて、例えばコンウェイのチェーン表記を用いて"${\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3}$"（コンウェイのテトラトリと呼ばれる数）などと書くだけでグラハム数よりも大きな数を表現可能である。

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

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2}$

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

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

表現

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

• クヌースの矢印表記

${\displaystyle 3\uparrow ^{G^{63}(4)+1}2}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-1}3}$,

${\displaystyle 3\uparrow ^{G^{62}\left(3\uparrow ^{5}2\right)+1}2}$,

${\displaystyle 3\uparrow ^{G^{62}\left(3\uparrow \uparrow \uparrow \uparrow \uparrow 2\right)+1}2}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}3\uparrow ^{1}\left[3\times \left\{3+(3+3)\right\}\right]}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}3\uparrow ^{1}\left\{3\times \left(3+6\right)\right\}}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}3^{3}\uparrow ^{1}\left(3+6\right)}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}27\uparrow ^{1}\left(3+6\right)}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}27\uparrow 9}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}3\uparrow ^{1}27}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}3^{27}}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}3\uparrow ^{2}7625597484987}$,

${\displaystyle 3\uparrow ^{G^{63}(4)-1}3\uparrow ^{G^{63}(4)-2}\cdots 3\uparrow ^{6}3\uparrow ^{5}3\uparrow ^{4}3\uparrow ^{3}\operatorname {Cg} \left(3\right)}$ (CgはCG関数, ${\displaystyle \operatorname {Cg} (n)=\underbrace {n\rightarrow n\rightarrow n\rightarrow \dots \rightarrow n\rightarrow n\rightarrow n} _{{\text{長さ}}n}}$)

${\displaystyle {\begin{aligned}&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(\cdots 3\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(\cdots 3\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),\\&3^{3\uparrow ^{2}\left(3\uparrow ^{3}\left(3\uparrow ^{4}\left(\cdots 3\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)}\end{aligned}}\left({\begin{aligned}\because G(n)=3\uparrow ^{n}3=&3\uparrow ^{n-1}3\uparrow ^{n-1}3=3\uparrow ^{n-1}G(n-1)\\=&\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{aligned}}\right)}$

• コンウェイのチェーン表記

${\displaystyle 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)}$

• ハイパー演算表記

${\displaystyle 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)}$
${\displaystyle \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) を

${\displaystyle F(n)=2\uparrow ^{n}3=2\underbrace {\uparrow \cdots \uparrow } _{n}3=2\rightarrow 3\rightarrow n}$

と定義したときの

${\displaystyle {\begin{aligned}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{aligned}}}$

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

その大きさ

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

${\displaystyle =\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)

${\displaystyle =\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)

${\displaystyle =\underbrace {2\uparrow ^{9}2\uparrow ^{9}\cdots \uparrow ^{9}2\uparrow ^{9}2} _{F(11){\text{ copies of }}2}}$

• 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(3) までは関数電卓やパソコンでも普通に計算できるが、F(4) ですら既に2の累乗を6万回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、9$_Pickoverよりは遥かに小さい。F(5) はその十進以下の表記が現実的に不可能な F(4) − 1 の数だけ↑↑（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっており、ましてやそれと同様の操作を繰り返したF(12)はなおさらである。

次の段階の F²(12) は2と3の間に F(12) 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 (${\displaystyle 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や宇宙論を用いた例えがそのまま適用され、log₁₀F≒Fと見做せる。

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

${\displaystyle 3\rightarrow 2\rightarrow 8\rightarrow 2<F<3\rightarrow 2\rightarrow 9\rightarrow 2}$

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

2→3→F⁵(2→3→12) を十進法で表したときの末尾3桁は 736 である。

表現

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

• クヌースの矢印表記

${\displaystyle 2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{11}4}3}3}3}3}3}3}$,

${\displaystyle 2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{2\uparrow ^{11}4}3}3}3}3}3-1}4}$,

${\displaystyle 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)}$,

${\displaystyle 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)}$,

${\displaystyle 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)}$,

${\displaystyle 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)}$,

${\displaystyle 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)}$

• コンウェイのチェーン表記

${\displaystyle 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)}$

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

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

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

${\displaystyle N'=2\uparrow \uparrow \uparrow 6=2\rightarrow 6\rightarrow 3=\operatorname {hyper} (2,5,6)}$

を示した。これでもなお十進表記が事実上不可能なほど非常に大きい数であるが、グラハム数および小グラハム数と比較すると格段に小さい数である。これによりグラハム問題の解 n は

${\displaystyle {\begin{aligned}13\leq n\leq 2\uparrow \uparrow \uparrow 6=&2\rightarrow 6\rightarrow 3=\operatorname {hyper} (2,5,6)\\=&2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 4=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 65536\\=&{}^{{}^{{}^{{}^{{}^{2}{2}}{2}}{2}}{2}}{2}={}^{{}^{{}^{{}^{4}{2}}{2}}{2}}{2}={}^{{}^{{}^{{2}^{{2}^{{2}^{2}}}}{2}}{2}}{2}={}^{{}^{{}^{65536}{2}}{2}}{2}\end{aligned}}}$

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

出典

1. ^ Guiness Book of World Record, 1980 Page 193, line 27-31 http://math.ucsd.edu/~fan/ron/images/record.jpg
2. ^ R. L. Graham and B. L. Rothschild, "Ramsey's theorem for n-parameter sets"
3. ^ Martin Gardner, "Mathematical Games"
4. ^ Lavrov, Mikhail; Lee, Mitchell; Mackey, John (2014). “Improved upper and lower bounds on a geometric Ramsey problem”. European Journal of Combinatorics 42: 135-144. doi:10.1016/j.ejc.2014.06.003. 
5. ^ Geoff Exoo, "A Ramsey Problem on Hypercubes"
6. ^ Barkley, Jerome (2008). "Improved lower bound on an Euclidean Ramsey problem". arXiv:0811.1055 [math.CO]。
7. ^ G(4)にはグラハルという名前がついている。
8. ^ 桁数が非常に大きいため、時間の単位をプランク時間・秒・年のいずれにしても無視できる範囲で近似する。
9. ^ TokusiN (2017). グラハム数百万桁表最終巻. 暗黒通信団. ISBN 9784873100647 
10. ^ グラハム数の末尾1600万桁表（オンライン版）【PDF】

関連項目

• グラハム数を超える巨大数の一覧

外部リンク

• Weisstein, Eric W. "Graham's Number". mathworld.wolfram.com (英語).