номер Грэма

Эта статья об очень большом числе, названном в честь Рональда Грэма. Чтобы узнать об инвестиционном термине, названном в честь Бенджамина Грэма, см. Число Грэма .

Число Грэма — огромное число , возникшее как верхняя граница ответа на задачу из математической области теории Рэмсея . Оно намного больше, чем многие другие большие числа, такие как число Скьюза и число Мозера , которые, в свою очередь, намного больше гуголплекса . Как и в случае с ними, оно настолько велико, что наблюдаемая Вселенная слишком мала, чтобы содержать обычное цифровое представление числа Грэма, если предположить, что каждая цифра занимает один планковский объем , возможно, наименьшее измеримое пространство. Но даже количество цифр в этом цифровом представлении числа Грэма само по себе было бы числом настолько большим, что его цифровое представление невозможно представить в наблюдаемой Вселенной. Не может даже количество цифр этого числа — и так далее, во много раз намного превышающее общее число планковских объемов в наблюдаемой Вселенной. Таким образом, число Грэма не может быть выражено даже с помощью физических силовых башен вселенского масштаба вида $a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$, хотя число Грэма действительно является степенью 3.

Однако число Грэма может быть явно задано с помощью вычислимых рекурсивных формул с использованием обозначения Кнута со стрелкой вверх или его эквивалента, как это сделал Рональд Грэм , тезка числа. Поскольку для его определения существует рекурсивная формула, оно намного меньше, чем типичные числа занятых бобров , последние из которых растут быстрее, чем любая вычислимая последовательность. Хотя последовательность цифр числа Грэма слишком велика, чтобы ее можно было вычислить полностью, ее можно вычислить явно с помощью простых алгоритмов; последние 13 цифр: ...7262464195387. Используя обозначение Кнута, направленное вверх , число Грэма равно $g_{64}$, где $$g_{n}={\begin{cases}3\uparrow \uparrow \uparrow \uparrow 3,&{\text{if }}n=1{\text{ and}}\\3\uparrow ^{g_{n-1}}3,&{\text{if }}n\geq 2.\end{cases}}$$

Число Грэма использовалось Грэмом в беседах с научно-популярным писателем Мартином Гарднером как упрощенное объяснение верхних границ проблемы, над которой он работал. В 1977 году Гарднер описал это число в журнале Scientific American , представив его широкой публике. На момент своего появления это было самое большое конкретное положительное целое число, которое когда-либо использовалось в опубликованных математических доказательствах. Это число было описано в Книге рекордов Гиннеса 1980 года , что еще больше усилило его популярный интерес. Другие конкретные целые числа (такие как TREE(3) ), которые, как известно, намного превышают число Грэма, с тех пор появлялись во многих серьезных математических доказательствах, например, в связи с Харви Фридмана различными конечными формами теоремы Краскала . Кроме того, с тех пор была доказана справедливость меньших верхних границ проблемы теории Рэмси, из которой было получено число Грэма.

Контекст

Пример двухцветного трехмерного куба, содержащего один одноцветный 4-вершинный копланарный полный подграф. Подграф показан под кубом. Этот куб не содержал бы такого подграфа, если бы, например, нижнее ребро в текущем подграфе было заменено синим ребром – тем самым доказывая контрпримером, что N * > 3.

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

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

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

$N=F^{7}(12)=F(F(F(F(F(F(F(12))))))),$

где $F(n)=2\uparrow ^{n}3$ в обозначении Кнута, направленном вверх ; это число находится в диапазоне от 4 → 2 → 8 → 2 до 2 → 3 → 9 → 2 в обозначении цепочки стрелок Конвея . В 2014 году это значение было уменьшено за счет верхних границ числа Хейлса – Джуитта до

$N'=2\uparrow \uparrow 2\uparrow \uparrow (3+2\uparrow \uparrow 8),$

который содержит три тетрации . В 2019 году это было дополнительно улучшено:

$N''=(2\uparrow \uparrow 5138)\cdot ((2\uparrow \uparrow 5140)\uparrow \uparrow (2\cdot 2\uparrow \uparrow 5137))\ll 2\uparrow \uparrow (2\uparrow \uparrow 5138)$

Нижняя граница в 6 позже была улучшена до 11 Джеффри Эксу в 2003 году. и до 13 Джерома Баркли в 2008 году. Таким образом, наиболее известные оценки для N* : 13 ≤ N* ≤ N'' .

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

Публикация

Число привлекло определенное внимание общественности, когда Мартин Гарднер описал его в разделе «Математические игры» журнала Scientific American в ноябре 1977 года, написав, что Грэм недавно установил в неопубликованном доказательстве «предел настолько обширный, что он является рекордсменом по количеству самое большое число, когда-либо использованное в серьёзном математическом доказательстве». 1980 года Книга рекордов Гиннеса повторила утверждение Гарднера, усилив общественный интерес к этому числу. По словам физика Джона Баэза , Грэм в разговоре с Гарднером изобрел величину, ныне известную как число Грэма. Пока Грэм пытался объяснить результат теории Рэмсея, который он получил вместе со своим сотрудником Брюсом Ли Ротшильдом , Грэм обнаружил, что указанную величину объяснить легче, чем фактическое число, фигурирующее в доказательстве. Поскольку число, которое Грэм описал Гарднеру, больше, чем число в самой статье, оба являются действительными верхними оценками для решения проблемы, изучаемой Грэмом и Ротшильдом.

Определение

Используя обозначение Кнута, направленное вверх , число Грэма G (как определено в статье Гарднера в журнале Scientific American ) равно $$\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 \quad \vdots \qquad \quad } \\&&3\underbrace {\uparrow \uparrow \cdots \cdots \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 layers}}$$

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

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

и где верхний индекс на стрелке вверх указывает, сколько стрелок имеется. Другими словами, G рассчитывается за 64 шага: первый шаг — вычислить g ₁ с четырьмя стрелками вверх между тройками; второй шаг — вычислить g ₂ со g ₁ стрелками вверх между 3 с; третий шаг — вычислить g ₃ со g ₂ стрелками вверх между 3 с; и так далее, пока, наконец, не вычислим G = g ₆₄ со g ₆₃ стрелками вверх между 3 с.

Эквивалентно, $$G=f^{64}(4),{\text{ where }}f(n)=3\uparrow ^{n}3,$$

а верхний индекс у f указывает на итерацию функции , например: $f^{4}(n)=f(f(f(f(n))))$. Выражается через семейство гиперопераций ${\text{H}}_{0},{\text{H}}_{1},{\text{H}}_{2},\cdots$, функция f представляет собой конкретную последовательность $f(n)={\text{H}}_{n+2}(3,3)$, которая является версией быстро растущей функции Аккермана A ( n , n ). (Фактически, $f(n)>A(n,n)$ для всех n .) Функцию f также можно выразить в виде цепочки стрелок Конвея как $f(n)=3\rightarrow 3\rightarrow n$, и это обозначение также дает следующие ограничения на G :

$$3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.$$

Величина

Чтобы передать сложность понимания огромного размера числа Грэма, может быть полезно выразить — только в терминах возведения в степень — только первый член ( g ₁ ) быстро растущей 64-членной последовательности. Во-первых, с точки зрения тетрации ( $\uparrow \uparrow$) один: $$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))$$

где количество троек в выражении справа равно $$3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3).$$

Теперь каждая тетрация ( $\uparrow \uparrow$) работа сводится к электробашне ( $\uparrow$) по определению $$3\uparrow \uparrow X=3\uparrow (3\uparrow (3\uparrow \dots (3\uparrow 3)\dots ))=3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}$$ где есть X 3s.

Таким образом, $$g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad {\text{where the number of 3s is}}\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)$$

становится, исключительно с точки зрения повторяющихся «башен возведения в степень», $$g_{1}=\underbrace {\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} _{\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3}$$

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

Другими словами, g ₁ вычисляется путем сначала расчета количества башен, $n=3\uparrow (3\uparrow (3\ \dots \ \uparrow 3))$ (где число троек равно $3\uparrow (3\uparrow 3)=7625597484987$), а затем вычисляем n ^й башня в следующей последовательности:

      1st tower:  3
     
      2nd tower:  3↑3↑3 (number of 3s is 3) = 7625597484987
     
      3rd tower:  3↑3↑3↑3↑...↑3 (number of 3s is 7625597484987) = …
     
      ⋮
     
 g1 = nth tower:  3↑3↑3↑3↑3↑3↑3↑...↑3 (number of 3s is given by the n − 1th tower)

где количество троек в каждой последующей башне определяется башней перед ней. Результатом расчета третьей башни является значение n , количество башен для g ₁ .

Величина этого первого члена, g ₁ , настолько велика, что ее практически невозможно понять, хотя приведенное выше изображение относительно легко понять. Даже n , простое количество башен в этой формуле для g ₁ , намного больше, чем количество планковских объемов (примерно 10 ¹⁸⁵ из них), на которые можно представить разделение наблюдаемой Вселенной . остается еще 63 члена, И после этого первого члена в быстро растущей последовательности g прежде чем будет достигнуто число Грэма G = g ₆₄ . Чтобы проиллюстрировать, насколько быстро растет эта последовательность, в то время как g ₁ равен $3\uparrow \uparrow \uparrow \uparrow 3$ поскольку стрелок вверх всего четыре, количество стрелок вверх в g ₂ равно непостижимо большому числу g ₁ .

Ссылки

Библиография

• Гарднер, Мартин (ноябрь 1977 г.). «Математические игры» (PDF) . Научный американец . 237 (5): 18–28. Бибкод : 1977SciAm.237e..18G . дои : 10.1038/scientificamerican1177-18 . ; перепечатано (переработано) в Gardner (2001), цитируется ниже.
• Гарднер, Мартин (1989). Плитки Пенроуза к шифрам с люками . Вашингтон, округ Колумбия: Математическая ассоциация Америки. ISBN  978-0-88385-521-8 .
• Гарднер, Мартин (2001). Колоссальная книга по математике: классические головоломки, парадоксы и проблемы . Нью-Йорк, штат Нью-Йорк: Нортон. ISBN  978-0-393-02023-6 .
• Грэм, РЛ; Ротшильд, Б.Л. (1971). «Теорема Рэмси для n наборов - параметров» (PDF) . Труды Американского математического общества . 159 : 257–292. дои : 10.2307/1996010 . JSTOR   1996010 . Явная формула для N приведена на стр. 290. Это не «число Грэма» G, опубликованное Мартином Гарднером.
• Грэм, РЛ; Ротшильд, Б.Л. (1978). «Теория Рэмси». В Роте, GC (ред.). Исследования по комбинаторике (MAA Studies in Mathematics) . Том. 17. Математическая ассоциация Америки. стр. 80–99. ISBN  978-0-88385-117-3 . На стр. 90, где формулируется «наилучшая доступная оценка» решения, явная формула для N повторяется из статьи 1971 года.

Внешние ссылки

• Последовательность OEIS A133613 (число Грэма)
• Статья Сбииса Сайбиана о числе Грэма
• « Задача Рэмси о гиперкубах », Джефф Эксу
• Вайсштейн, Эрик В. «Число Грэма» . Математический мир .
• Как вычислить число Грэма
• Концептуализация числа Грэма
• В некоторых результатах Рэмси для предварительной публикации n-куба упоминается число Грэма.
• Падилья, Тони; Паркер, Мэтт. «Число Грэма» . Числофил . Брэйди Харан . Архивировано из оригинала 27 мая 2014 г. Проверено 08 апреля 2013 г.
• Архивировано в Ghostarchive и Wayback Machine : Рон Грэм . «Что такое номер Грэма? (с участием Рона Грэма)» (видео) . Числофил . Брэйди Харан .
• Архивировано в Ghostarchive и Wayback Machine : Рон Грэм . «Насколько велико число Грэма? (с участием Рона Грэма)» (видео) . Числофил . Брэйди Харан .
• Последние 16 миллионов цифр номера Грэма, предоставленного коммуникационной группой Darkside.