葛立恒数

时间:2020-03-26 18:54:01

葛立恒数由葛立恒提出,曾经被视为在正式数学证明中出现过最大的数,后来则被TREE(3)英语TREE(3)取代。它大得连高德纳箭号表示法也难以简单表示,而必须使用64层高德纳箭号表示法才表示得出来。

马丁·加德纳于1977年11月在美国科学人杂志的“数学游戏”专栏将此数刊登出来,1980年被吉尼斯世界纪录订为在正式数学证明中出现过最大的数。

问题背景

一个将三维立方体的边,著上红蓝二色的例子。此例中恰存在一个“四顶点共平面且单色的完全子图”,子图绘于三维立方体的下方。注意到若将此子图的下方改成蓝色,则此例将不再含有“四顶点共平面且单色的完全子图”,也就提供了一个反例,证明 N {displaystyle N^{*}} 至少大于3。

葛立恒数与拉姆齐理论有关:考虑一个 n {displaystyle n} 维的超立方体,在连结所有顶点后,将形成一个 2 n {displaystyle 2^{n}} 个顶点的完全图。将这个图的每条边填上红色或蓝色。求 n {displaystyle n} 的最小值,才使得所有填法中都必定存在一个在同一平面上有四个顶点的单色完全子图。

在1971年Graham与Rothschild证明了此题之解 N {displaystyle N^{*}} 的上下界为 6 N N {displaystyle 6leq N^{*}leq N} ,其中 N {displaystyle N} 是一个极大但明确定义的数字 F 7 ( 12 ) = F ( F ( F ( F ( F ( F ( F ( 12 ) ) ) ) ) ) ) {displaystyle F^{7}(12)=F(F(F(F(F(F(F(12)))))))} ,用高德纳箭号表示法, F {displaystyle F} 可表示为 F ( n ) = 2 n 3 {displaystyle F(n)=2uparrow ^{n}3} ;康威链式箭号表示法也可以表示此数的大略范围,此数介于 4 2 8 2 {displaystyle 4rightarrow 2rightarrow 8rightarrow 2} 2 3 9 2 {displaystyle 2rightarrow 3rightarrow 9rightarrow 2} 之间[1] N {displaystyle N^{*}} 的上界在2014年借由Hales–Jewett数的上界而降为 2 ↑↑↑ 6 {displaystyle 2uparrow uparrow uparrow 6} [2];下界则在2003年由Geoffrey Exoo提高为11,并由Jerome Barkley在2008年进一步的提高为13。因此目前所知最佳的 N {displaystyle N^{*}} 上下界为 13 N 2 ↑↑↑ 6 {displaystyle 13leq N^{*}leq 2uparrow uparrow uparrow 6}

葛立恒数 G {displaystyle G} N {displaystyle N} 大得多, G {displaystyle G} 可表示为 f 64 ( 4 ) {displaystyle f^{64}(4)} ,其中 f ( n ) = 3 n 3 {displaystyle f(n)=3uparrow ^{n}3} 。葛立恒数为此问题的较弱上界,是葛立恒未出版的工作,最后由马丁·加德纳刊登在1977年11月的美国科学人杂志。

定义

定义函数 f ( n ) = 3 n 3 = 3 [ n + 2 ] 3 = 3 3 n {displaystyle f(n)=3uparrow ^{n}3=3[n+2]3=3rightarrow 3rightarrow n} (参见高德纳箭号表示法、超运算、康威链式箭号表示法),则葛立恒数可使用迭代函数表示为 f 64 ( 4 ) {displaystyle f^{64}(4)}

虽然葛立恒数不可以用康威链式箭号表示法很方便地表达,但康威链式箭号表示法能为它简单地定上下界:

3 3 64 2 < {displaystyle 3rightarrow 3rightarrow 64rightarrow 2<} 葛立恒数 < 3 3 65 2 {displaystyle <3rightarrow 3rightarrow 65rightarrow 2}

使用高德纳箭号表示法来表示葛立恒数:

G = 3 3 3 3 ↑↑↑↑ 3 3 3 3 64  layers = 3 ↑↑ 3 ↑↑ 3 ↑↑ 3 ↑↑↑↑ 3 3 3 3 } 64  layers {displaystyle G=underbrace {3uparrow ^{3uparrow ^{3uparrow ^{cdot ^{cdot ^{cdot ^{3uparrow uparrow uparrow uparrow 3}cdot }cdot }cdot }3}3}3} _{64{text{ layers}}}=left.3underbrace {uparrow uparrow cdots cdots cdots cdots uparrow } _{displaystyle 3underbrace {uparrow uparrow cdots cdots cdots uparrow } _{displaystyle underbrace {qquad vdots qquad } _{displaystyle 3underbrace {uparrow uparrow cdots uparrow } _{displaystyle 3uparrow uparrow uparrow uparrow 3}3}}3}3right}64{text{ layers}}}

巨大的葛立恒数

利用超运算,葛立恒数G可以表示为:

3 [ 3 [ 3 [ 3 [ 3 [ 3 64 [ 6 ] 3 + 2 ] 3 + 2 ] 3 ] 3 + 2 ] 3 + 2 ] 3 {displaystyle underbrace {3[3[3[cdots 3[3[3} _{64}[6]3+2]3+2]3cdots ]3+2]3+2]3}

其中, 64 {displaystyle 64} 表示共有64层超运算。从内至外,每一层中的超运算级数由方括号内的那一层所表示的数值决定。 计算G值需要经过64步,首先从最内层开始计算:

g 1 = 3 [ 6 ] 3 = 3 [ 5 ] ( 3 [ 5 ] 3 ) = 3 [ 4 ] ( 3 [ 4 ] ( 3 [ 4 ] ( 3 [ 4 ] ( 3 [ 4 ] 3 3 [ 5 ] 3 ) ) ) ) {displaystyle g_{1}=3[6]3=3[5](3[5]3)=underbrace {3[4](3[4](3[4]cdots (3[4](3[4]3} _{3[5]3}))cdots ))}

让: X = 3 [ 5 ] 3 = 3 [ 4 ] ( 3 [ 4 ] 3 ) = 3 [ 4 ] ( 3 [ 3 ] ( 3 [ 3 ] 3 ) ) = 3 [ 4 ] ( 3 [ 3 ] 27 ) {displaystyle X=3[5]3=3[4](3[4]3)=3[4](3[3](3[3]3))=3[4](3[3]27)}

= 3 [ 4 ] 7625597484987 = 3 [ 3 ] 3 [ 3 ] [ 3 ] 3 7625597484987 = 3 3 . . . 3 7625597484987 {displaystyle =3[4]7625597484987=underbrace {3[3]3[3]cdots [3]3} _{7625597484987}=underbrace {3_{}^{3^{{}^{.,^{.,^{.,^{3}}}}}}} _{7625597484987}} (迭代幂次)
g 1 = 3 [ 6 ] 3 = 3 [ 5 ] ( 3 [ 5 ] 3 ) = 3 [ 5 ] X = 3 [ 4 ] 3 [ 4 ] [ 4 ] 3 X = 3 3 . . . 3 3 3 . . . 3 3 } X {displaystyle g_{1}=3[6]3=3[5](3[5]3)=3[5]X=underbrace {3[4]3[4]cdots [4]3} _{X}=left.underbrace {3^{3^{.^{.^{.{3}}}}}} _{underbrace {3^{3^{.^{.^{.{3}}}}}} _{underbrace {vdots } _{3}}}right}X}

给定函数:

f ( n ) = 3 [ n + 2 ] 3 {displaystyle f(n)=3[n+2]3}

例如: f ( 1 ) = 3 [ 3 ] 3 ,   f ( 2 ) = 3 [ 4 ] 3 {displaystyle f(1)=3[3]3, f(2)=3[4]3}

g 1 = f ( 4 ) = 3 [ 6 ] 3 = 3 [ 5 ] X = 3 [ 4 ] 3 [ 4 ] [ 4 ] 3 X = 3 3 . . . 3 3 3 . . . 3 3 } X {displaystyle g_{1}=f(4)=3[6]3=3[5]X=underbrace {3[4]3[4]cdots [4]3} _{X}=left.underbrace {3^{3^{.^{.^{.{3}}}}}} _{underbrace {3^{3^{.^{.^{.{3}}}}}} _{underbrace {vdots } _{3}}}right}X}

然后计算g2

g 2 = f 2 ( 4 ) = f ( f ( 4 ) ) = 3 [ g 1 + 2 ] 3 {displaystyle g_{2}=f^{2}(4)=f(f(4))=3[g_{1}+2]3}

接着计算:

g 3 = f ( f 2 ( 4 ) ) = 3 [ g 2 + 2 ] 3 {displaystyle g_{3}=f(f^{2}(4))=3[g_{2}+2]3}
{displaystyle vdots vdots }
g 63 = f ( f 62 ( 4 ) ) = 3 [ g 62 + 2 ] 3 {displaystyle g_{63}=f(f^{62}(4))=3[g_{62}+2]3}

最后:

G = g 64 = f 64 ( 4 ) = f ( f ( f 64 ( 4 ) ) ) = 3 [ g 63 + 2 ] 3 {displaystyle G=g_{64}=f^{64}(4)=underbrace {f(f(cdots f} _{64}(4)cdots ))=3[g_{63}+2]3}

一般来说:

g n = 3 [ g n 1 + 2 ] 3 {displaystyle g_{n}=3[g_{n-1}+2]3}

其中:

f 2 ( n ) = f ( f ( n ) ) ,   f 3 ( n ) = f ( f ( f ( n ) ) ) , {displaystyle f^{2}(n)=f(f(n)), f^{3}(n)=f(f(f(n))),} 以此类推。

葛立恒数最尾端的500位数字

...

02425 95069 50647 38395 65747 91365 19351 79833 45353 62521

43003 54012 60267 71622 67216 04198 10652 26316 93551 88780

38814 48314 06525 26168 78509 55526 46051 07117 20009 97092

91249 54437 88874 96062 88291 17250 63001 30362 29349 16080

25459 46149 45788 71427 83235 08292 42102 09182 58967 53560

43086 99380 16892 49889 26809 95101 69055 91995 11950 27887

17830 83701 83402 36474 54888 22221 61573 22801 01329 74509

27344 59450 43433 00901 09692 80253 52751 83328 98844 61508

94042 48265 01819 38515 62535 79639 96189 93967 90549 66380

03222 34872 39670 18485 18643 90591 04575 62726 24641 95387.

事实上,对于所有正整数 n > 500 {displaystyle n>500} 3 [ 4 ] n {displaystyle 3[4]n} 的末500位数也与葛立恒数相同。

与本文近似的文章: