グラハム数のソースを表示

{{出典明記|date=2023年10月}}

'''グラハム数'''（グラハムすう、{{lang-en-short|Graham's number}}）は、[[ラムゼー理論]]に関する[[数学上の未解決問題|未解決問題]]の解の推定値の上限として得られた[[自然数]]である。数学の証明で使われたことのある最大の数として[[1980年]]に[[ギネス・ワールド・レコーズ|ギネスブック]]に認められた<ref>Guiness Book of World Record, 1980
Page 193, line 27-31 http://math.ucsd.edu/~fan/ron/images/record.jpg</ref>。

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

== グラハム問題 ==
[[Image:GrahamCube.svg|right|thumb|3次元の立方体で同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在している例。線をどのように塗ってもこのような平面が少なくとも1つ現れてしまうのは何次元以上の超立方体か、というのがこの問題の骨子である。]]
この数は[[1970年]]の[[ロナルド・グラハム]]、[[ブルース・リー・ロスチャイルド]]による「グラハムの定理」
{{Cquote|
''n'' 次元[[超立方体]]の [[2の冪|2<sup>''n''</sup>]] 個の頂点のそれぞれを互いに全て[[線分|線]]で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。<br/>このとき ''n'' が十分大きければ、どのような塗り方をしても、同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在する。
}}
に関係する。つまり、''n'' が十分大きければというが、
{{Cquote|
''n'' がいくらより大きければ、この関係は常に成立するか
}}
ということである。これが'''グラハム問題'''である。[[グラハムの定理]]より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。

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

ただし、グラハムらは実際にはこの数を論文では発表しておらず、翌[[1971年]]にグラハム数より小さなグラハム問題の解の上限として、[[#小グラハム数|小グラハム数]]という数を発表した<ref>R. L. Graham and B. L. Rothschild, [http://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/ "Ramsey's theorem for n-parameter sets"]</ref>。その後、[[マーティン・ガードナー]]が[[1977年]]に[[サイエンティフィック・アメリカン]]でグラハム数を紹介した<ref>Martin Gardner, [http://www.nature.com/scientificamerican/journal/v237/n5/pdf/scientificamerican1177-18.pdf "Mathematical Games"]</ref>ことによってこの数は広く知られるようになった。

解の上限はのち[[2014年]]に[[ミハイル・ラブロフ]]らによって[[#ラブロフらによる解の上限|さらに小さい数]]が示された<ref>{{cite journal |last1=Lavrov|first1=Mikhail |last2=Lee|first2=Mitchell |last3=Mackey|first3=John |date=2014 |title=Improved upper and lower bounds on a geometric Ramsey problem |journal=European Journal of Combinatorics |volume=42 |pages=135-144 |doi=10.1016/j.ejc.2014.06.003}}</ref>。

一方、この問題の解の下限（つまりこの数より小さい数では成り立たないことを示した数）としては、グラハムとロスチャイルドは1971年の小グラハム数を示したものと同じ論文中で [[6]] を与えた。ガードナーは[[1989年]]に著書の中で[[ラムゼー理論]]の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、[[2003年]]に[[ジェフ・エクスー]]がより良い下限として [[11]] を<ref>Geoff Exoo, [http://isu.indstate.edu/ge/GEOMETRY/cubes.html "A Ramsey Problem on Hypercubes"]</ref>、[[2008年]]には[[ジェローム・バークレー]]が [[13]] を与えた<ref>{{cite arXiv |eprint=0811.1055 |last1=Barkley |first1=Jerome |title=Improved lower bound on an Euclidean Ramsey problem |class=math.CO |year=2008 }}</ref>。

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

まず、[[クヌースの矢印表記]]を使い、''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}}\\
\approx &10^{6.0022\times 10^{3638334640023}}\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'' 本)…↑」＝「↑<sup>''n''</sup>」を次のように定義する。
:<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 \mathbin{\underbrace{\uparrow\cdots\uparrow}_{n\ \textrm{arrows}}}3 </math>
と定義したときの
:<math>\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}</math>
を'''グラハム数'''といい、その計算法は[[3の冪|3の冪乗]]や[[テトレーション]]からの発展を基本としている。

== その値の大きさ ==
{{出典の明記| date = 2022年6月| section = 1}}
''G''(''x'') を実際に計算してみると、

*''G''(1) = 3↑3 = 3→3→1 = 3→3 = 3<sup>3</sup> = 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（[[トリトリ]]）
::<math>= \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)</math>
*''G''(4) = 3↑↑↑↑3 = 3→3→4 =3↑↑↑↑3 = 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''<sup>2</sup>(4) = ''G''(''G''(4)) = 3&uarr;…(''G''(4) 本)…&uarr;3 = 3→3→''G''(4) = 3&uarr;{{sup|''G''(4)-1}}3&uarr;{{sup|''G''(4)-2}}…&uarr;{{sup|3}}3&uarr;{{sup|2}}3&uarr;3&uarr;3

*''G''<sup>3</sup>(4) = ''G''(''G''<sup>2</sup>(4)) = 3&uarr;…(''G''<sup>2</sup>(4) 本)…&uarr;3 = 3→3→''G''<sup>2</sup>(4)
:：
:：
*''G''<sup>64</sup>(4) {{=}} ''G''(''G''<sup>63</sup>(4)) {{=}} 3&uarr;…(''G''<sup>63</sup>(4) 本)…&uarr;3 {{=}} 3→3→''G''<sup>63</sup>(4) = hyper(3, ''G''<sup>63</sup>(4)+2, 3) = 3&uarr;…((''G''<sup>63</sup>(4)+1) 本)…&uarr;2 = 3→2→(''G''<sup>63</sup>(4)+1) = hyper(3, ''G''<sup>63</sup>(4)+3, 2) = hyper(3, ''G''{{sup|62}}(''G''(4))+2, 3) = hyper(3, ''G''{{sup|62}}(3→2→5)+2, 3) = 3&uarr;{{sup|''G''{{sup|63}}(4)-1}}3&uarr;{{sup|''G''{{sup|63}}(4)-2}}…&uarr;{{sup|3}}3&uarr;{{sup|2}}3&uarr;3&uarr;3
''G''(2) までは[[関数電卓]]や[[パーソナルコンピュータ|パソコン]]でも普通に計算できるが、''G''(3) ですら既に3の累乗を7兆6,255億回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、{{math|16[[超階乗|${{sub|Pickover}}]]}}の方が遥かに大きい（しかし3↑↑↑4よりは遥かに小さい）。''G''(4) <ref>''G''(4)には[[グラハル]]という名前がついている。</ref>はその十進以下の表記が現実的に不可能な ''G''(3) &minus; 1 の数だけ &uarr;&uarr;（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっている。

次の段階の ''G''<sup>2</sup>(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回繰り返した数がグラハム数である。

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

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

これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。[[宇宙論]]で使われた最大の数（複数の宇宙の全質量を1個の[[ブラックホール]]に圧縮しそれが蒸発した後に、[[ポアンカレの回帰定理]]に従い再びブラックホールができる時間）をaとすると、aですら<math>{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]</math><ref name="3&uarr;&uarr;5">桁数が非常に大きいため、時間の単位を[[プランク時間]]・[[秒]]・[[年]]のいずれにしても無視できる範囲で近似する。</ref>であり、これもグラハム数はおろか''G''(3) ともとても比較にならない。

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

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

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

チェーン表記を用いても ''G'' = {{math|3→2→(''G''<sup>63</sup>(4) + 1)}} を簡潔に表すことはできないが、次の不等式が成立する。
:<math>3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2</math>

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

{{math|3→2→(''G''<sup>63</sup>(4) + 1)}} を十進法で表したときの末尾10桁は {{math|2,464,195,387}} であり、[[暗黒通信団]]が末尾100万桁を記した書籍も出版し<ref>{{cite book|author=TokusiN|year=2017|title=グラハム数百万桁表最終巻|publisher=[[暗黒通信団]]|isbn=9784873100647}}</ref>、その後、暗黒通信団のウェブサイトで末尾1,600万桁を記したPDF形式のファイルも公開している<ref>[http://ankokudan.org/d/dl/others/Graham-16M.pdf グラハム数の末尾1600万桁表（オンライン版）【PDF】]</ref>。

== 表現 ==
{{出典の明記| date = 2022年6月| section = 1}}
グラハム数を表すにはいくつか等価な表現がある。
*[[クヌースの矢印表記]]
:<math>3 \uparrow^{G^{63}(4)+1} 2</math>,
:<math>3 \uparrow^{G^{63}(4)-1} 3 \uparrow^{G^{63}(4)-1} 3</math>,
:<math>3 \uparrow^{G^{62}\left(3 \uparrow^{5} 2\right)+1} 2</math>,
:<math>3 \uparrow^{G^{62}\left(3 \uparrow\uparrow\uparrow\uparrow\uparrow 2\right)+1} 2</math>,
:<math>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]</math>,
:<math>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+6\right)\right\}</math>,
:<math>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^3\uparrow^{1}\left(3+6\right)</math>,
:<math>3\uparrow^{G^{63}(4)-1}3\uparrow^{G^{63}(4)-2}\cdots3\uparrow^{5}3\uparrow^{4}3\uparrow^{3}3\uparrow^{2}27\uparrow^{1}\left(3+6\right)</math>,
:<math>3\uparrow^{G^{63}(4)-1}3\uparrow^{G^{63}(4)-2}\cdots3\uparrow^{5}3\uparrow^{4}3\uparrow^{3}3\uparrow^{2}27\uparrow 9</math>,
:<math>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</math>,
:<math>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^{27}</math>,
:<math>3\uparrow^{G^{63}(4)-1}3\uparrow^{G^{63}(4)-2}\cdots3\uparrow^{5}3\uparrow^{4}3\uparrow^{3}3\uparrow^{2}7625597484987
</math>,
:<math>3\uparrow^{G^{63}(4)-1}3\uparrow^{G^{63}(4)-2}\cdots3\uparrow^{6}3\uparrow^{5}3\uparrow^{4}3\uparrow^{3}\operatorname{Cg}\left(3\right)</math> ({{math|Cg}}は[[CG関数]], <math>\operatorname{Cg}(n) = \underbrace{n\rightarrow n\rightarrow n\rightarrow \dots \rightarrow n\rightarrow n\rightarrow n}_{\text{長さ}n}</math>)
:<math>\begin{align}
&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),\\
&3^{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)}\\
&\left(\begin{align}\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{align}\right)
\end{align}</math>
*[[コンウェイのチェーン表記]]
:<math>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)</math>
*[[ハイパー演算]]表記
:<math>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)</math><br><math>\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)</math>
<!--
*バウアーズの配列表記
:<math>\lbrace a,b,3 \rbrace</math>
*ハイパーE表記<ref>[https://sites.google.com/site/largenumbers/ One to Infinity: A Guide to the Finite]</ref>
:<math>E(a)1\#1\#n</math>
-->

== 小グラハム数 ==
{{出典の明記| date = 2022年6月| section = 1}}
グラハムとロートシルトは[[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<sup>3</sup> = 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{{sup|2{{sup|2{{sup|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↑{{sup|12}}3 = 2→3→12 = 2↑{{sup|11}}2↑{{sup|11}}2 = 2↑{{sup|11}}4 = 2↑{{sup|10}}2↑{{sup|10}}2↑{{sup|10}}2 = 2↑{{sup|10}}''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''<sup>2</sup>(12) = ''F''(''F''(12)) = 2&uarr;…(''F''(12) 本)…&uarr;3 = 2→3→''F''(12)

*''F''<sup>3</sup>(12) = 2&uarr;…(''F''{{sup|2}}(12) 本)…&uarr;3 = 2→3→''F''{{sup|2}}(12)
:：
:：
*''F''<sup>7</sup>(12) = 2&uarr;…(''F''{{sup|6}}(12) 本)…&uarr;3 = 2→3→''F''{{sup|6}}(12)

''F''(3) までは[[関数電卓]]や[[パーソナルコンピュータ|パソコン]]でも普通に計算できるが、''F''(4) ですら十進法以下の表記で表すことすら現実的には不可能である（ただし{{math|9[[超階乗|${{sub|Pickover}}]]}}よりは遥かに小さい）。同様の操作を繰り返した''F''(12)も同様に巨大数である。

次の段階の ''F''<sup>2</sup>(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>)]]も超える。この操作を6回繰り返した数が小グラハム数である。

グラハム数の大きさの議論と同様に、log<sub>10</sub>F≒Fと見做せる。

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

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

{{math|2→3→''F''<sup>5</sup>(2→3→12)}} を十進法で表したときの末尾3桁は {{math|736}} である。

=== 表現 ===
小グラハム数を表すにはいくつか等価な表現がある。
*[[クヌースの矢印表記]]
:<math>2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 } 3</math>, 
:<math>2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 11 } 4 } 3 } 3 } 3 } 3 } 3 -1} 4</math>, 
:<math>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)</math>, 
:<math>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)</math>, 
:<math>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)</math>, 
:<math>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)</math>, 
:<math>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)</math><!--, 
:<math>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 -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 -1\right)\right)</math>-->
*[[コンウェイのチェーン表記]]
:<math>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)</math>

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

== ラブロフらによる解の上限 ==
ラブロフらは[[2014年]]に、多次元[[三目並べ]]に関する{{仮リンク|ヘイルズ＝ジュエットの定理|en|Hales–Jewett theorem}}を応用し、より小さい上限として
:<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\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow4 = 2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow65536 \\
=& {}^{{}^{{}^{{}^{{}^{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>
の範囲にあることになる。

<!--== 注釈 ==
<references group="注釈"/>
-->

== 出典 ==
<references/>

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

== 外部リンク ==
*{{MathWorld|title=Graham's Number|urlname=GrahamsNumber}}

{{巨大数}}

{{DEFAULTSORT:くらはむすう}}
[[Category:整数|+くらはむすう]]
[[Category:ラムゼー理論]]
[[Category:数学に関する記事]]
[[Category:ギネス世界記録]]
[[Category:3の冪]]
[[Category:数学のエポニム]]
[[Category:巨大数]]