グラハム数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

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

グラハム問題[編集]

この数は、1970年ロナルド・グラハム英語版ブルース・リー・ロスチャイルド英語版による「グラハムの定理」

n 次元超立方体の 2n 個の頂点のそれぞれを互いに全て線で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。
このとき n が十分大きければ、どんな塗り方をしても、同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在する。

に関係する。つまり、n が十分大きければというが、

n がいくらより大きければ、この関係は常に成立するか

ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。

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

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

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

定義[編集]

矢印表記[編集]

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

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

 x \uparrow y = x ^ y

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

 x \uparrow\uparrow 1 = x
 x \uparrow\uparrow y = x \uparrow \left\{x \uparrow\uparrow \left(y - 1\right)\right\}

つまり、


x\uparrow\uparrow y =\ \underbrace{x\uparrow x\uparrow \cdots \uparrow x}_y = \underbrace{x^{x^{\cdot^{\cdot^{\cdot^x}}}}}_{y}

となる(\underbrace{}_y は、xy 個あることを表す)。ただし演算は右から行う。つまり例えば、xxx = x↑(xx) である。例を挙げると次のようになる。

\begin{align}
3\uparrow\uparrow2=&3^3=27 \\
3\uparrow\uparrow3=&3^{3^3}=3^{27}=7625597484987 \\
3\uparrow\uparrow4=&3^{3^{3^3}}=3^{7625597484987}\\
\approx &1.258\times 10^{3638334640024} \\
3 \uparrow\uparrow 5=&3^{3^{3^{3^3}}}=3^{3^{7625597484987}}\\
\approx &3^{1.258\times 10^{3638334640024}}\end{align}

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

 x \uparrow\uparrow\uparrow 1 = x
 x \uparrow\uparrow\uparrow y = x \uparrow\uparrow \left\{x \uparrow\uparrow\uparrow (y - 1)\right\}

つまり、


x\uparrow\uparrow\uparrow y = \underbrace{x\uparrow\uparrow x\uparrow\uparrow \cdots \uparrow\uparrow x}_{y\text{ copies of }x}

である。

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

 x \uparrow^n 1 = x
 x \uparrow^n y = x \uparrow^{n-1} \left\{x \uparrow^n \left(y - 1 \right)\right\}

グラハム数[編集]

これを用いて、関数 G(n) を

 G(n) = 3 \uparrow^n 3

と定義したときの

\begin{align}
G &= G^{64} (4) = \underbrace{G(G(\cdots G}_{64} (4) \cdots ))\\
&= \left.
\begin{matrix}
3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \cdots \cdots \uparrow}3 \\
3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\
\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
3\underbrace{\uparrow \uparrow \cdots\cdots \uparrow}3 \\
3\uparrow \uparrow \uparrow \uparrow3
\end{matrix}
\right \} 64 \text{ stages}
\end{align}

グラハム数と言う。

その大きさ[編集]

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↑↑G(2) = 3↑↑7625597484987
= \underbrace{3^{3^{3^{ \cdot ^{ \cdot^ { \cdot^ { \cdot^ { \cdot^ { \cdot^ {\cdot^ { \cdot^ { \cdot^ { \cdot^ { 3^{ 3^ 3}}}}}}}}}}}}}}}_{7625597484987}
  • G(4) = 3↑↑↑↑3 = 3→3→4 = 3↑↑↑G(3)
=\underbrace{3\uparrow\uparrow 3\uparrow\uparrow \cdots \uparrow\uparrow 3 \uparrow\uparrow 3 }_{G(3) \text{ copies of }3 }
  • G2(4) = G(G(4)) = 3↑…(G(4) 本)…↑3 = 3→3→G(4)
  • 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)

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

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

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

コンウェイのチェーン表記を用いても G = G64(4) を簡潔に表すことは出来ないが、次の不等式が成立する。

3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2

ちなみに、グラハム数を十進法で表したときの下3桁は387である。

小グラハム数[編集]

グラハムとロートシルトは1971年に、より小さい上限として小グラハム数 (Little Graham) を示した。この数は関数 F(n) を

F(n) = 2 \uparrow^{n} 3 =2\underbrace{\uparrow \cdots \uparrow}_{n}3 = 2 \rightarrow 3 \rightarrow n

と定義したときの

\begin{align}
F &:= F^{7} (12) = F \left(F \left(F \left (F \left (F \left (F \left(F(12) \right) \right ) \right) \right ) \right ) \right)\\
  &= \left. \begin{matrix}
2\underbrace{\uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\
2\underbrace{\uparrow \cdots \cdots \cdots \uparrow}3 \\
\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
2\underbrace{\uparrow \cdots \cdots \cdots \uparrow}3 \\
2\uparrow^{12}3 \end{matrix}
\right \}7\text{ stages}
= 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 12 } 3 } 3 } 3 } 3 } 3 } 3 } 3
= 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow^{ 2 \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow \uparrow\uparrow\uparrow 3 } 3 } 3 } 3 } 3 } 3 } 3 \end{align}

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


出典[編集]

  1. ^ Guiness Book of World Record, 1980 Page 193, line 27-31 http://math.ucsd.edu/~fan/ron/images/record.jpg
  2. ^ R. L. Graham and B. L. Rothschild, "Ramsey's theorem for n-parameter sets"
  3. ^ Martin Gardner, "Mathematical Games"
  4. ^ Geoff Exoo, "A Ramsey Problem on Hypercubes"

外部リンク[編集]