Число Грэхэма - Grahams number - Wikipedia

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

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

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

Тем не менее, число Грэма можно явно определить как вычислимый рекурсивные формулы с использованием Обозначение Кнута со стрелкой вверх или эквивалент, как это сделал Грэм. Поскольку существует рекурсивная формула для его определения, она намного меньше типичной занятой бобер числа. Хотя она слишком велика, чтобы ее можно было вычислить полностью, последовательность цифр числа Грэма может быть вычислена явно с помощью простых алгоритмов. Последние 12 цифр ... 262464195387. С Обозначение Кнута со стрелкой вверх, Число Грэма ${\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^п вершины. Раскрасьте каждое из ребер этого графа в красный или синий цвет. Какое наименьшее значение п для которого каждый такая раскраска содержит хотя бы один одноцветный полный подграф на четырех копланарный вершины?

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

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

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

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

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

${\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 году.^[4] и 13 Джеромом Баркли в 2008 году.^[5] Таким образом, наиболее известные оценки для N * находятся 13 ≤ N * ≤ N ''.

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

Публикация

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

Определение

С помощью Обозначение Кнута со стрелкой вверх, Число Грэма грамм (как определено в Gardner's 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 layers}}}$$

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

$${\displaystyle G=g_{64},}$$

куда ${\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,}$ ${\displaystyle g_{n}=3\uparrow ^{g_{n-1}}3,}$

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

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

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

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

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

Величина

Чтобы передать трудность понимания огромного размера числа Грэма, может быть полезно выразить - в терминах одного возведения в степень - только первый член (грамм₁) быстрорастущей 64-членной последовательности. Во-первых, с точки зрения тетрация (${\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}}}}}}$$

где есть Икс 3с.

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

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

становится, исключительно с точки зрения повторяющихся "башен возведения в степень",

$${\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 {\text{where the number of towers is}}\quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3}$$

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

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

      1-я башня: 3           2-я башня: 3 ↑ 3 ↑ 3 (количество троек равно 3) = 7625597484987           3-я башня: 3 ↑ 3 ↑ 3 ↑ 3 ↑ ... ↑ 3 (количество троек равно 7625597484987) = …           ⋮      грамм1 = пth башня: 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑ ... ↑ 3 (количество троек задается п-1th башня)

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

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

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

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

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

Количество различных возможных значений 3 ↑ 3 ↑… 3 ↑Икс когда все кроме самого правого d десятичные цифры игнорируются

Количество цифр (d)	3↑Икс	3↑3↑Икс	3↑3↑3↑Икс	3↑3↑3↑3↑Икс	3↑3↑3↑3↑3↑Икс
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 (строка в таблице), количество возможных значений для 3${\displaystyle \scriptstyle \uparrow }$3↑…3↑Икс мод 10^d, так как Икс колеблется по всем неотрицательным целым числам, неуклонно уменьшается по мере увеличения высоты, пока в конечном итоге не уменьшится «набор возможностей» до одного числа (цветные ячейки), когда высота превышает d+2.

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

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

k=т-1, где G (т):=3↑↑т.^[9] Следует, что, грамм₆₃ ≪ к ≪ г₆₄.

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

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

Рекомендации

1. "Числовые рекорды Грэма". Iteror.org. Архивировано из оригинал в 2013-10-19. Получено 2014-04-09.
2. Лавров, Михаил; Ли, Митчелл; Макки, Джон (2014). «Улучшенные верхние и нижние оценки геометрической задачи Рамсея». Европейский журнал комбинаторики. 42: 135–144. Дои:10.1016 / j.ejc.2014.06.003.
3. Липка, Эрик (2019). «Дальнейшее улучшение верхней оценки геометрической задачи Рамсея». arXiv:1905.05617 [math.CO ].
4. Экзу, Джеффри (2003). "Проблема Евклида Рамсея". Дискретная и вычислительная геометрия. 29 (2): 223–227. Дои:10.1007 / s00454-002-0780-5. Exoo относится к верхней границе Грэма и Ротшильда. N термином «число Грэма». Это не «число Грэма». грамм опубликовано Мартином Гарднером.
5. Баркли, Джером (2008). «Улучшенная нижняя оценка проблемы Евклида Рамсея». arXiv:0811.1055 [math.CO ].
6. Мартин Гарднер (1977) «В котором объединение наборов точек ведет к разным (и расходящимся) путям» В архиве 2013-10-19 в Wayback Machine. Scientific American, ноябрь 1977 г.
7. Джон Баэз (2013). "Некоторое время назад я рассказывал вам о номере Грэма ..." Архивировано из оригинал на 2015-11-16.
8. "The Math Forum @ Drexel (" Последние восемь цифр Z ")". Mathforum.org. Получено 2014-04-09.
9. Рипа, Марко (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. Дои:10.1038 / scientificamerican1177-18.; перепечатано (отредактировано) в Gardner (2001), цитируется ниже.
• Гарднер, Мартин (1989). Плитки Пенроуза для тайных шифров. Вашингтон, округ Колумбия: Математическая ассоциация Америки. ISBN  978-0-88385-521-8.
• Гарднер, Мартин (2001). Колоссальная книга математики: классические головоломки, парадоксы и задачи. Нью-Йорк, штат Нью-Йорк: Нортон. ISBN  978-0-393-02023-6.
• Graham, R.L .; Ротшильд, Б. Л. (1971). "Теорема Рамсея для п-Наборы параметров » (PDF). Труды Американского математического общества. 159: 257–292. Дои:10.2307/1996010. JSTOR  1996010. Явная формула для N появляется на стр. 290. Это не «число Грэма». грамм опубликовано Мартином Гарднером.
• Graham, R.L .; Ротшильд, Б. Л. (1978). «Теория Рэмси». В Рота, G-C (ред.). Исследования по комбинаторике (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. Получено 2013-04-08.
• Рон Грэм. "Что такое число Грэма? (С участием Рона Грэма)" (видео). Numberphile. Брэди Харан.
• Рон Грэм. "Насколько велико число Грэма? (С участием Рона Грэма)" (видео). Numberphile. Брэди Харан.
• Последние 16 миллионов цифр числа Грэма посредством Коммуникационная группа Darkside