Число Грэма

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грэма в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. На самом деле вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грэма (предполагается, что запись каждой цифры занимает по меньшей мере объём Планка). Даже степенные башни вида бесполезны для этой цели, хотя это число и может быть записано с использованием рекурсивных формул, таких, как стрелочная нотация Кнута или эквивалентных, что и было сделано Грэмом. Последние 50 цифр числа Грэма — это …03222348723967018485186439059104575627262464195387.

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

Проблема Грэма[править | править код]

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

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

Рассмотрим -мерный гиперкуб и соединим все пары вершин для получения полного графа с вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в синий цвет. При каком наименьшем значении каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?

Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, , и показали, что , где  — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как , где . Это число именуется "малое число Грэма" (англ. Little Graham).

Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что должно быть не меньше 13. Потом последовало и улучшение верхней границы до и затем до . Таким образом, .

Предметом настоящей статьи является верхняя граница , которая много слабее (то есть больше), чем : , где . Именно эта граница, описанная в неопубликованной работе Грэма, и была описана (и названа числом Грэма) Мартином Гарднером.

Определение числа Грэма[править | править код]

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

,

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

где

где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, вычисляется в 64 шага: на первом шаге мы вычисляем с четырьмя стрелками между тройками, на втором — с стрелками между тройками, на третьем — с стрелками между тройками и так далее; в конце мы вычисляем с стрелок между тройками.

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

, где

где верхний индекс у означает итерации функций. Функция является частным случаем гипероператоров и может также быть записана при помощи цепных стрелок Конвея как . Последняя запись также позволяет записать следующие граничные значения для :

С помощью массивов Бауэрса границы можно записать в виде {3,64,1,2} (меньшая граница) и {3,65,1,2} (большая граница).

Масштаб числа Грэма[править | править код]

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

,

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

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

, где X — количество троек.

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

, где количество троек — .

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

, где число башен — ,

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

Другими словами, вычисляется путём вычисления количества башен, (где число троек — = 7 625 597 484 987), и затем вычисления башен в следующем порядке:

1-я башня: 3

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

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

.

.

.

= -я башня: 3↑3↑3↑3↑3↑3↑3↑…↑3 (количество троек задаётся результатом вычисления -й башни)

Масштаб первого члена, , настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя  — это всего лишь количество башен в этой формуле для , уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно ). Оно уже больше гуголплекса, и вся запись с 7625597484987 тройками уже на третьей башне (так называемое "тритри", Tritri) протянется до Солнца, если вести запись от Земли. Даже башня с четырьмя тройками уже слишком большое, чтобы представить его непосредственно. После первого члена нас ожидают ещё 63 члена стремительно растущей последовательности.

См. также[править | править код]

Литература[править | править код]

Ссылки[править | править код]