グラハム数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/05/02 05:32 UTC 版)
極めて巨大な巨大数であり指数で表記するのは事実上不可能なため特別な表記法を用いて表される。
グラハム問題
この数は、1970年のロナルド・グラハムとロートシルト (B. L. Rothschild) による「グラハムの定理」
| “ |
n 次元超立方体の 2n 個の頂点のそれぞれを互いに全て線で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。 |
” |
に関係する。つまり、n が十分大きければというが、
| “ |
n がいくらより大きければ、この関係は常に成立するか |
” |
ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。
しかし、この関係がグラハム数以上の n について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。
ただしグラハムらは実際にはこの数を論文では発表しておらず、翌1971年にグラハム数より小さなグラハム問題の解の上限として、小グラハム数という数を発表した[1]。その後、マーティン・ガードナーが1977年にサイエンティフィック・アメリカンでグラハム数を紹介した[2]ことによってこの数は広く知られるようになった。
グラハムとロートシルトは1971年の小グラハム数を示したものと同じ論文中で解の下限として 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、Geoff Exoo は2003年により良い下限として 11 を与えた[3]。
定義
矢印表記
グラハム数は巨大すぎて、通常の指数では事実上表現不可能である。そのため次のような特殊な関数を用いる。
まず、クヌースの矢印表記を使い、x, y を自然数としたとき、演算子「↑」を次のように定義する。
さらに「↑↑」を次のように帰納的に定義する。
つまり、
（
は、x が y 個あることを表す）
となる。例を挙げると次のようになる。
同様に「↑↑↑」を次のように定義する。
つまり、
である。
このようにして、一般に「↑…(n個)…↑」＝「↑n」を定義する。
グラハム数
これを用いて、関数 G(x) を
と定義したときの
をグラハム数と言う。
その大きさ
G(x) を実際に計算してみると、
- G(1) = 3↑3 = 33 = 27
- G(2) = 3↑↑3 = 3↑(3↑3) = 3↑G(1) = 3↑27 = 7625597484987
- G(3) = 3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑G(2) = 3↑↑7625597484987 =
- G(4) = 3↑↑↑↑3 = 3↑↑↑G(3) =
- G2(4) = G(G(4)) = 3↑…(G(4) 個)…↑3
- G3(4) = G(G2(4)) = 3↑…(G2(4) 個)…↑3
- ：
- ：
- G64(4) = G(G63(4)) = 3↑…(G63(4) 個)…↑3
G(2)までは十進法表記で表すことができるが、G(3)ですら既に3の累乗を7兆回以上繰り返した数であるため、現実の何物とも比べられないような巨大数になっており、後述するように十進法表記で表すことすら事実上不可能である。G(4)はその十進表記が事実上不可能なG(3)の数だけ↑↑（二重矢印）を繰り返した数であるため、既に想像を絶する大きさとなっている。
次の段階の G2(4)は3と3の間はG(4)個矢印をおいたものであり、この時点で指数のみの表記も括弧を駆使しても事実上不可能となり、モーザー数も超える。この操作を63回繰り返した数がグラハム数である。
この大きさをたとえる話として、「グラハム数を十進記数法を用いて印字しようとした場合（十分に印刷できる面積を持つ物体があるとして）、この全宇宙にある物質すべてをインクに変えても全く足りない」というものがある。しかし、観測可能な宇宙の素粒子の総数は 1080 と考えられているので、このたとえで表せる数は、粒子1個で1文字を印刷するとしてもせいぜい 
に過ぎない。この数はグラハム数どころか G(3) と比較しても圧倒的に小さく（G(3) の遥か手前、
が既に約 
である）、グーゴルプレックスにも満たない。これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。
コンウェイのチェーン表記を用いても G64(4) を簡潔に表すことは出来ないが、次の不等式が成立する。
小グラハム数
グラハムとロートシルトは1971年に、より小さい上限として小グラハム数(Little Graham)を示した。この数は関数 F(x) を
と定義したときの
である。これはグラハム数よりは遥かに小さいが、それでもなお非常に大きい数である。
- ^ ちなみに、ある意味のある数列の比較的小さいn番目の数がグラハム数を超えるほど大きいという事例は、ツリー数列やサブキュービックグラフ数など例があるが、これは単なる巨大さの考察であるとする。
- ^ R. L. Graham and B. L. Rothschild, "Ramsey's theorem for n-parameter sets"
- ^ Martin Gardner, "Mathematical Games"
- ^ Geoff Exoo, "A Ramsey Problem on Hypercubes"
グラハム数に関連した本
- 異次元の刻印(上)-人類史の裂け目あるいは宗教の起源 グラハム・ハンコック バジリコ
- 異次元の刻印(下)-人類史の裂け目あるいは宗教の起源 グラハム・ハンコック バジリコ
- できるリーダーのための奇跡のコーチング グラハム アレクサンダー PHP研究所
- グラハム数のページへのリンク
