Математики виконали квест зі створення «сферичних кубів»

У четвертому столітті грецький математик Папп з Александрії хвалив бджіл за їхнє «геометричне передбачливість». Гексагональна структура їх стільників здавалася оптимальним способом розділити двовимірний простір на комірки однакової площі та мінімального периметра, що дозволило комахам скоротити кількість воску, необхідного для виробництва, і витрачати менше часу та енергії на будівництво своїх сот. вулик.

Принаймні так припускали Паппус та інші. Протягом тисячоліть ніхто не міг довести, що шестикутники є оптимальними — поки нарешті в 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% найкращого рішення, може бути NP-важко досягти 95% найкращого рішення, залишаючи невирішеним питання про те, де саме між 80% і 95% проблема потрапляє на NP-жорстку територію.

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

Але незабаром після того, як UGC було запропоновано в 2002 році, дослідники показали, що якщо гіпотеза вірна, то ви можете легко обчислити поріг жорсткості для будь-якої проблеми задоволення обмежень. (Це тому, що UGC також передбачає, що відомий алгоритм досягає найкращого можливого наближення для всіх цих проблем.) «Це було саме стрижнею для всіх цих проблем оптимізації», — сказав О'Доннелл.

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

Ускладнення складних проблем

У 2005 році О'Доннелл працював у Microsoft Research. Він і двоє колег — Уріель Фейгі, зараз в Інституті науки Вейцмана, і Гай Кіндлер, який зараз працює в Єврейському університеті в Єрусалимі — об’єдналися, щоб боротися з UGC.

Вони мали туманне уявлення про те, як вони хочуть діяти далі. Вони почали б із запитання про графіки, які дуже схожі на UGC. Проблема так званого максимального розрізу («max-cut») запитує, коли задано граф, як розділити його вершини на два набори (або кольори), щоб кількість ребер, що з’єднують ці набори, була якомога більшою. (Ви можете розглядати максимальне скорочення як питання про найкращий спосіб розфарбувати граф двома кольорами, щоб якомога менше ребер з’єднувало вершини одного кольору.)

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

Натомість Файгі, Кіндлер і О’Доннелл хотіли піти в протилежному напрямку: вони сподівалися показати, що максимальне скорочення важко приблизно визначити, а потім використовувати це, щоб довести UGC. Їхній план спирався на силу техніки під назвою паралельне повторення — розумної стратегії, яка ускладнює важкі завдання.

Скажімо, ви знаєте, що NP-важко відрізнити проблему, яку ви можете вирішити, від тієї, яку ви можете вирішити переважно. Паралельне повторення дозволяє вам спиратися на це, щоб продемонструвати набагато сильніший результат твердості: що також NP-важко відрізнити проблему, яку ви можете вирішити, від тієї, яку ви ледве можете вирішити взагалі. «Це неінтуїтивне, глибоке явище… є сьогодні в глибині багатьох інформатичних наук», — сказав Наор.

Але тут є заковика. Паралельне повторення не завжди посилює складність проблеми настільки, наскільки того хочуть інформатики. Зокрема, є аспекти проблеми максимального скорочення, які «створюють великий головний біль для паралельного повторення», сказав Регев.

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

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

Паралельне повторення дозволяє розглянути багатовимірну версію цієї проблеми — таку, в якій вам потрібно розірвати всі дивні цикли, які з’являються. Файгі, Кіндлер і О'Доннел повинні були показати, що коли кількість вимірів стає дуже великою, вам потрібно видалити дуже велику частку ребер, щоб розірвати всі непарні цикли. Якби це було правдою, це означало б, що паралельне повторення могло б ефективно посилити жорсткість цієї проблеми «дурного максимального скорочення».

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

Від лимонів до лимонаду

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

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

Невдовзі їхні надії розвіялися.

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

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

«Наш план використовувати паралельне повторення, щоб показати складність унікальних ігор, не спрацював навіть у найпростішому випадку», — сказав О'Доннелл. «Це зламало весь план».

Незважаючи на розчарування, результат Раза також натякнув на існування сферичних кубів: форм, які можна скласти плиткою. 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 років тому: що ви не можете зробити набагато краще, ніж площа поверхні куба.

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

«У геометрії є великий потенціал», — сказав Мінцер. «Просто ми недостатньо добре це розуміємо».