グラハム数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/07/05 04:29 UTC 版)
|
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2023年10月)
|
グラハム数（グラハムすう、英: Graham's number）は、ラムゼー理論に関する未解決問題の解の推定値の上限として得られた自然数である。数学の証明で使われたことのある最大の数として1980年にギネスブックに認められた[1]。
極めて巨大な自然数（巨大数）であり、指数表記を用いるのは事実上不可能なため、特別な表記法を用いて表される。
グラハム問題
この数は1970年のロナルド・グラハム、ブルース・リー・ロスチャイルドによる「グラハムの定理」
| 「 | n 次元超立方体の 2n 個の頂点のそれぞれを互いに全て線で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。 |
」 |
に関係する。つまり、n が十分大きければというが、
| 「 | n がいくらより大きければ、この関係は常に成立するか |
」 |
ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。
しかし、この関係がグラハム数以上の n について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。
ただし、グラハムらは実際にはこの数を論文では発表しておらず、翌1971年にグラハム数より小さなグラハム問題の解の上限として、小グラハム数という数を発表した[2]。その後、マーティン・ガードナーが1977年にサイエンティフィック・アメリカンでグラハム数を紹介した[3]ことによってこの数は広く知られるようになった。
解の上限はのち2014年にミハイル・ラブロフらによってさらに小さい数が示された[4]。
一方、この問題の解の下限（つまりこの数より小さい数では成り立たないことを示した数）としては、グラハムとロスチャイルドは1971年の小グラハム数を示したものと同じ論文中で 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、2003年にジェフ・エクスーがより良い下限として 11 を[5]、2008年にはジェローム・バークレーが 13 を与えた[6]。
定義
矢印表記
グラハム数は巨大すぎて、通常の指数では桁数の表現すら事実上不可能である。そのため、次のような特殊な関数を用いる。
まず、クヌースの矢印表記を使い、x, y を自然数としたとき、演算子「↑」を次のように定義する。
-
この節は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2022年6月)
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↑↑3) = 3↑↑G(2) = 3↑↑7625597484987（トリトリ）
グラハム数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/17 16:24 UTC 版)
「コンウェイのチェーン表記」の記事における「グラハム数」の解説
グラハム数 G {\displaystyle G} それ自体を、コンウェイのチェーン表記を用いて簡潔に表す事は出来ない。しかし、仲介させる関数を g ( n ) = 3 → 3 → n = 3 ↑↑ ⋯ ↑ ⏟ 3 n 本 の 矢 印 {\displaystyle g(n)=3\rightarrow 3\rightarrow n={\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \uparrow } 3\\{\text{n 本 の 矢 印}}\end{matrix}}} と定義することで G = g 64 ( 4 ) {\displaystyle G=g^{64}(4)} と表記できる。(写像の冪を参照。)又、 3 → 3 → 64 → 2 < G < 3 → 3 → 65 → 2 {\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2} である。 証明: 定義の"反復合成を用いた規則"を適用させると、次の様になる。: g 64 ( 1 ) {\displaystyle g^{64}(1)} = 3 → 3 → ( 3 → 3 → ( ⋯ ( 3 → 3 → ( 3 → 3 → 1 ) ) ⋯ ) ) {\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))} (64組の " 3 → 3 {\displaystyle 3\rightarrow 3} ") = 3 → 3 → ( 3 → 3 → ( ⋯ ( 3 → 3 → ( 3 → 3 ) → 1 ) ⋯ ) → 1 ) → 1 {\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1)\cdots )\rightarrow 1)\rightarrow 1} = 3 → 3 → 64 → 2 ; {\displaystyle =3\rightarrow 3\rightarrow 64\rightarrow 2;} = 3 ↑↑ ⋯ ⋯ ⋯ ⋅ ↑ ⏟ 3 3 ↑↑ ⋯ ⋯ ⋯ ↑ ⏟ 3 本 ⋮ ⏟ 3 ↑↑ ⋯ ⋅ ↑ ⏟ 3 本 3 ↑ 3 本 } 64層 {\displaystyle \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3{\text{本}}\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3{\text{本}}\\&3\uparrow 3{\text{本}}\end{matrix}}\right\}{\text{64層 }}} g 64 ( 4 ) = G ; {\displaystyle g^{64}(4)=G;} = 3 → 3 → ( 3 → 3 → ( ⋯ ( 3 → 3 → ( 3 → 3 → 4 ) ) ⋯ ) ) {\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))} (64組の " 3 → 3 {\displaystyle 3\rightarrow 3} ") = 3 ↑↑ ⋯ ⋯ ⋯ ⋅ ↑ ⏟ 3 3 ↑↑ ⋯ ⋯ ⋯ ↑ ⏟ 3 本 ⋮ ⏟ 3 ↑↑ ⋯ ⋅ ↑ ⏟ 3 本 3 ↑↑↑↑ 3 本 } 64層 {\displaystyle \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3{\text{本}}\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3{\text{本}}\\&3\uparrow \uparrow \uparrow \uparrow 3{\text{本}}\end{matrix}}\right\}{\text{64層 }}} g 64 ( 27 ) {\displaystyle g^{64}(27)} = 3 → 3 → ( 3 → 3 → ( ⋯ ( 3 → 3 → ( 3 → 3 → 27 ) ) ⋯ ) ) {\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))} (64組の " 3 → 3 {\displaystyle 3\rightarrow 3} ") = 3 → 3 → ( 3 → 3 → ( ⋯ ( 3 → 3 → ( 3 → 3 → ( 3 → 3 ) ) ) ⋯ ) ) {\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\cdots ))} (65組の " 3 → 3 {\displaystyle 3\rightarrow 3} ") = 3 → 3 → 65 → 2 {\displaystyle =3\rightarrow 3\rightarrow 65\rightarrow 2} (上記のように計算する) = g 65 ( 1 ) {\displaystyle =g^{65}(1)} = 3 ↑↑ ⋯ ⋯ ⋯ ⋅ ↑ ⏟ 3 3 ↑↑ ⋯ ⋯ ⋯ ↑ ⏟ 3 本 ⋮ ⏟ 3 ↑↑ ⋯ ⋅ ↑ ⏟ 3 本 3 ↑ 3 本 } 65層 {\displaystyle \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3\\&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3{\text{本}}\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } 3{\text{本}}\\&3\uparrow 3{\text{本}}\end{matrix}}\right\}{\text{65層 }}} g は単調増加なので、 g 64 ( 1 ) < g 64 ( 4 ) < g 64 ( 27 ) {\displaystyle g^{64}(1)<g^{64}(4)<g^{64}(27)} コンウェイのチェーン表記を用いれば上記の数よりも非常に大きい数を表記する事は、とても容易い。次にその例を記す。 3 → 3 → 3 → 3 {\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3} = 3 → 3 → ( 3 → 3 → 27 → 2 ) → 2 {\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2\,} = g 3 → 3 → 27 → 2 ( 1 ) {\displaystyle =g^{3\rightarrow 3\rightarrow 27\rightarrow 2}(1)} = g g 27 ( 1 ) ( 1 ) {\displaystyle =g^{g^{27}(1)}(1)} = 3 ↑↑↑ ⋯ ⋯ ⋯ ⋅ ⋅ ↑↑↑ ⏟ 3 3 ↑↑↑ ⋯ ⋯ ⋯ ⋅ ↑↑↑ ⏟ 3 本 3 ↑↑↑ ⋯ ⋯ ⋯ ↑↑↑ ⏟ 3 本 ⋮ ⏟ 3 ↑↑↑ ⋯ ⋅ ↑↑↑ ⏟ 3 ↑ 3 本 3 本 } 3 ↑↑ ⋯ ⋯ ⋯ ⋅ ↑ ⏟ 3 層 3 ↑↑ ⋯ ⋯ ⋯ ↑ ⏟ 3 本 ⋮ ⏟ 3 ↑↑ ⋯ ⋅ ↑ ⏟ 3 ↑ 3 本 3 本 } 3 ↑ 3 = 27 層 {\displaystyle \left.{\begin{matrix}=&3\underbrace {\uparrow \uparrow \uparrow \cdots \cdots \cdots \cdot \cdot \uparrow \uparrow \uparrow } _{}3\\&3\underbrace {\uparrow \uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow \uparrow \uparrow } _{}3{\text{本}}\\&3\underbrace {\uparrow \uparrow \uparrow \cdots \cdots \cdots \uparrow \uparrow \uparrow } _{}3{\text{本}}\\&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \uparrow \uparrow \cdots \cdot \uparrow \uparrow \uparrow } _{3\uparrow 3{\text{本}}}3{\text{本}}\end{matrix}}\right\}\left.{\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdot \uparrow } 3{\text{層 }}\\3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \uparrow } 3{\text{本}}\\\underbrace {\qquad \;\;\vdots \qquad \;\;} \\3\underbrace {\uparrow \uparrow \cdots \cdot \uparrow } _{3\uparrow 3{\text{本}}}3{\text{本}}\end{matrix}}\right\}\ 3\uparrow 3=27{\text{層 }}} 数 3 → 3 → 27 → 2 = g 27 ( 1 ) {\displaystyle 3\rightarrow 3\rightarrow 27\rightarrow 2=g^{27}(1)} は65よりもはるかに大きいので、 3 → 3 → 3 → 3 {\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3} はグラハム数よりはるかに大きい。さらに末尾の数字を増やしたりチェーンを伸ばしたりすることで極めて巨大な数を表記可能である。 3 → 3 → 3 → 3 {\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3} はコンウェイのテトラトリと呼ばれる。
※この「グラハム数」の解説は、「コンウェイのチェーン表記」の解説の一部です。
「グラハム数」を含む「コンウェイのチェーン表記」の記事については、「コンウェイのチェーン表記」の概要を参照ください。
- グラハム数のページへのリンク
