Число Грэма¶
Число Грэма — верхняя граница, предложенная математиком Роном Грэмом в 1971 году для решения задачи о гиперкубе. Значение числа настолько велико, что его невозможно записать в стандартной десятичной системе счисления, а для его обозначения используются специальные многократно вложенные операции, такие как стрелочная нотация Кнута и функция Акермана. Число Грэма считается одним из самых больших чисел, когда-либо использованных в серьёзных математических доказательствах.
¶История
Число было введено в 1971 году американским математиком Рональдом Грэмом (Ronald Graham, 1935—2020) в ходе работы над комбинаторной задачей, связанной с гиперкубом. Задача была сформулирована в статье, посвящённой проблеме Рамсея, и опубликована в 1977 году в соавторстве с Джозефом Бёркхардтом и Элвином С. Ротом. Грэм доказал, что для определённого конечного графа, построенного на вершинах n-мерного гиперкуба, при определённых условиях раскраски его рёбер число вершин, при котором гарантировано появление одноцветного полного подграфа, не превышает некоторого числа G. Это число и получило название «число Грэма».
Задача формулируется следующим образом: каждая пара вершин n-мерного гиперкуба соединяется рёбром, и каждое ребро раскрашивается в один из четырёх цветов. Требуется найти минимальное n, при котором при любой раскраске обязательно существует одноцветный полный подграф на четырёх вершинах. Грэм доказал, что такое n существует и не превышает определённого числа, которое впоследствии стало известно как число Грэма.
¶Способы записи
Число Грэма настолько велико, что его невозможно представить в виде обычного числа с конечным числом цифр. Для его записи используются иерархические конструкции.
¶Стрелочная нотация
Стрелочная нотация Кнута позволяет записывать гипероперации компактно. Одна стрелка обозначает возведение в степень, две стрелки — тетрацию (повторённое возведение в степень), три стрелки — пентацию и так далее. Число Грэма можно записать как многократно вложенную конструкцию из стрелок, где количество стрелок определяется предыдущим уровнем вложенности.
¶Функция Акермана
Функция Акермана — рекурсивная функция, растущая быстрее любого примитивно-рекурсивного числа. Число Грэма можно выразить через функцию Акермана с определёнными аргументами, причём уровень вложенности функции также определяется предыдущим уровнем.
¶Конкретная запись
Число Грэма можно описать следующим образом. Пусть g₁ = 3↑↑↑↑3 (где ↑↑↑↑ — гипероперация с четырьмя стрелками). Затем g₂ = 3↑^(g₁)3, где количество стрелок равно g₁. Далее g₃ = 3↑^(g₂)3, и так далее. Число Грэма равно g₆₄, то есть результату 64-кратного применения этой процедуры. Каждый следующий уровень gᵢ определяется предыдущим, и уже g₂ представляет собой число, которое невозможно записать в виде обычного числа с конечным числом цифр.
¶Сравнение с другими большими числами
Число Грэма значительно превосходит многие известные большие числа, такие как число Скьюса, число Мозера и число Грэма-Рамсея. Оно также значительно больше числа Грэма, используемого в других контекстах, таких как число Грэма в теории Рамсея.
| Число | Приближённая величина |
|---|---|
| 10¹⁰⁰ (гугол) | 10¹⁰⁰ |
| 10^(10^100) (гуголплекс) | 10^(10^100) |
| Число Мозера | 10^(10^(10^...)) |
| Число Грэма | g₆₄ |
¶Значение
Число Грэма стало символом того, насколько огромными могут быть числа, возникающие в математике. Оно широко используется в популяризации математики и в литературе, посвящённой большим числам. В 2014 году число Грэма было включено в Книгу рекордов Гиннесса как одно из самых больших чисел, когда-либо использованных в серьёзных математических доказательствах.
¶Интересные факты
- Рон Грэм был не только математиком, но и профессиональным жонглёром. Он установил рекорд, продержавшийся много лет, по количеству одновременно жонглируемых объектов.
- Грэм был женат на писательнице и математике Фанни Грэм (Fanny Graham).
- Число Грэма было упомянуто в книге «Числа: Руководство по числам» (The Book of Numbers) Джона Конвея и Ричарда Гая.
¶Источники
- Graham R. L., Rothschild B. L., Spencer J. H. Ramsey Theory. — New York: John Wiley & Sons, 1980.
- Conway J. H., Guy R. K. The Book of Numbers. — New York: Copernicus, 1996.
- Weisstein E. W. Graham's Number // MathWorld — A Wolfram Web Resource.
