Число Грэма

Число Грэма  — большое число, которое является верхнейграницей для решения определённой проблемы в теории Рамсея. Являетсянекоторой очень большой степенью тройки, которая записывается с помощьюстрелочной нотации Кнута. Названо в честь Рональда Грэма.
 Оно стало известно широкой публике после того, как Мартин Гарднер описалего в своей колонке «Математические игры» в журнале 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 \{64layers\} ,


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

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 \{uparrow3)
 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 члена стремительно растущейпоследовательности.