Число Грэма

Число Грэма  — большое число, которое является верхней границей для решения определённой проблемы в теории Рамсея. Является некоторой очень большой степенью тройки, которая записывается с помощью стрелочной нотации Кнута. Названо в честь Рональда Грэма.
 Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке «Математические игры» в журнале Scientific American в ноябре 1977 года, где было сказано: «В неопубликованном доказательстве Грэм недавно установил \ldots границу настолько большую, что ей принадлежит рекорд как наибольшему числу, когда-либо использовавшемуся в серьёзном математическом доказательстве».
 В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грэма в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. На самом деле вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грэма (предполагается, что запись каждой цифры занимает по меньшей мере объём Планка). Даже степенные башни вида abc бесполезны для этой цели, хотя это число и может быть записано с использованием рекурсивных формул, таких, как стрелочная нотация Кнута или эквивалентных, что и было сделано Грэмом. Последние 50 цифр числа Грэма — это \ldots03222348723967018485186439059104575627262464195387.
 В современных математических доказательствах иногда встречаются числа, ещё много большие, чем число Грэма, например, в работе с конечной формой Фридмана в теореме Краскала.

Проблема Грэма


 Число Грэма связано со следующей проблемой в теории Рамсея:

Рассмотрим n-мерный гиперкуб и соединим все пары вершин для получения полного графа с 2n вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в синий цвет. При каком наименьшем значении n каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?
  Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, N, и показали, что 6NN, где N — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как N=F7(12), где F(n)=2n3.
 Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что N должно быть не меньше 13. Таким образом, 13NN.
 Предметом настоящей статьи является верхняя граница G, которая много слабее (то есть больше), чем N: G=f64(4), где f(n)=3n3. Именно эта граница, описанная в неопубликованной работе Грэма, и была описана (и названа числом Грэма) Мартином Гарднером.

Определение числа Грэма


 При использовании Стрелочной нотации Кнута число Грэма G может быть записано как


 \{left.
 \texttt\{begin\{matrix\} \\\texttt G \&=\&3 \{underbrace\{\{uparrow \{uparrow \{cdots \{cdots \{cdots \{cdots \{cdots \{uparrow\}3 \{\{\\\texttt   \& \&3 \{underbrace\{\{uparrow \{uparrow \{cdots \{cdots \{cdots \{cdots \{uparrow\}3 \{\{ \\\texttt   \& \& \{underbrace\{\{qquad \{;\{; \{vdots \{qquad\{;\{;\} \{\{ \\\texttt   \& \&3 \{underbrace\{\{uparrow \{uparrow \{cdots \{cdot \{cdot \{uparrow\}3 \{\{\\\texttt   \& \&3 \{uparrow \{uparrow \{uparrow \{uparrow3\\\texttt\{end\{matrix\} 
 \{right \{\} \{text \{64 layers\} ,


 где количество стрелок в каждом слое, начиная с верхнего, определяется числом в следующем слое, то есть

G=g64, где g1=3↑↑↑↑3, gn=3gn13,
  где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, G вычисляется в 64 шага: на первом шаге мы вычисляем g1 с четырьмя стрелками между тройками, на втором — g2 с g1 стрелками между тройками, на третьем — g3 с g2 стрелками между тройками и так далее; в конце мы вычисляем G=g64 с g63 стрелок между тройками.
 Это может быть записано как

G=f64(4), где f(n)=3n3,
  где верхний индекс у f означает итерации функций. Функция f является частным случаем гипероператоров f(n)=hyper(3,n+2,3) и может также быть записана при помощи цепных стрелок Конвея как f(n)=33(n+2). Последняя запись также позволяет записать следующие граничные значения для G:

33642<G<33652.

Масштаб числа Грэма


 Для того, чтобы осознать невероятный размер числа Грэма, полезно попробовать представить через возведение в степень хотя бы первый член (g1) стремительно растущей 64-членной последовательности. На языке тетраций ↑↑ означает:


  g\_1 = 3 \{uparrow \{uparrow \{uparrow \{uparrow 3

3 \{

uparrow \{uparrow \{uparrow (3 \{uparrow \{uparrow \{uparrow 3)
 3 \{uparrow\{uparrow \{Bigl(3 \{uparrow\{uparrow \{bigl(3 \{uparrow\{uparrow \{ \{dots \{ (3 \{uparrow\{uparrow 3) \{dots \{bigr)\{Bigr) ,
 где число троек в выражении справа

3↑↑↑3 = 3↑↑(3↑↑3).
  Теперь каждая тетрация (↑↑) по определению разворачивается в «степенную башню» как

3↑↑X = 3(3(3(33))) = 333, где X — количество 3-ек.
  Таким образом,

g1=3↑↑(3↑↑(3↑↑  (3↑↑3))), где количество троек — 3↑↑(3↑↑3).
  Оно может быть записано на языке степеней:


  g\_1 =
 \texttt \{left. \\\texttt   \{begin\{matrix\}3\^\{3\^\{\{cdot\^\{\{cdot\^\{\{cdot\^\{\{cdot\^\{3\}\}\}\}\}\}\{end\{matrix\}\\\texttt \{right \{\} \\\texttt \{left. \\\texttt   \{begin\{matrix\}3\^\{3\^\{\{cdot\^\{\{cdot\^\{\{cdot\^\{3\}\}\}\}\}\{end\{matrix\}\\\texttt \{right \{\}\\\texttt   \{dots \\\texttt \{left. \\\texttt   \{begin\{matrix\}3\^\{3\^3\}\{end\{matrix\}\\\texttt \{right \{\}\\\texttt   3\\\texttt \{quad \texttt, где число башен — 333}333}3\texttt,
 где количество троек в каждой башне, начиная слева, указывается предыдущей башней.
 Другими словами, g1 вычисляется путём вычисления количества башен, n=333 (где число троек — 333 = 7625597484987), и затем вычисления n башен в следующем порядке:
 1-я башня: 3
 2-я башня: 3↑3↑3 (количество троек — 3) = 7625597484987
 3-я башня: 3↑3↑3↑3↑\ldots↑3 (количество троек — 7625597484987) = \ldots
 .
 .
 .
g1 = n-я башня: 3↑3↑3↑3↑3↑3↑3↑\ldots↑3 (количество троек задаётся результатом вычисления (n1)-й башни)
 Масштаб первого члена, g1, настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя n — это всего лишь количество башен в этой формуле для g1, уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно 8,510185). После первого члена нас ожидают ещё 63 члена стремительно растущей последовательности.