グラハム数

他の用法については、グラハム数 (曖昧さ回避) をご覧ください。

グラハム数 (Graham's number) は、Ronald Grahamが定義した有名な巨大数^[1]である。

矢印表記を使って、このように定義出来る。

\[\begin{eqnarray*} G_0 &=& 4 \\ G_1 &=& 3 \underbrace{\uparrow\uparrow\uparrow\uparrow}_{G_0=4} 3 \\ G_2 &=& 3 \underbrace{\uparrow\uparrow\cdots\uparrow\uparrow}_{G_1 \text{ 本の↑}} 3 \\ G_{k + 1} &=& 3 \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow\uparrow\uparrow}_{G_k \text{ 本の↑}} 3 \\ G_{64} &=& \text{グラハム数} \end{eqnarray*}\]

すなわち、\(G(n) = 3\uparrow^{n}3\) としたときの\(G^{64}(4)=\underbrace{G(G( \cdots G(}_{64}4)\cdots))\)である。

グラハム数は数学の証明で使われた最大の数としてギネスブックにも登録されている。ちなみに、「数学的に意味のある」巨大数に関しては、TREE(3)、SCG(13)等、グラハム数より遥かに巨大なものが存在する。

巨大数漫画「寿司虚空編」^[2]では、第1話でグラハム数の話からはじまり、読者を巨大数の世界へと引き込んでいる。

歴史[]

グラハム数は、次のラムゼー理論に関する未解決問題から生まれた。

Let N* be the smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored for any n ≥ N*, a complete graph K₄ of one color with coplanar vertices will be forced. Find N*.

グラハムは、この問題の答えが存在する事を証明する論文を発表し、その値の上限を \(F(n) = 2 \uparrow^{n} 3\) (矢印表記を使用)としたときの\(F^{7}(12)\)であるとした^[3]。Sbiis Saibian は、この数を"小グラハム数"と呼んだ。グラハム数は、この論文の前に未公表の論文に書かれていたことがあり、マーティン・ガードナーがサイエンティフィック・アメリカンにそのことを書いた^[4]ことで有名になった。

ガードナーの記事には小さなミスがあり、\(3\uparrow\uparrow7625597484987=3\uparrow(7625597484987\uparrow7625597484987)\)であると書かれているが、実際には \(3 \uparrow (3\uparrow\uparrow7625597484986)\)である。

比較[]

\(G_0\)が3ではなくて4のため、巨大数論で使われる多くの関数で、グラハム数を正確かつ簡潔に表現することができないが、近似することはできる。チェーン表記では、\(3 → 3 → 64 → 2\)、配列表記では \(\lbrace 3,65,1,2\rbrace\) と近似でき、上限は \(\lbrace 3,66,1,2\rbrace\) である。多変数アッカーマン関数では、\(A(1,1,64)<G<A(1,1,65)\)である。

Tim Chow は、グラハム数がモーザー数よりもはるかに大きい事を証明した^[5]。この証明は、スタインハウス・モーザー表記で(k + 2)角形の中の nは \(n\underbrace{\uparrow\uparrow\ldots\uparrow\uparrow}_{2k-1}n\) よりも小さいことを利用している。彼はこの証明を Susan Stepney に1998年7月7日に送った^[6]。偶然にも、Stepney は Todd Cesere から同様の証明を数日後に受け取った。

グラハム数はビジービーバー関数の\(\Sigma(64)\)よりもずっと小さいことが証明されている^[7]。Googology WikiユーザーのWythagorasによると、Wythagorasは同じくGoogology WikiユーザーであるDeedlit11によるチューリングマシンを改良することで、\(\Sigma(18) > G\)を導くようなチューリングマシンを発見したと主張し、厳密な証明の代わりに証明のスケッチを公開した^[8]。

グラハム数は\(f_{\omega+1}(64)\)よりも小さいことがふぃっしゅによって証明されている^[9]。

最後の桁の計算[]

グラハム数の末尾桁は、剰余法を用いた単純なアルゴリズムを適用することで容易に計算できる。以下は、x が小さい場合のグラハム数の末尾 \(x\) 桁 \(N(x)\) を求める簡単なアルゴリズムである：

\(N(0) = 3\)
\(N(x) = 3^{N(x-1)} \text{ mod } 10^x\)

ただし、この公式は理論的に極めて大きなx値に適用すると『間違っている』ことが判明している。とはいえ、英語版のコミュニティでは正しいと信じられており、2019年12月まで広まっていた。この誤りは、グラハム数 \(G_{64}\) が単に基数 \(3\) と非常に大きな超指数 \(b\) による整数テトラションであること（すなわち \(G_{64}:={^{b}3}\)）を考慮すれば容易に修正できる。

その後、2020年にマルコ・リパは、基数10（よく知られた十進法）において、剰余速度が0となるのは、その（正の整数である）超指数が1である場合のみであり、それ以外の場合には剰余速度が1となることを証明した（https:// nntdm.net/volume-26-2020/number-3/245-260/ の補題 1、および詳細については https://nntdm.net/volume-28-2022/number-3/441-457/ の式 (16) も参照）。

したがって、\(G_{64}\) はすべての \(c=1,2,\ldots,b-2,b-1\) に対して \({^{c}3}\) の右端から \(b-1\) 桁目までが同一である。しかし、\(G_{64}\) の右端から \(b\) 番目の桁を考慮すると、これはもはや成立しない。なぜなら、この桁は \({^{b+1}3}, {^{b+2}3}, {^{b+3}3}, \ldots\) の右端から \(b\) 番目の桁とは等しくないからである。

ここで \( b-1 = slog_3(G_{64})-1 \) であることから（ここで \( slog \) は超対数関数を示す）、\( G_{63} << b-1 << G_{64} \) が成り立つ。したがって、最終的に次のように述べることができる：\(G_{64} \equiv ^{slog_3(G_{64})+c}3 \pmod {{10}^{slog_3(G_{64})-1}} \wedge G_{64} \not\equiv ^{slog_3(G_{64})+c}3 \pmod <nowiki>{{10}^{slog_3(G_{64})-1}} \wedge G_{64} \not\equiv ^{slog_3(G_{64})+c}3 \pmod {{10}^{slog_3(G_{64})}}\) が、すべての \(c \in \mathbb{Z}^+\) に対して成立する。^[10]^{定理 2.3}

実際、任意の桁数に対して、この方法は \(x \mapsto 3^x\) の \(10\)進固定点の末尾桁を返す。

したがって、前述の「誤ったアルゴリズム」はグラハム数の末尾 \(b-1\) 桁しか返せない。モジュラー乗法の主記事を参照のこと。ただし、\(b\)の値は極めて大きい（実際、このスケールではグラハム数自体とほとんど変わらない）ため、この方法は実用的な\(x\)の値すべてに対して機能する。おそらくこれが、この方法が仮定された理由である。

グラハム数の末尾20桁は...04,575,627,262,464,195,387である。現在の数学コミュニティにおいて、グラハム数の10進法における先頭桁を計算する方法が知られていない（そしておそらく永遠に知られないだろう）一方で、その先頭桁は2進法では1（0を除く全ての正の整数がこの性質を持つため）、 3進法では1（3の冪乗であるため）、9進法では3（3の奇数乗であるため）であることが分かっている。現在のコミュニティでは、3の冪（例：27）である場合、あるいは少なくともグラハム数と同程度（例：グラハム数 - 64）でない限り、他の基数におけるグラハム数の先頭桁を計算する方法が知られていない。