查看“︁葛立恒数”︁的源代码

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

=== 定义 ===

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

<math>G(n)=\begin{cases}3\uparrow^{G(n-1)}3&,n\neq0\\4&,n=0\end{cases}</math>

葛立恒函数的 [[FGH]] [[增长率]]约为<math>\omega +1</math>。

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

更出名的一个写法是：

<math>G(64)=\left. \begin{matrix} 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 \uparrow3\end{matrix} \right \} \text{64 layers}</math>

=== 历史 ===
葛立恒数源于拉姆齐理论中以下未解决的问题：<ref>Weisstein, Eric W. "Graham's Number." From ''MathWorld''--A Wolfram Resource. https://mathworld.wolfram.com/GrahamsNumber.html</ref>

设 <math>N</math> ''为超立方体的最小维度'' <math>n</math>''，使得对于任意'' <chem>n\geqslant N</chem>，若将连接所有顶点对的线段用两种颜色着色，则必然存在一个单色的完全图 K₄（其顶点共面）。求N*的值。
[[文件:GrahamCube.png|缩略图|图中展示了一个立方体的示例，包含 12 个共面的 K₄ 完全图，其中下方显示了一个单色 K₄。若将该 K₄ 底部的边改为蓝色，则立方体中将不存在单色的共面 K₄，从而证明 <math>N^*</math> 至少为 4。]]
为理解问题，首先考虑任意维度的超立方体（1维为线段，2维为正方形，3维为立方体，4维为超立方体等），记其维度为 <math>N</math>。然后想象将所有顶点对用线段连接，并用红色或蓝色为每条线段着色（右侧展示了3维立方体的一种着色方式）。问题要求找到最小的维度 <math>N</math>，使得所有可能的着色方式中必然存在一个单色的完全图 K₄（由四个两两相连的顶点构成，且所有边颜色相同）。

1971 年，R.L.Graham 和 B.L.Rothschild 在他们的论文<ref>GRAHAM R L, ROTHSCHILD B L. Ramsey’s theorem for ff-parameter sets[J]. Transactions of the American Mathematical Society, 1971, 159: 257-292. https://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf</ref>中为葛立恒问题提供的上界是 <math>F(F(F(F(F(F(F(12,3),3),3),3),3),3),3)</math>，其中 <math>F</math> 函数的定义为： <math>F(m,n)=\begin{cases}F(m-1,F(m,n-1))&,m\geqslant1\text{ and }n\geqslant2\\2^n&,m=1\\4&,n=2\end{cases}</math>，这相当于 <math>F^7(12)</math> 其中 <math>F(n)=2\uparrow^n3</math>。Sbiis Saibian 称这个数字为 “Little Graham”。

1976 年，Donald E.Knuth 在他的论文<ref>Donald E. Knuth, ''Mathematics and Computer Science: Coping with Finiteness'', Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, Science 194, pp. 1235--1242, 1976.https://cse-robotics.engr.tamu.edu/dshell/cs625/finiteness.pdf</ref>中定义了现在所使用的高德纳箭头。

1977 年，M.Gardner 在他的文章<ref>GARDNER M. Mathematical games[J]. Scientific American, 1977, 237(3): 28-38.https://raw.githubusercontent.com/AllenDowney/ModSimPy/master/papers/scientific_american_nov_77.pdf</ref>中定义了现在的葛立恒数。Gardner 在发现这个数字的大小时，发现很难解释，他设计了一个更大、更容易解释的数字，格雷厄姆在 1977 年一篇未发表的论文中证明了这一点。他在 Scintific Amercian 上写了关于这个数字的文章，它甚至在 1980 年作为数学证明中使用的最大数字进入吉尼斯世界纪录，尽管几年后该称号从吉尼斯世界纪录中删除。一说是 Gardner 在与 Graham 交流后，Graham 给他提供的这个较为宽松的上界，但无从考证，Gardner 的原文章里也没有提及此事。

1995 年，John.H.Conway 和 Richard.K.Guy 在 The Book of Numbers 一书<ref>Conway, J. H., & Guy, R. K. (1995). The Book of Numbers. Copernicus. https://studylib.net/doc/26253636/the-book-of-numbers</ref>中给出了葛立恒数，这被许多人认为是它的来源。

2013 年，使用 Hales-Jewett 定理<ref>http://arxiv.org/abs/1304.6910</ref>将上限进一步降低到 <math>N^*=2\uparrow\uparrow2\uparrow\uparrow(3+2\uparrow\uparrow8)</math>，并在 2019 年<ref>http://arxiv.org/abs/1905.05617</ref>进一步降低到 <math>(2\uparrow\uparrow5138)\times((2\uparrow\uparrow5140)\uparrow\uparrow(2\times2\uparrow\uparrow5137))\ll2\uparrow\uparrow\uparrow5</math>。截至 2014 年，最著名的 ''N*''<math>N^*</math> ''下''限是 13<ref>http://arxiv.org/abs/0811.1055</ref>，由 Jerome Barkley 在 2008 年提出。

=== 参考资料 ===
<references />
[[分类:入门]]
[[分类:经典大数]]