Число Грема

Число Грема (англ. Graham's number)  — велике число, верхня межа в популярному поясненні доведення одного з аналогів теореми Рамсея. Назване на честь американського математика Рональда Грема.

Під час роботи з популяризації математики в 1977 році Рональд Грем запропонував Мартіну Гарднеру велике число G, що було одним із варіантів верхньої межі. Стаття Гарднера була надрукована в розділі «Математичні ігри» часопису Scientific American ^[1]. Це число стало загальновідомим після його реєстрації у Книзі рекордів Гіннеса 1980 року як найбільшого числа, використаного для серйозного математичного доведення^[2]. Проте в науковій статті Грем із співавтором використовували трохи менше число^[3].

Число Грема G виникає при різних математичних діях з трійкою. У результаті виходить число значно більше, ніж гуголплекс (а це: ${\displaystyle 10^{10^{100}}}$, для порівняння, кількість атомів у Всесвіті обраховують як ${\displaystyle 10^{87}}$). Через неможливість адекватно відобразити його звичними знаками, математики використовують спеціальні позначення, розроблені Дональдом Кнутом.

${\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 рівні}}}$

Останні десять знаків числа Грема: …2464195387.

${\displaystyle G=3\rightarrow 3\rightarrow 65\rightarrow 2=g_{64},}$

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

Число Грема пов'язане з наступною проблемою теорії Ремзі:

З'єднайте кожну пару геометричних вершин n-вимірного гіперкуба, щоб отримати повний граф на 2ⁿ вершин. Розфарбуйте кожне з ребер цього графа червоним або синім кольором. Яке найменше значення n, для якого кожне таке розфарбовування містить принаймні один одноколірний повний підграф на чотирьох [[Компланарність |компланарних]] вершинах?

У 1971 році Грем і Ротшильд довели теорему Грема-Ротшильда про теорію параметричних слів Рамсея, окремий випадок якої показує, що ця задача має розв'язок N* . Вони обмежили значення N* величиною 6 ≤ N* ≤ N, де N — велике, але явно визначене число.

$${\displaystyle N=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 у нотації Конвея зі стрілками^[4]. Це було зменшено у 2014 році за допомогою верхніх меж числа Хейлза-Джуетта до

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

який містить три тетрації^[5]. У 2019 році оцінка додатково покращена до^[6]

$${\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 році^[7] та до 13 Джеромом Барклі у 2008 році^[8] Таким чином, найвідомішими межами для N* є 13 ≤ N* ≤ N'' .

Число Грема, G, набагато більше, ніж N : воно ${\displaystyle f^{64}(4)}$, де ${\displaystyle f(n)=3\uparrow ^{n}3}$ Цю слабшу верхню межу для задачі, що приписується неопублікованій роботі Грема, врешті-решт опублікував і назвав Мартін Гарднер у журналі Scientific American у листопаді 1977 року^[9].