Число Грэма

Число Грэма

Число Грэма (Грехема, англ. Graham's number) — большое число, которое является верхней границей для решения определённой проблемы в теории Рамсея. Названо в честь Рональда Грэма (англ.).

Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке «Математические игры» в журнале Scientific American в ноябре 1977 года, где было сказано: «В неопубликованном доказательстве Грэм недавно установил … границу настолько большую, что ей принадлежит рекорд как наибольшему числу, когда-либо использовавшемуся в серьёзном математическом доказательстве».

В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грехема в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. На самом деле, вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грехема, предполагая, что запись каждой цифры занимает по меньшей мере объём Планка. Даже степенные башни вида a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}} бесполезны для этой цели, хотя это число и может быть записано с использованием рекурсивных формул, таких как стрелочная нотация Кнута или эквивалентных, что и было сделано Грехемом. Последние 500 цифр числа Грехема — это ...02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387.

В современных математических доказательствах иногда встречаются числа, ещё много бо́льшие, чем число Грехема, например, в работе с конечной формой Фридмана в теореме Краскала.

Содержание

Проблема Грехема

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

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

Грехем и Ротшильд в 1971 году доказали, что эта проблема имеет решение, N*, и показали что 6 ≤ N*N, где N — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как N = F^7(12) \,\!, где F(n) = 2\uparrow^{n} 3 \,\!.

Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что N* должно быть не меньше 13. Таким образом, 13 ≤ N*N.

Предметом настоящей статьи является верхняя граница G, которая много слабее (то есть больше), чем N; а именно G = f^{64}(4) \,\!, где f(n) = 3 \uparrow^n 3 \,\!. Именно эта граница, описанная в неопубликованной работе Грехема, и была описана (и названа числом Грехема) Мартином Гарднером.

Определение числа Грехема

Используя стрелочную нотацию Кнута, число Грехема G может быть записано как

 
\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 \uparrow3
 \end{matrix} 
\right \} \text{64 layers}

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

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

и где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, G вычисляется в 64 шага: на первом шаге мы вычисляем g1 с четырьмя стрелками между тройками, на втором — g2 с g1 стрелок между тройками, на третьем — g3 с g2 стрелок между тройками и так далее, в конце мы вычисляем G = g64 с g63 стрелок между тройками.

Это может быть записано как

G = f^{64}(4),\text{ где }f(n) = 3 \uparrow^n 3,

где верхний индекс у f означает итерации функций. Функция f является частным случаем гипероператоров, f(n) = \text{hyper}(3,n+2,3), и может быть так же записана при помощи цепных стрелок Конвея как f(n) = 3 \rightarrow 3 \rightarrow n. Последняя запись так же позволяет записать следующие граничные значения для G:

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

Масштаб числа Грехема

Для того, чтобы осознать невероятный размер числа Грехема, полезно попробовать представить через возведение в степень хотя бы первый член (g1) стремительно растущей 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) по определению разворачивается в «степенную башню» как

3 \uparrow\uparrow X \ = \ 3 \uparrow (3 \uparrow (3 \uparrow \dots (3 \uparrow 3) \dots )) \ = \ 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}, где X — количество 3-ек.

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

g_1 = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots )), где количество троек — 3 \uparrow \uparrow (3 \uparrow \uparrow 3)

записанное на языке степеней


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 , где число башен —  \quad 
  \left. 
    \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}
  \right \}
  \left. 
    \begin{matrix}3^{3^3}\end{matrix}
  \right \}
    3

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

Другими словами, g1 вычисляется путём вычисления количества башен, n = 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}} (где число троек — 3^{3^{3}} = 7625597484987), и затем вычисляя n башен в следующем порядке:

      1ая башня:  3

      2ая башня:  3↑3↑3 (количество троек — 3) = 7625597484987

      3я башня:  3↑3↑3↑3↑...↑3 (количество троек — 7625597484987) = ...

      .
      .
      .

 g1 = nая башня:  3↑3↑3↑3↑3↑3↑3↑...↑3 (количество троек задаётся результатом вычисления n-1ой башни)

Масштаб первого члена, g1, настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя n это всего лишь количество башен в этой формуле для g1, уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно 8.5*10185). После первого члена нас ожидает ещё 63 члена стремительно растущей последовательности.

См. также

Литература

  • Graham, R. L.; Rothschild, B. L. (1971). «Ramsey's Theorem for n-Parameter Sets». Transactions of the American Mathematical Society 159: 257-292. DOI:10.2307/1996010. The explicit formula for N appears on p. 290.
  • Graham, R. L.; Rothschild, B.L. (1978). «Ramsey Theory», Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80-99. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.
  • Gardner, Martin (November 1977). «Mathematical Games». Scientific American 237: 18-28.; reprinted (revised 2001) in the following book:
  • Gardner Martin The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. — New York, NY: Norton, 2001. — ISBN 0393020231
  • Gardner Martin Penrose Tiles to Trapdoor Ciphers. — Washington, D.C.: Mathematical Association of America, 1989. — ISBN 0-88385-521-6
  • Exoo, Geoffrey (2003). «A Euclidean Ramsey Problem». Discrete Computational Geometry 29: 223-227. DOI:10.1007/s00454-002-0780-5.

Ссылки



Wikimedia Foundation. 2010.

Поможем написать реферат

Полезное


Смотреть что такое "Число Грэма" в других словарях:

  • Число Скьюза — (англ. Skewes number)  наименьшее натуральное число такое, что начиная с него неравенство перестает выполняться, при этом   количество простых чисел, не превосходящих ,   сдвинутый интегральный лога …   Википедия

  • Число зверя — …   Википедия

  • Число — У этого термина существуют и другие значения, см. Число (значения). Число  основное понятие математики[1], используемое для количественной характеристики, сравнения и нумерации объектов. Возникнув ещё в первобытном обществе из потребностей… …   Википедия

  • e (число) — У этого термина существуют и другие значения, см. E. Не следует путать с Числами Эйлера I рода. Не следует путать с постоянной Эйлера. Иррациональные числа γ ζ(3)  √2  √3  √5  φ  α  e  π  δ …   Википедия

  • 13 (число) — У этого термина существуют и другие значения, см. 13 (значения). Запрос «Чёртова дюжина» перенаправляется сюда; см. также другие значения. 13 тринадцать 10 · 11 · 12 · 13 · 14 · 15 · 16 Факторизация: Простое Римская запись: XIII …   Википедия

  • 666 (число) — 666 шестьсот шестьдесят шесть 663 · 664 · 665 · 666 · 667 · 668 · 669 Факторизация: Римская запись: DCLXVI Двоичное: 1010011010 Восьмеричное: 1232 Шестнадцатеричное: 29A …   Википедия

  • Пи (число) — У этого термина существуют и другие значения, см. Пи (значения). Иррациональные числа γ ζ(3)  √2  √3  √5  φ  α  e  π  δ Система счисления Оценка числа …   Википедия

  • 1729 (число) — 1729 одна тысяча семьсот двадцать девять 1726 · 1727 · 1728 · 1729 · 1730 · 1731 · 1732 Факторизация: Римская запись: MDCCXXIX Двоичное: 11011000001 Восьмеричное: 3301 Шестнадцатеричное: 6C1 …   Википедия

  • 1458 (число) — 1458 одна тысяча четыреста пятьдесят восемь 1455 · 1456 · 1457 · 1458 · 1459 · 1460 · 1461 Факторизация: Римская запись: MCDLVIII Двоичное: 10110110010 Восьмеричное: 2662 Шестнадцатеричное: 5B2 …   Википедия

  • 1728 (число) — 1728 одна тысяча семьсот двадцать восемь 1725 · 1726 · 1727 · 1728 · 1729 · 1730 · 1731 Факторизация: Римская запись: MDCCXXVIII Двоичное: 11011000000 Восьмеричное: 3300 Шестнадцатеричное: 6C0 …   Википедия

Книги

Другие книги по запросу «Число Грэма» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»