WikiSort.ru - Не сортированное

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

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

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

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

Проблема Грэма

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

Рассмотрим ${\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}$ .

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

Предметом настоящей статьи является верхняя граница ${\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 layers}}}$ ,

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

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

См. также

• Теорема Краскала^[en]*

Литература

• Graham, R. L.; Rothschild, B. L. (1971). “Ramsey's Theorem for n-Parameter Sets”. Transactions of the American Mathematical Society. 159: 257–292. DOI:10.2307/1996010. Используется устаревший параметр |coauthors= (справка) 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 (November 1977). “Mathematical Games”. Scientific American. 237: 18–28. Используется устаревший параметр |month= (справка); reprinted (revised 2001) in the following book:
• Gardner, Martin. The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. — New York, NY : Norton, 2001. — ISBN 0393020231.
• Gardner, Martin. Penrose Tiles to Trapdoor Ciphers. — Washington, D.C. : Mathematical Association of America, 1989. — ISBN 0-88385-521-6.
• Exoo, Geoffrey (2003). “A Euclidean Ramsey Problem”. Discrete Computational Geometry. 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 (англ.)