グラハム数 グラハム数の概要

グラハム数

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/04/23 07:31 UTC 版)

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

グラハム問題

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

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

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

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

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

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

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

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

定義

矢印表記

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

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

 x \uparrow y = x ^ y

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

 x \uparrow\uparrow 1 = x
 x \uparrow\uparrow y = x \uparrow (x \uparrow\uparrow (y - 1))

つまり、


x\uparrow\uparrow y =\ \underbrace{x\uparrow x\uparrow \cdots \uparrow x}_y = \underbrace{x^{x^{\cdot^{\cdot^{\cdot^x}}}}}_{y} 
\underbrace{}_y は、xy 個あることを表す)

となる。例を挙げると次のようになる。

3\uparrow\uparrow2=3^3=27
3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987
\begin{align}
3\uparrow\uparrow4&=3^{3^{3^3}}=3^{7625597484987}\\
&\approx 1.258\times 10^{3638334640024}
\end{align}
\begin{align}
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 (x \uparrow\uparrow\uparrow (y - 1))

つまり、


x\uparrow\uparrow\uparrow y = \underbrace{x\uparrow\uparrow x\uparrow\uparrow \cdots \uparrow\uparrow x}_y

である。

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

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

グラハム数

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

 G(x) = 3 \uparrow^x 3=3 \underbrace{\uparrow\cdots\uparrow}_{x} 3

と定義したときの

 G = G^{64} (4) = \underbrace{G(G(\cdots G(G(}_{64}4\underbrace{))\cdots))}_{64}= \left.
 \begin{matrix}
  3\underbrace{\uparrow \uparrow \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\cdot\cdot \uparrow}3 \\
  3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix}
\right \} 64

グラハム数と言う。

その大きさ

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
=\underbrace{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}_{7625597484987}
  • G(4) = 3↑↑↑↑3 = 3↑↑↑G(3)
=\underbrace{3\uparrow\uparrow 3\uparrow\uparrow \cdots \uparrow\uparrow 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文字を印刷するとしてもせいぜい 101080 に過ぎない。この数はグラハム数どころか G(3) と比較しても圧倒的に小さく(G(3) の遥か手前、3^{3^{3^{3^3}}} が既に約 10^{6.0 \times 10^{3638334640023}} \approx 10^{10^{3638334640024}} である)、グーゴルプレックスにも満たない。これほど極端な例えですら言い表すことができないほど巨大な数がグラハム数である。

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

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

小グラハム数

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

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

と定義したときの

 F = F^{7} (12) = F(F(F(F(F(F(F(12)))))))= \left. 
\begin{matrix}
2\underbrace{\uparrow\cdots\uparrow}_{2\underbrace{{}_{\uparrow\cdots\uparrow}}_{\underbrace{\vdots}_{{}_2 \underbrace{{}_{{}_{\uparrow\cdots\uparrow}}}_{12} {}_3}}3}3
\end{matrix}
\right \}8 = \left. 
\begin{matrix}
2\underbrace{\uparrow\cdots\uparrow}_{2\underbrace{{}_{\uparrow\cdots\uparrow}}_{\underbrace{\vdots}_{{}_2 \underbrace{{}_{{}_{\uparrow\cdots\uparrow}}}_{11} {}_4}}3}3
\end{matrix}
\right \}8

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


  1. ^ ちなみに、ある意味のある数列の比較的小さい n 番目の数がグラハム数を超えるほど大きいという事例は、ツリー数列やサブキュービックグラフ数など例があるが、これは単なる巨大さの考察であるとする。
  1. ^ R. L. Graham and B. L. Rothschild, "Ramsey's theorem for n-parameter sets"
  2. ^ Martin Gardner, "Mathematical Games"
  3. ^ Geoff Exoo, "A Ramsey Problem on Hypercubes"


「グラハム数」の続きの解説一覧




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「グラハム数」の関連用語

グラハム数のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す

2000系

John F. Kennedy

カンナツノザヤウミウシ

ヴァンガード

スパッタリング

W61S

口永良部島

ヒプシロフォドン・フォクシイ





グラハム数のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのグラハム数 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2015 Weblio RSS