Два математика доказали давнюю гипотезу, которая стала шагом на пути к поиску худшей формы для упаковки фигур на плоскости
На протяжении столетий математики подозревали, что шестиугольные плитки — лучший способ заполнения пространства. Под этим они имели в виду, что если вы хотите разделить большую площадь на плитки одинакового размера и при этом минимизировать периметр каждой плитки, то лучше шестиугольников ничего не придумаешь. В 1999 году Томас Хейлз из Питтсбургского университета наконец доказал это. Они лучше, чем квадраты, треугольники или любые другие альтернативы.
Но многие фигуры не могут быть выложены плиткой без зазоров. Например, круги, очевидно, не могут. При наилучшем варианте укладки — шестиугольной форме круга — вы заполните почти 90,69 % плоскости.
В 1920-х годах математики задались вопросом: какая форма упаковывается хуже всего? Другими словами, какая форма заставляет вас оставлять самые большие пробелы, даже если вы упаковываете её наилучшим возможным способом? Новая статья Хейлза и его бывшей аспирантки Кундиньи Ваджха, ныне инженера компании Intel, знаменует собой большой прорыв в этом поиске.
Определение наихудшей формы требует соблюдения нескольких правил. Легко придумать произвольно плохие формы, содержащие отверстия или углубления внутрь, как эти полые квадраты:
С математической точки зрения они не так уж интересны, потому что, делая края всё тоньше, можно легко получить форму, которая заставит произвольно большую часть пространства быть пустой. Но если добавить требование, чтобы фигура была выпуклой — то есть, чтобы при выборе любых двух точек фигуры соединяющий их отрезок был внутри фигуры, — то такие полые фигуры становятся запрещёнными, и задача становится более интригующей.
Математиков интересуют фигуры, которые имеют одно дополнительное ограничение: центральную симметрию. Без неё худшей известной фигурой является семисторонний правильный семиугольник (заполненность пространства — около 89,27 %), хотя математики пока не могут доказать, что он самый худший. Хейлз и Ваджха работали над более ограниченным и, следовательно, более простым вопросом: какая фигура с наихудшей упаковкой является одновременно выпуклой и центрально-симметричной?
Сначала математики считали, что это круг. Затем, в 1934 году, немецкий математик по имени Карл Рейнхардт обнаружил нечто худшее: восьмиугольник с закруглёнными краями. Если нарисовать дуги в углах с помощью гипербол, то общий охват составит около 90,24 %. Разница между ним и 90,69 % круга ничтожна, но с математической точки зрения она очень важна.
Рейнхардт не смог доказать, что его округлый восьмиугольник — самая худшая из подобных форм. Не смог этого сделать и никто другой. «Я всегда считал, что Рейнхардт, вероятно, прав, но теории для решения этой проблемы не было», — говорит Генри Кон , математик из Microsoft Research, известный своей работой по упаковке сфер в высших измерениях. «Увидим ли мы когда-нибудь доказательство? Вероятно, не при моей жизни».
Такое доказательство пока не появилось. Но майская работа Хейлза и Ваджхи подтвердила важнейшую промежуточную гипотезу.
Даже больше, чем своим результатом о шестиугольниках, Хейлз известен тем, что в конце 1990-х годов доказал предположение Иоганна Кеплера XVII века о наилучшем способе упаковки сфер в трёх измерениях (иногда его называют проблемой укладки апельсинов, поскольку она напоминает фруктовые пирамиды на рынке). Поскольку доказательство опиралось на компьютерные расчёты, ему потребовались годы после его публикации, чтобы убедить математическое сообщество в его справедливости.
В 2007 году, находясь в академическом отпуске во Вьетнаме, Хейлз доделывал оставшиеся мелочи в своём доказательстве догадки Кеплера, когда он переключил внимание с наилучших возможных упаковок на наихудшие. Но прогресс был медленным.
Худшее, конечно, впереди
В задаче о наихудшей упаковке требуется найти фигуру, наибольшая плотность упаковки которой покрывает наименьшую часть плоскости. Подобные ограничения относятся к классу задач, называемых минимаксными задачами, которые по своей сути являются довольно хитрыми. Стандартный способ решения этих задач — набор методов, называемых вариационным исчислением. Рейнхардт использовал его в своей проблеме упаковки, чтобы попытаться доказать оптимальность округлых восьмиугольников. Скруглённые точки прослеживаются с помощью гипербол — кривых, которые сбривают как можно больше площади, не меняя схемы упаковки. Это означало, что ожидаемое решение будет включать не только кривые, но и смесь кривых и прямых граней.
Хейлз попытался продолжить начатое Рейнхардтом, но вскоре понял, что вариационного исчисления будет недостаточно для решения проблемы. Основная проблема, как он заметил, заключалась в том, что, хотя эти методы хороши для поиска оптимальных кривых, соответствующих набору нужных параметров, искомое решение не было именно кривой. Если бы решение было таким, как предполагал Рейнхардт, то оно представляло бы собой более сложную структуру, в которой сочетались бы кривые и прямые грани.
В 2017 году, после десятилетия непрерывной работы, Хейлз опубликовал препринт, в котором предложил своего рода план доказательства. Он предложил использовать ветвь математики под названием теория оптимального управления, которая, по его мнению, лучше подходит для исследования структур с переворотами. Для других математиков неприступная проблема вдруг стала выполнимой. «Я был очень впечатлен творческим подходом», — говорит Кон. «Но, с другой стороны, я подумал, что потребуется очень много работы, чтобы на самом деле осуществить это».
Вскоре после того, как Хейлз изложил свой план, Ваджха приехал в Питтсбург, чувствуя себя немного потерянным, как и многие студенты в начале обучения в аспирантуре. Он надеялся изучать формальные методы — техники, используемые для проверки программного и аппаратного обеспечения, — и посещал всевозможные конференции по всему городу в поисках подходящей проблемы, на которой можно было бы сосредоточиться. На одном из них он узнал о поиске лучшего упаковщика, и хитрость этой проблемы показалась ему интригующей. Ещё больше его заинтересовало, когда в тот же день он нашёл препринт Хейлза, в котором предлагался радикально новый подход к решению проблемы.
Они встретились на следующей неделе. Я сказал ему: «Если это так просто, почему бы тебе не сделать это?» вспоминает Ваджха. Хейлз ответил, что вместе они, вероятно, справятся с этим примерно за шесть месяцев. Ваджха согласился. «Всё никогда не бывает так просто», — сказал он недавно.
Чтобы доказать, что округлый восьмиугольник — это форма с наихудшей упаковкой, Хейлзу и Ваджхе пришлось исключить все остальные возможные формы. Даже с учётом таких ограничений, как центральная симметрия и выпуклость, они столкнулись с проблемой с бесконечным количеством потенциальных ответов, многие из которых демонстрируют странное поведение, из-за которого они могут казаться жизнеспособными решениями, хотя на самом деле они таковыми не являются. Например, есть фигуры-кандидаты, которые могут бесконечно часто переходить от прямых линий к кривым, что называется «болтающими» решениями. Это может показаться парадоксальным, но такие фигуры могут быть лучше, чем круг. Может быть, они даже лучше, чем округлый восьмиугольник Рейнхардта?
В объёмном доказательстве догадки Кеплера, проведённом Хейлзом, использовался компьютерный подход, который предполагал исключение почти бесконечного множества возможных упаковок с помощью грубой силы. Эта работа считалась новаторской — и в то время несколько противоречивой, поскольку рецензенты сочли, что проверить результаты работы программ слишком трудно. Хейлз надеялся использовать аналогичные методы для поиска наихудшей формы, но ему мешало огромное количество «лишних» решений. «Если всё будет меняться бесконечно много раз, то это будет нелегко обработат на компьютере», — говорит Хейлз.
Чтобы избавиться от этих и других непонятных структур, нужно было найти творческий подход к их исключению. Они попробовали упростить проблему, введя новые симметричные ограничения, а затем вернулись к исходной задаче. «Как и в физике, в математике есть идея, что если у вас есть симметрия, то есть и законы сохранения, — говорит Хейлз. Эти законы могут помочь исключить некоторые из структур.
Тем не менее, новые возможности продолжали появляться. «Когда я решил заняться этой проблемой, я знал, что она сложна, но при попытке её упростить в ней постоянно находилось ещё больше скрытой структуры», — говорит Ваджха. «И до окончания работы всегда оставалось ещё шесть месяцев». Прошло пять лет, и ему уже пора было получать диплом. Он планировал жениться и переехать на Западное побережье. «Мы не могли знать наверняка, не начнёт ли эта проблема сопротивляться и не решит ли она остаться нерешённой ещё на столетие». Мысль о том, чтобы оставить после себя незаконченное доказательство, была мучительной, но у него просто заканчивались возможности. Он окончил университет в августе 2022 года, недолго поработал в стартапе по разработке ИИ, а затем устроился на работу в Intel для формальной проверки процессоров, вернувшись к намеченной специальности.
Весной следующего года Ваджха вернулся в Питтсбург на церемонию вручения дипломов. Они с Хейлзом сетовали на то, что им удалось подробно изложить множество новых идей и методов, но так и не создать надёжной теоремы. Неделю спустя Хейлза осенило: они были близки к доказательству связанной с их работой гипотезы, выдвинутой Куртом Малером, математиком, работавшим независимо от Рейнхардта, в 1946 году. «Я всегда как бы отмахивался от Малера, потому что он делал то же самое, что и Рейнхардт, только на несколько лет позже», — говорит Хейлз. Но Малер сделал важное наблюдение, разбив проблему на два этапа. Его первая гипотеза заключалась в том, что ответом на задачу будет сглаженный многоугольник с прямыми краями и углами, закруглёнными гиперболами. Его вторая гипотеза совпадала с гипотезой Рейнхардта — закруглённый восьмиугольник является наихудшей из возможных форм. Пара ещё не дошла до первого шага Малера, но Хейлз понял, что они близки к этому. Он попросил у Ваджхи месяц на обдумывание.
Месяц прошёл, и двое начали обмениваться электронными письмами — раскрывая все новые структуры и отвергая их, признавая наличие все большего количества сомнений и усталости. Месяц растянулся на год. Наконец Хейлз отправил Ваджхе сообщение. Первая догадка Малера «снова появилась на горизонте. Я почти уверен, что доказал её».
Их доказательство первой гипотезы Малера — спустя шесть лет, а не шесть месяцев — представляет собой 260-страничное исследование темы, в котором подробно описывается головокружительное множество структур-кандидатов и используется гораздо больший спектр теории, чем даже Хейлз первоначально предполагал. Работа ещё не прошла рецензирование, но математики, которые неофициально ознакомились с ней, включая Кона и Грега Куперберга, математика из Калифорнийского университета в Дэвисе, сказали, что они уверены в результате, учитывая репутацию Хейлза, который очень осторожно относится к сложным доказательствам.
Однако, добавил Куперберг, «на самом деле они не пересекли финишную черту». Иногда проблемы томятся десятилетиями, даже когда теории разработаны и промежуточные шаги достигнуты. В конце концов, доказательство Хейлзом догадки Кеплера опиралось на подходы, разработанные венгерским математиком Ласло Фейешем Тотом 50 годами ранее. «Возможно, все идеи для завершения работы Рейнхардта уже есть. Возможно, нет», — говорит Хейлз. «Мы оставим это под знаком вопроса».
