Число Грэма - это огромное число, которое возникло как верхняя граница ответа на проблему в математической области теории Рамсея . Он назван в честь математика Рональда Грэма , который использовал это число в беседах с научно-популярным писателем Мартином Гарднером в качестве упрощенного объяснения верхних границ задачи, над которой он работал. В 1977 году Гарднер описал это число в Scientific American , представив его широкой публике. На момент его введения это было наибольшее конкретное положительное целое число, которое когда-либо использовалось в опубликованном математическом доказательстве. Номер был описан в 1980 году.Книга рекордов Гиннеса , добавляющая к ней популярный интерес. Другие конкретные целые числа (такие как TREE (3) ), которые, как известно, намного больше числа Грэхема, с тех пор появились во многих серьезных математических доказательствах, например, в связи сразличными конечными формами теоремы Крускала Харви Фридманом . Кроме того, с тех пор было доказано, что меньшие верхние границы проблемы теории Рамсея, из которой получено число Грэма, являются действительными.
Число Грэма гораздо больше , чем во многих других больших чисел , таких как число скьюза и числа Мозера , оба из которых в свою очередь , намного больше , чем гуголплекс . Как и в случае с ними, оно настолько велико, что наблюдаемая Вселенная слишком мала, чтобы содержать обычное цифровое представление числа Грэма, предполагая, что каждая цифра занимает один объем Планка , возможно, наименьшее измеримое пространство. Но даже количество цифр в этом цифровом представлении числа Грэма само по себе будет настолько большим, что его цифровое представление не может быть представлено в наблюдаемой Вселенной. Не может даже количество цифр этого числа - и так далее, во много раз намного превышающее общее количество томов Планка в наблюдаемой Вселенной. Таким образом, число Грэма не может быть выражено даже физическими энергетическими башнями вселенского масштаба в форме.
Однако число Грэма может быть явно задано вычислимыми рекурсивными формулами с использованием нотации Кнута со стрелкой вверх или эквивалента, как это было сделано Грэмом. Поскольку для его определения существует рекурсивная формула, оно намного меньше, чем типичные числа занятых бобра . Хотя она слишком велика, чтобы ее можно было вычислить полностью, последовательность цифр числа Грэма может быть вычислена явно с помощью простых алгоритмов. Последние 12 цифр: 262464195387. С обозначением стрелки вверх Кнута число Грэма равно, где
Контекст
Число Грэма связано со следующей проблемой теории Рамсея :
Подключение каждой пары геометрических вершин в качестве п - мерного гиперкуба , чтобы получить полный граф на 2 п вершин . Раскрасьте каждое из ребер этого графа в красный или синий цвет. Какое наименьшее значение n, при котором каждая такая раскраска содержит хотя бы один одноцветный полный подграф на четырех компланарных вершинах?
В 1971 году Грэм и Rothschild доказал теорему Graham-Rothschild по теории Рамсея из параметров слов , особый случай , который показывает , что эта проблема имеет решение N * . Они ограничили значение N * на 6 ≤ N * ≤ N , где N было большим, но явно определенным числом.
где в нотации Кнута, направленной вверх ; число находится между 4 → 2 → 8 → 2 и 2 → 3 → 9 → 2 в обозначении цепной стрелки Конвея . [1] В 2014 году это число было уменьшено с помощью оценки сверху числа Хейлза – Джеветта до
который содержит три тетрации . [2] В 2019 году это было улучшено до: [3]
Нижняя граница числа 6 была позже улучшена до 11 Джеффри Экзу в 2003 году [4] и до 13 Джеромом Баркли в 2008 году. [5] Таким образом, наиболее известные оценки для N * - это 13 ≤ N * ≤ N '' .
Число Грэма G намного больше N :, где . Эта более слабая верхняя граница проблемы, приписываемая неопубликованной работе Грэма, в конце концов была опубликована и названа Мартином Гарднером в Scientific American в ноябре 1977 года [6].
Публикация
Число привлекло внимание общественности, когда Мартин Гарднер описал его в разделе «Математические игры» журнала Scientific American в ноябре 1977 года, написав, что Грэм недавно установил в неопубликованном доказательстве «границу, столь обширную, что она является рекордной для самое большое число, которое когда-либо использовалось в серьезном математическом доказательстве ». Книга рекордов Гиннеса 1980 года повторила утверждение Гарднера, что усилило популярность этого числа. По словам физика Джона Баэза , Грэм изобрел количество, известное теперь как число Грэма, в разговоре с Гарднером. В то время как Грэм пытался объяснить результат теории Рэмси, который он получил со своим сотрудником Брюсом Ли Ротшильдом , Грэм обнаружил, что указанную величину объяснить легче, чем действительное число, фигурирующее в доказательстве. Поскольку число, которое Грэм описал Гарднеру, больше числа в самой статье, оба являются допустимыми верхними границами для решения проблемы, изученной Грэмом и Ротшильдом. [7]
Определение
Используя обозначение Кнута со стрелкой вверх , число Грэма G (как определено в статье Гарднера в Scientific American ) равно
где количество стрелок в каждом последующем слое определяется значением следующего слоя под ним; это,
и где верхний индекс на стрелке вверх указывает, сколько там стрелок. Другими словами, G вычисляется за 64 шага: первый шаг - вычислить g 1 с четырьмя стрелками вверх между 3s; второй шаг - вычислить g 2 со стрелкой вверх g 1 между 3 с; третий шаг - вычислить g 3 со стрелкой вверх g 2 между 3s; и так далее, пока не будет окончательно вычислено G = g 64 с g 63, стрелкой вверх между 3s.
Эквивалентно,
а верхний индекс f указывает на итерацию функции , например,. Выражается в терминах семейства гиперопераций , функция f - это конкретная последовательность, который является вариантом быстрорастущей функции Аккермана A ( n , n ). (По факту,для всех n .) Функция f также может быть выражена в обозначении стрелок Конвея как, и это обозначение также дает следующие оценки на G :
Величина
Чтобы передать трудность понимания огромного размера числа Грэма, может быть полезно выразить - в терминах одного возведения в степень - только первый член ( g 1 ) быстрорастущей 64-членной последовательности. Во-первых, с точки зрения тетрации () один:
где число троек в выражении справа равно
Теперь каждая тетрация () работа сводится к силовой вышке () по определению
Таким образом,
становится, исключительно с точки зрения повторяющихся "башен возведения в степень",
и где количество троек в каждой башне, начиная с самой левой башни, определяется значением следующей башни справа.
Другими словами, g 1 вычисляется сначала путем вычисления количества башен, (где количество троек равно ), а затем вычислить n- ю башню в следующей последовательности:
1-я башня: 3 2-я башня: 3 ↑ 3 ↑ 3 (количество троек равно 3 ) = 7625597484987 3-я башня: 3 ↑ 3 ↑ 3 ↑ 3 ↑ ... ↑ 3 (количество троек - 7625597484987 ) =… ⋮ g 1 = n- я башня: 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ ... ↑ 3 (количество троек определяется n-1- ой башней )
где число троек в каждой последующей башне дано башней непосредственно перед ней. Обратите внимание, что результатом вычисления третьей башни является значение n , количество башен для g 1 .
Величина этого первого члена, g 1 , настолько велика, что практически непонятна, даже несмотря на то, что показанное выше отображение относительно легко понять. Даже n , простое количество башен в этой формуле для g 1 , намного больше, чем количество томов Планка (примерно 10 185 из них), на которые можно представить разделение наблюдаемой Вселенной . И после этого первого члена в быстрорастущей g- последовательности остаются еще 63 члена, прежде чем будет достигнуто число Грэма G = g 64 . Чтобы проиллюстрировать, насколько быстро эта последовательность растет, тогда как g 1 равнос четырьмя стрелками вверх число стрелок вверх в g 2 является непостижимо большим числом g 1 .
Крайние правые десятичные цифры
Число Грэма представляет собой «башню силы» в форме 3 ↑↑ n (с очень большим значением n ), поэтому его крайние правые десятичные цифры должны удовлетворять определенным свойствам, общим для всех таких башен. Одно из этих свойств состоит в том, что все такие башни высотой больше d (скажем) имеют одинаковую последовательность d крайних правых десятичных цифр . Это частный случай более общего свойства: d крайних правых десятичных цифр всех таких башен высотой больше d +2 не зависят от самой верхней цифры "3" в башне; т.е. верхнюю "3" можно заменить на любое другое неотрицательное целое число, не затрагивая d крайних правых цифр.
В следующей таблице показано , как это происходит для нескольких значений d . Для данной высоты башни и количества цифр d полный диапазон d- значных чисел (10 d из них) не встречается; вместо этого некоторое меньшее подмножество значений повторяется в цикле. Длина цикла и некоторые значения (в скобках) показаны в каждой ячейке этой таблицы:
Количество цифр ( d ) | 3 ↑ х | 3 ↑ 3 ↑ х | 3 ↑ 3 ↑ 3 ↑ х | 3 ↑ 3 ↑ 3 ↑ 3 ↑ х | 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ x |
---|---|---|---|---|---|
1 | 4 (1,3,9, 7 ) | 2 (3, 7 ) | 1 ( 7 ) | 1 ( 7 ) | 1 ( 7 ) |
2 | 20 (01,03,…, 87 ,…, 67) | 4 (03,27,83, 87 ) | 2 (27, 87 ) | 1 ( 87 ) | 1 ( 87 ) |
3 | 100 (001 003,…, 387 ,…, 667) | 20 (003 027,… 387 ,…, 587) | 4 (027 987 227 387 ) | 2 (987, 387 ) | 1 ( 387 ) |
Конкретные крайние правые цифры d , которые в конечном итоге являются общими для всех достаточно высоких башен из 3, выделены жирным шрифтом, и их можно увидеть, как они развиваются с увеличением высоты башни. Для любого фиксированного количества цифр d (строка в таблице) количество возможных значений для 33 ↑… 3 ↑ x mod 10 d , поскольку x изменяется по всем неотрицательным целым числам, видно, что оно неуклонно уменьшается с увеличением высоты, пока в конечном итоге не уменьшится «набор возможностей» до одного числа (цветные ячейки), когда высота превышает d + 2.
Простой алгоритм [8] для вычисления этих цифр может быть описан следующим образом: пусть 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 . [9] Отсюда следует, что g 63 ≪ k ≪ g 64 .
Приведенный выше алгоритм производит следующие 500 крайних правых десятичных цифр числа Грэма ( OEIS : A133613 ):
... 02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387
Рекомендации
- ^ "Числовые рекорды Грэма" . Iteror.org. Архивировано из оригинала на 2013-10-19 . Проверено 9 апреля 2014 .
- ^ Лавров, Михаил; Ли, Митчелл; Макки, Джон (2014). «Улучшенные верхние и нижние оценки геометрической задачи Рамсея» . Европейский журнал комбинаторики . 42 : 135–144. DOI : 10.1016 / j.ejc.2014.06.003 .
- ^ Липка, Эрик (2019). «Дальнейшее улучшение верхней оценки геометрической задачи Рамсея». arXiv : 1905.05617 [ math.CO ].
- ^ Экзу, Джеффри (2003). «Проблема Евклида Рамсея» . Дискретная и вычислительная геометрия . 29 (2): 223–227. DOI : 10.1007 / s00454-002-0780-5 .Exoo относится к верхней границе N Грэма и Ротшильда термином «число Грэма». Это не «число Грэма» G, опубликованное Мартином Гарднером.
- ^ Баркли, Джером (2008). «Улучшенная нижняя оценка проблемы Евклида Рамсея». arXiv : 0811.1055 [ math.CO ].
- ^ Мартин Гарднер (1977) «В котором объединение наборов точек ведет к различным (и отклоняющимся) путям». Архивировано 19 октября 2013 г. в Wayback Machine . Scientific American, ноябрь 1977 г.
- ^ Джон Баэз (2013). «Некоторое время назад я говорил вам о номере Грэма ...» В архиве с оригинала на 2015-11-16.
- ^ «Математический форум @ Drexel (« Последние восемь цифр Z »)» . Mathforum.org . Проверено 9 апреля 2014 .
- ^ Рипа, Марко (2011). La strana coda della serie n ^ n ^ ... ^ n (на итальянском языке). UNI Service. ISBN 978-88-6178-789-6.
Библиография
- Гарднер, Мартин (ноябрь 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