Liczba Grahama

Liczba Grahama - ogromna liczba, która jest górnym oszacowaniem rozwiązania problemu twierdzenia Ramseya. W momencie publikacji była największą liczbą całkowitą dodatnią mającą swoje zastosowanie w dowodzie matematycznym.

Geneza

Liczba Grahama jest związana z następującym problemem teorii Ramseya:

Połącz wszystkie pary geometrycznych wierzchołków n-wymiarowego hipersześcianu aby uzyskać graf pełny na 2n wierzchołkach. Pokoloruj każdą krawędź tego grafu na czerwono lub niebiesko. Jaka jest najmniejsza wartość n, dla której każde takie zabarwienie zawiera co najmniej jeden pełny podgraf o jednym kolorze na płaszczyźnie określonej czterema wierzchołkami?

Dokładna wartość liczby n nie jest znana, wiadomo, że zawiera się w przedziale <math>13 \leqslant n \leqslant G</math> (gdzie G to liczba Grahama).

Definicja

Używając notacji strzałkowej Knutha, liczba Grahama określona jest w następujący sposób

<math> \left.

\begin{matrix}
 G &=&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 warstwy} </math>

gdzie liczba strzałek w poszczególnej warstwie jest określona wartością warstwy poprzedniej:

<math>G = g_{64}, </math>

gdzie <math>g_1=3\uparrow\uparrow\uparrow\uparrow 3, \quad g_n = 3\uparrow^{g_{n-1}}3,</math>

gdzie indeks górny strzałki symbolizuje ilość strzałek. Innymi słowy, G jest zdefiniowana w 64 krokach - pierwszym z nich jest obliczenie g₁, z czterema strzałkami pomiędzy trójkami; kolejnym krokiem jest obliczenie g₂ z g₁ strzałkami pomiędzy trójkami; kolejnym krokiem jest obliczenie g₃ z g₂ strzałkami pomiędzy trójkami, i tak dalej, aż do osiągnięcia G = g₆₄ z g₆₃ strzałkami pomiędzy trójkami.

Notacja strzałkowa Knutha

Dla osób niezaznajomionych z tak zwaną notacją strzałkową - jest ona używana do zapisywania bardzo dużych liczb; została wprowadzona przez amerykańskiego matematyka Donalda Knutha w 1976 roku. Ideą tej metody jest iterowane potęgowanie, w sposób podobny do tego, jak potęgowanie jest iterowanym mnożeniem, mnożenie jest iterowanym dodawaniem, a dodawanie jest iterowaną inkrementacją. Celem tej notacji było zapisanie bardzo dużych liczb, których nawet zapisanie w postaci wykładniczej było trudne lub niemożliwe do wykonania.

Zaczynając od początku, operacje dodawania, mnożenia i potęgowania mogą być zdefiniowane w następujący sposób.

Dodawanie to iterowana inkrementacja:

<math>

 \begin{matrix}
  a+b & = & a+\underbrace{1+1+\dots+1} \\
  & & b\mbox{ razy}
 \end{matrix} 
</math>

Mnożenie to iterowane dodawanie:

<math>

 \begin{matrix}
  a\cdot b & = & \underbrace{a+a+\dots+a} \\
  & & b\mbox{ razy}
 \end{matrix} 
</math>

Dla przykładu:

<math>

 \begin{matrix}   3\cdot 4 & = & \underbrace{3+3+3+3} & = & 12\\
  & & 4\mbox{ razy}
 \end{matrix} 
</math>

Potęgowanie to iterowane mnożenie, które w notacji strzałkowej jest zdefiniowane pojedynczą strzałką:

<math>

 \begin{matrix}
  a\uparrow b= a^b = & \underbrace{a\cdot a\cdot\dots\cdot a}\\
  & b\mbox{ razy}
 \end{matrix} 
</math>

Dla przykładu:

<math>

 \begin{matrix}
  4\uparrow 3= 4^3 = & \underbrace{4\cdot 4\cdot 4} & = & 64\\
  & 3\mbox{ razy}
 \end{matrix} 
</math>

Aby rozszerzyć tą sekwencję ponad potęgowanie, Knuth zdefiniował dwie strzałki jako iterowane potęgowanie (tak zwana tetracja):

<math>

 \begin{matrix}
  a\uparrow\uparrow b =&  \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & 
  = & \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))} 

\\

   & b\mbox{ razy}
   & & b\mbox{ razy}
 \end{matrix}
</math>

Dla przykładu:

<math>

 \begin{matrix}
  4\uparrow\uparrow 3 = & \underbrace{4^{4^4}} & 
  = & \underbrace{4\uparrow (4\uparrow 4)} & = & 4^{256} & \approx & 1{,}34078079\cdot 10^{154}&

\\

   & 3\mbox{ razy}
   & &3\mbox{ razy}
 \end{matrix} 
</math>