グラハム数

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

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

1. グラハム問題
---------

この数は1970年のロナルド・グラハム、ブルース・リー・ロスチャイルドによる「グラハムの定理」 に関係する。つまり、//n// が十分大きければというが、 ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。しかし、この関係がグラハム数以上の //n// について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。

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

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

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

2. 定義
-----

2.1. 矢印表記
---------

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

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

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

つまり、

となる。ただし、演算は右から行う。つまり例えば、//x//↑//x//↑//x// = //x//↑ である。例を挙げると次のようになる。

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

つまり、

である。

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

2.2. グラハム数
----------

これを用いて、関数 //G// を

と定義したときの

をグラハム数といい、その計算法は3の冪乗やテトレーションからの発展を基本としている。

3. その値の大きさ
----------

{ date = 2022年6月}//G// を実際に計算してみると、

//G// = 3↑3 = 3→3→1 = 3→3 = 33 = 27
//G// = 3↑↑3 = 3→3→2 = 3↑ = 3↑//G// = 3↑27 = 7625597484987
//G// = 3↑↑↑3 = 3→3→3 = 3↑↑↑3 = 3↑↑ = 3↑↑//G// = 3↑↑7625597484987
//G// = 3↑↑↑↑3 = 3→3→4 =3↑↑↑↑3 = 3↑↑↑//G//
//G//2 = //G//) = 3↑… 本)…↑3 = 3→3→//G// = 3↑{//G//-1}}3↑{//G//-2}}…↑{3}}3↑{2}}3↑3↑3
//G//3 = //G//) = 3↑… 本)…↑3 = 3→3→//G//2：：
//G//64 //G//) 3↑… 本)…↑3 3→3→//G//63 = hyper+2, 3) = 3↑…+1) 本)…↑2 = 3→2→+1) = hyper+3, 2) = hyper)+2, 3) = hyper+2, 3) = 3↑{//G//sup}3↑{//G//sup}…↑{3}}3↑{2}}3↑3↑3//G// までは関数電卓やパソコンでも普通に計算できるが、//G// ですら既に3の累乗を7兆6,255億回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、{16[[超階乗}の方が遥かに大きい。//G// はその十進以下の表記が現実的に不可能な //G// − 1 の数だけ ↑↑を繰り返した数であるため、想像を絶する大きさとなっている。

次の段階の //G//2 は3と3の間に //G// 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 も超える。この操作を63回繰り返した数がグラハム数である。

この大きさをたとえる話として、//「グラハム数を十進記数法を用いて印字しようとした場合、この全宇宙にある物質すべてをインクに変えても全く足りない」//というものがある。しかし、その例えを使ったとしてもGにすら満たない。

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

これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。宇宙論で使われた最大の数をaとすると、aですらであり、これもグラハム数はおろか//G// ともとても比較にならない。

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

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

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

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

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

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

4. 表現
-----

{ date = 2022年6月} グラハム数を表すにはいくつか等価な表現がある。

クヌースの矢印表記,,,,,,,,,,,, 
コンウェイのチェーン表記
ハイパー演算表記

5. 小グラハム数
---------

{ date = 2022年6月} グラハムとロートシルトは1971年に、より小さい上限として小グラハム数  を示した。この数は関数 //F// を

と定義したときの

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

5.1. その大きさ
----------

//F// を実際に計算してみると、

//F// = 2↑3 = 2→3→1 = 2→3 = 23 = 8
//F// = 2↑↑3 = 2→3→2 = 2↑ = 2↑4 = 16
//F// = 2↑↑↑3 = 2→3→3 = 2↑↑ = 2↑↑4 = 2 = 2↑//F// = 65536
//F// = 2↑↑↑↑3 = 2→3→4 = 2↑↑↑ = 2↑↑↑4 = 2↑↑2↑↑2↑↑2 = 2↑↑//F// = 2↑↑65536
//F// = 2↑↑↑↑↑3 = 2→3→5 = 2↑↑↑↑2↑↑↑↑2 = 2↑↑↑↑4 = 2↑↑↑2↑↑↑2↑↑↑2 = 2↑↑↑//F//：：
//F// = 2↑3 = 2→3→12 = 2↑2↑2 = 2↑4 = 2↑2↑2↑2 = 2↑//F//
//F//2 = //F//) = 2↑… 本)…↑3 = 2→3→//F//
//F//3 = 2↑… 本)…↑3 = 2→3→//F//：：
//F//7 = 2↑… 本)…↑3 = 2→3→//F////F// までは関数電卓やパソコンでも普通に計算できるが、//F// ですら既に2の累乗を6万回以上繰り返した数であるため、現実世界の現象で例えることなど到底不可能な巨大数になっており、後述するように十進法以下の表記で表すことすら現実的には不可能であるが、よりは遥かに小さい。//F// はその十進以下の表記が現実的に不可能な //F// − 1 の数だけ↑↑を繰り返した数であるため、想像を絶する大きさとなっており、ましてやそれと同様の操作を繰り返した//F//はなおさらである。

次の段階の //F//2 は2と3の間に //F// 本矢印を置いたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数 も超える。この操作を6回繰り返した数がリトル・グラハム数である。

この大きさをたとえる話として、//「リトル・グラハム数を十進記数法を用いて印字しようとした場合、この全宇宙にある物質すべてをインクに変えても全く足りない」//というものがある。しかし、その例えを使ったとしてもFにすら満たず、Fの時点で、グラハム数の大きさを例えるのに使用した、Unicodeや宇宙論を用いた例えがそのまま適用され、log10F≒Fと見做せる。

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

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

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

5.2. 表現
-------

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

クヌースの矢印表記,,,,,,
コンウェイのチェーン表記これはどちらも を根拠としている。

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

ラブロフらは2014年に、多次元三目並べに関するを応用し、より小さい上限として

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

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

7. 出典
-----

8. 関連項目
-------

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

9. 外部リンク
--------