グラハム数（グラハムすう、）は、極めて巨大であることで知られる自然数（巨大数）の一つ。ラムゼー理論に関する未解決問題の解の上限として与えられた。数学の証明で使われたことのある最大の数として1980年にギネスブックに認められたGuiness Book of World Record, 1980 Page 193, line 27-31 http://math.ucsd.edu/~fan/ron/images/record.jpg。
グラハム問題
この数は1970年のロナルド・グラハム、ブルース・リー・ロスチャイルドによる「グラハムの定理」（以下に記載）に関連している。
つまり、n が十分大きければというが、
ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。
しかし、この関係がグラハム数以上の n について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。
ただし、グラハムらは実際にはこの数を論文では発表しておらず、翌1971年にグラハム数より小さなグラハム問題の解の上限として、小グラハム数という数を発表したR. L. Graham and B. L. Rothschild, "Ramsey's theorem for n-parameter sets"。その後、マーティン・ガードナーが1977年にサイエンティフィック・アメリカンでグラハム数を紹介したMartin Gardner, "Mathematical Games"ことによってこの数は広く知られるようになった。
解の上限はのち2014年にミハイル・ラブロフらによってさらに小さい数が示された。
一方、この問題の解の下限（つまりこの数より小さい数では成り立たないことを示した数）としては、グラハムとロスチャイルドは1971年の小グラハム数を示したものと同じ論文中で 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、2003年にジェフ・エクスーがより良い下限として 11 をGeoff Exoo, "A Ramsey Problem on Hypercubes"、2008年にはジェローム・バークレーが 13 を与えた。
定義 矢印表記 グラハム数は巨大すぎて、通常の指数では桁数の表現すら事実上不可能である。そのため、次のような特殊な関数を用いる。
まず、クヌースの矢印表記を使い、x, y を自然数としたとき、演算子「↑」を次のように定義する。
さらに「↑↑」を次のように再帰的に定義する。
つまり、
となる（ は、x が y 個あることを表す）。ただし、演算は右から行う。つまり例えば、x↑x↑x = x↑(x↑x) である。例を挙げると次のようになる。
同様に「↑↑↑」を次のように再帰的に定義する。
つまり、
である。
一般の場合も同様に、「↑…(n 本)…↑」＝「↑n」を次のように定義する。
グラハム数 これを用いて、関数 G(n) を
と定義したときの
をグラハム数といい、その計算法は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（トリトリ）
G(4) = 3↑↑↑↑3 = 3→3→4 =3↑↑↑↑3 = 3↑↑↑G(3)（グラハル）
G2(4) = G(G(4)) = 3↑…(G(4) 本)…↑3 = 3→3→G(4) = 3↑3↑…↑3↑3↑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, G(G(4))+2, 3) = hyper(3, G(3→2→5)+2, 3) = 3↑3↑…↑3↑3↑3↑3 G(2) までは関数電卓やパソコンでも普通に計算できるが、G(3) ですら既に3の累乗を7兆6,255億回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、の方が遥かに大きい（しかし3↑↑↑4よりは遥かに小さい）。G(4) G(4)にはグラハルという名前がついている。はその十進以下の表記が現実的に不可能な G(3) − 1 の数だけ ↑↑（二重矢印）を繰り返した数であるため、想像を絶する大きさとなっている。
次の段階の G2(4) は3と3の間に G(4) 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 も超える。この操作を63回繰り返した数がグラハム数である。
この大きさをたとえる話として、「グラハム数を十進記数法を用いて印字しようとした場合（十分に印刷できる面積を持つ物体があるとして）、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。しかし、その例えを使ったとしてもG(3)にすら満たない。
観測可能な宇宙の素粒子の総数は 1080 と考えられているので、このたとえで表せる数は、素粒子1個で1文字を印刷するとしても n 進表記ならせいぜい n1080 に過ぎない。この数は1 < | n | ≤ 16 のときグラハム数やどころか G(3) と比較しても圧倒的に小さい（G(3) の遥か手前、 が既におよそ である）。16進表記ではアルファベットの大文字と小文字を区別しないが、Unicodeでは区別されている。現在Unicodeで使用されている文字の総数は13万7468個であり、未使用領域が全て埋め尽くされると n = 1114112となるが、 n が1億まで拡張されたとしても108×1080 であり、グーゴルプレックス にも満たない。
これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。宇宙論で使われた最大の数（複数の宇宙の全質量を1個のブラックホールに圧縮しそれが蒸発した後に、ポアンカレの回帰定理に従い再びブラックホールができる時間）をtとすると、tですら桁数が非常に大きいため、時間の単位をプランク時間・秒・年のいずれにしても無視できる範囲で近似する。であり、これもグラハム数はおろかG(3) ともとても比較にならない。
レオナルド・サスキンドは宇宙の直径をと推定しているが、この値をlとすると、lもtと同様に桁数が大きすぎて単位が考慮されていない。しかし、1辺がbクエタパーセクの立方体に1辺が1プランク長の立方体が隙間なく詰め込まれ、それらの立方体がa千年紀に渡って1プランク時間ごとに1種類の文字を生成し、作業完了時点で完全に重複する文字が1種類も存在しない場合ですら、生成された文字をc種類とし、c進法でc-1を表現する文字をc個並べた数をdとした場合、dはグラハム数はおろかG(3) ともとても比較にならない。
なお、強いて「グラハム数を十進法で表した時の桁数」を考えるなら、log10Gとなるが、Gは十分な巨大数なので、この場合にあってはlog10という関数で厳密には元の数より小さくなるものの、巨大数としては無視できるレベルでしかなく、近似に吸収されてしまう。すなわち、log10G≒Gである。
近年は巨大数の研究・開発がより進み、現在ではグラハム数を遥かに上回る数も多数登場していて、例えばコンウェイのチェーン表記を用いて""（コンウェイのテトラトリと呼ばれる数）などと書くだけでグラハム数よりも大きな数を表現可能である。
チェーン表記を用いても G = を簡潔に表すことはできないが、次の不等式が成立する。
先述の通り、グラハム数自体は桁数を指数で表現することすら不可能なほど大きく、スーパーコンピュータでもG(3)の計算すら望めないが、末尾の数字を計算する方法は確立しており、ある程度の桁数は判明している。
を十進法で表したときの末尾10桁は であり、暗黒通信団が末尾100万桁を記した書籍も出版し、その後、暗黒通信団のウェブサイトで末尾1,600万桁を記したPDF形式のファイルも公開しているグラハム数の末尾1600万桁表（オンライン版）【PDF】。
表現
グラハム数を表すにはいくつか等価な表現がある。 クヌースの矢印表記 , , , , , , , , , , , , (はCG関数, )
コンウェイのチェーン表記
ハイパー演算表記
小グラハム数
グラハムとロートシルトは1971年に、より小さい上限として小グラハム数 (Little Graham) を示した。この数は関数 F(n) を
と定義したときの
である。これはグラハム数よりは遥かに小さいが、それでもなお非常に大きい数である。
その大きさ 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 = 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
F(5) = 2↑↑↑↑↑3 = 2→3→5 = 2↑↑↑↑2↑↑↑↑2 = 2↑↑↑↑4 = 2↑↑↑2↑↑↑2↑↑↑2 = 2↑↑↑F(4)
： ： F(12) = 2↑3 = 2→3→12 = 2↑2↑2 = 2↑4 = 2↑2↑2↑2 = 2↑F(11)
F2(12) = F(F(12)) = 2↑…(F(12) 本)…↑3 = 2→3→F(12)
F3(12) = 2↑…(F(12) 本)…↑3 = 2→3→F(12) ： ： F7(12) = 2↑…(F(12) 本)…↑3 = 2→3→F(12)
F(3) までは関数電卓やパソコンでも普通に計算できるが、F(4) ですら十進法以下の表記で表すことすら現実的には不可能である（ただしよりは遥かに小さい）。同様の操作を繰り返したF(12)も同様に巨大数である。
次の段階の F2(12) は2と3の間に F(12) 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 ()も超える。この操作を6回繰り返した数が小グラハム数である。
グラハム数の大きさの議論と同様に、log10F≒Fと見做せる。
チェーン表記を用いても F = F7(12) を簡潔に表すことはできないが、次の不等式が成立する。
小グラハム数もグラハム数と同様に末尾の数字を計算する方法は確立しており、ある程度の桁数は判明している。
を十進法で表したときの末尾3桁は である。
表現 小グラハム数を表すにはいくつか等価な表現がある。 クヌースの矢印表記 , , , , , ,
コンウェイのチェーン表記
これはどちらも を根拠としている。
ラブロフらによる解の上限 ラブロフらは2014年に、多次元三目並べに関するを応用し、より小さい上限として
を示した。これでもなお十進表記が事実上不可能なほど非常に大きい数であるが、グラハム数および小グラハム数と比較すると格段に小さい数である。これによりグラハム問題の解 n は
の範囲にあることになる。
出典
関連項目 グラハム数を超える巨大数の一覧
外部リンク