葛立恒数

葛立恒数(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$维的超立方体(1维为线段，2维为正方形，3维为立方体，4维为超立方体等)，

在连结所有顶点后，将形成一个$2^n$个顶点的完全图。将这个图的每条边填上红色或蓝色，求使得所有填法中都必定存在一个在同一平面上有四个顶点的单色完全子图(由四个两两相连的顶点构成，且所有边颜色相同)的$n$的最小值$N^{*}$。

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

1971 年，R.L.Graham和B.L.Rothschild 在他们的论文中证明了$N^{\prime }\le N^{*}\le N$，

其中$N^{\prime }=6$，$N=F(F(F(F(F(F(F(12,3),3),3),3),3),3),3)$。

$F$ 函数的定义为： $F(m,n)=\{\begin{array}{ll}{2}^n& ,m=1\\ 4& ,n=2\\ F(m-1,F(m,n-1))& ,m\ge 2\text{ and }n\ge 3\end{array}$

它等价于 $F^7(12)$ ，其中 $F(n)=2{\uparrow }^{n}3$。

Sbiis Saibian 称这个数字为 “Little Graham”。

目前，该问题有可靠来源的最新下界为$13$，最新上界为

$(2\uparrow \uparrow 5138)\times ((2\uparrow \uparrow 5140)\uparrow \uparrow (2\times 2\uparrow \uparrow 5137))\ll 2\uparrow \uparrow \uparrow 5$。

历史

葛立恒数的由来

从目前的证据来看，葛立恒数的作者并非葛立恒。

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

1977 年，M.Gardner 在他的文章中定义了现在的葛立恒数。Gardner 在发现这个数字的大小时，发现很难解释，于是他设计了一个更大、更容易解释的数字。他在 Scientific Amercian 上写了关于这个数字的文章，后来在 1980 年作为数学证明中使用的最大数字进入吉尼斯世界纪录，尽管几年后该记录已被删除。

一说是 Gardner 在与 Graham 交流后，Graham 给他提供的这个较为宽松的上界，但无从考证，Gardner 的原文章里也没有提及此事。

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

葛立恒问题的进展

2003 年，Exoo 证明了 $N^{*}⩾11$。

2008 年，Jerome Barkley 证明了 $N^{*}⩾13$。

2013 年，Mikhail Lavrov, Mitchell Lee, John Mackey 通过使用 Hales-Jewett 定理将上限进一步降低到 $N^{*}=2\uparrow \uparrow 2\uparrow \uparrow (3+2\uparrow \uparrow 8)$。

2019 年，Eryk Lipka 将上限进一步降低到 $(2\uparrow \uparrow 5138)\times ((2\uparrow \uparrow 5140)\uparrow \uparrow (2\times 2\uparrow \uparrow 5137))\ll 2\uparrow \uparrow \uparrow 5$。

比较

由于 $G(0)$ 是 4 而不是 3，因此葛立恒数不能用链式箭头表示法或 BEAF 有效表示。使用 Jonathan Bowers 的 base-3 G 函数，它正好是 $G^{64}4$。它也可以在 Graham Array Notation 中精确表示为 $[3,3,4,64]$。Tim Chow 证明了葛立恒数比 Moser 大得多。证明取决于这样一个事实，即使用 Steinhaus-Moser 符号，a(k+2)-gon 中的 n 小于 $n{\uparrow }^{2k-1}n$。他于 1998 年 7 月 7 日将证明发送给 Susan Stepney。巧合的是，几天后 Todd Cesere 向 Stepney 发送了类似的证明。

日本 googologist Fish 证明 Graham 的数小于 $f_{\omega +1}(64)$ 在 FGH 中，相对于 Wainer 层次结构。

已知远大于葛立恒数的特定整数此后出现在许多严肃的数学证明中，例如，与 Harvey Friedman 的各种有限形式的 Kruskal 定理有关。

与 Busy Beaver 函数的比较

• 2010-09-19： 事实证明，葛立恒数远小于 $\mathrm{\Sigma }(64)$。
• 2016-07-24：根据 Wythagoras 的说法，他发现了一台图灵机，证明了 $\mathrm{\Sigma }(18)>G$ 通过改进 Deedlit11 的机器，并写了一份简短的证明草图，而不是一份严格的证明。
• 在英语 googology 社区中，人们认为更好的上限 $\mathrm{\Sigma }(17)$ 直到 2021 年 7 月 9 日才被某人证明，但至少没有关于结果的引用来源。
• 2021-03-18：Daniel Nagaj 声称他的 16 态图灵机实现了多展开并超过了葛立恒数，这意味着 $\mathrm{\Sigma }(16)>G$。
• 2022-07-11： S. Ligocki 证实 Daniel Nagaj 的 16 态图灵机超过了葛立恒数。

在其他记号中的近似

• $3\to 3\to 64\to 2$（链式箭头表示法）
• $\{3,65,1,2\}$（BEAF）
• $[3,3,4,64]$（Graham Array Notation，精确值）
• $E[3]3\mathrm{\#}\mathrm{\#}4\mathrm{\#}64$（Hyper-E Notation）
• $s(3,64,2,2)$（SAN）
• $64[\mathrm{\&}1]$（Ampersand Notation）
• $f_{\omega +1}(64)$（FGH）
• $H_{{\omega }^{\omega +1}}(64)$ 或 $H_{{\omega }^{\omega }64}(4)$（HH）
• $g_{{\mathrm{\Gamma }}_0}(65)$（SGH）

计算末位数字

可通过简单的模幂算法轻松计算葛立恒数的最后位数。以下是一个获取较小 x 值对应葛立恒数末 x 位数 N(x) 的简易算法：

$N(x)=\{\begin{array}{ll}3& ,x=0\\ 3^{N(x-1)}(\mathrm{mod}10^x)& ,x\ne 0\end{array}$

然而，若将该公式应用于极大的x值则不成立——尽管该错误公式曾被认为正确，并在 2019 年 12 月前于英语 googology 社区流传。可通过以下思路修正错误：葛立恒数 G(64) 实质是以 3 为底、以极大值 b 为超指数的整数迭代幂次（即 $G(64)={}^{b}3$ )。

2020年，Marco Ripà 证明了在十进制下，当且仅当超指数为 1 时 3 的 congruence speed（同余速度）为 0，否则恒为 1。因此，对所有 $c=1,2,\cdots ,b-2,b-1$， G(64) 的末 b-1 位数与 ${}^{c}3$ 相同。但此性质不适用于 G(64) 的第 b 位数——该数字与 ${}^{b+1}3,{}^{b+2}3,{}^{b+3}3,\cdots$ 的第 b 位数均不相等。由 $b-1={\text{slog}}_3(G_{64})-1$（其中 slog 表示超对数）可得 $G_{63}\ll b-1\ll G_{64}$。故最终可证：对所有正整数 c ，满足：

$G_{64}\equiv {}^{slo{g}_3(G_{64})+c}3(\mathrm{mod}{10}^{slo{g}_3(G_{64})-1})\wedge G_{64}\equiv ̸{}^{slo{g}_3(G_{64})+c}3(\mathrm{mod}{10}^{slo{g}_3(G_{64})})$

实际上，该方法会返回映射 $x\mapsto 3^x$ 在 10 进制整数中的不动点的最后位数。因此上述“错误算法”仅能计算葛立恒数的末 b-1 位。由于 b 值极大（在此尺度下几乎与葛立恒数本身相当），该算法对所有实际应用的 x 值均有效——这可能是其曾被推广至任意正整数 x 的原因。

葛立恒数的末 20 位是：...04,575,627,262,464,195,387。

当前学术界尚无法计算葛立恒数在十进制下的首位数字（且很可能永远无法实现），但可确定：

• 二进制下首位必为1（因所有非零正整数均满足此性质）
• 三进制下首位必为1（因其是3的幂）
• 九进制下首位必为3（因其是3的奇数次幂）

除非进制本身是3的幂（如27进制），或与葛立恒数可比（如葛立恒数减64），否则无法计算其在其他进制下的首位数字。

最后 400 位数字如下：

3881448314065252616878509555264605107117
2000997092912495443788874960628829117250
6300130362293491608025459461494578871427
8323508292421020918258967535604308699380
1689249889268099510169055919951195027887
1783083701834023647454888222216157322801
0132974509273445945043433009010969280253
5275183328988446150894042482650181938515
6253579639961899396790549663800322234872
3967018485186439059104575627262464195387.