葛立恆數

葛立恆數（英語：Graham's number）由羅納德·葛立恆所創造，是一個相當有名的大數，常被認為是「數學證明中出現過最大的數」，的確有一段時間是這樣，但現在已經不是了。現在數學證明中出現的許多數，如TREE(3)和SCG(13)都比葛立恆數大很多。Bowers的corporal^[英語]和Saibian的graatagold^[英語]都是作者各自命名且超过葛立恆數的最小数。

它可以使用上箭號表示法來定義：

\begin{eqnarray*} g_0 &=& 4 \\ g_1 &=& 3 \uparrow\uparrow\uparrow\uparrow 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 \ \ (\forall k \in \mathbb{N})\\ g_{64} &=& \text{葛立恆數} \end{eqnarray*}

背景

葛立恒数产生于拉姆齐理论中的一个未解决的问题：

设N*是能够满足下述命题的超立方体的维数N的最小值：把N维的超立方体的所有顶点两两相连，每一条连线都涂上红色或者蓝色，那么至少有一个面的所有连线都是同色的。那么N*是多少？

葛立恒于1971年发表了一篇论文，证明了答案的存在，并给出了N*的上限$F(F(F(F(F(F(F(12)))))))$，其中$F(n)$表示$2\uparrow ^{n}3$。 塞比安称这个号码为“小葛立恒数”。马丁·加德纳在发现这个数字的大小时，发现很难解释，于是就选择了一个更大、更容易解释的数字，即我们通常所说的“葛立恒数”。葛立恒在1977年一篇未发表的论文中证明了这一点。马丁·加德纳在《科学美国人》上写过这个数字，它甚至在1980年被吉尼斯世界纪录列为数学证明中使用过的最大的数字，尽管几年后这个头衔从吉尼斯世界纪录中删除了。

2013年，N*的上限降至N'=2↑↑2↑↑(3+2↑↑8) ;

2019年，N*的上限降至 (2↑↑5138) x ((2↑↑5140)↑↑(2 x (2↑↑5137)))<<2 ↑↑2↑↑5138<< 2↑↑↑5。（实际上，他可以证明上限小于2↑↑2↑↑426)

截至2014年，N*的下限是13。

近似

由於\(g_0\)是4而不是3，使用鏈式箭號表示法和BEAF都無法準確表達，然而還是可以給出近似值：

\(3 \rightarrow 3 \rightarrow 64 \rightarrow 2 < g_{64} < 3 \rightarrow 3 \rightarrow 65 \rightarrow 2\) （鏈式箭號表示法）

\(\{3,65,1,2\} < g_{64} << \{3,66,1,2\}\) （BEAF）

\(g_{64} = \underbrace{3 \uparrow^{3 \uparrow^{3 \uparrow^{\cdot^{\cdot^{\cdot^{3 \uparrow \uparrow \uparrow \uparrow 3}\cdot}\cdot}\cdot}3}3}3}_{64\text{个}} = \left. 3 \underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}_{\displaystyle 3 \underbrace{\uparrow \uparrow \cdots \cdots \cdots \uparrow}_{\displaystyle \underbrace{\qquad \vdots \qquad}_{\displaystyle 3 \underbrace{\uparrow \uparrow \cdots \uparrow}_{\displaystyle 3 \uparrow \uparrow \uparrow \uparrow 3}3}}3}3 \right \} 64 \text{个}\)

由于哈代层级^[英語]在使用Wainer 的基本列时能得出\(H_{\omega^\omega}(n) \approx \{n,n,n-1\}\),葛立恒数可近似写作\(H_{\omega^\omega 64}(4)\)、\(H_{\omega^{\omega+1}}(64)\) 或快速增長層級中\(f_{\omega+1}(64)\)。

含义

公式：

\(g_{64} = \underbrace{3 \uparrow^{3 \uparrow^{3 \uparrow^{\cdot^{\cdot^{\cdot^{3 \uparrow \uparrow \uparrow \uparrow 3}\cdot}\cdot}\cdot}3}3}3}_{64\text{ layers}} = \left. 3 \underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}_{\displaystyle 3 \underbrace{\uparrow \uparrow \cdots \cdots \cdots \uparrow}_{\displaystyle \underbrace{\qquad \vdots \qquad}_{\displaystyle 3 \underbrace{\uparrow \uparrow \cdots \uparrow}_{\displaystyle 3 \uparrow \uparrow \uparrow \uparrow 3}3}}3}3 \right \} 64 \text{ layers}\)

本方法使用高德纳箭头法表示。

首先，第一层（$G_1$）是$3 \uparrow \uparrow \uparrow \uparrow 3$。

这一层的结果已经非常大了。

第二层（$G_2$）的箭头个数是$G_1$的结果。注意：是箭头个数，而不是指数！

第三层（$G_3$）的箭头个数是$G_2$的结果。

以此类推。

最后迭代到$G_{64}$的结果则是葛立恒数的值。