葛立恒数

葛立恒数（Graham's Number）是拉姆齐理论中一个问题（即葛立恒问题）的上界。它也是大数领域中最著名的数之一，与TREE(3)、SCG(3)齐名。

定义

葛立恒函数

葛立恒函数（Graham's Function）是用高德纳箭头递归定义的：

$G(n)=\{\begin{array}{ll}3{\uparrow }^{G(n-1)}3& ,n\ne 0\\ 4& ,n=0\end{array}$

葛立恒函数的 FGH 增长率约为$\omega +1$。

葛立恒数

葛立恒数被定义为 $G(64)$（有时也被写作 $G,g_{64},g(64)$ 等）。

更出名的一个写法是：

$G(64)=\begin{array}{c}3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow }3\\ 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow }3\\ \underbrace{⋮}\\ 3\underbrace{\uparrow \uparrow \cdots \cdots \uparrow }3\\ 3\uparrow \uparrow \uparrow \uparrow 3\end{array}\}\text{64 layers}$

历史

葛立恒数源于拉姆齐理论中以下未解决的问题：

设 $N$ 为超立方体的最小维度 $n$，使得对于任意 $\mathrm{n}⩾\mathrm{N}$，若将连接所有顶点对的线段用两种颜色着色，则必然存在一个单色的完全图 K₄（其顶点共面）。求N*的值。

图中展示了一个立方体的示例，包含 12 个共面的 K₄ 完全图，其中下方显示了一个单色 K₄。若将该 K₄ 底部的边改为蓝色，则立方体中将不存在单色的共面 K₄，从而证明 $N^{*}$ 至少为 4。

为理解问题，首先考虑任意维度的超立方体（1维为线段，2维为正方形，3维为立方体，4维为超立方体等），记其维度为 $N$。然后想象将所有顶点对用线段连接，并用红色或蓝色为每条线段着色（右侧展示了3维立方体的一种着色方式）。问题要求找到最小的维度 $N$，使得所有可能的着色方式中必然存在一个单色的完全图 K₄（由四个两两相连的顶点构成，且所有边颜色相同）。

1971 年，R.L.Graham 和 B.L.Rothschild 在他们的论文中为葛立恒问题提供的上界是 $F(F(F(F(F(F(F(12,3),3),3),3),3),3),3)$，其中 $F$ 函数的定义为： $F(m,n)=\{\begin{array}{ll}F(m-1,F(m,n-1))& ,m⩾1\text{ and }n⩾2\\ 2^n& ,m=1\\ 4& ,n=2\end{array}$，这相当于 $F^7(12)$ 其中 $F(n)=2{\uparrow }^{n}3$。Sbiis Saibian 称这个数字为 “Little Graham”。

1976 年，Donald E.Knuth 在他的论文中定义了现在所使用的高德纳箭头。

1977 年，M.Gardner 在他的文章中定义了现在的葛立恒数。Gardner 在发现这个数字的大小时，发现很难解释，他设计了一个更大、更容易解释的数字，格雷厄姆在 1977 年一篇未发表的论文中证明了这一点。他在 Scintific Amercian 上写了关于这个数字的文章，它甚至在 1980 年作为数学证明中使用的最大数字进入吉尼斯世界纪录，尽管几年后该称号从吉尼斯世界纪录中删除。一说是 Gardner 在与 Graham 交流后，Graham 给他提供的这个较为宽松的上界，但无从考证，Gardner 的原文章里也没有提及此事。

1995 年，John.H.Conway 和 Richard.K.Guy 在 The Book of Numbers 一书中给出了葛立恒数，这被许多人认为是它的来源。

2013 年，使用 Hales-Jewett 定理将上限进一步降低到 $N^{*}=2\uparrow \uparrow 2\uparrow \uparrow (3+2\uparrow \uparrow 8)$，并在 2019 年进一步降低到 $(2\uparrow \uparrow 5138)\times ((2\uparrow \uparrow 5140)\uparrow \uparrow (2\times 2\uparrow \uparrow 5137))\ll 2\uparrow \uparrow \uparrow 5$。截至 2014 年，最著名的 N*$N^{*}$ 下限是 13，由 Jerome Barkley 在 2008 年提出。