グラハムの番号

グラハム数は、ラムゼー理論という数学分野における問題の解の上限として現れた巨大な数です。これは、数学において有効な上限として導入された他の多くの大きな数、例えばスキューズの限界（グーゴルプレックスよりもはるかに大きい）よりもはるかに大きい数です。グラハム数は非常に大きいため、各桁がプランク体積1つを占めると仮定すると、観測可能な宇宙はその通常のデジタル表現を収めるには小さすぎます。しかし、グラハム数のこのデジタル表現の桁数自体も非常に大きいため、そのデジタル表現は観測可能な宇宙では表現できません。さらにその桁数も同様に、観測可能な宇宙のプランク体積の総数をはるかに超える回数だけ表現できます。したがって、グラハム数は、物理的な宇宙規模のパワータワーの形でさえ表現できません。${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$グレアムの数は確かに3のべき乗であるにもかかわらず。

しかし、グラハム数は、その名の由来となったロナルド・グラハムが行ったように、クヌースの上向き矢印記法またはそれに相当するものを用いた計算可能な再帰式によって明示的に与えることができます。再帰式で定義できるため、グラハム数は、計算可能な数列よりも速く増加する典型的なビジービーバー数よりもはるかに小さいです。グラハム数は大きすぎて完全に計算することはできませんが、その桁の列は単純なアルゴリズムによって明示的に計算できます。グラハム数の下10桁は...2464195387です。^{[ 1 ]}クヌースの上向き矢印記法を用いると、グラハム数は${\displaystyle g_{64}}$[ ^{2 ]}ここ ^で$${\displaystyle g_{n}={\begin{cases}3\uparrow \uparrow \uparrow \uparrow 3,&{\text{if }}n=1{\text{ and}}\\3\uparrow ^{g_{n-1}}3,&{\text{if }}n\geq 2.\end{cases}}}$$

グラハム数は、グラハムが人気科学ライターのマーティン・ガードナーとの会話の中で、彼が取り組んでいた問題の上限を簡略化して説明するために使用されました。1977年、ガードナーはサイエンティフィック・アメリカン誌でこの数を紹介し、一般に公開しました。発表当時、これは出版された数学的証明で使用された最大の特定の正の整数でした。この数は1980年のギネス世界記録にも掲載され、さらに広く知られるようになりました。グラハム数よりもはるかに大きいことが知られている他の特定の整数（ TREE(3)など）は、その後、ハーヴェイ・フリードマンのクルスカルの定理のさまざまな有限形式に関連して、多くの本格的な数学的証明に登場しています。さらに、グラハム数が導出されたラムゼー理論の問題に対するより小さな上限が、その後有効であることが証明されています。

グラハム数は、ラムゼー理論における以下の問題と関連している。

n次元超立方体の幾何学的頂点の各ペアを接続して、 2 ⁿ個の頂点を持つ完全グラフを作成します。このグラフの各辺を赤または青のいずれかで着色します。このような着色のすべてにおいて、少なくとも1つの単色完全部分グラフが4つの同一平面上の頂点を持つような最小のnの値はいくつですか？

1971年、グラハムとロスチャイルドは、パラメータ語のラムゼー理論に関するグラハム・ロスチャイルド定理を証明した。この定理の特殊なケースでは、この問題に解N*が存在することが示されている。彼らはN*の値を6 ≤ N* ≤ Nで制限した。ここでNは大きく、明示的に定義された数である。

$${\displaystyle N=F^{7}(12)=F(F(F(F(F(F(F(12)))))))),}$$

どこ${\displaystyle F(n)=2\uparrow ^{n}3}$クヌースの上向き矢印表記では、この数は4 → 2 → 8 → 2とコンウェイの連鎖矢印表記の2 → 3 → 9 → 2の間にある。^{[ 3 ]}これは 2014 年にヘイルズ・ジュエット数の上限によって削減され、

$${\displaystyle N'=2\uparrow \uparrow (2\uparrow \uparrow (3+2\uparrow \uparrow 8)),}$$

これには3つのテトラシオンが含まれています。^{[ 4 ]} 2019年にはこれがさらに改良され^{[ 5 ]}

$${\displaystyle N''=(2\uparrow \uparrow 5138)\cdot ((2\uparrow \uparrow 5140)\uparrow \uparrow (2\cdot 2\uparrow \uparrow 5137))\ll 2\uparrow \uparrow (2\uparrow \uparrow 5138).}$$

下限値6は、2003年にジェフリー・エクソーによって11に改善され^{[ 6 ]}、2008年にはジェローム・バークレーによって13に改善された^{[ 7 ]} 。したがって、 N*の最もよく知られている境界は13 ≤ N* ≤ N''である。

グラハム数GはNよりはるかに大きい。${\displaystyle f^{64}(4)}$、 どこ${\displaystyle f(n)=3\uparrow ^{n}3}$この問題に対するこの弱い上限は、グラハムの未発表の研究に起因するもので、最終的にマーティン・ガードナーによって1977年11月にサイエンティフィック・アメリカン誌で発表され、命名された。 ^{[ 8 ]}

この数は、マーティン・ガードナーが1977年11月のサイエンティフィック・アメリカンの「数学ゲーム」のセクションで、グラハムが最近未発表の証明で「真剣な数学的証明で使用された最大の数として記録を保持するほど巨大な上限」を確立したと書いたことで、ある程度の注目を集めた。1980年のギネス世界記録はガードナーの主張を繰り返し、この数に対する一般の関心を高めた。物理学者のジョン・バエズによると、グラハムは現在グラハム数として知られる量をガードナーとの会話の中で発明した。グラハムは共同研究者のブルース・リー・ロスチャイルドと共に導き出したラムゼー理論の結果を説明しようとしていたとき、グラハムは、証明に現れる実際の数よりも、その量の方が説明しやすいことに気づいた。グラハムがガードナーに説明した数は論文自体の数よりも大きいので、どちらもグラハムとロスチャイルドが研究した問題の解の有効な上限である。^{[ 9 ]}

クヌースの上向き矢印表記法を用いると、グラハム数G （ガードナーのサイエンティフィック・アメリカン誌の記事で定義されている）は次のようになる。 $${\displaystyle \left.{\begin{matrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\&&\underbrace {\qquad \quad \vdots \qquad \quad } \\&&3\underbrace {\uparrow \uparrow \cdots \cdots \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 layers}}}$$

ここで、各層の矢印の数は、その下の次の層の値によって指定されます。つまり、

$${\displaystyle G=g_{64},}$$どこ${\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,}$${\displaystyle g_{n}=3\uparrow ^{g_{n-1}}3,}$

ここで、上付き矢印の添え字は矢印の数を示します。言い換えれば、Gは 64 のステップで計算されます。最初のステップは、 3 の間に 4 つの上付き矢印があるg ₁を計算することです。2 番目のステップは、 3 の間にg ₁の上付き矢印があるg _{2 を}計算することです。3 番目のステップは、 3 の間にg _{2 の}上付き矢印があるg _{3 を計算することです。このようにして、最終的に 3 の間に}g ₆₃の上付き矢印があるG = g ₆₄を計算します。

同様に、 $${\displaystyle G=f^{64}(4),{\text{ where }}f(n)=3\uparrow ^{n}3,}$$

また、 fの上付き文字は関数の反復を表します。例:${\displaystyle f^{4}(n)=f(f(f(f(n))))}$ハイパーオペレーションのファミリーの観点から表現する${\displaystyle {\text{H}}_{0},{\text{H}}_{1},{\text{H}}_{2},\cdots }$関数fは特定の数列です${\displaystyle f(n)={\text{H}}_{n+2}(3,3)}$これは、急速に成長するアッカーマン関数A ( n , n )の一種です。(実際には、${\displaystyle f(n)>A(n,n)}$すべてのnについて。）関数fは、コンウェイ連鎖矢印表記法で次のように表すこともできます。${\displaystyle f(n)=3\rightarrow 3\rightarrow n}$また、この表記法はGに対して以下の境界も提供する。

$${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.}$$

n = 1から始まる、グラハム数の mod nの剰余は、

• OEIS配列A133613 （グラハム番号）
• Sbiis Saibianによるグラハム数に関する記事（ 2023年1月17日にWayback Machineにアーカイブ済み）
• ジェフ・エクソー著「ハイパーキューブ上のラムジー問題」
• ワイススタイン、エリック・W. 「グラハム数」 . MathWorld .
• グラハム数の計算方法
• Urban, Tim. 「1,000,000 から Graham 数まで」 . Wait But Why . 2026-04-24取得。
• nキューブのプレプリントに関するラムジーの結果の一部は、グラハムの数に言及している。
• Padilla, Tony ; Parker, Matt . "Graham's Number" . Numberphile . Brady Haran . 2014-05-27 のオリジナルからアーカイブ済み . 2013-04-08に取得.
• Ghostarchiveにアーカイブされていますそしてウェイバックマシン:ロン・グラハム(2014年7月21日)。「グラハムの数字とは？（ロン・グラハム出演）」(動画)。Numberphile。ブレイディ・ハラン。
• Ghostarchiveにアーカイブされていますそしてウェイバックマシン:ロン・グラハム(2014 年 7 月 22 日)。「グラハムの数字はどれくらい大きいか？ (feat. ロン・グラハム)」(動画)。Numberphile。ブレイディ・ハラン。
• ダークサイド通信グループによるグラハム番号の最後の1600万桁