查看“葛立恆數”的源代码

{{expert|time=2016-09-15T12:22:53+00:00}}
'''葛立恆數'''由[[葛立恆]]提出，曾經被視為在正式數學[[證明]]中出現過最大的數，後來則被{{Link-en|TREE(3)|TREE(3)}}取代。它大得連[[高德納箭號表示法]]也難以簡單表示，而必須使用64層高德納箭號表示法才表示得出來。

[[馬丁·加德納]]於1977年11月在美國[[科學人|科學人雜誌]]的「數學遊戲」專欄將此數刊登出來，1980年被金氏世界紀錄訂為在正式數學[[證明]]中出現過最大的數。

== 問題背景 ==
[[Image:GrahamCube.svg|right|thumb|一個將三維立方體的邊，著上紅藍二色的例子。此例中恰存在一個「四[[顶点 (图论)|頂點]]共平面且單色的完全子圖」，子圖繪於三維立方體的下方。注意到若將此子圖的下方改成蓝色，則此例將不再含有「四頂點共平面且單色的完全子圖」，也就提供了一個反例，證明<math>N^*</math>至少大於3。]]
葛立恆數與[[拉姆齊理論]]有關：考慮一個<math>n</math>維的[[超立方体]]，在連結所有[[顶点 (图论)|頂點]]後，將形成一個<math>2^n</math>個[[顶点 (图论)|頂點]]的[[完全圖]]。將這個圖的每條邊填上紅色或藍色。求<math>n</math>的最小值，才使得所有填法中都必定存在一個在同一平面上有四個頂點的單色完全子圖。

在1971年Graham與Rothschild證明了此題之解<math>N^*</math>的上下界為<math>6 \le N^* \le N</math>，其中<math>N</math>是一個極大但明確定義的數字<math>F^7(12) = F(F(F(F(F(F(F(12)))))))</math>，用[[高德納箭號表示法]]，<math>F</math>可表示為<math>F(n) = 2 \uparrow^n 3</math>；[[康威鏈式箭號表示法]]也可以表示此數的大略範圍，此數介於<math>4 \rightarrow 2 \rightarrow 8 \rightarrow 2</math>與<math>2 \rightarrow 3 \rightarrow 9 \rightarrow 2</math>之間<ref>{{cite web |url=http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html |title=Graham's number records |publisher=Iteror.org |accessdate=2014-04-09 |archive-url=https://web.archive.org/web/20131019135451/http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html |archive-date=2013-10-19 |dead-url=yes }}</ref>，<math>N^*</math>的上界在2014年藉由Hales–Jewett數的上界而降為<math>2 \uparrow \uparrow \uparrow 6</math><ref>{{cite journal |last1=Lavrov|first1=Mikhail |last2=Lee|first2=Mitchell |last3=Mackey|first3=John |date=2014 |title=Improved upper and lower bounds on a geometric Ramsey problem |journal=European Journal of Combinatorics |volume=42 |pages=135–144 |doi=10.1016/j.ejc.2014.06.003}}</ref>；下界則在2003年由Geoffrey Exoo提高為11<ref>{{cite journal |last=Exoo |first=Geoffrey |date=2003 |title=A Euclidean Ramsey Problem |journal=Discrete & Computational Geometry |volume=29 |issue=2 |pages=223–227 |doi=10.1007/s00454-002-0780-5}}Exoo將Graham與Rothschild提出的上界<math>N</math>稱為「葛立恆數」，但這不是馬丁·加德納所說的「葛立恆數」<math>G</math>。
</ref>，並由Jerome Barkley在2008年進一步的提高為13<ref>{{cite arXiv |eprint=0811.1055 |last1=Barkley |first1=Jerome |title=Improved lower bound on an Euclidean Ramsey problem |class=math.CO |year=2008 }}</ref>。因此目前所知最佳的<math>N^*</math>上下界為<math>13 \le N^* \le 2 \uparrow \uparrow \uparrow 6</math>。

葛立恆數<math>G</math>比<math>N</math>大得多，<math>G</math>可表示為<math>f^{64}(4)</math>，其中<math>f(n) = 3 \uparrow^n 3</math>。葛立恆數為此問題的較弱上界，是葛立恆未出版的工作，最後由馬丁·加德納刊登在1977年11月的美國[[科學人雜誌]]<ref>[[馬丁·加德納]] (1977) [http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html "In which joining sets of points leads into diverse (and diverting) paths"] {{Wayback|url=http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html |date=20131019135451 }}. Scientific American, November 1977</ref>。

== 定義 ==
定義函數<math>f(n) = 3 \uparrow^n 3 = 3[n + 2]3 = 3 \rightarrow 3 \rightarrow n</math>（參見[[高德納箭號表示法]]、[[超運算]]、[[康威鏈式箭號表示法]]），則葛立恆數可使用[[疊代函數]]表示為<math>f^{64}(4)</math>。

雖然葛立恆數不可以用康威鏈式箭號表示法很方便地表達，但康威鏈式箭號表示法能為它簡單地定上下界：
:<math>3 \rightarrow 3 \rightarrow 64 \rightarrow 2 <</math>葛立恆數<math>< 3 \rightarrow 3 \rightarrow 65 \rightarrow 2</math>

使用高德納箭號表示法來表示葛立恆數：
:<math>
G = \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}
</math>

== 巨大的葛立恆數 ==
利用[[超運算]]，葛立恆數''G''可以表示為：
:<math>\underbrace{3 [3 [3 [ \cdots 3 [ 3[ 3}_{64} [6] 3+2] 3+2] 3 \cdots ] 3+2] 3+2] 3</math>

其中，<math>64</math>表示共有64層超運算。從內至外，每一層中的超運算級數由方括號內的那一層所表示的數值決定。 計算''G''值需要經過64步，首先從最內層開始計算：
:<math> 
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 )) 
</math>

讓：<math>X
= 3 [5] 3 
= 3 [4] (3 [4] 3) 
= 3 [4] (3 [3] (3 [3] 3))
= 3 [4] (3 [3] 27) </math><br>
:<math>
= 3 [4] 7625597484987 
= \underbrace{3 [3] 3 [3] \cdots [3] 3}_{7625597484987}
= \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}_{7625597484987} </math>（[[迭代冪次]]）

:<math>
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</math>

給定函數：
:<math>f(n) = 3 [n+2] 3</math>

例如：<math>f(1) = 3 [3] 3,\ f(2) = 3 [4] 3</math>

:<math>
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</math>

然後計算g<sub>2</sub>：
:<math>g_2 = f^{2}(4) = f(f(4)) = 3 [g_1+2] 3</math>

接著計算：
:<math>g_3 = f(f^{2}(4)) = 3 [g_2+2] 3</math>

:<math>  
\vdots \vdots
</math>
:<math>g_{63} = f(f^{62}(4)) = 3 [g_{62}+2] 3</math>
最後：
:<math>G = g_{64} = f^{64}(4)= \underbrace{f(f(\cdots f}_{64}(4) \cdots )) = 3 [g_{63}+2] 3</math>

一般來說：
:<math>g_n = 3 [g_{n-1}+2] 3</math>

其中：
:<math>f^{2}(n) = f(f(n)),\ f^{3}(n) = f(f(f(n))),</math> 以此類推。

==葛立恆數最尾端的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.

事實上，對於所有正整數<math>n > 500</math>，<math>3 [4] n</math>的末500位數也與葛立恆數相同。

==参考文献==
{{reflist}}

{{大数}}

[[Category:离散数学]]
[[Category:大数]]

[[pl:Notacja strzałkowa#Liczba Grahama]]