グラハム数 (グラハムすう、英 : Graham's number )は、ラムゼー理論 に関する未解決問題 の解の推定値の上限として得られた自然数 である。数学の証明で使われたことのある最大の数として1980年 にギネスブック に認められた[ 1] 。
極めて巨大な自然数 (巨大数 )であり、指数表記 を用いるのは事実上不可能なため、特別な表記法を用いて表される。
グラハム問題
3次元の立方体で同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在している例。線をどのように塗ってもこのような平面が少なくとも1つ現れてしまうのは何次元以上の超立方体か、というのがこの問題の骨子である。
この数は1970年 のロナルド・グラハム 、ブルース・リー・ロスチャイルド による「グラハムの定理」
「
n 次元超立方体 の 2n 個の頂点のそれぞれを互いに全て線 で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。 このとき n が十分大きければ、どのような塗り方をしても、同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在する。
」
に関係する。つまり、n が十分大きければというが、
「
n がいくらより大きければ、この関係は常に成立するか
」
ということである。これがグラハム問題 である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。
しかし、この関係がグラハム数 以上の n について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。
ただし、グラハムらは実際にはこの数を論文では発表しておらず、翌1971年 にグラハム数より小さなグラハム問題の解の上限として、小グラハム数 という数を発表した[ 2] 。その後、マーティン・ガードナー が1977年 にサイエンティフィック・アメリカン でグラハム数を紹介した[ 3] ことによってこの数は広く知られるようになった。
解の上限はのち2014年 にミハイル・ラブロフらによってさらに小さい数 が示された[ 4] 。
一方、この問題の解の下限(つまりこの数より小さい数では成り立たないことを示した数)としては、グラハムとロスチャイルドは1971年の小グラハム数を示したものと同じ論文中で 6 を与えた。ガードナーは1989年 に著書の中でラムゼー理論 の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、2003年 にジェフ・エクスーがより良い下限として 11 を[ 5] 、2008年 にはジェローム・バークレーが 13 を与えた[ 6] 。
定義
矢印表記
グラハム数は巨大すぎて、通常の指数では桁数の表現すら事実上不可能である。そのため、次のような特殊な関数を用いる。
まず、クヌースの矢印表記 を使い、x , y を自然数としたとき、演算子「↑」を次のように定義する。
x
↑
y
=
x
y
{\displaystyle x\uparrow y=x^{y}}
この節は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方 ) 出典検索? : "グラハム数" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (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(トリトリ)
=
3
3
3
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
3
3
3
⏟
高 さ
7625597484987
=
3
3
3
3
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
3
3
3
⏟
高 さ
7625597484986
≈
exp
10
7
,
625
,
597
,
484
,
986
(
1.09902
)
{\displaystyle =\underbrace {3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3^{3^{3}}}}}}}}}}}}}}}} _{{\text{高 さ }}7625597484987}=3^{\underbrace {3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3^{3^{3}}}}}}}}}}}}}}}} _{{\text{高 さ }}7625597484986}}\approx \exp _{10}^{7,625,597,484,986}(1.09902)}
この節は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方 ) 出典検索? : "グラハム数" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2022年6月 )
グラハム数を表すにはいくつか等価な表現がある。
3
↑
G
63
(
4
)
+
1
2
{\displaystyle 3\uparrow ^{G^{63}(4)+1}2}
この節は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方 ) 出典検索? : "グラハム数" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2022年6月 )
グラハムとロートシルトは1971年 に、より小さい上限として小グラハム数 (Little Graham) を示した。この数は関数 F (n ) を
F
(
n
)
=
2
↑
n
3
=
2
↑
⋯
↑
⏟
n
3
=
2
→
3
→
n
{\displaystyle F(n)=2\uparrow ^{n}3=2\underbrace {\uparrow \cdots \uparrow } _{n}3=2\rightarrow 3\rightarrow n}
カテゴリ