Перейти к содержанию

Число Грэма

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

Число Грэма (англ. Graham's number) — сверхгигантское число, которое является верхней границей для решения определённой проблемы в теории Рамсея. Является некоторой очень большой степенью тройки, которая записывается с помощью нотации Кнута. Названо в честь Рональда Грэма.

Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке «Математические игры» в журнале Scientific American в ноябре 1977 года, где было сказано: «В неопубликованном доказательстве Грэм недавно установил границу настолько большую, что ей принадлежит рекорд как наибольшему числу, когда-либо использовавшемуся в серьёзном математическом доказательстве».

В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грэма в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. На самом деле вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грэма (предполагается, что запись каждой цифры занимает по меньшей мере объём Планка). Даже степенные башни вида [math]\displaystyle{ a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}} }[/math] бесполезны для этой цели (в том же смысле), хотя это число и может быть записано с использованием рекурсивных формул, таких, как нотация Кнута или эквивалентных, что и было сделано Грэмом. Последние 50 цифр числа Грэма — это 03222348723967018485186439059104575627262464195387.

В современных математических доказательствах иногда встречаются числа, ещё много бо́льшие, чем число Грэма, например, в работе с конечной формой Фридмана в теореме Краскала — так называемое TREE(3).

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

Пример: 2 цвета и 3-мерный куб, содержащий один одноцветный 4-вершинный копланарный полный подграф. Подграф показан ниже куба. Этот куб не будет содержать такой подграф, если, например, нижний край у настоящего подграфа будет заменен на синий — что доказывает с помощью контрпримера, что Н *> 3.

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

Рассмотрим [math]\displaystyle{ n }[/math]-мерный гиперкуб и соединим все пары вершин для получения полного графа с [math]\displaystyle{ 2^n }[/math] вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в синий цвет. При каком наименьшем значении [math]\displaystyle{ n }[/math] каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?

Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, [math]\displaystyle{ N^* }[/math], и показали, что [math]\displaystyle{ 6\leqslant N^* \leqslant N }[/math], где [math]\displaystyle{ N }[/math] — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как [math]\displaystyle{ N = F^7(12) }[/math], где [math]\displaystyle{ F(n) = 2\uparrow^{n} 3 }[/math]. Это число именуется как «малое число Грэма» (англ. Little Graham).

Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что [math]\displaystyle{ N^* }[/math] должно быть не меньше 13. Потом последовало и улучшение верхней границы до [math]\displaystyle{ 2\uparrow^{3} 6 }[/math] и затем до [math]\displaystyle{ 2\uparrow \uparrow 2 \uparrow \uparrow 2 \uparrow \uparrow 9 }[/math]. Таким образом, [math]\displaystyle{ 13\leqslant N^* \leqslant 2\uparrow \uparrow 2 \uparrow \uparrow 2 \uparrow \uparrow 9 }[/math].

Предметом настоящей статьи является верхняя граница [math]\displaystyle{ G }[/math], которая много слабее (то есть больше), чем [math]\displaystyle{ N }[/math]: [math]\displaystyle{ G = f^{64}(4) }[/math], где [math]\displaystyle{ f(n) = 3 \uparrow^n 3 }[/math]. Именно эта граница, описанная в неопубликованной работе Грэма, и была описана (и названа числом Грэма) Мартином Гарднером.

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

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

[math]\displaystyle{ \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 \;\; \vdots \qquad\;\;} \\ & &3 \underbrace{\uparrow \uparrow \cdots \cdot \cdot \uparrow}3 \\ & &3 \uparrow \uparrow \uparrow \uparrow3 \end{matrix} \right \} \text {64 слоя} }[/math],

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

[math]\displaystyle{ G = g_{64}, }[/math] где [math]\displaystyle{ g_1 = 3 \uparrow \uparrow \uparrow \uparrow 3,\ g_n = 3 \uparrow ^{g_{n-1}}3, }[/math]

где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, [math]\displaystyle{ G }[/math] вычисляется в 64 шага: на первом шаге мы вычисляем [math]\displaystyle{ g_1 }[/math] с четырьмя стрелками между тройками, на втором — [math]\displaystyle{ g_2 }[/math] с [math]\displaystyle{ g_1 }[/math] стрелками между тройками, на третьем — [math]\displaystyle{ g_3 }[/math] с [math]\displaystyle{ g_2 }[/math] стрелками между тройками и так далее; в конце мы вычисляем [math]\displaystyle{ G = g_{64} }[/math] с [math]\displaystyle{ g_{63} }[/math] стрелок между тройками.

Это может быть записано как

[math]\displaystyle{ G = f^{64}(4) }[/math], где [math]\displaystyle{ f(n) = 3 \uparrow^n 3, }[/math]

где верхний индекс у [math]\displaystyle{ f }[/math] означает итерации функций. Функция [math]\displaystyle{ f }[/math] является частным случаем гипероператоров [math]\displaystyle{ f(n) = \text{hyper}(3,n+2,3) }[/math] и может также быть записана при помощи цепных стрелок Конвея как [math]\displaystyle{ f(n) = 3 \rightarrow 3 \rightarrow (n+2) }[/math]. Последняя запись также позволяет записать следующие граничные значения для [math]\displaystyle{ G }[/math]:

[math]\displaystyle{ 3\rightarrow 3\rightarrow 64\rightarrow 2 \lt G \lt 3\rightarrow 3\rightarrow 65\rightarrow 2. }[/math]

С помощью массивной нотации Бауэрса границы числа Грэма можно записать как:

{3,64,1,2} < G < {3,65,1,2}.

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

Для того, чтобы осознать размер числа Грэма, полезно попробовать представить через возведение в степень хотя бы первый член (g1) стремительно растущей 64-членной последовательности (т. н. «грааль», Grahal). На языке тетраций [math]\displaystyle{ \uparrow\uparrow }[/math] означает:

[math]\displaystyle{ 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) }[/math],

где число троек в выражении справа

[math]\displaystyle{ 3 \uparrow \uparrow \uparrow 3 \ = \ 3 \uparrow \uparrow (3 \uparrow \uparrow 3). }[/math]

Теперь каждая тетрация ([math]\displaystyle{ \uparrow\uparrow }[/math]) по определению разворачивается в «степенную башню» как

[math]\displaystyle{ 3 \uparrow\uparrow X \ = \ 3 \uparrow \Bigl(3 \uparrow \bigl(3 \uparrow \dots (3 \uparrow 3) \dots \bigr)\Bigr) \ = \ 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}} }[/math], где X — количество троек.

Таким образом,

[math]\displaystyle{ g_1 = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots )) }[/math], где количество троек — [math]\displaystyle{ 3 \uparrow \uparrow (3 \uparrow \uparrow 3) }[/math].

Оно может быть записано на языке степеней:

[math]\displaystyle{ g_1 = \left. \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}\end{matrix} \right \} \left. \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix} \right \} \dots \left. \begin{matrix}3^{3^3}\end{matrix} \right \} 3 \quad }[/math], где число башен — [math]\displaystyle{ \quad \left. \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix} \right \} \left. \begin{matrix}3^{3^3}\end{matrix} \right \} 3 }[/math],

где количество троек в каждой башне, начиная слева, указывается предыдущей башней.

Другими словами, [math]\displaystyle{ g_1 }[/math] вычисляется путём вычисления количества башен, [math]\displaystyle{ n=3^{3^{\cdot^{\cdot^{\cdot^{3}}}}} }[/math] (где число троек — [math]\displaystyle{ 3^{3^{3}} }[/math] = 7 625 597 484 987), и затем вычисления [math]\displaystyle{ n }[/math] башен в следующем порядке:

1-я башня: 3

2-я башня: 3↑3↑3 (количество троек — 3) = 7 625 597 484 987

3-я башня: 3↑3↑3↑3↑…↑3 (количество троек — 7 625 597 484 987) = …

.

.

.

[math]\displaystyle{ g_1 }[/math] = [math]\displaystyle{ n }[/math]-я башня: 3↑3↑3↑3↑3↑3↑3↑…↑3 (количество троек задаётся результатом вычисления [math]\displaystyle{ (n-1) }[/math]-й башни)

Масштаб первого члена, [math]\displaystyle{ g_1 }[/math], настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя [math]\displaystyle{ n }[/math] — это всего лишь количество башен в этой формуле для [math]\displaystyle{ g_1 }[/math], уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно [math]\displaystyle{ 4\cdot 10^{185} }[/math]). Оно уже больше гуголплекса, и вся запись с 7625597484987 тройками уже на третьей башне (так называемое «тритри», Tritri) будет занимать расстояние от Земли до Солнца. Даже башня с четырьмя тройками [math]\displaystyle{ 3^{3^{3^3}}=3^{7\,625\,597\,484\,987}\approx 1{,}3\times 10^{3\,638\,334\,640\,024} }[/math] представляет собой уже слишком большое число, чтобы представить его непосредственно. После первого члена нас ожидают ещё 63 члена стремительно растущей последовательности.

См. также

Литература

  • Graham, R. L.; Rothschild, B. L. Ramsey's Theorem for n-Parameter Sets (англ.) // Transactions of the American Mathematical Society. — 1971. — Vol. 159. — P. 257—292. — doi:10.2307/1996010. The explicit formula for N appears on p. 290.
  • Graham, R. L.; Rothschild, B.L. (1978). «Ramsey Theory», Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80-99. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.
  • Gardner, Martin. Mathematical Games (англ.) // Scientific American. — Springer Nature, 1977. — November (vol. 237). — P. 18—28.; reprinted (revised 2001) in the following book:
  • Martin Gardner. The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems (англ.). — New York, NY: Norton, 2001. — ISBN 0393020231.
  • Martin Gardner. Penrose Tiles to Trapdoor Ciphers (неопр.). — Washington, D.C.: Mathematical Association of America, 1989. — ISBN 0-88385-521-6.
  • Exoo, Geoffrey. A Euclidean Ramsey Problem (неопр.) // Discrete Computational Geometry. — 2003. — Т. 29. — С. 223—227. — doi:10.1007/s00454-002-0780-5.

Ссылки