Число Грэма: как устроена верхняя граница

Число Грэма - это конкретное натуральное число, которое долгое время держало рекорд как самое большое число, реально использованное в строгом математическом доказательстве. Оно возникло как верхняя граница в одной задаче теории Рамсея, и его размер настолько чудовищен, что обычная запись «цифрами» невозможна в принципе: во Вселенной не хватит частиц, чтобы выписать даже число его десятичных знаков. Чтобы вообще говорить о таком числе, нужна особая запись - стрелочная нотация Кнута. Ниже разберём, как из неё собирается верхняя граница, и калькулятор покажет, как быстро всё взрывается уже на первом шаге.

Откуда взялось число Грэма

Число названо в честь математика Рональда Грэма, который в 1970-х получил его как верхнюю оценку в задаче из комбинаторной теории Рамсея. Сама задача формулируется просто: рассматриваются вершины $n$-мерного гиперкуба, все пары вершин соединены рёбрами, и каждое ребро красят в один из двух цветов. Вопрос - при каком наименьшем $n$ любая такая раскраска обязательно содержит одноцветный «плоский» полный подграф на четырёх вершинах.

Грэм доказал, что такое $n$ заведомо существует и не превосходит некоторого огромного числа $G$. Это $G$ и есть число Грэма. Любопытно, что нижняя граница задачи долго оставалась смехотворно маленькой по сравнению с верхней: было известно лишь, что ответ не меньше 6 (позже 11, затем 13). Разрыв между «не меньше 13» и «не больше числа Грэма» - один из самых драматичных в математике.

Рассчитать для своей задачи

Важно понимать: число Грэма - это именно граница, а не точный ответ задачи. Настоящее искомое $n$, скорее всего, совсем небольшое. Но методы доказательства давали лишь грубую оценку сверху, и эта оценка оказалась невообразимо больше истинного значения.

Стрелочная нотация Кнута: как вообще записать гиганта

Обычные операции выстраиваются в лестницу. Сложение - это повторённый счёт, умножение - повторённое сложение, возведение в степень - повторённое умножение. Дональд Кнут предложил продолжить эту лестницу дальше с помощью стрелок $\uparrow$.

Одна стрелка - это просто степень:

$$3 \uparrow 3 = 3^3 = 27.$$

Две стрелки - тетрация, то есть башня степеней. Запись $3 \uparrow\uparrow n$ означает башню из $n$ троек, которая вычисляется сверху вниз:

$$3 \uparrow\uparrow 3 = 3^{3^{3}} = 3^{27} = 7\,625\,597\,484\,987.$$

Уже три тройки дают почти восемь триллионов. Добавим один этаж - и $3 \uparrow\uparrow 4 = 3^{7\,625\,597\,484\,987}$ становится числом примерно с 3,6 триллионами знаков. Три стрелки - пентация - означают повторённую тетрацию:

$$3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow (3 \uparrow\uparrow 3) = 3 \uparrow\uparrow 7\,625\,597\,484\,987,$$

то есть башню степеней высотой в семь с лишним триллионов этажей. Каждая новая стрелка - это не «чуть больше», а скачок на целый уровень бесконечной иерархии гипероперций. По духу это близко к числу Скьюза - ещё одному знаменитому гиганту, который записывают через многоэтажную степень, а не цифрами.

Рассчитать для своей задачи

Как из слоёв собирается верхняя граница

Теперь главный фокус. Число Грэма строится не одной стрелкой и не двумя, а последовательностью слоёв, где количество стрелок само определяется предыдущим слоём.

Первый слой:

$$g_1 = 3 \uparrow\uparrow\uparrow\uparrow 3.$$

Здесь уже четыре стрелки - гипероперация настолько высокого порядка, что $g_1$ невообразимо больше всего, что мы выписали выше. Но это только начало. Каждый следующий слой использует столько стрелок, сколько равно предыдущему слою:

$$g_{k} = 3 \underbrace{\uparrow \cdots \uparrow}_{g_{k-1}} 3.$$

То есть в $g_2$ между тройками стоит $g_1$ стрелок. В $g_3$ - уже $g_2$ стрелок. И так далее. Число Грэма - это 64-й слой:

$$G = g_{64}.$$

Осознать это почти невозможно: количество стрелок в записи $g_2$ само по себе чудовищно велико, а таких удвоений-надстроек делается 64 раза. Калькулятор выше показывает рост только самой нижней операции - тетрации $3 \uparrow\uparrow n$, и даже он на высоте башни 5–6 уже выходит за пределы любого формата. А полное число Грэма стоит несоизмеримо выше.

Почему точное значение нельзя записать

У числа Грэма нет «десятичной записи» в обычном смысле - и дело не в том, что её трудно посчитать, а в том, что её физически негде разместить. Количество цифр в этом числе само по себе настолько велико, что превосходит число атомов в наблюдаемой Вселенной не на порядки, а на немыслимые «этажи» тетрации. Даже число цифр у числа цифр невозможно записать.

При этом - и это красивый парадокс - последние цифры числа Грэма известны точно. Последовательность степеней тройки по модулю $10^k$ периодична, поэтому конечный «хвост» десятичной записи можно вычислить рекуррентно, поднимаясь по этажам башни и каждый раз беря остаток. Например, число Грэма оканчивается на $\ldots 2\,464\,195\,387$. Мы знаем, чем оно кончается, но не знаем - и не можем узнать - с чего начинается.

Чтобы прочувствовать масштаб, полезен другой угол. Если бы каждую цифру числа Грэма мы записали на отдельном протоне, всех протонов Вселенной не хватило бы даже на запись числа его цифр. И это число цифр само по себе тоже невыразимо - его число цифр снова невыразимо, и так далее на огромную глубину. Именно поэтому единственная честная мера величины здесь - не «сколько знаков», а «сколько раз нужно взять логарифм», то самое, что считает калькулятор выше для нижней операции.

Зачем нужны такие числа

Может показаться, что число Грэма - курьёз ради рекорда. На деле оно показывает, насколько грубыми бывают верхние границы в комбинаторике: метод доказательства гарантирует существование ответа, но даёт оценку, бесконечно далёкую от истины. Это типичная ситуация в комбинаторике, где даже хроматический полином графа и подсчёт раскрасок быстро упираются в гигантские величины, хотя сами объекты конечны.

С тех пор рекорд «самого большого числа в доказательстве» был побит (например, числами из теоремы Краскала и TREE(3)), но число Грэма осталось каноническим примером того, как стрелочная нотация Кнута позволяет хотя бы записать величину, которую невозможно представить.

Частые ошибки

• Путают число Грэма с бесконечностью. Это конечное натуральное число: у него есть последняя цифра, его можно сравнивать с другими числами. Оно просто очень большое.
• Считают $G$ точным ответом задачи Рамсея. Нет, это лишь верхняя граница; истинное искомое $n$, по современным оценкам, совсем небольшое.
• Читают стрелки как обычную степень. Две стрелки $3 \uparrow\uparrow n$ - это башня степеней, а не $3^n$ и не $3 \cdot n$. Порядок операции задаёт количество стрелок.
• Думают, что слоёв «всего 4», потому что в $g_1$ четыре стрелки. Стрелок в $g_1$ четыре, а слоёв $g_k$ - шестьдесят четыре, и каждый следующий неизмеримо больше предыдущего.
• Пытаются «прикинуть число знаков». Уже у $3 \uparrow\uparrow 5$ число десятичных знаков само не помещается в запись - оценивать имеет смысл только высоту лестницы логарифмов.

FAQ

Чему равно число Грэма «в цифрах»? Записать его цифрами невозможно: количество знаков превосходит любые физические масштабы. Корректная запись - только через стрелочную нотацию Кнута как $g_{64}$. Известны лишь последние цифры: оно оканчивается на $\ldots 387$.

Почему именно 64 слоя? Так получилось из самого доказательства Грэма: оценка сверху давала ровно такую конструкцию из 64 шагов надстройки стрелок. Число 64 не несёт особого смысла, кроме как «столько потребовалось методу».

Это и есть самое большое число в математике? Нет. Число Грэма было рекордом для чисел, реально фигурировавших в доказательстве, но позже его превзошли (TREE(3), числа из теоремы Краскала). А функций, растущих ещё быстрее, бесконечно много.

Коротко

Число Грэма - конечное, но невообразимо огромное натуральное число, возникшее как верхняя граница в задаче теории Рамсея о раскраске рёбер гиперкуба. Его нельзя записать цифрами, поэтому используют стрелочную нотацию Кнута: одна стрелка - степень, две - башня степеней (тетрация), три и больше - гипероперации ещё выше. Само число собирается из 64 слоёв $g_k$, где количество стрелок в каждом слое равно предыдущему слою, а $G = g_{64}$. Известны только последние цифры числа; первые - принципиально нет.