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

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

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

...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 : . 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 . (англ.) . — 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 : .

Ссылки

• « ». Geoff Exoo (англ.)
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• (англ.)
• (англ.)