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

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

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

...02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387.

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

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

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

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

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

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

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

${\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 \uparrow 3\end{matrix}}\right\}{\text{64 слоя}}}$,

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

${\displaystyle G=g_{64},}$ где ${\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,}$

где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, ${\displaystyle G}$ вычисляется в 64 шага: на первом шаге мы вычисляем ${\displaystyle g_{1}}$ с четырьмя стрелками между тройками, на втором — ${\displaystyle g_{2}}$ с ${\displaystyle g_{1}}$ стрелками между тройками, на третьем — ${\displaystyle g_{3}}$ с ${\displaystyle g_{2}}$ стрелками между тройками и так далее; в конце мы вычисляем ${\displaystyle G=g_{64}}$ с ${\displaystyle g_{63}}$ стрелок между тройками.

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

${\displaystyle G=f^{64}(4)}$, где ${\displaystyle f(n)=3\uparrow ^{n}3,}$

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

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.}$

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

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

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

${\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 )}}$,

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

${\displaystyle 3\uparrow \uparrow \uparrow 3\ =\ 3\uparrow \uparrow (3\uparrow \uparrow 3).}$

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

${\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}}}}}}$, где X — количество троек.

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

${\displaystyle g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))}$, где количество троек — ${\displaystyle 3\uparrow \uparrow (3\uparrow \uparrow 3)}$.

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

${\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 }$, где число башен — ${\displaystyle \quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3}$,

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

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

1-я башня: 3

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

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

.

.

.

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

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

• Число Райо
• TREE(3)
• Большие числа

• 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.

• Число Грэма на пальцах
• «Проблема Рамсея о гиперкубах». Geoff Exoo (англ.)
• Weisstein, Eric W. Graham’s number (англ.) на сайте Wolfram MathWorld.
• Как вычислить число Грэма (англ.)
• Numeropedia — the Special Encyclopedia of Numbers (англ.)