グラハム数すう

グラハム数すう（グラハムすう、英えい: Graham's number）は、ラムゼー理論りろんに関かんする未み解決かいけつ問題もんだいの解かいの推定すいてい値ちの上限じょうげんとして得えられた自然しぜん数すうである。数学すうがくの証明しょうめいで使つかわれたことのある最大さいだいの数かずとして1980年ねんにギネスブックに認みとめられた。

極きわめて巨大きょだいな自然しぜん数すうであり、指数しすう表記ひょうきを用もちいるのは事実じじつ上じょう不可能ふかのうなため、特別とくべつな表記ひょうき法ほうを用もちいて表あらわされる。

グラハム問題もんだい

3次元じげんの立方体りっぽうたいで同どう一いち平面へいめん上じょうにある四よん点てんでそれらを結むすぶ線せんが全すべて同一どういつの色いろであるものが存在そんざいしている例れい。線せんをどのように塗ぬってもこのような平面へいめんが少すくなくとも1つ現あらわれてしまうのは何なん次元じげん以上いじょうの超ちょう立方体りっぽうたいか、というのがこの問題もんだいの骨子こっしである。

この数かずは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}}\\\approx &10^{6.0022\times 10^{3638334640023}}\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\mathbin {\underbrace {\uparrow \cdots \uparrow } _{n\ {\textrm {arrows}}}} 3$

と定義ていぎしたときの

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

$=\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) はその十じゅう進しん以下いかの表記ひょうきが現実げんじつ的てきに不可能ふかのうな 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[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) の遥はるか手前てまえ、$3^{3^{3^{3^{3}}}}$ が既すでにおよそ ${10}^{{10}^{3.6\times {10}^{12}}}$ である）。16進しん表記ひょうきではアルファベットの大文字おおもじと小文字こもじを区別くべつしないが、Unicodeでは区別くべつされている。現在げんざいUnicodeで使用しようされている文字もじの総数そうすうは13万まん7468個こであり、未み使用しよう領域りょういきが全すべて埋うめ尽つくされると n = 1114112となるが、 n が1億おくまで拡張かくちょうされたとしても10^8×1080 であり、グーゴルプレックス ${10}^{{10}^{100}}$ にも満みたない。

これほど極端きょくたんな例たとえですらい表いあらわすことができないほど巨大きょだいな数かずがグラハム数すうである。宇宙うちゅう論ろんで使つかわれた最大さいだいの数かず（複数ふくすうの宇宙うちゅうの全ぜん質量しつりょうを1個いっこのブラックホールに圧縮あっしゅくしそれが蒸発じょうはつした後のちに、ポアンカレの回帰かいき定理ていりに従したがい再ふたたびブラックホールができる時間じかん）をaとすると、aですら${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]$であり、これもグラハム数すうはおろかG(3) ともとても比較ひかくにならない。

レオナルド・サスキンドは宇宙うちゅうの直径ちょっけいを$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である。

近年きんねんは巨きょ大数たいすうの研究けんきゅう・開発かいはつがより進すすみ、現在げんざいではグラハム数すうを遥はるかに上回うわまわる数かずも多数たすう登場とうじょうしていて、例たとえばコンウェイのチェーン表記ひょうきを用もちいて"$3\rightarrow 3\rightarrow 3\rightarrow 3$"（コンウェイのテトラトリと呼よばれる数かず）などと書かくだけでグラハム数すうよりも大おおきな数かずを表現ひょうげん可能かのうである。

チェーン表記ひょうきを用もちいても G = 3→2→(G⁶³(4) + 1) を簡潔かんけつに表あらわすことはできないが、次つぎの不等式ふとうしきが成立せいりつする。

$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万まん桁けたを記しるした書籍しょせきも出版しゅっぱんし、その後ご、暗黒あんこく通信つうしん団だんのウェブサイトで末尾まつび1,600万まん桁けたを記しるしたPDF形式けいしきのファイルも公開こうかいしている。

表現ひょうげん

グラハム数すうを表あらわすにはいくつか等価とうかな表現ひょうげんがある。

• クヌースの矢印やじるし表記ひょうき

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

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

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

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

$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]$,

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

$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)$,

$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)$,

$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$,

$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$,

$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}$,

$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$,

$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)}

• コンウェイのチェーン表記ひょうき

$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{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

$=\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↑¹²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²(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) 本ほん矢印やじるしを置おいたものであり、この時点じてんで指数しすうのみの表記ひょうきも括弧かっこを駆使くししても事実じじつ上じょう不可能ふかのうとなり、モーザー数すう ($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) を簡潔かんけつに表あらわすことはできないが、次つぎの不等式ふとうしきが成立せいりつする。

$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 である。

表現ひょうげん

小しょうグラハム数すうを表あらわすにはいくつか等価とうかな表現ひょうげんがある。

• クヌースの矢印やじるし表記ひょうき

$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{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}}$

の範囲はんいにあることになる。

関連かんれん項目こうもく

• グラハム数すうを超こえる巨きょ大数たいすうの一覧いちらん

外部がいぶリンク

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