Перейти к содержимому 
Теперь можно точно сказать, что гипотеза развенчана.
Почти 40 лет простая гипотеза скромно ютилась в уголке теории графов, никого не трогая. Известная как “гипотеза двухъярусной кровати”, она казалась самоочевидной – да, никто не мог её доказать, но она имела смысл, и уж точно никто не находил контрпримера.
До недавнего времени. К всеобщему удивлению, группа математиков в прошлом месяце объявила о публикации статьи, в которой, по их утверждению, доказывается ложность гипотезы. Статья, пока находящаяся на сервере препринтов arXiv и, следовательно, еще не прошедшая рецензирование, тем не менее, уже вызвала бурное обсуждение в математическом мире – не только из-за самого доказательства, но и из-за того, что оно говорит о математике как о науке в целом.
Содержание
Гипотеза
Впервые выдвинутая физиком Питером Кастейном своему коллеге в 1985 году, гипотеза двухъярусной кровати на самом деле не имеет никакого отношения к кроватям. Скорее, она касается графов – и если вы не практикующий математик, то, вероятно, вы сейчас представляете себе не те графы.
“Граф состоит из множества вершин и множества ребер, соединяющих вершины”, – объясняет Трефор Базетт, доцент кафедры математики и статистики Университета Виктории, в недавнем видео на YouTube, посвященном доказательству. “Можно представить, например, людей в социальной сети”, – предлагает он, – “и тогда связь – это дружба или её отсутствие”.
Удвоив этот граф, можно создать так называемый граф “двухъярусной кровати”: два одинаковых графа, расположенных друг над другом и соединенных “стойками”. Посмотрите – как только вы увидите его, вы поймете всю тематическую терминологию.
Итак, у нас есть наша конструкция – дружба между людьми, или места на карте, соединенные улицами, или что угодно, что вы представляете своим графом. Теперь мы просто подумаем о том, как перемещаться по самому графу. Допустим, вы хотите добраться из точки u в точку v на нашем графе. У нас есть следующие варианты:
Вы еще здесь? Отлично, потому что сейчас все немного усложнится. Теперь мы удалим некоторые рёбра – потеряем друзей, перекроем улицы, что угодно – и посмотрим, насколько вероятно, что мы всё ещё сможем добраться из u в v.
Итак, имея всю эту информацию, мы можем перейти к формулировке гипотезы двухъярусной кровати: P(u ↔ v) ≥ P(u ↔ v’).
“Она гласит, что вероятность того, что я могу добраться из u в v – то есть вероятность того, что я могу перемещаться по основанию, – больше или равна вероятности того, что я могу начать в основании и затем добраться до v’ […] на верхнем ярусе”, – объяснил Базетт.
“Гипотеза утверждает, что это верно для всех связных графов, всех подмножеств стоек и всех пар u и v”.
Интуитивно это имеет смысл: конечно, будет легче добраться до конечной точки на том же уровне, что и ваша начальная точка, чем до той, которая требует от вас еще и подъема по стойке. Попробовав несколько примеров, вы только укрепитесь в этом убеждении – если, конечно, вы не готовы построить граф с несколькими тысячами вершин и рёбер.
Доказательство
Часто в математике опровергнуть гипотезу легче, чем доказать ее. Ведь чтобы доказать что-то, нужно показать, что это верно для каждого возможного примера во всех ситуациях, а чтобы опровергнуть – достаточно найти всего один контрпример.
Проблема с гипотезой двухъярусной кровати заключалась в том, что… никто не искал этот контрпример. “Зачем искать контрпример, если гипотеза настолько очевидна?” – написал Игорь Пак, профессор математики Калифорнийского университета в Лос-Анджелесе и один из авторов новой статьи.
“Ну, потому это так всегда”, – возразил он. “Для любой гипотезы. Особенно если все остальные уверены, абсолютно без тени сомнения, что гипотеза верна.”
Сейчас на дворе 2020-е годы; вы знаете, как сейчас делается математика, и Пак тоже. “Мы начали с множества компьютерных экспериментов, перебирая все небольшие графы”, – написал он. “Когда это не удалось, мы попытались использовать ИИ и другие инструменты компьютерного анализа”.
Даже при этом никаких контрпримеров не появлялось, и команда начала переживатья, что даже если таковой и появится, этого будет недостаточно для полного опровержения гипотезы. Графы, которые анализировались нейронными сетями, были настолько большими, что точный расчет соответствующих вероятностей невозможен, поэтому любое доказательство будет, в лучшем случае, примерно на 99,9999 процентов верным.
Хотя “99,99-процентная уверенность […] может быть золотым стандартом в ядерной физике”, – писал Пак, – “математические журналы, как правило, предпочитают 100-процентную корректность.”
“Большинство журналов отказались бы даже рассматривать ‘пятисигмовый контрпример'”, – добавил он.
Поэтому вместо того, чтобы продолжать использовать методы машинного обучения, которые не приносили результатов – и результаты которых могли быть не приняты, даже если бы они были успешными, – команда сделала шаг назад.
А затем, в июне этого года, на arXiv появилась статья, которая всё изменила.
“Я наткнулся на нее вечером и читал до 3 часов ночи”, – рассказал Никита Гладков, один из аспирантов Пака и соавтор статьи. “Я подумал: ‘Вау, это безумие. Абсолютно умопомрачительно'”.
Это не было точным доказательством гипотезы двухъярусной кровати, но это было близко – формулировка утверждения, которая имела дело с объектами, называемыми гиперграфами, а не графами. Автор, аспирант Кембриджского университета и опытный гуголог по имени Лоуренс Холлом, показал, что в этих объектах гипотеза двухъярусной кровати… ложна.
Холлом представил свою работу как попытку обобщить гипотезу двухъярусной кровати – или, как оказалось, показать, что ее нельзя обобщить. В конце концов, именно его статья вдохновила на доказательство первоначальной гипотезы.
Преобразовав гиперграф Холлома, команда создала граф, который потенциально мог опровергнуть гипотезу двухъярусной кровати. Он был абсолютно монструозным – 7222 вершины, соединенные 14442 ребрами, – а разница в соответствующих вероятностях была ничтожной: “астрономически малой”, – писал Пак, – “порядка -10⁻⁶⁵⁰⁰”.
“Но она отрицательна, а это всё, что нам нужно”, – добавил он. Гипотеза была официально опровергнута.
Итог
Итак, что это значит, помимо очевидного? Ну, есть некоторые разочарования, особенно для прикладных математиков и физиков: если бы гипотеза двухъярусной кровати оказалась верной, она подтвердила бы широко распространенное предположение о том, как жидкости движутся через твердые тела, и дала бы точку опоры исследователям, изучающим физику перколяции.
Но больше того, есть и моральные последствия этого прорыва. Должны ли будущие математики быть более склонны принимать вероятностные доказательства? Будут ли они столь же достоверными или полными?
“Это философский вопрос”, – сказал Нога Алон, профессор математики из Принстона. “Как мы рассматриваем доказательства, которые верны только с высокой вероятностью?”
“Возможно, вероятностное доказательство даст вам меньше понимания или интуитивного представления о том, что на самом деле происходит”, – сказал он.
Наконец, это предупреждение математикам не принимать гипотезу только потому, что она им нравится. “Мы должны относиться с подозрением даже к тому, что интуитивно кажется очень вероятным”, – сказал Алон.
Это убеждение, которое Пак долго отстаивал. “Некоторые предположения мотивированы содержанием, – сказал он, – а другие основаны на принятии желаемого за действительное.”
Гипотеза двухъярусной кровати, похоже, относилась к последним.
Статью, которая пока не прошла рецензирование, можно найти на arXiv.
Читайте также: Является ли математика изобретением человека, или она может быть языком Вселенной?
Комментировать можно ниже в разделе “Добавить комментарий”.