Математики завершили квест по созданию «сферических кубов»

В четвертом веке греческий математик Папп Александрийский похвалил пчел за их «геометрическую предусмотрительность». Шестиугольная структура их сот казалась оптимальным способом разделить двухмерное пространство на ячейки одинаковой площади и минимального периметра, что позволило насекомым сократить количество воска, которое им необходимо для производства, и тратить меньше времени и энергии на строительство своих строений. улей.

Или так предполагали Папп и другие. На протяжении тысячелетий никто не мог доказать, что шестиугольники оптимальны — пока, наконец, в 1999 году математик Томас Хейлз не показал, что никакая другая форма не может быть лучше. Сегодня математики до сих пор не знают, какие фигуры могут строить мозаику из трех или более измерений с наименьшей возможной площадью поверхности.

Эта проблема «пены» нашла широкое применение — для физиков, изучающих поведение мыльных пузырей (или пены), и химиков, анализирующих структуру кристаллов, для математиков, изучающих устройства упаковки сфер, и статистиков, разрабатывающих эффективные методы обработки данных. .

В середине 2000-х особая формулировка проблемы пены также привлекла внимание теоретиков-компьютерщиков, которые, к своему удивлению, обнаружили, что она тесно связана с важной открытой проблемой в их области. Они смогли использовать эту связь, чтобы найти новую многомерную форму с минимальной площадью поверхности.

«Мне нравится это туда-сюда», — сказал Ассаф Наор Принстонского университета. «Некоторая старая математика становится актуальной для информатики; информатика окупается и решает вопрос в математике. Очень приятно, когда это происходит».

Но этой форме, хотя и оптимальной, не хватало чего-то важного: геометрической основы. Поскольку его существование было доказано с помощью компьютерных технологий, его фактическую геометрию было трудно понять. Вот что Наор вместе с Одед Регев, ученый-компьютерщик из Курантского института Нью-Йоркского университета, решил исправить в доказательство, размещенное в Интернете в прошлом месяце.

«Это очень хороший конец истории, — сказал Регев.

Кубические пены

Математики рассмотрели и другие версии проблемы пены, в том числе то, что произойдет, если вам разрешено делить пространство только в соответствии с так называемой целочисленной решеткой. В этой версии задачи вы берете квадратный массив равномерно расположенных точек (каждая на расстоянии 1 единицы друг от друга) и делаете каждую из этих точек центром фигуры. В «кубической» задаче о пене задается вопрос, какой будет минимальная площадь поверхности, когда вам потребуется таким образом выложить пространство плиткой.

Первоначально исследователи были заинтересованы в наложении этого ограничения, чтобы понять свойства топологических пространств, называемых многообразиями. Но вопрос обрел собственную жизнь, став актуальным в анализе данных и других приложениях.

Это также интересно с геометрической точки зрения, потому что это меняет то, что может означать «оптимальный». Например, в двух измерениях правильные шестиугольники больше не могут замостить плоскость, если их можно сдвинуть только на целое число по горизонтали и вертикали. (Вы должны перемещать их на иррациональные количества в одном из двух направлений.)

Квадраты могут. Но разве это лучшее, что можно сделать? Как математик Джейгён Чхве обнаружен в 1989 году, ответ отрицательный. Вместо этого оптимальной формой является шестиугольник, сплющенный в одном направлении и удлиненный в другом. (Периметр такого шестиугольника приблизительно равен 3.86, когда его площадь равна 1, что превосходит периметр квадрата, равный 4.)

Эти различия могут показаться тривиальными, но они становятся намного больше в более высоких измерениях.

Среди всех форм данного объема та, которая минимизирует площадь поверхности, — это сфера. Как n, число измерений растет, площадь поверхности сферы увеличивается пропорционально квадратному корню из n.

Но сферы не могут замостить пространство, не оставляя пробелов. С другой стороны, n-мерный куб объемом 1 банка. Загвоздка в том, что площадь его поверхности равна 2n, растущий прямо пропорционально его размерности. 10,000 1-мерный куб объема 20,000 имеет площадь поверхности 400 10,000 — намного больше, чем XNUMX, приблизительная площадь поверхности XNUMX XNUMX-мерной сферы.

Поэтому исследователи задались вопросом, смогут ли они найти «сферический куб» — форму, которая n-мерное пространство, похожее на куб, но площадь поверхности которого растет медленно, как у сферы.

Это казалось маловероятным. «Если вы хотите, чтобы ваш пузырь точно заполнил пространство и был центрирован на этой кубической сетке, трудно представить, что бы вы использовали, кроме кубического пузыря», — сказал он. Райан О'Доннелл, ученый-теоретик из Университета Карнеги-Меллона. «Действительно кажется, что куб должен быть лучшим».

Теперь мы знаем, что это не так.

Сложность сложных проблем

В течение десятилетий проблема кубической пены оставалась относительно неисследованной в более высоких измерениях. Первые исследователи, добившиеся прогресса в этом, пришли не из области геометрии, а из области теоретической информатики. Они наткнулись на него случайно, когда искали способ доказать центральное утверждение в своей области, известное как уникальная игровая гипотеза. «Гипотеза об уникальных играх, — сказал Регев, — это то, что я сейчас считаю самым большим открытым вопросом в теоретической информатике».

Предложен в 2002 г. Субхаш Хот, в то время аспирант, предполагает, что если конкретная проблема — та, которая включает в себя присвоение цветов узлам сети — не может быть решена точно, то найти даже приблизительное решение очень сложно. Если это правда, эта гипотеза позволит исследователям одним махом понять сложность широкого спектра других вычислительных задач.

Ученые-компьютерщики часто классифицируют задачи на основе того, могут ли они быть решены с помощью эффективного алгоритма или же они являются «NP-трудными» (что означает, что они не могут быть эффективно решены по мере роста размера проблемы, пока широко распространено мнение). но недоказанная гипотеза о вычислительной сложности верна). Например, задача коммивояжера, в которой требуется найти кратчайший путь, необходимый для посещения каждого города в сети только один раз, является NP-трудной. То же самое можно сказать и о том, можно ли пометить граф — набор вершин, соединенных ребрами, — не более чем тремя цветами, чтобы любые две связанные вершины были разных цветов.

Оказывается, для многих из этих задач NP-сложно найти даже приблизительное решение. Допустим, вы хотите пометить вершины графа разными цветами таким образом, чтобы он удовлетворял некоторому списку ограничений. Если удовлетворить все эти ограничения NP-трудно, как насчет того, чтобы попытаться выполнить только 90% из них, или 75%, или 50%? Ниже некоторого порога можно придумать эффективный алгоритм, но выше этого порога проблема становится NP-сложной.

На протяжении десятилетий ученые-компьютерщики работали над определением пороговых значений для различных интересующих задач оптимизации. Но некоторые вопросы ускользают от такого описания. В то время как алгоритм может гарантировать 80% наилучшего решения, достижение 95% наилучшего решения может быть NP-сложным, оставляя нерешенным вопрос о том, где именно между 80% и 95% проблема переходит на NP-трудную территорию.

Гипотеза об уникальных играх, или UGC, предлагает способ немедленно определить ответ. Он делает утверждение, которое на первый взгляд кажется более ограниченным: NP-трудно определить разницу между графом, для которого можно удовлетворить почти всем из определенного набора ограничений на раскраску (скажем, более 99%), и графом для которые вы можете удовлетворить едва ли (скажем, менее 1%).

Но вскоре после того, как в 2002 году был предложен UGC, исследователи показали, что если гипотеза верна, то вы можете легко вычислить порог сложности для любой задачи удовлетворения ограничений. (Это связано с тем, что UGC также подразумевает, что известный алгоритм достигает наилучшего возможного приближения для всех этих проблем.) «Это был именно стержень для всех этих проблем оптимизации», — сказал О'Доннелл.

Итак, теоретики-компьютерщики решили доказать UGC — задача, которая в конечном итоге привела некоторых из них к открытию сферических кубов.

Делаем сложные проблемы еще сложнее

В 2005 году О'Доннелл работал в Microsoft Research. Он и двое его коллег — Уриэль Файги, ныне в Институте науки Вейцмана, и Гай Киндлер, в настоящее время в Еврейском университете в Иерусалиме — объединились для борьбы с UGC.

У них было смутное представление о том, как они хотели действовать. Они начинали с вопроса о графиках — очень похожего на пользовательский контент. Так называемая задача о максимальном разрезе («максимальном разрезе») спрашивает, как разбить граф на два набора (или цвета) так, чтобы количество ребер, соединяющих эти наборы, было как можно больше. (Вы можете думать о максимальном разрезе как о наилучшем способе раскрасить граф двумя цветами, чтобы как можно меньше ребер соединяли вершины одного цвета.)

Если UGC верен, это будет означать, что для некоторого случайного графа эффективный алгоритм аппроксимации может получить только около 87% истинного максимального разреза этого графа. Сделать что-то лучше было бы NP-сложно.

Файги, Киндлер и О'Доннелл вместо этого хотели пойти в противоположном направлении: они надеялись показать, что максимальное сокращение трудно приблизить, а затем использовать это, чтобы доказать пользовательский контент. Их план основывался на силе техники, называемой параллельным повторением — умной стратегии, усложняющей сложные задачи.

Скажем, вы знаете, что NP-трудно отличить проблему, которую вы можете решить, от той, которую вы в основном можете решить. Параллельное повторение позволяет вам опираться на это, чтобы показать гораздо более сильный результат сложности: также NP-трудно отличить проблему, которую вы можете решить, от той, которую вы едва можете решить вообще. «Это неинтуитивное, глубокое явление… сегодня лежит в основе многих компьютерных наук», — сказал Наор.

Но есть одна загвоздка. Параллельное повторение не всегда усложняет задачу так сильно, как того хотят компьютерщики. В частности, есть аспекты проблемы максимального сокращения, которые «создают большую головную боль для параллельного повторения», — сказал Регев.

Файги, Киндлер и О'Доннелл сосредоточились на том, чтобы показать, что параллельное повторение может работать, несмотря на головную боль. «Это действительно сложная вещь для анализа», — сказал Дана Мошковитцученый-теоретик из Техасского университета в Остине. «Но это казалось мучительно близким. Казалось, что параллельное повторение [поможет установить] эту связь между максимальной версией и уникальными играми».

В качестве разминки исследователи попытались понять параллельное повторение для простого случая максимального сокращения, которое Мошковиц назвал «самым глупым максимальным сокращением». Рассмотрим нечетное количество вершин, соединенных ребрами, образующих круг или «нечетный цикл». Вы хотите пометить каждую вершину одним из двух цветов, чтобы ни одна пара смежных вершин не была одного цвета. В данном случае это невозможно: одно ребро всегда будет соединять вершины одного цвета. Вы должны удалить это ребро, «разорвав» нечетный цикл, чтобы ваш граф удовлетворял ограничениям задачи. В конечном счете, вы хотите свести к минимуму общую долю ребер, которые необходимо удалить, чтобы правильно раскрасить граф.

Параллельное повторение позволяет вам рассмотреть многомерную версию этой задачи, в которой вы должны разорвать все появляющиеся нечетные циклы. Файги, Киндлер и О'Доннелл должны были показать, что по мере того, как количество измерений становится очень большим, вам нужно удалить очень большую часть ребер, чтобы разорвать все нечетные циклы. Если бы это было правдой, это означало бы, что параллельное повторение могло бы эффективно усилить сложность этой глупой проблемы «максимального сокращения».

Именно тогда команда обнаружила любопытное совпадение: существовал геометрический способ интерпретировать, будет ли параллельное повторение работать так, как они надеялись. Секрет заключался в площади поверхности кубической пены.

От лимонов к лимонаду

Их задача, переписанная на языке пен, сводилась к тому, чтобы показать, что сферические кубы не могут существовать — что нельзя разбить многомерное пространство вдоль целочисленной решетки на ячейки с площадью поверхности, много меньшей, чем у куба. (Большая площадь поверхности соответствует необходимости удаления большего количества «плохих» ребер в графе нечетных циклов, как надеялись показать ученые-компьютерщики.)

«Мы подумали: о, какая странная задача по геометрии, но, наверное, это правда, верно?» — сказал О'Доннелл. «Нам действительно нужно было, чтобы это был верный ответ». Но ни он, ни Файги, ни Киндлер не смогли этого доказать. Так, в 2007 г. опубликовал статью с изложением того, как они планировали использовать эту проблему, чтобы помочь атаковать пользовательский контент.

Вскоре их надежды рухнули.

Ран Раз, ученый-теоретик из Принстона, который уже доказал несколько важных результатов о параллельном повторении, был заинтригован их статьей. Он решил проанализировать параллельное повторение для проблемы нечетного цикла, отчасти из-за связи с геометрией, которую обнаружили Файги, Киндлер и О'Доннелл.

Раз начал не с проблемы с пеной, а в лоб атаковал компьютерную версию вопроса. Он показал, что можно удалить гораздо меньше ребер, чтобы разбить все нечетные циклы в графе. Другими словами, параллельное повторение не может в достаточной степени усилить сложность этой проблемы максимального сокращения. «Параметры, которые получаются в результате параллельного повторения, точно не соответствуют этому», — сказал Мошковиц.

«Наш план использовать параллельное повторение, чтобы показать сложность уникальных игр, не сработал даже в самом простом случае», — сказал О'Доннелл. «Это нарушило весь план».

Хотя результат Раза и разочаровал, он также намекнул на существование сферических кубов: формы, которые можно замостить. n-мерное пространство с площадью поверхности, которая пропорциональна квадратному корню из n. «Мы подумали: давайте сделаем лимонад из лимонов и возьмем этот разочаровывающий технический результат о параллельном повторении и дискретных графах и превратим его в изящный интересный результат в геометрии», — сказал О'Доннелл.

Он и Киндлер в сотрудничестве с учеными-компьютерщиками Ануп Рао и Ави Вигдерсон, корпели над доказательством Раза, пока не изучили его методы достаточно хорошо, чтобы применить их к задаче о пене. В 2008 году они показали, что сферические кубы действительно возможны.

«Это хороший способ рассуждать о проблеме», — сказал Марк Браверман Принстона. "Это красиво."

И это подняло вопросы о геометрической стороне истории. Поскольку они использовали работу Раза о параллельном повторении для построения своей мозаичной формы, Киндлер, О'Доннелл, Рао и Вигдерсон в итоге получили что-то уродливое и похожее на Франкенштейна. Плитка была грязной и полной углублений. С математической точки зрения она не была выпуклой. Хотя это работало для их целей, у сферического куба не было свойств, которые предпочитают математики — свойств, которые делают форму более конкретной, легкой для определения и изучения и более подходящей для потенциальных приложений.

«Есть что-то очень неудовлетворительное в их конструкции, — сказал Регев. «Похоже на амебу. Это не похоже на то, что вы ожидаете, красивое мозаичное тело».

Это то, что он и Наор намеревались найти.

Вырваться из клетки

С самого начала Наор и Регев поняли, что им придется начинать с нуля. «Отчасти из-за того, что выпуклые тела настолько ограничены, ни один из предыдущих методов не имел шансов сработать», — сказал он. Дор Минзерученый-теоретик из Массачусетского технологического института.

На самом деле было вполне правдоподобно, что выпуклость была бы слишком ограничительной — что выпуклого сферического куба просто не существует.

Но в прошлом месяце Наор и Регев доказали, что можно разделить n-мерное пространство в целых координатах с выпуклой формой, площадь поверхности которой довольно близка к площади сферы. И они сделали это совершенно геометрически — вернув проблему к ее математическим корням.

Сначала им нужно было обойти серьезное препятствие. Задача кубической пены требует, чтобы каждая плитка была сосредоточена в целочисленных координатах. Но в целочисленной решетке между некоторыми точками очень короткие расстояния — и эти короткие расстояния вызывают проблемы.

Рассмотрим точку в двумерной сетке. Он расположен на расстоянии 1 единицы от ближайших точек по горизонтали и вертикали. Но в диагональном направлении ближайшая точка находится на расстоянии $latex sqrt{2}$ единиц — это несоответствие становится еще более значительным на больших пространствах. в n-мерная целочисленная решетка, ближайшие точки по-прежнему находятся на расстоянии 1 единицы, но эти «диагональные» точки теперь находятся на расстоянии $latex sqrt{n}$ единиц. Скажем, в 10,000 100 измерений это означает, что ближайший «диагональный» сосед любой точки находится на расстоянии 10,000 единиц, даже если есть 1 XNUMX других точек (по одной в каждом направлении), которые удалены всего на XNUMX единицу.

В других решетках эти два вида расстояний растут пропорционально друг другу. Математики десятилетиями знали, как замостить такие решетки выпуклыми формами минимальной площади поверхности.

Но в целочисленной решетке кратчайшее расстояние всегда будет равно 1. Это мешает построению красивой плитки с оптимальной площадью поверхности. «Они вроде как посадили тебя в эту клетку», — сказал Регев. «Они делают все очень тесным вокруг вас».

Поэтому Наор и Регев вместо этого рассматривали часть полного n-мерное пространство. Они тщательно выбрали это подпространство так, чтобы оно по-прежнему было богато целыми точками, но ни одна из этих точек не располагалась слишком близко друг к другу.

Другими словами, подпространство, которое они получили, было именно тем типом, который математики уже знали, как оптимально замостить.

Но это была только половина дела. Наору и Регеву нужно было разделить все пространство, а не только его часть. Чтобы получить n-мерный сферический куб, они должны были умножить свою эффективную плитку на плитку из оставшегося пространства (подобно тому, как вы можете умножить двумерный квадрат на одномерный отрезок прямой, чтобы получить трехмерный куб). Это поднимет их конструкцию обратно в исходное пространство, но также увеличит ее площадь поверхности.

Пара должна была показать, что плитка из оставшегося пространства, которая была не такой оптимальной, не слишком увеличивала площадь поверхности. Как только они это сделали, их строительство было завершено. (Площадь поверхности их окончательной формы оказалась немного больше, чем у невыпуклого сферического куба, но они считают, что можно найти выпуклую плитку, столь же эффективную, как и ее невыпуклый аналог.)

«Их доказательство полностью отличается» от предыдущей работы о сферических кубах, — сказал математик. Нога Алон. «И, оглядываясь назад, это, может быть, более естественное доказательство. Это то, с чего кто-то, возможно, должен был попытаться начать».

«Когда что-то делается по-другому, — добавил Раз, — иногда обнаруживаются интересные дополнительные последствия».

Возрождение надежды

Пока неясно, какими могут быть эти последствия, хотя работа касается потенциального использования целочисленных решеток в криптографии и других приложениях. Учитывая, насколько эта проблема связана с другими областями, «она может привести к другим вещам», — сказал Алон.

На данный момент компьютерщики не видят способа интерпретировать выпуклый результат на языке параллельного повторения и UGC. Но они не полностью отказались от первоначального плана использовать проблему пены для доказательства гипотезы. «Существуют различные способы, которыми вы можете попытаться разрушить очевидные барьеры, с которыми мы столкнулись», — сказал Киндлер.

Браверман и Минзер попробовали один из таких способов, когда они пересмотрены пены в 2020 г.. Вместо того чтобы требовать, чтобы мозаичная форма была выпуклой, они требовали, чтобы она подчинялась определенной симметрии, чтобы она выглядела одинаково независимо от того, как вы меняете ее координаты. (В 2D квадрат будет работать, а прямоугольник — нет; то же самое можно сказать и о многомерных сферических кубах, описанных до сих пор.) При этом новом ограничении пара смогла показать то, на что Киндлер и другие надеялись 15 лет назад: что вы не можете сделать намного лучше, чем площадь поверхности куба в конце концов.

Это соответствовало другому типу параллельного повторения — такому, которое сделало бы простейший случай максимального сокращения настолько трудным, насколько это необходимо. Хотя результат дает некоторую надежду на это направление исследований, неясно, будет ли эта версия параллельного повторения работать для всех задач максимального сокращения. «Это не значит, что вы закончили, — сказал Брейверман. — Это просто означает, что ты снова в деле.

«В геометрии есть большой потенциал, — сказал Минзер. — Просто мы недостаточно хорошо это понимаем.