Matematicienii finalizează căutarea pentru a construi „cuburi sferice”

În secolul al patrulea, matematicianul grec Pappus din Alexandria a lăudat albinele pentru „premeditarea lor geometrică”. Structura hexagonală a fagurelor lor părea a fi modalitatea optimă de a împărți spațiul bidimensional în celule de suprafață egală și perimetru minim - permițând insectelor să reducă cantitatea de ceară de care aveau nevoie să producă și să petreacă mai puțin timp și energie construindu-le. stup.

Sau așa au emis ipoteza Pappus și alții. Timp de milenii, nimeni nu a putut dovedi că hexagoanele sunt optime – până când în cele din urmă, în 1999, matematicianul Thomas Hales a arătat că nicio altă formă nu ar putea face mai bine. Astăzi, matematicienii încă nu știu ce forme pot placa trei sau mai multe dimensiuni cu cea mai mică suprafață posibilă.

Această problemă de „spumă” s-a dovedit a avea aplicații ample – pentru fizicienii care studiază comportamentul bulelor de săpun (sau spume) și chimiștii care analizează structura cristalelor, pentru matematicienii care explorează aranjamentele de împachetare a sferei și pentru statisticienii care dezvoltă tehnici eficiente de procesare a datelor .

La mijlocul anilor 2000, o formulare specială a problemei spumei a atras atenția informaticienilor teoreticieni, care au descoperit, spre surprinderea lor, că aceasta era profund conectată la o problemă deschisă importantă în domeniul lor. Ei au putut folosi acea conexiune pentru a găsi o nouă formă de înaltă dimensiune cu o suprafață minimă.

„Îmi place acest dus-întors”, a spus Assaf Naor de la Universitatea Princeton. „Unele matematici vechi devin relevante pentru informatică; informatica plătește înapoi și rezolvă întrebarea la matematică. Este foarte frumos când se întâmplă asta.”

Dar acelei forme, deși optime, îi lipsea ceva important: o fundație geometrică. Deoarece existența sa a fost dovedită folosind tehnici din informatică, geometria sa reală a fost greu de înțeles. Asta e ceea ce Naor, împreună cu Oded Regev, un informatician la Institutul Courant de la Universitatea din New York, și-a propus să corecteze în o dovadă postată online luna trecută.

„Este un final foarte frumos al poveștii”, a spus Regev.

Spume cubice

Matematicienii au luat în considerare și alte versiuni ale problemei spumei - inclusiv ce se întâmplă dacă ți se permite să împărțiți spațiul numai în funcție de ceea ce se numește rețea cu numere întregi. În acea versiune a problemei, luați o matrice pătrată de puncte uniform distanțate (fiecare la 1 unitate una de alta) și faceți din fiecare dintre acele puncte centrul unei forme. Problema spumei „cubice” întreabă care va fi suprafața minimă atunci când vi se cere să plătiți spațiu în acest fel.

Cercetătorii au fost inițial interesați să impună această restricție pentru a înțelege proprietățile spațiilor topologice numite varietăți. Dar întrebarea a căpătat o viață proprie, devenind relevantă în analiza datelor și în alte aplicații.

Este, de asemenea, interesant din punct de vedere geometric, deoarece schimbă ceea ce ar putea însemna „optim”. În două dimensiuni, de exemplu, hexagoanele obișnuite nu mai pot placa planul dacă pot fi deplasate doar cu cantități întregi în direcțiile orizontale și verticale. (Trebuie să le mutați în cantități iraționale în una dintre cele două direcții.)

Pătratele pot. Dar este cel mai bun lucru care se poate face? Ca matematician Jagyoung Choe descoperit în 1989, răspunsul este nu. Forma optimă este în schimb un hexagon care a fost strivit într-o direcție și alungit în alta. (Perimetrul unui astfel de hexagon este de aproximativ 3.86 când aria lui este 1 - învingând perimetrul pătratului de 4.)

Aceste diferențe ar putea părea banale, dar devin mult mai mari în dimensiuni mai mari.

Dintre toate formele unui volum dat, cea care minimizează suprafața este sfera. La fel de n, numărul de dimensiuni, crește, aria suprafeței sferei crește proporțional cu rădăcina pătrată a n.

Dar sferele nu pot placa un spațiu fără a lăsa goluri. Pe de altă parte, an n-cubul dimensional al volumului 1 can. Problema este că suprafața sa este de 2n, crescând direct proporţional cu dimensiunea sa. Un cub de 10,000 de dimensiuni din volumul 1 are o suprafață de 20,000 - mult mai mare decât 400, suprafața aproximativă a unei sfere de 10,000 de dimensiuni.

Așa că cercetătorii s-au întrebat dacă ar putea găsi un „cub sferic” – o formă pe care o placă n-spațiu dimensional, ca un cub, dar a cărui suprafață crește lent, ca a unei sfere.

Părea puțin probabil. „Dacă vrei ca bula ta să umple exact spațiul și să fie centrată pe această grilă cubică, este greu să te gândești la ce ai folosi, cu excepția unei bule cubice”, a spus Ryan O'Donnell, un informatician teoretic la Universitatea Carnegie Mellon. „Se pare într-adevăr că cubul ar trebui să fie cel mai bun.”

Acum știm că nu este.

Duritatea problemelor grele

Timp de zeci de ani, problema spumei cubice a rămas relativ neexplorată în dimensiuni mai mari. Primii cercetători care au făcut progrese în acest domeniu nu au venit din domeniul geometriei, ci din domeniul informaticii teoretice. Au dat peste ea întâmplător, în timp ce căutau o modalitate de a dovedi o afirmație centrală în domeniul lor, cunoscută sub numele de presupunerea jocurilor unice. „Conjectura unică a jocurilor”, a spus Regev, „este ceea ce consider în prezent cea mai mare întrebare deschisă din informatica teoretică”.

Propus în 2002 de Subhash Khot, student absolvent la acea vreme, conjectura presupune că, dacă o anumită problemă – una care implică alocarea de culori nodurilor unei rețele – nu poate fi rezolvată exact, atunci găsirea chiar și a unei soluții aproximative este foarte dificilă. Dacă este adevărată, conjectura le-ar permite cercetătorilor să înțeleagă complexitatea unui sortiment vast de alte sarcini de calcul dintr-o singură lovitură.

Informaticienii clasifică adesea sarcinile în funcție de faptul dacă pot fi rezolvate cu un algoritm eficient sau dacă sunt în schimb „NP-hard” (înseamnă că nu pot fi rezolvate eficient pe măsură ce dimensiunea problemei crește, atâta timp cât un larg crezut). dar conjectura nedovedită despre complexitatea computațională este adevărată). De exemplu, problema agentului de vânzări ambulant, care cere cea mai scurtă cale necesară pentru a vizita fiecare oraș dintr-o rețea o singură dată, este dificilă. La fel este și determinarea dacă un grafic - o colecție de vârfuri conectate prin muchii - poate fi etichetat cu cel mult trei culori, astfel încât oricare două vârfuri conectate să aibă culori diferite.

Se pare că este greu de găsit chiar și o soluție aproximativă pentru multe dintre aceste sarcini. Să presupunem că doriți să etichetați vârfurile unui grafic cu culori diferite într-un mod care să satisfacă o listă de constrângeri. Dacă este NP-greu să satisfaci toate aceste constrângeri, ce zici de a încerca să le îndeplinești doar 90%, sau 75%, sau 50%? Sub un anumit prag, ar putea fi posibil să se vină cu un algoritm eficient, dar peste acest prag, problema devine NP-grea.

Timp de zeci de ani, informaticienii au lucrat pentru a stabili praguri pentru diferite probleme de optimizare de interes. Dar unele întrebări eludează acest tip de descriere. În timp ce un algoritm ar putea garanta 80% din cea mai bună soluție, ar putea fi NP-greu să se obțină 95% din cea mai bună soluție, lăsând nesoluționată întrebarea unde exact între 80% și 95% problema se îndreaptă către un teritoriu NP-hard.

Conjectura unică a jocurilor, sau UGC, oferă o modalitate de a identifica imediat răspunsul. Face o afirmație care la început pare mai limitată: că este NP-greu să faci diferența dintre un grafic pentru care poți satisface aproape toate un anumit set de constrângeri de colorare (să zicem, mai mult de 99%) și un grafic pentru pe care abia le poți satisface (să zicem, mai puțin de 1%).

Dar la scurt timp după ce UGC a fost propus în 2002, cercetătorii au arătat că, dacă presupunerea este adevărată, atunci puteți calcula cu ușurință pragul de duritate pentru orice problemă de satisfacție a constrângerii. (Acest lucru se datorează faptului că UGC implică, de asemenea, că un algoritm cunoscut realizează cea mai bună aproximare posibilă pentru toate aceste probleme.) „A fost exact cheia pentru toate aceste probleme de optimizare”, a spus O'Donnell.

Așa că oamenii de știință teoreticieni și-au propus să demonstreze UGC - o sarcină care i-a determinat în cele din urmă pe unii dintre ei să descopere cuburi sferice.

Îngreunarea problemelor grele

În 2005, O'Donnell lucra la Microsoft Research. El și doi colegi - Uriel Feige, acum la Institutul de Știință Weizmann și Guy Kindler, acum la Universitatea Ebraică din Ierusalim — au făcut echipă pentru a aborda UGC.

Aveau o idee vagă despre cum voiau să procedeze. Ei ar începe cu o întrebare despre grafice - una care este foarte asemănătoare cu UGC. Așa-numita problemă de tăiere maximă („max-cut”) întreabă, atunci când i se oferă un grafic, cum să-și împărțiți vârfurile în două seturi (sau culori), astfel încât numărul de muchii care leagă acele seturi să fie cât mai mare posibil. (Puteți să vă gândiți la tăierea maximă ca la o întrebare despre cel mai bun mod de a colora un grafic cu două culori, astfel încât cât mai puține muchii posibil să conecteze vârfuri de aceeași culoare.)

Dacă UGC este adevărat, ar implica că, având în vedere un grafic aleatoriu, un algoritm eficient de aproximare poate ajunge doar în aproximativ 87% din tăietura maximă adevărată a acelui grafic. A face ceva mai bine ar fi NP-greu.

Feige, Kindler și O'Donnell au vrut în schimb să meargă în direcția opusă: au sperat să arate că tăierea maximă este greu de aproximat și apoi să o folosească pentru a demonstra UGC. Planul lor s-a bazat pe puterea unei tehnici numită repetiție paralelă - o strategie inteligentă care îngreunează problemele grele.

Să spunem că știi că este NP-greu să faci distincția între o problemă pe care o poți rezolva și una pe care o poți rezolva în mare parte. Repetarea paralelă vă permite să construiți pe asta pentru a arăta un rezultat de duritate mult mai puternic: că este, de asemenea, greu de făcut distincția între o problemă pe care o puteți rezolva și una pe care abia o puteți rezolva deloc. „Acest fenomen neintuitiv și profund... este în curajul multor științe informatice de astăzi”, a spus Naor.

Dar există o captură. Repetarea paralelă nu amplifică întotdeauna duritatea unei probleme atât de mult pe cât își doresc oamenii de știință. În special, există aspecte ale problemei de tăiere maximă care „creează o mare durere de cap pentru repetarea paralelă”, a spus Regev.

Feige, Kindler și O'Donnell s-au concentrat să arate că repetiția paralelă ar putea funcționa în ciuda durerilor de cap. „Acesta este un lucru foarte complicat de analizat”, a spus Dana Moshkovitz, un informatician teoretic la Universitatea din Texas, Austin. „Dar asta părea îngrozitor de aproape. Repetarea paralelă părea că ar [ajuta] la realizarea acestei conexiuni de la tăierea maximă la jocuri unice.”

Ca o încălzire, cercetătorii au încercat să înțeleagă repetiția paralelă pentru un caz simplu de tăiere maximă, ceea ce Moshkovitz a numit „cea mai stupidă tăiere maximă”. Luați în considerare un număr impar de vârfuri conectate prin muchii pentru a forma un cerc sau „ciclu impar”. Doriți să etichetați fiecare vârf cu una dintre cele două culori, astfel încât nicio pereche de vârfuri adiacente să nu aibă aceeași culoare. În acest caz, este imposibil: o muchie va conecta întotdeauna vârfuri de aceeași culoare. Trebuie să ștergeți acea margine, „rupând” ciclul impar, pentru ca graficul dvs. să satisfacă constrângerea problemei. În cele din urmă, doriți să minimizați fracția totală de muchii pe care trebuie să o ștergeți pentru a vă colora corect graficul.

Repetarea paralelă vă permite să luați în considerare o versiune înaltă a acestei probleme - una în care trebuie să întrerupeți toate ciclurile ciudate care apar. Feige, Kindler și O'Donnell trebuiau să arate că, pe măsură ce numărul de dimensiuni devine foarte mare, trebuie să ștergeți o fracțiune foarte mare de margini pentru a întrerupe toate ciclurile impare. Dacă acest lucru ar fi adevărat, ar însemna că repetiția paralelă ar putea amplifica în mod eficient duritatea acestei probleme de „taiere maximă stupidă”.

Atunci echipa a descoperit o coincidență curioasă: a existat o modalitate geometrică de a interpreta dacă repetiția paralelă va funcționa așa cum sperau ei. Secretul stă în suprafața spumei cubice.

De la lămâi la limonadă

Problema lor, rescrisă în limbajul spumelor, s-a rezumat la a arăta că cuburile sferice nu pot exista - că este imposibil să împărțiți spațiul de dimensiuni mari de-a lungul rețelei întregi în celule cu suprafață mult mai mică decât cea a cubului. (O suprafață mai mare corespunde nevoii de a șterge mai multe margini „rele” în graficul cu cicluri impare, așa cum sperau să arate informaticienii.)

„Am fost ca, oh, ce problemă ciudată de geometrie, dar probabil că este adevărat, nu?” spuse O'Donnell. „Avem nevoie cu adevărat de acesta să fie răspunsul adevărat.” Dar el, Feige și Kindler nu au putut dovedi. Deci, în 2007, ei a publicat o lucrare subliniind modul în care au plănuit să folosească această problemă pentru a ajuta la atacarea UGC.

Destul de curând, speranțele lor s-au năruit.

Ran Raz, un informatician teoretic de la Princeton care a demonstrat deja câteva rezultate majore despre repetiția paralelă, a fost intrigat de lucrarea lor. El a decis să analizeze repetiția paralelă pentru problema ciclului impar, în parte din cauza conexiunii cu geometria pe care Feige, Kindler și O'Donnell au descoperit-o.

Raz nu a început cu problema spumei, ci a atacat direct versiunea informatică a întrebării. El a arătat că puteți scăpa cu ștergerea mult mai puține margini pentru a întrerupe toate ciclurile impare dintr-un grafic. Cu alte cuvinte, repetarea paralelă nu poate amplifica suficient duritatea acestei probleme de tăiere maximă. „Parametrii pe care îi obținem din repetarea paralelă, exact, nu pot oferi acest lucru”, a spus Moshkovitz.

„Planul nostru de a folosi repetiția paralelă pentru a arăta duritatea jocurilor unice nici măcar nu a funcționat în cel mai simplu caz”, a spus O'Donnell. „Asta a rupt întregul plan.”

Deși dezamăgitor, rezultatul lui Raz a sugerat și existența cuburilor sferice: forme capabile să placă. n-spațiu dimensional cu o suprafață care a scalat proporțional cu rădăcina pătrată a n. „Am fost ca, ei bine, să facem limonadă din lămâi și să luăm acest rezultat tehnic dezamăgitor despre repetarea paralelă și grafice discrete și să-l transformăm într-un rezultat frumos, interesant în geometrie”, a spus O'Donnell.

El și Kindler, în colaborare cu informaticienii Anup Rao și Avi Wigderson, a studiat cu atenție dovezile lui Raz până când i-au învățat tehnicile suficient de bine pentru a le traduce în problema spumei. În 2008, au arătat asta cuburile sferice sunt într-adevăr posibile.

„Este un mod frumos de a raționa problema”, a spus Mark Braverman din Princeton. "E frumos."

Și a ridicat întrebări în ceea ce privește geometria poveștii. Deoarece au folosit lucrarea lui Raz la repetarea paralelă pentru a-și construi forma de plăci, Kindler, O'Donnell, Rao și Wigderson au ajuns să aibă ceva urât și asemănător lui Frankenstein. Tigla era dezordonată și plină de adâncituri. În termeni matematici, nu a fost convex. În timp ce acest lucru a funcționat pentru scopurile lor, cubul sferic nu avea proprietăți pe care matematicienii le preferă - proprietăți care fac o formă mai concretă, mai ușor de definit și studiat și mai potrivită pentru potențiale aplicații.

„Este ceva foarte nesatisfăcător în construcția lor”, a spus Regev. „Arată ca o amibă. Nu arată ca ceea ce te-ai aștepta, un corp frumos de faianță.”

Asta și-au propus el și Naor să găsească.

Eliberarea din cușcă

De la început, Naor și Regev și-au dat seama că va trebui să înceapă de la zero. „Parțial pentru că corpurile convexe sunt atât de restrictive, niciuna dintre tehnicile anterioare nu a avut nicio șansă de a funcționa”, a spus Dor Minzer, un informatician teoretic la Institutul de Tehnologie din Massachusetts.

De fapt, era cu totul plauzibil ca convexitatea să fie prea restrictivă - că un cub sferic convex pur și simplu nu există.

Dar luna trecută, Naor și Regev au demonstrat că poți să faci partiții n-spațiul dimensional de-a lungul coordonatelor întregi cu o formă convexă a cărei suprafață este destul de apropiată de cea a sferei. Și au făcut-o în întregime geometric - readucerea problemei la rădăcinile ei matematice.

Mai întâi au trebuit să ocolească un obstacol major. Problema spumei cubice necesită ca fiecare țiglă să fie centrată la coordonate întregi. Dar în rețeaua întregă, există distanțe foarte scurte între unele puncte - și acele distanțe scurte provoacă probleme.

Luați în considerare un punct din grila bidimensională. Este situat la 1 unitate de punctele sale cele mai apropiate în direcțiile orizontale și verticale. Dar în direcția diagonală, cel mai apropiat punct este $latex sqrt{2}$ unități distanță - o discrepanță care se înrăutățește în spații mai mari. În nzăbrele întregi dimensionale, cele mai apropiate puncte sunt încă la 1 unitate distanță, dar acele puncte „diagonale” sunt acum $latex sqrt{n}$ unități distanță. În, să zicem, 10,000 de dimensiuni, aceasta înseamnă că cel mai apropiat vecin „diagonal” de orice punct este la 100 de unități distanță, chiar dacă există alte 10,000 de puncte (câte unul în fiecare direcție) care sunt la doar 1 unitate distanță.

În alte zăbrele, aceste două tipuri de distanțe cresc proporțional unul cu celălalt. Matematicienii știu de zeci de ani cum să placa astfel de rețele cu forme convexe cu o suprafață minimă.

Dar în rețeaua întregă, cele mai scurte distanțe vor fi întotdeauna blocate la 1. Acest lucru împiedică construirea unei plăci frumos cu o suprafață optimă. „Te-au cam băgat în această cușcă”, a spus Regev. „Ei fac totul foarte strâns în jurul tău.”

Așa că Naor și Regev au considerat în schimb o felie din plin n-spațiul dimensional. Ei au ales cu grijă acest subspațiu astfel încât să fie încă bogat în puncte întregi, dar niciunul dintre aceste puncte nu ar fi prea apropiat unul de celălalt.

Cu alte cuvinte, subspațiul cu care au ajuns a fost tocmai tipul pe care matematicienii știau deja să-l placa în mod optim.

Dar aceasta a fost doar jumătate din muncă. Naor și Regev trebuiau să împartă întreg spațiul, nu doar o bucată din el. Pentru a obține un n-cub sferic dimensional, au trebuit să-și înmulțească țigla eficientă cu o țiglă din spațiul rămas (asemănător cu modul în care ați putea multiplica un pătrat bidimensional cu un segment de linie unidimensional pentru a obține un cub tridimensional). Procedând astfel, construcția lor ar ridica înapoi în spațiul original, dar ar crește și suprafața acesteia.

Perechea a trebuit să arate că faianta din spațiul rămas, care nu era la fel de optimă, nu a adăugat prea mult suprafeței. Odată ce au făcut asta, construcția lor a fost finalizată. (Suprafața formei lor finale a ajuns să fie puțin mai mare decât cea a cubului sferic neconvex, dar ei cred că ar putea fi posibil să găsească o placă convexă care să fie la fel de eficientă ca omologul său neconvex.)

„Dovada lor este complet diferită” de lucrările anterioare pe cuburi sferice, a spus matematicianul Noga Alon. „Și retrospectiv, este poate o dovadă mai firească. Cu asta ar fi trebuit cineva să încerce să înceapă.”

„Când lucrurile sunt făcute diferit”, a adăugat Raz, „uneori găsiți implicații suplimentare interesante.”

Speranța reaprinsă

Nu este încă clar care ar putea fi aceste implicații – deși lucrarea exploatează potențiala utilizare a rețelelor întregi în criptografie și alte aplicații. Având în vedere cât de conectată este această problemă cu alte domenii, „este posibil să ducă la alte lucruri”, a spus Alon.

Momentan, informaticienii nu văd o modalitate de a interpreta rezultatul convex în limbajul repetiției paralele și a UGC. Dar ei nu au renunțat complet la planul inițial de a folosi problema spumei pentru a dovedi conjectura. „Există diferite moduri prin care puteți încerca să subminați barierele evidente pe care le-am întâlnit”, a spus Kindler.

Braverman și Minzer au încercat un astfel de mod atunci când ei spume revăzute în 2020. În loc să ceară ca forma plăcii să fie convexă, au cerut ca aceasta să respecte anumite simetrii, astfel încât să arate la fel, indiferent de modul în care îi răsturnați coordonatele. (În 2D, un pătrat ar funcționa, dar un dreptunghi nu ar funcționa; nici cuburile sferice cu dimensiuni mari descrise până în prezent.) Sub această nouă constrângere, perechea a putut să arate ceea ce Kindler și alții au sperat să facă cu 15 ani mai devreme: că nu poți face cu mult mai bine decât suprafața cubului până la urmă.

Acest lucru corespundea unui alt tip de repetiție paralelă - una care ar face cel mai simplu caz de tăiere maximă atât de greu pe cât trebuia să fie. În timp ce rezultatul oferă o oarecare speranță pentru această linie de cercetare, nu este clar dacă această versiune de repetiție paralelă va funcționa pentru toate problemele de tăiere maximă. „Nu înseamnă că ai terminat”, a spus Braverman. „Înseamnă doar că te-ai întors în afaceri.”

„Există mult potențial în geometrie”, a spus Minzer. „Doar că nu înțelegem suficient de bine.”