グラハム数

グラハム数 (Graham's number) は、テンプレート:仮リンクに関する未解決問題の解の推定値の上限として得られた自然数である。単なる巨大さ以外で意味のある考察の対象となったことがある最大の数としてギネスブックに認められた。

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

グラハム問題

この数は、1970年のテンプレート:仮リンクとロートシルト (B. L. Rothschild) による「グラハムの定理」 テンプレート:Cquote に関係する。つまり、n が十分大きければというが、 テンプレート:Cquote ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。

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

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

グラハムとロートシルトは1971年の小グラハム数を示したものと同じ論文中で解の下限として 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、Geoff Exoo は2003年により良い下限として 11 を与えた。

定義

矢印表記

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

まず、クヌースの矢印表記を使い、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個)…↑」＝「↑ⁿ」を定義する。

<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³ = 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²(4) = G(G(4)) = 3↑…(G(4) 個)…↑3

• G³(4) = G(G²(4)) = 3↑…(G²(4) 個)…↑3

：

：

• G⁶⁴(4) = G(G⁶³(4)) = 3↑…(G⁶³(4) 個)…↑3

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

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

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

コンウェイのチェーン表記を用いても G⁶⁴(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>

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

外部リンク

• テンプレート:MathWorldpl:Notacja strzałkowa#Liczba Grahama