Matematycy ukończą zadanie, aby zbudować „sferyczne sześciany”

W IV wieku grecki matematyk Pappus z Aleksandrii wychwalał pszczoły za ich „geometryczną przezorność”. Sześciokątna struktura ich plastra miodu wydawała się optymalnym sposobem podziału dwuwymiarowej przestrzeni na komórki o równej powierzchni i minimalnym obwodzie – pozwalając owadom zmniejszyć ilość wosku potrzebną do wyprodukowania oraz poświęcić mniej czasu i energii na budowanie ich ul.

Tak przynajmniej przypuszczali Pappus i inni. Przez tysiąclecia nikt nie mógł udowodnić, że sześciokąty są optymalne — aż w końcu w 1999 roku matematyk Thomas Hales wykazał, że żaden inny kształt nie może być lepszy. Dziś matematycy wciąż nie wiedzą, które kształty mogą układać trzy lub więcej wymiarów z najmniejszą możliwą powierzchnią.

Okazało się, że ten problem „piany” ma szerokie zastosowanie — dla fizyków badających zachowanie baniek mydlanych (lub pianek) i chemików analizujących strukturę kryształów, dla matematyków badających układy upakowania sfer i statystyków opracowujących skuteczne techniki przetwarzania danych .

W połowie 2000 roku szczególne sformułowanie problemu piany przykuło również uwagę informatyków-teoretyków, którzy ku swojemu zaskoczeniu odkryli, że jest on głęboko powiązany z ważnym otwartym problemem w ich dziedzinie. Byli w stanie wykorzystać to połączenie, aby znaleźć nowy, wielowymiarowy kształt o minimalnej powierzchni.

„Uwielbiam to w kółko” — powiedział Asaf Naor z Uniwersytetu Princeton. „Część starej matematyki staje się istotna dla informatyki; informatyka się opłaca i rozwiązuje problem w matematyce. To bardzo miłe, kiedy tak się dzieje”.

Jednak w tym kształcie, choć optymalnym, brakowało czegoś ważnego: geometrycznej podstawy. Ponieważ jego istnienie zostało udowodnione przy użyciu technik informatycznych, trudno było uchwycić jego rzeczywistą geometrię. To właśnie Naor wraz z nim Oded Regev, informatyk z Courant Institute na Uniwersytecie Nowojorskim, postanowił poprawić błędy dowód opublikowany online w zeszłym miesiącu.

„To bardzo miłe zakończenie tej historii” — powiedział Regev.

Pianki sześcienne

Matematycy rozważali inne wersje problemu piany — w tym to, co się stanie, jeśli wolno ci dzielić przestrzeń tylko zgodnie z tak zwaną siatką liczb całkowitych. W tej wersji problemu bierzesz kwadratową tablicę równomiernie rozmieszczonych punktów (każdy od siebie o 1 jednostkę) i czynisz każdy z tych punktów środkiem kształtu. Problem z „sześcienną” pianką polega na pytaniu, jaka będzie minimalna powierzchnia, gdy będziesz musiał wyłożyć kafelki w ten sposób.

Naukowcy byli początkowo zainteresowani nałożeniem tego ograniczenia w celu zrozumienia właściwości przestrzeni topologicznych zwanych rozmaitościami. Ale pytanie zaczęło żyć własnym życiem, stając się istotne w analizie danych i innych zastosowaniach.

Jest to również interesujące z geometrycznego punktu widzenia, ponieważ zmienia to, co może oznaczać „optymalny”. Na przykład w dwóch wymiarach sześciokąty foremne nie mogą już pokrywać płaszczyzny, jeśli można je przesuwać tylko o wartości całkowite w kierunku poziomym i pionowym. (Musisz je przesunąć o nieracjonalne ilości w jednym z dwóch kierunków.)

Kwadraty mogą. Ale czy to najlepsze, co można zrobić? Jako matematyk Jaigyoung Choe odkryta w 1989 roku, odpowiedź brzmi: nie. Optymalny kształt to zamiast tego sześciokąt, który został zgnieciony w jednym kierunku i wydłużony w innym. (Obwód takiego sześciokąta wynosi około 3.86, gdy jego powierzchnia wynosi 1 - pokonując obwód kwadratu równy 4).

Te różnice mogą wydawać się trywialne, ale stają się znacznie większe w wyższych wymiarach.

Spośród wszystkich kształtów o danej objętości, tym, który minimalizuje pole powierzchni, jest kula. Jak n, liczba wymiarów rośnie, pole powierzchni kuli wzrasta proporcjonalnie do pierwiastka kwadratowego z n.

Ale kule nie mogą układać płytek w przestrzeni bez pozostawiania luk. Z drugiej strony an n-wymiarowa kostka o objętości 1 puszki. Haczyk polega na tym, że jego pole powierzchni wynosi 2n, rosnąc wprost proporcjonalnie do swoich wymiarów. 10,000 1-wymiarowy sześcian o objętości 20,000 ma pole powierzchni 400 10,000 — znacznie większe niż XNUMX, przybliżona powierzchnia kuli o XNUMX XNUMX wymiarów.

Dlatego badacze zastanawiali się, czy uda im się znaleźć „sferyczny sześcian” — kształt, który można układać n-wymiarowa przestrzeń, jak sześcian, ale której pole powierzchni rośnie powoli, jak kula.

Wydawało się to mało prawdopodobne. „Jeśli chcesz, aby twoja bańka dokładnie wypełniała przestrzeń i była wyśrodkowana na tej sześciennej siatce, trudno pomyśleć o tym, czego byś użył poza sześcienną bańką” – powiedział Ryan O'Donnell, informatyk teoretyczny na Carnegie Mellon University. „Naprawdę wydaje się, że sześcian powinien być najlepszy”.

Teraz wiemy, że nie.

Twardość trudnych problemów

Przez dziesięciolecia problem piany sześciennej był stosunkowo niezbadany w wyższych wymiarach. Pierwsi badacze, którzy poczynili postępy w tej dziedzinie, nie pochodzili z dziedziny geometrii, ale z informatyki teoretycznej. Natknęli się na to przypadkowo, szukając sposobu na udowodnienie kluczowego stwierdzenia w swojej dziedzinie, znanego jako unikalne gry domysły. „Wyjątkowa hipoteza dotycząca gier” — powiedział Regev — „jest obecnie największym otwartym pytaniem w informatyce teoretycznej”.

Zaproponowany w 2002 r. przez Subhash Khot, wówczas doktorant, hipoteza zakłada, że ​​jeśli konkretnego problemu — takiego, który polega na przypisywaniu kolorów do węzłów sieci — nie można dokładnie rozwiązać, to znalezienie nawet przybliżonego rozwiązania jest bardzo trudne. Jeśli to prawda, przypuszczenie to pozwoliłoby naukowcom zrozumieć złożoność szerokiego asortymentu innych zadań obliczeniowych za jednym zamachem.

Informatycy często klasyfikują zadania na podstawie tego, czy można je rozwiązać za pomocą wydajnego algorytmu, czy raczej są one „NP-trudne” (co oznacza, że ​​nie można ich skutecznie rozwiązać w miarę wzrostu rozmiaru problemu, o ile powszechnie uważa się, że ale nieudowodnione przypuszczenie o złożoności obliczeniowej jest prawdziwe). Na przykład problem komiwojażera, który wymaga najkrótszej drogi potrzebnej do odwiedzenia każdego miasta w sieci tylko raz, jest NP-trudny. Podobnie jest z ustaleniem, czy graf — zbiór wierzchołków połączonych krawędziami — można oznaczyć co najwyżej trzema kolorami, tak aby dowolne dwa połączone wierzchołki miały różne kolory.

Okazuje się, że znalezienie nawet przybliżonego rozwiązania wielu z tych zadań jest NP-trudne. Załóżmy, że chcesz oznaczyć wierzchołki grafu różnymi kolorami w sposób spełniający pewną listę ograniczeń. Jeśli spełnienie wszystkich tych ograniczeń jest NP-trudne, co powiesz na próbę spełnienia tylko 90% z nich, 75% lub 50%? Poniżej pewnego progu możliwe jest opracowanie wydajnego algorytmu, ale powyżej tego progu problem staje się NP-trudny.

Przez dziesięciolecia informatycy pracowali nad określeniem progów dla różnych interesujących ich problemów optymalizacyjnych. Ale niektóre pytania wymykają się tego rodzaju opisowi. Podczas gdy algorytm może gwarantować 80% najlepszego rozwiązania, osiągnięcie 95% najlepszego rozwiązania może być NP-trudne, pozostawiając nierozstrzygniętą kwestię, gdzie dokładnie między 80% a 95% problem przechyla się na terytorium NP-trudne.

Wyjątkowe domysły dotyczące gier, czyli UGC, oferują sposób na natychmiastowe znalezienie odpowiedzi. Zawiera stwierdzenie, które na pierwszy rzut oka wydaje się bardziej ograniczone: że NP-trudno jest stwierdzić różnicę między wykresem, dla którego można spełnić prawie wszystkie określone ograniczenia kolorowania (powiedzmy, ponad 99%), a wykresem dla które możesz zaspokoić prawie żadne (powiedzmy mniej niż 1%).

Ale wkrótce po zaproponowaniu UGC w 2002 r. naukowcy wykazali, że jeśli przypuszczenie jest prawdziwe, to można łatwo obliczyć próg twardości dla dowolnego problemu spełnienia ograniczeń. (Dzieje się tak, ponieważ UGC sugeruje również, że znany algorytm osiąga najlepsze możliwe przybliżenie dla wszystkich tych problemów.) „To był właśnie filar wszystkich tych problemów optymalizacyjnych” — powiedział O'Donnell.

I tak informatycy teoretyczni postanowili udowodnić UGC — zadanie, które ostatecznie doprowadziło niektórych z nich do odkrycia kulistych sześcianów.

Trudne problemy stają się trudniejsze

W 2005 roku O'Donnell pracował w Microsoft Research. On i dwóch kolegów — Uriela Feige'a, obecnie w Instytucie Nauki Weizmanna i Guya Kindlera, obecnie na Uniwersytecie Hebrajskim w Jerozolimie — połączyli siły, by zająć się UGC.

Mieli mgliste pojęcie o tym, jak chcą postąpić. Zaczęliby od pytania o wykresy — bardzo podobnego do UGC. Tak zwany problem maksymalnego cięcia ("max-cut") polega na pytaniu, kiedy mamy dany graf, jak podzielić jego wierzchołki na dwa zbiory (lub kolory), aby liczba krawędzi łączących te zbiory była jak największa. (Możesz myśleć o maksymalnym cięciu jako o pytaniu o najlepszy sposób pokolorowania wykresu dwoma kolorami, tak aby jak najmniej krawędzi łączyło wierzchołki tego samego koloru.)

Jeśli UGC jest prawdziwe, oznaczałoby to, że przy pewnym losowym wykresie wydajny algorytm aproksymacji może uzyskać tylko około 87% prawdziwego maksymalnego cięcia tego wykresu. Zrobienie czegoś lepszego byłoby NP-trudne.

Feige, Kindler i O'Donnell zamiast tego chcieli pójść w przeciwnym kierunku: mieli nadzieję pokazać, że maksymalne cięcie jest trudne do przybliżenia, a następnie wykorzystać to do udowodnienia UGC. Ich plan opierał się na sile techniki zwanej równoległym powtarzaniem — sprytnej strategii, która sprawia, że ​​trudne problemy stają się trudniejsze.

Załóżmy, że wiesz, że rozróżnienie problemu, który możesz rozwiązać, od problemu, który możesz rozwiązać w większości, jest NP-trudne. Równoległe powtarzanie pozwala na oparcie się na tym, aby pokazać znacznie lepszy wynik twardości: że jest również NP-trudne rozróżnienie między problemem, który można rozwiązać, a takim, którego prawie w ogóle nie można rozwiązać. „To nieintuicyjne, głębokie zjawisko… tkwi we wnętrznościach wielu dzisiejszych informatyków” — powiedział Naor.

Ale jest pewien haczyk. Równoległe powtarzanie nie zawsze zwiększa twardość problemu tak bardzo, jak chcą tego informatycy. W szczególności istnieją aspekty problemu maksymalnego cięcia, które „powodują duży ból głowy przy powtarzaniu równoległym” – powiedział Regev.

Feige, Kindler i O'Donnell skupili się na pokazaniu, że równoległe powtarzanie może działać pomimo bólu głowy. „To naprawdę skomplikowana sprawa do analizy” – powiedział Dana Moskowicz, informatyk teoretyczny na University of Texas w Austin. „Ale wydawało się to kusząco bliskie. Wydawało się, że równoległe powtarzanie [pomoże] w stworzeniu połączenia między maksymalnym cięciem a wyjątkowymi grami”.

Na rozgrzewkę naukowcy próbowali zrozumieć równoległe powtórzenia dla prostego przypadku maksymalnego cięcia, które Moshkovitz nazwał „najgłupszym maksymalnym cięciem”. Rozważ nieparzystą liczbę wierzchołków połączonych krawędziami, aby utworzyć okrąg lub „cykl nieparzysty”. Chcesz oznaczyć każdy wierzchołek jednym z dwóch kolorów, tak aby żadna para sąsiednich wierzchołków nie miała tego samego koloru. W tym przypadku jest to niemożliwe: jedna krawędź zawsze łączy wierzchołki tego samego koloru. Musisz usunąć tę krawędź, „przerywając” nieparzysty cykl, aby twój wykres spełniał ograniczenie problemu. Ostatecznie chcesz zminimalizować całkowitą część krawędzi, które musisz usunąć, aby poprawnie pokolorować wykres.

Równoległe powtarzanie pozwala rozważyć wielowymiarową wersję tego problemu — taką, w której musisz przerwać wszystkie pojawiające się nieparzyste cykle. Feige, Kindler i O'Donnell musieli wykazać, że gdy liczba wymiarów staje się bardzo duża, trzeba usunąć bardzo dużą część krawędzi, aby przerwać wszystkie nieparzyste cykle. Gdyby to była prawda, oznaczałoby to, że równoległe powtarzanie mogłoby skutecznie wzmocnić twardość tego „głupiego maksymalnego cięcia”.

Wtedy zespół odkrył ciekawy zbieg okoliczności: istniał geometryczny sposób interpretacji, czy równoległe powtarzanie zadziała tak, jak tego oczekiwali. Sekret tkwił w powierzchni pianek sześciennych.

Od cytryn do lemoniady

Ich problem, przepisany na język pianek, sprowadzał się do wykazania, że ​​kuliste sześciany nie mogą istnieć — że nie można podzielić wielowymiarowej przestrzeni wzdłuż sieci liczb całkowitych na komórki o polu powierzchni znacznie mniejszym niż sześcian. (Większa powierzchnia odpowiada potrzebie usunięcia większej liczby „złych” krawędzi na wykresie nieparzystych cykli, co informatycy mieli nadzieję pokazać).

„Pomyśleliśmy sobie, och, co za dziwny problem z geometrią, ale to chyba prawda, prawda?” - powiedział O'Donnell. „Naprawdę potrzebowaliśmy, aby to była prawdziwa odpowiedź”. Ale on, Feige i Kindler nie mogli tego udowodnić. Tak więc w 2007 r opublikował artykuł przedstawiając, w jaki sposób planowali wykorzystać ten problem, aby pomóc w ataku na UGC.

Wkrótce ich nadzieje zostały rozwiane.

Ran Raz, informatyk-teoretyk z Princeton, który udowodnił już kilka ważnych wyników dotyczących powtórzeń równoległych, był zaintrygowany ich artykułem. Zdecydował się przeanalizować powtórzenia równoległe dla problemu cykli nieparzystych, częściowo ze względu na związek z geometrią, który odkryli Feige, Kindler i O'Donnell.

Raz nie zaczął od problemu z pianką, ale od razu zaatakował informatyczną wersję pytania. Pokazał, że można uniknąć usunięcia znacznie mniejszej liczby krawędzi, aby przerwać wszystkie nieparzyste cykle na wykresie. Innymi słowy, równoległe powtarzanie nie może wystarczająco wzmocnić twardości tego problemu z maksymalnym cięciem. „Parametry, które uzyskuje się dokładnie z powtórzeń równoległych, dokładnie nie dają tego” – powiedział Moshkovitz.

„Nasz plan użycia równoległych powtórzeń w celu pokazania trudności unikalnych gier nie zadziałał nawet w najprostszym przypadku” — powiedział O'Donnell. „To zrujnowało cały plan”.

Chociaż rozczarowujący, wynik Raza wskazywał również na istnienie kulistych kostek: kształtów zdolnych do układania płytek n-wymiarowa przestrzeń z polem powierzchni skalowanym proporcjonalnie do pierwiastka kwadratowego n. „Pomyśleliśmy sobie, cóż, zróbmy lemoniadę z cytryn i weźmy ten rozczarowujący wynik techniczny dotyczący równoległych powtórzeń i dyskretnych wykresów, i zamieńmy go w zgrabny, interesujący wynik w geometrii”, powiedział O'Donnell.

On i Kindler we współpracy z informatykami Anup Rao i Aviego Wigdersona, ślęczeli nad dowodem Raza, dopóki nie poznali jego technik na tyle dobrze, by przełożyć je na problem z pianą. Pokazali to w 2008 roku kuliste sześciany są rzeczywiście możliwe.

„To dobry sposób na wyjaśnienie problemu” — powiedział Marka Bravermana z Princeton. "To jest piękne."

I wzbudziło to pytania dotyczące geometrii tej historii. Ponieważ wykorzystali pracę Raza nad równoległymi powtórzeniami, aby skonstruować swój kafelkowy kształt, Kindler, O'Donnell, Rao i Wigderson skończyli z czymś brzydkim i podobnym do Frankensteina. Płytka była brudna i pełna wgłębień. Z matematycznego punktu widzenia nie był wypukły. Chociaż działało to dla ich celów, sferyczny sześcian nie miał właściwości preferowanych przez matematyków – właściwości, które sprawiają, że kształt jest bardziej konkretny, łatwiejszy do zdefiniowania i zbadania oraz bardziej odpowiedni do potencjalnych zastosowań.

„W ich konstrukcji jest coś bardzo niezadowalającego” — powiedział Regev. „Wygląda jak ameba. To nie wygląda tak, jak można by się spodziewać, ładne, układające się ciało.

To właśnie on i Naor postanowili znaleźć.

Uwolnienie się z klatki

Od samego początku Naor i Regev zdawali sobie sprawę, że będą musieli zacząć od zera. „Częściowo dlatego, że ciała wypukłe są tak restrykcyjne, żadna z poprzednich technik nie miała szans zadziałać” – powiedział Dor Minzer, informatyk teoretyczny w Massachusetts Institute of Technology.

W rzeczywistości było całkowicie prawdopodobne, że wypukłość byłaby zbyt restrykcyjna — wypukły sferyczny sześcian po prostu nie istnieje.

Ale w zeszłym miesiącu Naor i Regev udowodnili, że można podzielić n-wymiarowa przestrzeń wzdłuż współrzędnych całkowitych o wypukłym kształcie, którego pole powierzchni jest dość zbliżone do pola powierzchni kuli. I zrobili to całkowicie geometrycznie – przywracając problem do jego matematycznych korzeni.

Najpierw musieli ominąć poważną przeszkodę. Problem z pianą sześcienną wymaga, aby każda płytka była wyśrodkowana na współrzędnych całkowitych. Ale w siatce liczb całkowitych odległości między niektórymi punktami są bardzo krótkie — i te krótkie odległości powodują problemy.

Rozważmy punkt w dwuwymiarowej siatce. Znajduje się w odległości 1 jednostki od najbliższych punktów w kierunku poziomym i pionowym. Jednak w kierunku ukośnym najbliższy punkt znajduje się w odległości jednostek $latex sqrt{2}$ — rozbieżność ta pogłębia się na większych przestrzeniach. w ndwuwymiarowej sieci całkowitej, najbliższe punkty nadal są oddalone o 1 jednostkę, ale te punkty „przekątne” są teraz oddalone o jednostki $latex sqrt{n}$. W, powiedzmy, 10,000 100 wymiarach oznacza to, że najbliższy „przekątny” sąsiad dowolnego punktu znajduje się w odległości 10,000 jednostek, mimo że istnieje 1 XNUMX innych punktów (po jednym w każdym kierunku), które są oddalone tylko o XNUMX jednostkę.

W innych sieciach te dwa rodzaje odległości rosną proporcjonalnie do siebie. Matematycy od dziesięcioleci wiedzą, jak układać takie kraty wypukłymi kształtami o minimalnej powierzchni.

Ale w siatce liczb całkowitych najkrótsze odległości zawsze będą utknęły na poziomie 1. Utrudnia to skonstruowanie ładnie wyglądającej płytki o optymalnej powierzchni. „W pewnym sensie umieścili cię w tej klatce” – powiedział Regev. „Sprawiają, że wszystko wokół ciebie jest bardzo ciasne”.

Więc zamiast tego Naor i Regev rozważali kawałek całości n-wymiarowa przestrzeń. Starannie wybrali tę podprzestrzeń, aby nadal była bogata w punkty całkowite, ale żaden z tych punktów nie znajdował się zbyt blisko siebie.

Innymi słowy, podprzestrzeń, którą uzyskali, była dokładnie tym typem, który matematycy już wiedzieli, jak optymalnie układać.

Ale to była dopiero połowa pracy. Naor i Regev musieli podzielić całą przestrzeń, a nie tylko jej wycinek. Aby uzyskać ndwuwymiarowy sferyczny sześcian, musieli pomnożyć swoją efektywną płytkę przez płytkę z pozostałej przestrzeni (podobnie jak można pomnożyć dwuwymiarowy kwadrat przez jednowymiarowy odcinek linii, aby uzyskać trójwymiarowy sześcian). Takie postępowanie podniosłoby ich konstrukcję z powrotem do pierwotnej przestrzeni, ale zwiększyłoby również jej powierzchnię.

Para musiała pokazać, że płytka z pozostałej przestrzeni, która nie była tak optymalna, nie dodała zbyt wiele do powierzchni. Kiedy to zrobili, ich budowa była zakończona. (Powierzchnia ich ostatecznego kształtu okazała się nieco większa niż powierzchnia niewypukłego sferycznego sześcianu, ale wierzą, że możliwe jest znalezienie wypukłej płytki, która byłaby równie wydajna, jak jej niewypukły odpowiednik).

„Ich dowód jest zupełnie inny” niż poprzednie prace nad sferycznymi sześcianami, powiedział matematyk Noga Alon. „Z perspektywy czasu jest to może bardziej naturalny dowód. Być może ktoś powinien spróbować zacząć od tego.

„Kiedy coś robi się inaczej” — dodał Raz — „czasami można znaleźć interesujące dodatkowe implikacje”.

Odnowiona nadzieja

Nie jest jeszcze jasne, jakie mogą być te implikacje — chociaż praca wykorzystuje potencjalne wykorzystanie sieci całkowitych w kryptografii i innych zastosowaniach. Biorąc pod uwagę, jak ten problem jest powiązany z innymi dziedzinami, „prawdopodobnie doprowadzi do innych rzeczy” – powiedział Alon.

W tej chwili informatycy nie widzą możliwości interpretacji wyniku wypukłego w języku równoległych powtórzeń i UGC. Ale nie zrezygnowali całkowicie z pierwotnego planu wykorzystania problemu piany do udowodnienia przypuszczenia. „Istnieje wiele sposobów na obalenie oczywistych barier, które napotkaliśmy” – powiedział Kindler.

Braverman i Minzer próbowali jednego z takich sposobów ponownie odwiedzane pianki w 2020 roku. Zamiast wymagać, aby kształt płytek był wypukły, poprosili, aby przestrzegał pewnych symetrii, tak aby wyglądał tak samo bez względu na to, jak odwrócisz jego współrzędne. (W 2D kwadrat zadziałałby, ale prostokąt nie; podobnie jak opisane do tej pory wielowymiarowe sferyczne kostki). W ramach tego nowego ograniczenia para była w stanie pokazać, na co Kindler i inni mieli nadzieję 15 lat wcześniej: że w końcu nie można zrobić nic lepszego niż pole powierzchni sześcianu.

Odpowiadało to innemu rodzajowi równoległych powtórzeń — takiemu, który sprawi, że najprostszy przypadek maksymalnego cięcia będzie tak trudny, jak powinien. Chociaż wynik daje nadzieję na tę linię badań, nie jest jasne, czy ta wersja równoległych powtórzeń będzie działać dla wszystkich problemów z maksymalnym cięciem. „To nie znaczy, że skończyłeś” — powiedział Braverman. – To po prostu oznacza, że ​​wróciłeś do biznesu.

„W geometrii drzemie duży potencjał” — powiedział Minzer. „Po prostu nie rozumiemy tego wystarczająco dobrze”.