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

'''グラハム数''' (Graham's number) は、{{仮リンク|ラムゼー理論|en|Ramsey theory}}に関する[[数学上の未解決問題|未解決問題]]の解の推定値の上限として得られた[[自然数]]である。単なる巨大さ以外で意味のある考察の対象となったことがある最大の数<ref group="注釈">ちなみに、ある意味のある数列の比較的小さいn番目の数がグラハム数を超えるほど大きいという事例は、[[ツリー数列]]や[[サブキュービックグラフ数]]など例があるが、これは単なる巨大さの考察であるとする。</ref>として[[ギネス・ワールド・レコーズ|ギネスブック]]に認められた。

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

== グラハム問題 ==
この数は、[[1970年]]の{{仮リンク|ロナルド・グラハム|en|Ronald Graham}}とロートシルト (B. L. Rothschild) による「グラハムの定理」
{{Cquote|
''n'' 次元[[超立方体]]の 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>ことによってこの数は広く知られるようになった。

グラハムとロートシルトは1971年の小グラハム数を示したものと同じ論文中で解の下限として 6 を与えた。ガードナーは[[1989年]]に著書の中で[[ラムゼー理論]]の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、Geoff Exoo は[[2003年]]により良い下限として 11 を与えた<ref>Geoff Exoo, [http://isu.indstate.edu/ge/GEOMETRY/cubes.html "A Ramsey Problem on Hypercubes"]</ref>。

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

まず、[[クヌースの矢印表記]]を使い、''x'', ''y'' を自然数としたとき、演算子「↑」を次のように定義する。
:<math> x \uparrow y = x ^ y </math>
さらに「↑↑」を次のように帰納的に定義する。
:<math> x \uparrow\uparrow 1 = x</math>
:<math> x \uparrow\uparrow y = x \uparrow (x \uparrow\uparrow (y - 1)) </math>

つまり、
:<math>
x\uparrow\uparrow y =\ \underbrace{x\uparrow x\uparrow \cdots \uparrow x}_y = \underbrace{x_{}^{x^{{}^{.\,^{.\,^{.\,^x}}}}}}_{y} 
</math> （<math>\underbrace{}_y</math> は、''x'' が ''y'' 個あることを表す）
となる。例を挙げると次のようになる。
:<math>3\uparrow\uparrow2=3^3=27</math>
:<math>3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987</math>
:<math>3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}</math>
:<math>3\uparrow\uparrow5=3^{3^{3^{3^3}}}=3^{3^{7625597484987}}</math>

同様に「↑↑↑」を次のように定義する。
:<math> x \uparrow\uparrow\uparrow 1 = x</math>
:<math> x \uparrow\uparrow\uparrow y = x \uparrow\uparrow (x \uparrow\uparrow\uparrow (y - 1)) </math>
つまり、
:<math>
x\uparrow\uparrow\uparrow y = \underbrace{x\uparrow\uparrow x\uparrow\uparrow \cdots \uparrow\uparrow x}_y</math>
である。

このようにして、一般に「↑…(''n''個)…↑」＝「↑<sup>''n''</sup>」を定義する。
:<math> x \uparrow^n 1 = x</math>
:<math> x \uparrow^n y = x \uparrow^{n-1} (x \uparrow^n (y - 1)) </math>

=== グラハム数 ===
これを用いて、[[関数 (数学)|関数]] ''G''(''x'') を
:<math> G(x) = 3 \uparrow^x 3</math>
と定義したときの
:<math> G = G^{64} (4) = \underbrace{G(G(\cdots G}_{64} (4) \cdots ))</math>
を'''グラハム数'''と言う。

== その大きさ ==
''G''(''x'') を実際に計算してみると、

*''G''(1) = 3↑3 = 3<sup>3</sup> = 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 = <math>
\underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}_{7625597484987}</math>
*''G''(4) = 3↑↑↑↑3 = 3↑↑↑''G''(3) = <math>\underbrace{3\uparrow\uparrow 3\uparrow\uparrow \cdots \uparrow\uparrow 3}_{G(3)}</math>

*''G''<sup>2</sup>(4) = ''G''(''G''(4)) = 3↑…(''G''(4) 個)…↑3

*''G''<sup>3</sup>(4) = ''G''(''G''<sup>2</sup>(4)) = 3↑…(''G<sup>2</sup>''(4) 個)…↑3
:：
:：
*''G''<sup>64</sup>(4) = ''G''(''G''<sup>63</sup>(4)) = 3↑…(''G<sup>63</sup>''(4) 個)…↑3
''G''(2)までは十進法表記で表すことができるが、''G''(3)ですら既に3の累乗を7兆回以上繰り返した数であるため、現実の何物とも比べられないような巨大数になっており、後述するように十進法表記で表すことすら事実上不可能である。''G''(4)はその十進表記が事実上不可能な''G''(3)の数だけ↑↑（二重矢印）を繰り返した数であるため、既に想像を絶する大きさとなっている。

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

この大きさをたとえる話として、''「グラハム数を[[十進法|十進記数法]]を用いて印字しようとした場合（十分に印刷できる面積を持つ物体があるとして）、この全宇宙にある物質すべてを[[インク]]に変えても全く足りない」''というものがある。しかし、[[観測可能な宇宙]]の[[素粒子]]の総数は 10<sup>80</sup> と考えられているので、このたとえで表せる数は、粒子1個で1文字を印刷するとしてもせいぜい <math>10^{10^{80}}</math> に過ぎない。この数はグラハム数どころか ''G''(3) と比較しても圧倒的に小さく（''G''(3) の遥か手前、<math>3^{3^{3^{3^3}}}</math> が既に約 <math>10^{10^{3600000000000}}</math> である）、[[グーゴルプレックス]]にも満たない。これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。

[[コンウェイのチェーン表記]]を用いても ''G''<sup>64</sup>(4) を簡潔に表すことは出来ないが、次の不等式が成立する。
:<math>3\rightarrow 3\rightarrow 64\rightarrow 2 < G^{64}(4) < 3\rightarrow 3\rightarrow 65\rightarrow 2</math>

== 小グラハム数 ==
グラハムとロートシルトは[[1971年]]に、より小さい上限として'''小グラハム数'''(Little Graham)を示した。この数は関数 ''F''(''x'') を
:<math> F(x) = 2 \uparrow^x 3</math>
と定義したときの
:<math> F = F^{7} (12) = F(F(F(F(F(F(F(12)))))))</math>
である。これはグラハム数よりは遥かに小さいが、それでもなお非常に大きい数である。

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

== 出典 ==
<references/>

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

{{DEFAULTSORT:くらはむすう}}
[[Category:整数|+くらはむすう]]
[[Category:数学に関する記事]]
[[Category:ギネス世界記録]]

[[pl:Notacja strzałkowa#Liczba Grahama]]