Откуда взялось число Грэма
Мнение редакции может не совпадать с мнением автора
Некоторые числа могут кардинально изменить наше понимание реальности. Окажется, например, что трехмерное пространство — это иллюзия, а Вселенная расширяется не совсем так, как мы думали. В книге «Удивительные числа Вселенной. Путешествие за грань воображения» (издательство «Манн, Иванов и Фербер»), переведенной на русский язык Евгением Поникаровым, физик-теоретик Антонио Падилья рассказывает о девяти числах, которые могут стать ключом к пониманию черных дыр, теории относительности и проблемы космологической постоянной. Предлагаем вам ознакомиться с фрагментом о появлении числа настолько большого, что попытка уместить его в голове приведет к смерти.
Когда я был маленьким, на канале BBC шло популярное телешоу под названием «Задумайте число». Его ведущий Джонни Болл бегал по сцене в отличных костюмах с кучей великолепного реквизита, наполняя наши юные впечатлительные умы радостями науки. Естественно, мне это безумно нравилось. «Задумайте число» — безобидная образовательная забава. Или нет?
Совершенно нормально придумать число 7, 15 или 476 522. Но что произойдет, когда вы задумаете число Грэма? Что ж, если вы это сделали, это действительно не нормально. Если вы будете думать о числе Грэма неправильно, вы умрете. Задним числом кажется, что Джонни Боллу в реальности следовало бы назвать свое шоу «Задумайте число, которое не убьет вас», но, полагаю, в Британии 1980-х вопросы здоровья и безопасности не были особо актуальными.
Заманчиво сравнить смерть от числа Грэма с судьбой некоторых людей, пострадавших при извержении Везувия в 79 году нашей эры. Возможно, вы видели изображения жертв в Помпеях: убитые жаром пирокластических потоков, они навсегда оказались погребены Под пеплом остались в лучшем случае кости. Изображения людей, которые вы могли видеть, — это гипсовые слепки, которыми ученые заливают пустоты в пепле, оставшиеся от испарившихся со временем тел. Полученные статуи показывают позы, в которых умерли люди (в основном от проблем с дыханием и от температуры). Прим. пер.
Смерть от превращения головы в черную дыру.
Истина в том, что вы не можете задумать число Грэма, — по крайней мере, во всей его гигантской красе. Оно просто слишком велико, чтобы с ним можно было иметь дело — вам или кому угодно. Проблема не в интеллекте, а в физике. Если вы попытаетесь впихнуть столько информации в человеческую голову, та неизбежно сколлапсирует и превратится в черную дыру. Как мы увидим, черные дыры ограничивают количество информации, которую можно втиснуть в определенный объем пространства, а ваша голова далеко не так велика, чтобы справиться со всей информацией, содержащейся в числе Грэма. Это проблема самого числа. Оно не просто огромно, а феерично, оно гораздо больше, чем гугол, гуголплекс или даже гуголплексиан. Число Грэма и все его цифры не могут существовать ни в вашей голове, ни в наблюдаемой Вселенной, ни даже в гуголплексианской Вселенной. В его десятичном представлении содержится слишком много информации, ее просто невозможно вместить.
Зачем кому-то изобретать число, способное вас убить? Ответственность за это несет обладатель многочисленных наград математик Рональд Грэм. Он без почтения относился к стереотипам о математиках. Когда в начале 1950-х пятнадцатилетний подросток с лицом младенца поступил в колледж в Чикаго, он начал заниматься прыжками на батуте и жонглированием; в итоге он достиг такого мастерства, что стал выступать с цирковой группой Bouncing Baers. Даже в старости он продолжал прыгать, хотя уже в комфортных условиях собственного дома. Как рассказывают его друзья, от Рона Грэма всегда ждали неожиданного. Он мог обсуждать математику, а в следующий момент — встать на руки или запрыгать вокруг вас на пого-стике.
История числа Грэма на самом деле начинается на заре XX века с другого яркого математика по имени Фрэнк Рамсей. Тот был эрудитом и членом тайного общества интеллектуалов, известного как «Кембриджские апостолы» — группа, занимавшаяся интеллектуальными дискуссиями и состоявшая в основном из студентов Кембриджского университета. Она приобрела некоторую известность в 1950-х и 1960-х, когда стало известно, что два ее бывших участника, Гай Берджесс и Энтони Блант, оказались частью кембриджской шпионской сети, передавшей британские секреты Советскому Союзу. Рамсей был «апостолом» в 1920-х, за десять лет до избрания Берджесса и Бланта, и, несмотря на его левые взгляды, нет никаких оснований предполагать, что он был замешан в шпионаже. Прим. авт. [Особенно если учесть, что Рамсей умер в 1930 году, когда до контактов Берджесса и Бланта с советской разведкой оставалось еще несколько лет. Прим. пер.]
Теория Рамсея связана с получением порядка из хаоса. Это немного Объяснение взято из книги: Freiberger M., Thomas R. Numericon. Quercus,
2015.
Сплошные линии обозначают людей, которые знакомы друг с другом, а пунктирные отражают незнакомых людей. Следующий гость — Дино, профессор одного из университетов Лига плюща — группа из восьми частных престижных университетов в северовосточном регионе США (Йельский, Колумбийский, Принстонский, Корнелльский, Гарвардский, Пенсильванский, Брауновский университеты и Дартмутский колледж). Прим. пер.
Осталось еще два человека. И Эрнест, и Фонси знают Беллу, но не знакомы ни друг с другом, ни с другими гостями. Эрнест — инженер, дед которого занимался ввозом североамериканских серых белок в Британию (это тоже реальная история). Фонси — начинающий политик. В очередной раз обновляю диаграмму.
Уже сейчас, когда гостей всего шесть, сетка сплошных и пунктирных линий выглядит хаотично. Но если вы заглянете внутрь этого хаоса, то начнете видеть определенный порядок. Например, Алджернон, Кларки и Дино образуют так называемую В общем случае кликой в теории графов называется полный подграф. Это некоторое подмножество вершин исходного графа, причем все вершины в этом подмножестве соединены ребрами между собой. Прим. пер.
Подобные сети лежат в основе теории Рамсея. На самом деле нет ничего удивительного, что на вечеринке с шестью гостями мы обнаружили такие клики из трех человек. Это неизбежно должно было Автор не совсем ясно выразился. Справедливо утверждение (задача Рамсея): в любой группе из шести человек всегда найдется либо трое знакомых между собой, либо трое не знакомых между собой. Обе тройки одновременно найтись могут, но не обязательно — в качестве контрпримера можно рассмотреть группы, где все шестеро знают друг друга или, наоборот, никто не знает друг друга. В терминах клик-задача Рамсея звучит так: если полный граф с шестью вершинами выкрашен в два цвета, то существует либо клика на трех вершинах цвета 1, либо клика на трех вершинах цвета 2. Прим. пер. Математики обычно определяют число Рамсея с помощью двух целых чисел
n и m. Число Рамсея R(m, n) — наименьшее количество гостей, которых необходимо пригласить на вечеринку, чтобы получить клику из m знакомых
или клику из n незнакомых. Но для простоты я всегда буду называть число
R(n, n) просто n-м числом Рамсея.
Рамсей показал, что можно получить клики любого конечного размера, если пригласить на вечеринку достаточно большое количество людей. Но он не смог определить, сколько именно людей придется созвать. Даже в случае клики всего из пяти человек ситуация резко усложняется. Большинство математиков считает, что для гарантированного получения клики из пяти человек требуется пригласить минимум 43 гостя, однако точный ответ никому не известен. Минимальное число находится где-то между 43 и 48.
Чтобы определить его точно, математикам требуется изобразить все возможные сети и посмотреть, где гарантированно возникнут клики из пяти элементов. Для этого можно попробовать привлечь компьютер, однако вам просто не хватит вычислительной мощности. Когда есть 43 гостя, вы поручаете компьютеру изучить 2903 разных сетей. Это число значительно больше гугола. Даже современные суперкомпьютеры отказываются работать с такими числами.
Чтобы гарантировать клику из шести человек, минимальное число гостей должно быть где-то между 102 и 165. Очевидно, что проблема нахождения точного значения шестого числа Рамсея значительно сложнее, чем нахождение пятого. Великий странствующий математик Пал Эрдеш предложил следующее апокалиптическое описание ситуации. Представьте вторжение инопланетян — армию пришельцев, намного опередивших нас в развитии. Они высадились на Землю и потребовали, чтобы мы сообщили им пятое число Рамсея, а иначе они уничтожат нашу цивилизацию за глупость. Стратегия Эрдеша для этого случая заключалась в том, чтобы объединить мощь всех компьютеров мира и довериться математикам, которые дадут ответ на вопрос. Но если бы пришельцы потребовали шестое число Рамсея, то такая стратегия бессмысленна. В этом случае придется искать способ уничтожить инопланетян до того, как они уничтожат нас.
Яркий пример Эрдеша позволяет познакомиться с его уникальным характером. Этот эксцентричный математик, родившийся в Будапеште перед Первой мировой войной, большую часть своей взрослой жизни провел в путешествиях, редко задерживаясь на одном месте более чем на месяц. Он постоянно ездил по континентам от одного коллеги к другому, разыскивая новые решения для своего сборника математических задач. Если Эрдеш появлялся с чемоданом у вашей двери, предполагалось, что вы обеспечите ему кров и еду на столько времени, на сколько он захочет, спланируете и организуете его дела. Если у вас имелись дети, он называл их эпсилонами, намекая на обозначение, которое математики используют, когда хотят описать что-то бесконечно малое. У него также имелась какая-то задача, предназначенная для вас. Это было его величайшее умение — соединить какую-нибудь математическую проблему с тем самым человеком, который может помочь решить ее. На протяжении своей удивительно необычной карьеры, подпитываемой пристрастием к запрещенным веществам, венгерский математик написал более 1500 статей, причем большинство его работ были совместными: у него насчитывалось свыше 500 соавторов. Из-за таких методов ученые ввели число Эрдеша (это длина кратчайшего пути от данного человека до Эрдеша посредством совместных публикаций), и у большинства математиков число Эрдеша очень Вот рекуррентный метод определения числа Эрдеша. Сам Эрдеш имеет число Эрдеша, равное нулю. Любой соавтор Эрдеша (ученый, написавший с ним хотя бы одну совместную статью), имеет число Эрдеша, равное 1. Соавторы людей, имеющих число Эрдеша 1, получают число Эрдеша 2 (если только уже не имеют число 1). И так далее: соавторы людей с числом Эрдеша n получают число n+1 (если только у них уже не определено число Эрдеша, меньшее или равное n). Например, и автор, и переводчик этой книги на данный момент имеют число Эрдеша 4. Свое число Эрдеша вы можете узнать, скажем, на сайте mathscinet.ams.org/mathscinet/freeTools.html (если у вас есть какие-то научные работы, попавшие в эту базу). Если же никакой цепочки из совместных работ от вас до Пала Эрдеша не найдется, то ваше число Эрдеша по определению равно бесконечности. Прим. пер.
У Рона Грэма число Эрдеша равно 1. Они были очень близкими людьми — настолько, что Грэм устроил в своем доме «комнату Эрдеша», где математик мог жить во время своих визитов и хранить вещи, когда уезжал. Грэм даже заботился о финансах Эрдеша, собирая его чеки и оплачивая счета. Однако к знаменитому числу Грэма венгерский математик отношения не имеет. Оно появилось благодаря сотрудничеству с другим американским математиком Брюсом Ли Ротшильдом, а затем с Мартином Гарднером, который вел рубрику математических развлечений в журнале Scientific American.
Грэм и Ротшильд занимались одной конкретной задачей из теории Рамсея. Чтобы понять ее, добавим к нашему званому ужину еще пару гостей — Грэма и Харольда. Грэм — дядя Беллы, а Харольд — какая-то загадка. Кажется, он свободно говорит на пяти разных языках, но никто толком не знает, кто он и чем занимается, да и разговаривает он мало, — возможно, он шпион. На самом деле это не имеет значения. Важно то, что теперь у нас есть восемь гостей, то есть мы можем расположить их в вершинах куба и создать сеть нового типа.
Предположим, я решил сделать через эту сеть какой-то разрез. Например, я мог бы провести его по диагонали через Беллу, Кларки, Эрнеста и Харольда. Эти четыре человека образуют своеобразную подсеть, которую гораздо проще нарисовать на плоском листе бумаги.
Но это не клика — это ничем не примечательное сочетание знакомых и незнакомых людей. Можно ли сделать более интересный разрез? В данном случае ответ положительный: проведя разрез по задней стенке куба через Эрнеста, Фонси, Грэма и Харольда, мы получим клику из четырех незнакомых попарно людей.
Грэму и Ротшильду хотелось узнать, в любом ли кубе всегда существует разрез, дающий такую клику. Если взять пространство трех измерений, то ответ отрицательный: существуют расстановки восьми гостей по вершинам куба, когда при любом разрезе клика не получится. Но, разумеется, математики не привязаны к трехмерному миру, поэтому Грэм и Ротшильд начали думать о гиперкубах в пространствах четырех, пяти, шести или любого другого числа измерений. Сколько измерений нужно взять, чтобы гарантировать клику на каком-нибудь Более строгая формулировка задачи. Возьмем n-мерный гиперкуб, у которого все вершины соединены между собой (иными словами, полный граф с 2n вершинами). Раскрасим каждое ребро в один из двух цветов. При каком наименьшем значении n при любой такой раскраске обязательно найдется одноцветный полный подграф с четырьмя вершинами, лежащими в одной плоскости? Прим. пер.
Не стоит и говорить, что Грэм и Ротшильд не смогли дать определенного ответа на этот вопрос, — так бывает с большинством задач в теории Рамсея. Однако они показали, что у задачи есть конечный ответ, и смогли дать для него оценку: это минимальное число измерений должно находиться между числом 6 и каким-то исполинским числовым монстром — неким конечным числом, превосходящим все, что мы когда-либо могли понять. Вопреки распространенному мнению, тот гигантский верхний предел, который они представили, — это не то, что мы сейчас называем Сейчас эта величина называется малым числом Грэма (Little Graham). Прим. пер.
Подробнее читайте:
Падилья, А. Удивительные числа Вселенной. Путешествие за грань воображения / Антонио Падилья ; пер. с англ. Евгения Поникарова ; науч. ред. Марка Ширченко. — Москва : МИФ, 2025. — 400 с. — (МИФ. Научно-популярные книги)