Число Грэма
Число Грэма (англ. Graham's number) — большое число, которое является верхней границей для решения определённой проблемы в теории Рамсея. Является некоторой очень большой степенью тройки, которая записывается с помощью стрелочной нотации Кнута. Названо в честь Рональда Грэма (англ.).
Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке «Математические игры» в журнале Scientific American в ноябре 1977 года, где было сказано: «В неопубликованном доказательстве Грэм недавно установил … границу настолько большую, что ей принадлежит рекорд как наибольшему числу, когда-либо использовавшемуся в серьёзном математическом доказательстве».
В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грэма в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. На самом деле вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грэма (предполагается, что запись каждой цифры занимает по меньшей мере объём Планка). Даже степенные башни вида <math>a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}}</math> бесполезны для этой цели, хотя это число и может быть записано с использованием рекурсивных формул, таких, как стрелочная нотация Кнута или эквивалентных, что и было сделано Грэмом. Последние 50 цифр числа Грэма — это …03222348723967018485186439059104575627262464195387.
В современных математических доказательствах иногда встречаются числа, ещё много бо́льшие, чем число Грэма, например, в работе с конечной формой Фридмана в теореме Краскала.
Содержание
Проблема Грэма
Число Грэма связано со следующей проблемой в теории Рамсея:
- Рассмотрим <math>n</math>-мерный гиперкуб и соединим все пары вершин для получения полного графа с <math>2^n</math> вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в синий цвет. При каком наименьшем значении <math>n</math> каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?
Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, <math>N^*</math>, и показали, что <math>6\leqslant N^* \leqslant N</math>, где <math>N</math> — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как <math>N = F^7(12)</math>, где <math>F(n) = 2\uparrow^{n} 3</math>.
Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что <math>N^*</math> должно быть не меньше 13. Таким образом, <math>13\leqslant N^* \leqslant N</math>.
Предметом настоящей статьи является верхняя граница <math>G</math>, которая много слабее (то есть больше), чем <math>N</math>: <math>G = f^{64}(4)</math>, где <math>f(n) = 3 \uparrow^n 3</math>. Именно эта граница, описанная в неопубликованной работе Грэма, и была описана (и названа числом Грэма) Мартином Гарднером.
Определение числа Грэма
При использовании Стрелочной нотации Кнута число Грэма G может быть записано как
- <math>
\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} </math>,
где количество стрелок в каждом слое, начиная с верхнего, определяется числом в следующем слое, то есть
- <math>G = g_{64},</math> где <math>g_1 = 3 \uparrow \uparrow \uparrow \uparrow 3,\ g_n = 3 \uparrow ^{g_{n-1}}3,</math>
где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, <math>G</math> вычисляется в 64 шага: на первом шаге мы вычисляем <math>g_1</math> с четырьмя стрелками между тройками, на втором — <math>g_2</math> с <math>g_1</math> стрелками между тройками, на третьем — <math>g_3</math> с <math>g_2</math> стрелками между тройками и так далее; в конце мы вычисляем <math>G = g_{64}</math> с <math>g_{63}</math> стрелок между тройками.
Это может быть записано как
- <math>G = f^{64}(4),\text{ где }f(n) = 3 \uparrow^n 3,</math>
где верхний индекс у <math>f</math> означает итерации функций. Функция <math>f</math> является частным случаем гипероператоров <math>f(n) = \text{hyper}(3,n+2,3)</math> и может также быть записана при помощи цепных стрелок Конвея как <math>f(n) = 3 \rightarrow 3 \rightarrow (n+2)</math>. Последняя запись также позволяет записать следующие граничные значения для <math>G</math>:
- <math> 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2.</math>
Масштаб числа Грэма
Для того, чтобы осознать невероятный размер числа Грэма, полезно попробовать представить через возведение в степень хотя бы первый член (g1) стремительно растущей 64-членной последовательности. На языке тетраций <math>\uparrow\uparrow</math> означает:
- <math>
g_1 = 3 \uparrow \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) = 3 \uparrow\uparrow \Bigl(3 \uparrow\uparrow \bigl(3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots \bigr)\Bigr) </math>,
где число троек в выражении справа
- <math>3 \uparrow \uparrow \uparrow 3 \ = \ 3 \uparrow \uparrow (3 \uparrow \uparrow 3).</math>
Теперь каждая тетрация (<math>\uparrow\uparrow</math>) по определению разворачивается в «степенную башню» как
- <math>3 \uparrow\uparrow X \ = \ 3 \uparrow \Bigl(3 \uparrow \bigl(3 \uparrow \dots (3 \uparrow 3) \dots \bigr)\Bigr) \ = \ 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}</math>, где X — количество 3-ек.
Таким образом,
- <math>g_1 = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots ))</math>, где количество троек — <math>3 \uparrow \uparrow (3 \uparrow \uparrow 3)</math>.
Оно может быть записано на языке степеней:
- <math>
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 </math>, где число башен — <math> \quad
\left.
\begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}
\right \}
\left.
\begin{matrix}3^{3^3}\end{matrix}
\right \}
3
</math>,
где количество троек в каждой башне, начиная слева, указывается предыдущей башней.
Другими словами, <math>g_1</math> вычисляется путём вычисления количества башен, <math>n=3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}</math> (где число троек — <math>3^{3^{3}}</math> = 7625597484987), и затем вычисления <math>n</math> башен в следующем порядке:
1-я башня: 3
2-я башня: 3↑3↑3 (количество троек — 3) = 7625597484987
3-я башня: 3↑3↑3↑3↑…↑3 (количество троек — 7625597484987) = …
.
.
.
<math>g_1</math> = <math>n</math>-я башня: 3↑3↑3↑3↑3↑3↑3↑…↑3 (количество троек задаётся результатом вычисления <math>(n-1)</math>-й башни)
Масштаб первого члена, <math>g_1</math>, настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя <math>n</math> — это всего лишь количество башен в этой формуле для <math>g_1</math>, уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно <math>8{,}5\cdot 10^{185}</math>). После первого члена нас ожидают ещё 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.
Ссылки
- [cosmos.d3.ru/chislo-grema-na-paltsakh-649073/ Число Грэма на пальцах]
- «[isu.indstate.edu/ge/GEOMETRY/cubes.html Проблема Рамсея о гиперкубах]». Geoff Exoo (англ.)
- Weisstein, Eric W. [mathworld.wolfram.com/GrahamsNumber.html Graham’s number] (англ.) на сайте Wolfram MathWorld.
- [www-users.cs.york.ac.uk/susan/cyc/g/graham.htm Как вычислить число Грэма] (англ.)
- [sites.google.com/site/numeropedia2/speciallylargenumbers Numeropedia — the Special Encyclopedia of Numbers] (англ.)
| ||||||||||||||||||||||||||
| ||||||||||||||
Отрывок, характеризующий Число Грэма
– Andre, [Андрей,] – сказала его жена, обращаясь к мужу тем же кокетливым тоном, каким она обращалась к посторонним, – какую историю нам рассказал виконт о m lle Жорж и Бонапарте!Князь Андрей зажмурился и отвернулся. Пьер, со времени входа князя Андрея в гостиную не спускавший с него радостных, дружелюбных глаз, подошел к нему и взял его за руку. Князь Андрей, не оглядываясь, морщил лицо в гримасу, выражавшую досаду на того, кто трогает его за руку, но, увидав улыбающееся лицо Пьера, улыбнулся неожиданно доброй и приятной улыбкой.
– Вот как!… И ты в большом свете! – сказал он Пьеру.
– Я знал, что вы будете, – отвечал Пьер. – Я приеду к вам ужинать, – прибавил он тихо, чтобы не мешать виконту, который продолжал свой рассказ. – Можно?
– Нет, нельзя, – сказал князь Андрей смеясь, пожатием руки давая знать Пьеру, что этого не нужно спрашивать.
Он что то хотел сказать еще, но в это время поднялся князь Василий с дочерью, и два молодых человека встали, чтобы дать им дорогу.
– Вы меня извините, мой милый виконт, – сказал князь Василий французу, ласково притягивая его за рукав вниз к стулу, чтоб он не вставал. – Этот несчастный праздник у посланника лишает меня удовольствия и прерывает вас. Очень мне грустно покидать ваш восхитительный вечер, – сказал он Анне Павловне.
Дочь его, княжна Элен, слегка придерживая складки платья, пошла между стульев, и улыбка сияла еще светлее на ее прекрасном лице. Пьер смотрел почти испуганными, восторженными глазами на эту красавицу, когда она проходила мимо него.
– Очень хороша, – сказал князь Андрей.
– Очень, – сказал Пьер.
Проходя мимо, князь Василий схватил Пьера за руку и обратился к Анне Павловне.
– Образуйте мне этого медведя, – сказал он. – Вот он месяц живет у меня, и в первый раз я его вижу в свете. Ничто так не нужно молодому человеку, как общество умных женщин.
Анна Павловна улыбнулась и обещалась заняться Пьером, который, она знала, приходился родня по отцу князю Василью. Пожилая дама, сидевшая прежде с ma tante, торопливо встала и догнала князя Василья в передней. С лица ее исчезла вся прежняя притворность интереса. Доброе, исплаканное лицо ее выражало только беспокойство и страх.
– Что же вы мне скажете, князь, о моем Борисе? – сказала она, догоняя его в передней. (Она выговаривала имя Борис с особенным ударением на о ). – Я не могу оставаться дольше в Петербурге. Скажите, какие известия я могу привезти моему бедному мальчику?
Несмотря на то, что князь Василий неохотно и почти неучтиво слушал пожилую даму и даже выказывал нетерпение, она ласково и трогательно улыбалась ему и, чтоб он не ушел, взяла его за руку.
– Что вам стоит сказать слово государю, и он прямо будет переведен в гвардию, – просила она.
– Поверьте, что я сделаю всё, что могу, княгиня, – отвечал князь Василий, – но мне трудно просить государя; я бы советовал вам обратиться к Румянцеву, через князя Голицына: это было бы умнее.
Пожилая дама носила имя княгини Друбецкой, одной из лучших фамилий России, но она была бедна, давно вышла из света и утратила прежние связи. Она приехала теперь, чтобы выхлопотать определение в гвардию своему единственному сыну. Только затем, чтоб увидеть князя Василия, она назвалась и приехала на вечер к Анне Павловне, только затем она слушала историю виконта. Она испугалась слов князя Василия; когда то красивое лицо ее выразило озлобление, но это продолжалось только минуту. Она опять улыбнулась и крепче схватила за руку князя Василия.
– Послушайте, князь, – сказала она, – я никогда не просила вас, никогда не буду просить, никогда не напоминала вам о дружбе моего отца к вам. Но теперь, я Богом заклинаю вас, сделайте это для моего сына, и я буду считать вас благодетелем, – торопливо прибавила она. – Нет, вы не сердитесь, а вы обещайте мне. Я просила Голицына, он отказал. Soyez le bon enfant que vous аvez ete, [Будьте добрым малым, как вы были,] – говорила она, стараясь улыбаться, тогда как в ее глазах были слезы.
– Папа, мы опоздаем, – сказала, повернув свою красивую голову на античных плечах, княжна Элен, ожидавшая у двери.
Но влияние в свете есть капитал, который надо беречь, чтоб он не исчез. Князь Василий знал это, и, раз сообразив, что ежели бы он стал просить за всех, кто его просит, то вскоре ему нельзя было бы просить за себя, он редко употреблял свое влияние. В деле княгини Друбецкой он почувствовал, однако, после ее нового призыва, что то вроде укора совести. Она напомнила ему правду: первыми шагами своими в службе он был обязан ее отцу. Кроме того, он видел по ее приемам, что она – одна из тех женщин, особенно матерей, которые, однажды взяв себе что нибудь в голову, не отстанут до тех пор, пока не исполнят их желания, а в противном случае готовы на ежедневные, ежеминутные приставания и даже на сцены. Это последнее соображение поколебало его.
– Chere Анна Михайловна, – сказал он с своею всегдашнею фамильярностью и скукой в голосе, – для меня почти невозможно сделать то, что вы хотите; но чтобы доказать вам, как я люблю вас и чту память покойного отца вашего, я сделаю невозможное: сын ваш будет переведен в гвардию, вот вам моя рука. Довольны вы?
– Милый мой, вы благодетель! Я иного и не ждала от вас; я знала, как вы добры.
Он хотел уйти.
– Постойте, два слова. Une fois passe aux gardes… [Раз он перейдет в гвардию…] – Она замялась: – Вы хороши с Михаилом Иларионовичем Кутузовым, рекомендуйте ему Бориса в адъютанты. Тогда бы я была покойна, и тогда бы уж…
Князь Василий улыбнулся.
– Этого не обещаю. Вы не знаете, как осаждают Кутузова с тех пор, как он назначен главнокомандующим. Он мне сам говорил, что все московские барыни сговорились отдать ему всех своих детей в адъютанты.
– Нет, обещайте, я не пущу вас, милый, благодетель мой…
– Папа! – опять тем же тоном повторила красавица, – мы опоздаем.
– Ну, au revoir, [до свиданья,] прощайте. Видите?
– Так завтра вы доложите государю?
– Непременно, а Кутузову не обещаю.
– Нет, обещайте, обещайте, Basile, [Василий,] – сказала вслед ему Анна Михайловна, с улыбкой молодой кокетки, которая когда то, должно быть, была ей свойственна, а теперь так не шла к ее истощенному лицу.
Она, видимо, забыла свои годы и пускала в ход, по привычке, все старинные женские средства. Но как только он вышел, лицо ее опять приняло то же холодное, притворное выражение, которое было на нем прежде. Она вернулась к кружку, в котором виконт продолжал рассказывать, и опять сделала вид, что слушает, дожидаясь времени уехать, так как дело ее было сделано.
– Но как вы находите всю эту последнюю комедию du sacre de Milan? [миланского помазания?] – сказала Анна Павловна. Et la nouvelle comedie des peuples de Genes et de Lucques, qui viennent presenter leurs voeux a M. Buonaparte assis sur un trone, et exaucant les voeux des nations! Adorable! Non, mais c'est a en devenir folle! On dirait, que le monde entier a perdu la tete. [И вот новая комедия: народы Генуи и Лукки изъявляют свои желания господину Бонапарте. И господин Бонапарте сидит на троне и исполняет желания народов. 0! это восхитительно! Нет, от этого можно с ума сойти. Подумаешь, что весь свет потерял голову.]
Князь Андрей усмехнулся, прямо глядя в лицо Анны Павловны.
– «Dieu me la donne, gare a qui la touche», – сказал он (слова Бонапарте, сказанные при возложении короны). – On dit qu'il a ete tres beau en prononcant ces paroles, [Бог мне дал корону. Беда тому, кто ее тронет. – Говорят, он был очень хорош, произнося эти слова,] – прибавил он и еще раз повторил эти слова по итальянски: «Dio mi la dona, guai a chi la tocca».
– J'espere enfin, – продолжала Анна Павловна, – que ca a ete la goutte d'eau qui fera deborder le verre. Les souverains ne peuvent plus supporter cet homme, qui menace tout. [Надеюсь, что это была, наконец, та капля, которая переполнит стакан. Государи не могут более терпеть этого человека, который угрожает всему.]
