Число Грэма в математике¶

Число Грэма — это огромное натуральное число, которое долгое время считалось самым большим числом, когда-либо использованным в математическом доказательстве. Оно было предложено американским математиком Рональдом Грэмом в 1971 году в рамках решения одной из задач теории Рамсея, связанной с раскраской рёбер многомерных гиперкубов.

¶История появления

Число Грэма возникло в контексте работы над проблемой, относящейся к разделу комбинаторики, известному как теория Рамсея. В 1971 году Рональд Грэм и Брюс Ротшильд исследовали задачу о раскраске рёбер n-мерного гиперкуба в два цвета. Вопрос заключался в том, при каком минимальном числе измерений n любая такая раскраска обязательно будет содержать определённую одноцветную конфигурацию — полный подграф на четырёх вершинах, лежащих в одной плоскости.

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

¶Нотация стрелок Кнута

Чтобы понять масштаб числа Грэма, необходимо разобраться в нотации стрелок:

• Одна стрелка (↑) означает обычное возведение в степень: a↑b = a^b.
• Две стрелки (↑↑) означают тетрацию, то есть повторное возведение в степень: a↑↑b = a↑(a↑(...↑a)) с b множителями.
• Три стрелки (↑↑↑) — это повторная тетрация, и так далее.

Уже число 3↑↑3 = 3^(3^3) = 3^27 = 7 625 597 484 987 — это более 7,6 триллиона. Число 3↑↑↑3 невообразимо больше: это башня из троек высотой в 7,6 триллиона уровней.

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

Число Грэма определяется через рекурсивную последовательность. Первый член последовательности — это g₁ = 3↑↑↑↑3 (четыре стрелки). Каждый следующий член gₙ₊₁ вычисляется как число, содержащее gₙ стрелок между тройками: gₙ₊₁ = 3↑^(gₙ)3.

Само число Грэма — это 64-й член этой последовательности, то есть G = g₆₄.

Для наглядности: g₁ = 3↑↑↑↑3 — это уже невообразимо огромное число. g₂ = 3↑^(g₁)3 — это число, в записи которого используется g₁ стрелок, то есть оно несопоставимо больше g₁. Каждый последующий шаг увеличивает число колоссальными темпами, и после 64 таких шагов получается число, которое невозможно выразить в десятичной записи даже теоретически.

¶Свойства

Число Грэма не является бесконечным — это конечное число, но его точное значение не может быть записано в стандартной десятичной форме из-за ограничений физической Вселенной. Количество цифр в числе Грэма настолько велико, что превосходит число атомов в наблюдаемой Вселенной (которое оценивается примерно в 10^80), причём многократно.

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

¶Значение в математике

Число Грэма сыграло важную роль в развитии комбинаторики и теории Рамсея. Оно продемонстрировало, что даже для простых на первый взгляд задач верхние границы могут быть настолько огромными, что выходят за пределы интуитивного понимания.

В 2013 году верхняя граница для исходной задачи была значительно улучшена. Математики показали, что минимальное число измерений n не превышает 2↑↑↑6, что гораздо меньше числа Грэма, хотя всё ещё является астрономически большим. Тем не менее, число Грэма осталось в истории как символ непостижимо больших величин и вошло в Книгу рекордов Гиннесса как самое большое число, когда-либо использованное в математическом доказательстве.

¶Интересные факты

• Число Грэма часто используется в популярной математике как пример числа, которое невозможно представить или записать.
• Для записи числа Грэма в стандартной нотации потребовалось бы больше знаков, чем существует частиц в наблюдаемой Вселенной.
• Существуют числа, значительно превосходящие число Грэма, например, числа, возникающие в доказательствах Харви Фридмана, но они не получили такой же широкой известности.

¶Источники

• Грэм Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики.
• Кнут Д. Е. Mathematics and Computer Science: Coping with Finiteness.
• Статья Рональда Грэма о верхней границе в задаче теории Рамсея, 1971 год.