Число Грэма - Graham's number

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

Число Грэма гораздо больше , чем во многих других больших чисел , таких как число скьюза и числа Мозера , оба из которых в свою очередь , намного больше , чем гуголплекс . Как и в случае с ними, оно настолько велико, что наблюдаемая Вселенная слишком мала, чтобы содержать обычное цифровое представление числа Грэма, предполагая, что каждая цифра занимает один объем Планка , возможно, наименьшее измеримое пространство. Но даже количество цифр в этом цифровом представлении числа Грэма само по себе будет настолько большим, что его цифровое представление не может быть представлено в наблюдаемой Вселенной. Не может даже количество цифр этого числа - и так далее, во много раз намного превышающее общее количество томов Планка в наблюдаемой Вселенной. Таким образом , число Грэма не могут быть выражены даже физической вселенной масштабных силовых башен формы . ${\ Displaystyle а ^ {Ь ^ {с ^ {\ cdot ^ {\ cdot ^ {\ cdot}}}}}}$

Однако число Грэхема может быть явно задано вычислимыми рекурсивными формулами с использованием нотации Кнута со стрелкой вверх или эквивалента, как это было сделано Грэмом. Поскольку для его определения существует рекурсивная формула, оно намного меньше, чем типичные числа занятых бобра . Хотя она слишком велика, чтобы ее можно было вычислить полностью, последовательность цифр числа Грэма может быть вычислена явно с помощью простых алгоритмов. Последние 13 цифр: 7262464195387. В нотации Кнута со стрелкой вверх число Грэма равно , где ${\ displaystyle g_ {64}}$

$${\ displaystyle g_ {n} = \ left \ {{\ begin {matrix} 3 \ uparrow \ uparrow \ uparrow \ uparrow 3, & n = 1 \\ 3 \ uparrow ^ {g_ {n-1}} 3, & n \ geq 2, n \ in \ mathbb {N} \ end {matrix}} \ right.}$$

Контекст

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

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

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

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

${\ Displaystyle F ^ {7} (12) = F (F (F (F (F (F (F (12))))))),}$

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

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

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

${\ displaystyle 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 :, где . Эта более слабая верхняя граница проблемы, приписываемая неопубликованной работе Грэхема, в конце концов была опубликована и названа Мартином Гарднером в Scientific American в ноябре 1977 года. ${\ displaystyle f ^ {64} (4)}$${\ displaystyle f (n) = 3 \ uparrow ^ {n} 3}$

Публикация

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

Определение

Используя обозначение Кнута со стрелкой вверх , число Грэма G (как определено в статье Гарднера в Scientific American ) равно

$${\ 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 \ quad \ vdots \ qquad \ quad} \\ && 3 \ underbrace {\ uparrow \ uparrow \ cdots \ cdots \ 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,}$

${\ displaystyle g_ {n} = 3 \ uparrow ^ {g_ {n-1}} 3,}$

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

Эквивалентно,

$${\ displaystyle G = f ^ {64} (4), {\ text {where}} f (n) = 3 \ uparrow ^ {n} 3,}$$

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

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

Величина

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

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

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

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

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

$${\ displaystyle 3 \ uparrow \ uparrow X = 3 \ uparrow (3 \ uparrow (3 \ uparrow \ dots (3 \ uparrow 3) \ dots)) = 3 ^ {3 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {3}}}}}}$$

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

$${\ displaystyle g_ {1} = 3 \ uparrow \ uparrow (3 \ uparrow \ uparrow (3 \ uparrow \ uparrow \ \ dots \ (3 \ uparrow \ uparrow 3) \ dots)) \ quad {\ text {, где число of 3s is}} \ quad 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 \} \ точки \ left. {\ begin {matrix} 3 ^ {3 ^ {3}} \ end {matrix}} \ right \} 3 \ quad {\ text {где количество башен равно}} \ quad \ left. { \ begin {matrix} 3 ^ {3 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {3}}}}} \ end {matrix}} \ right \} \ left. {\ begin {matrix} 3 ^ {3 ^ {3}} \ end {matrix}} \ right \} 3}$$

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

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

      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 ¹⁸⁵ из них), на которые можно представить разделение наблюдаемой Вселенной . И после этого первого члена в быстрорастущей g- последовательности остаются еще 63 члена, прежде чем будет достигнуто число Грэма G = g ₆₄ . Чтобы проиллюстрировать, насколько быстро эта последовательность растет, в то время как g ₁ равен только четырем стрелкам вверх, количество стрелок вверх в g ₂ составляет это непостижимо большое число g ₁ . ${\ displaystyle 3 \ uparrow \ uparrow \ uparrow \ uparrow 3}$

Крайние правые десятичные цифры

Число Грэма представляет собой «башню силы» в форме 3 ↑↑ n (с очень большим значением n ), поэтому его крайние правые десятичные цифры должны удовлетворять определенным свойствам, общим для всех таких башен. Одно из этих свойств состоит в том, что все такие башни высотой больше d (скажем) имеют одинаковую последовательность d крайних правых десятичных цифр . Это частный случай более общего свойства: d крайних правых десятичных цифр всех таких башен высотой больше d +2 не зависят от самой верхней цифры "3" в башне; т.е. верхнюю "3" можно заменить на любое другое неотрицательное целое число, не затрагивая d крайних правых цифр.

В следующей таблице показано , как это происходит для нескольких значений d . Для данной высоты башни и количества цифр d полный диапазон d- значных чисел (10 ^d из них) не встречается; вместо этого некоторое меньшее подмножество значений повторяется в цикле. Длина цикла и некоторые значения (в скобках) показаны в каждой ячейке этой таблицы:

Конкретные крайние правые цифры d , которые в конечном итоге являются общими для всех достаточно высоких башен из 3, выделены жирным шрифтом, и их можно увидеть, как они развиваются по мере увеличения высоты башни. Для любого фиксированного количества цифр d (строка в таблице) количество возможных значений для 3 3 ↑… 3 ↑ x mod 10 ^d , поскольку x изменяется по всем неотрицательным целым числам, будет неуклонно уменьшаться с увеличением высоты, пока в конечном итоге сокращение «множества возможностей» до одного числа (цветные ячейки), когда высота превышает d +2. ${\ displaystyle \ scriptstyle \ uparrow}$

Простой алгоритм вычисления этих цифр может быть описан следующим образом: пусть x = 3, затем повторите d раз, присвоение x = 3 ^x mod 10 ^d . За исключением исключения любых ведущих нулей, окончательное значение, присвоенное x (как десятичное число), затем состоит из d крайних правых десятичных цифр 3 ↑↑ n для всех n > d . (Если в конечном значении x меньше d цифр, необходимо добавить необходимое количество ведущих нулей.)

Пусть k - количество этих стабильных цифр, которые удовлетворяют соотношению сравнения G (mod 10 ^k ) ≡ [G ^G ] (mod 10 ^k ).

k = t -1, где G ( t ): = 3 ↑↑ t . Отсюда следует, что g ₆₃ ≪ k ≪ g ₆₄ .

Приведенный выше алгоритм производит следующие 500 крайних правых десятичных цифр числа Грэма ( OEIS :  A133613 ):

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

использованная литература

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

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

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

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