Matematikere fuldfører opgaven for at bygge 'sfæriske terninger'

I det fjerde århundrede roste den græske matematiker Pappus fra Alexandria bier for deres "geometriske omtanke". Den sekskantede struktur af deres honeycomb virkede som den optimale måde at opdele todimensionelt rum i celler med lige areal og minimal omkreds - hvilket gør det muligt for insekterne at skære ned på, hvor meget voks de skulle producere, og bruge mindre tid og energi på at bygge deres bikube.

Eller det havde Pappus og andre hypoteser. I årtusinder kunne ingen bevise, at sekskanter var optimale - indtil til sidst, i 1999, viste matematikeren Thomas Hales, at ingen anden form kunne gøre det bedre. I dag ved matematikere stadig ikke, hvilke figurer der kan flisebelægge tre eller flere dimensioner med det mindst mulige overfladeareal.

Dette "skum"-problem har vist sig at have vidtrækkende anvendelser - for fysikere, der studerer sæbeboblers (eller skums) adfærd og kemikere, der analyserer krystallers struktur, for matematikere, der udforsker kuglepakningsarrangementer, og statistikere, der udvikler effektive databehandlingsteknikker .

I midten af ​​2000'erne fangede en særlig formulering af skumproblemet også teoretiske dataloger, som til deres overraskelse opdagede, at det var dybt forbundet med et vigtigt åbent problem inden for deres felt. De var i stand til at bruge den forbindelse til at finde en ny højdimensionel form med minimal overflade.

"Jeg elsker det her frem og tilbage," sagde Assaf Naor fra Princeton University. ”Noget gammel matematik bliver relevant for datalogi; datalogi betaler tilbage og løser spørgsmålet i matematik. Det er meget rart, når det her sker.”

Men den form, selvom den var optimal, manglede noget vigtigt: et geometrisk fundament. Fordi dens eksistens var blevet bevist ved hjælp af teknikker fra computervidenskab, var dens faktiske geometri svær at forstå. Det er hvad Naor sammen med Oded Regev, en datalog ved Courant Institute ved New York University, satte sig for at rette ind et bevis lagt ud på nettet i sidste måned.

"Det er en meget fin afslutning på historien," sagde Regev.

Kubisk skum

Matematikere har overvejet andre versioner af skumproblemet - herunder hvad der sker, hvis du kun får lov til at opdele rummet i henhold til det, der kaldes heltalsgitteret. I den version af problemet tager du en firkantet række af punkter med jævnt mellemrum (hver 1 enhed fra hinanden) og gør hvert af disse punkter til midten af ​​en form. Det "kubiske" skumproblem spørger, hvad det minimale overfladeareal vil være, når du skal flise plads på denne måde.

Forskere var oprindeligt interesseret i at pålægge denne begrænsning for at forstå egenskaberne ved topologiske rum kaldet manifolds. Men spørgsmålet fik sit eget liv og blev relevant i dataanalyse og andre applikationer.

Det er også geometrisk interessant, fordi det ændrer, hvad "optimal" kan betyde. I to dimensioner, for eksempel, kan regulære sekskanter ikke længere fliselægge planet, hvis de kun kan forskydes med heltal i vandret og lodret retning. (Du skal flytte dem med irrationelle mængder i en af ​​de to retninger.)

Firkanter kan. Men er det det bedste, der kan gøres? Som matematiker Jaigyoung Choe opdaget i 1989, er svaret nej. Den optimale form er i stedet en sekskant, der er blevet klemt i én retning og forlænget i en anden. (Omkredsen af ​​en sådan sekskant er cirka 3.86, når dens areal er 1 - hvilket slår kvadratets omkreds på 4 ud.)

Disse forskelle kan virke trivielle, men de bliver meget større i højere dimensioner.

Blandt alle former for et givet volumen er kuglen den, der minimerer overfladearealet. Som n, antallet af dimensioner, vokser, kuglens overfladeareal øges i forhold til kvadratroden af n.

Men kugler kan ikke flisebelægge et rum uden at efterlade huller. På den anden side er en n-dimensionel terning af volumen 1 dåse. Fangsten er, at dens overfladeareal er 2n, der vokser i direkte forhold til dens dimension. En 10,000-dimensionel terning af volumen 1 har et overfladeareal på 20,000 - meget større end 400, det omtrentlige overfladeareal af en 10,000-dimensional kugle.

Og derfor spekulerede forskere på, om de kunne finde en "sfærisk terning" - en form, der fliser n-dimensionelt rum, som en terning, men hvis overflade vokser langsomt, som en kugles.

Det virkede usandsynligt. "Hvis du vil have, at din boble nøjagtigt fylder rummet og være centreret på dette kubiske gitter, er det svært at tænke på, hvad du ville bruge bortset fra en kubisk boble," sagde Ryan O'Donnell, en teoretisk datalog ved Carnegie Mellon University. "Det ser virkelig ud til, at kuben burde være den bedste."

Det ved vi nu, at det ikke er.

Hårdheden af ​​hårde problemer

I årtier gik det kubiske skumproblem relativt uudforsket i højere dimensioner. De første forskere, der gjorde fremskridt på det, kom ikke fra geometriens område, men fra teoretisk datalogi. De stødte på det ved et tilfælde, mens de ledte efter en måde at bevise et centralt udsagn på deres felt kendt som unikke spil formodninger. "Den unikke spilformodning," sagde Regev, "er, hvad jeg i øjeblikket ser som det største åbne spørgsmål inden for teoretisk datalogi."

Foreslået i 2002 af Subhash Khot, en kandidatstuderende på det tidspunkt, antyder formodningen, at hvis et bestemt problem - et der involverer tildeling af farver til et netværks noder - ikke kan løses nøjagtigt, så er det meget svært at finde selv en omtrentlig løsning. Hvis det er sandt, ville formodningen give forskere mulighed for at forstå kompleksiteten af ​​et stort udvalg af andre beregningsopgaver i ét hug.

Dataloger klassificerer ofte opgaver baseret på, om de kan løses med en effektiv algoritme, eller om de i stedet er "NP-hårde" (hvilket betyder, at de ikke kan løses effektivt, efterhånden som problemets størrelse vokser, så længe en almindeligt antaget men ubeviste formodninger om beregningsmæssig kompleksitet er sande). For eksempel er problemet med den rejsende sælger, som beder om den korteste vej, der er nødvendig for kun at besøge hver by i et netværk én gang, NP-svært. Det samme er at bestemme, om en graf - en samling af hjørner forbundet med kanter - kan mærkes med højst tre farver, så to forbundne hjørner har forskellige farver.

Det viser sig, at det er NP-svært at finde selv en omtrentlig løsning på mange af disse opgaver. Lad os sige, at du vil mærke hjørnerne af en graf med forskellige farver på en måde, der opfylder en liste over begrænsninger. Hvis det er NP-svært at opfylde alle disse begrænsninger, hvad med at prøve at opfylde kun 90 % af dem, eller 75 % eller 50 %? Under en eller anden tærskel kan det være muligt at komme med en effektiv algoritme, men over den tærskel bliver problemet NP-hårdt.

I årtier har dataloger arbejdet på at fastlægge tærskler for forskellige optimeringsproblemer af interesse. Men nogle spørgsmål undgår denne form for beskrivelse. Selvom en algoritme kan garantere 80 % af den bedste løsning, kan det være NP-svært at opnå 95 % af den bedste løsning, hvilket efterlader uafklaret spørgsmålet om, hvor præcis mellem 80 % og 95 % problemet tipper ind i NP-hårdt territorium.

Den unikke spilformodning, eller UGC, tilbyder en måde at finde svaret på med det samme. Den fremsætter en erklæring, som i første omgang virker mere begrænset: at det er NP-svært at se forskel på en graf, for hvilken du kan opfylde næsten alle et bestemt sæt af farvebegrænsninger (f.eks. mere end 99%) og en graf for som du næsten ikke kan tilfredsstille (f.eks. mindre end 1%).

Men kort efter at UGC blev foreslået i 2002, viste forskere, at hvis formodningen er sand, så kan du nemt beregne hårdhedstærsklen for ethvert problem med begrænsningstilfredshed. (Dette skyldes, at UGC også indebærer, at en kendt algoritme opnår den bedst mulige tilnærmelse til alle disse problemer.) "Det var netop omdrejningspunktet for alle disse optimeringsproblemer," sagde O'Donnell.

Og så teoretiske dataloger satte sig for at bevise UGC - en opgave, der i sidste ende fik nogle af dem til at opdage sfæriske terninger.

Gør svære problemer sværere

I 2005 arbejdede O'Donnell hos Microsoft Research. Han og to kolleger - Uriel Feige, nu ved Weizmann Institute of Science, og Guy Kindler, nu ved det hebraiske universitet i Jerusalem - gik sammen om at tackle UGC.

De havde en vag idé om, hvordan de ville gå videre. De ville starte med et spørgsmål om grafer - et spørgsmål, der minder meget om UGC. Det såkaldte maximum cut ("max-cut") problem spørger, når der gives en graf, hvordan man opdeler dens hjørner i to sæt (eller farver), så antallet af kanter, der forbinder disse sæt, er så stort som muligt. (Du kan tænke på max cut som et spørgsmål om den bedste måde at farve en graf med to farver, så så få kanter som muligt forbinder hjørner af samme farve.)

Hvis UGC er sand, ville det betyde, at givet en tilfældig graf, kan en effektiv tilnærmelsesalgoritme kun komme inden for omkring 87 % af den sande maksimale snit af denne graf. At gøre det bedre ville være NP-hårdt.

Feige, Kindler og O'Donnell ønskede i stedet at gå i den modsatte retning: De håbede at vise, at max cut er svært at anslå, og derefter bruge det til at bevise UGC. Deres plan var afhængig af styrken af ​​en teknik kaldet parallel gentagelse - en smart strategi, der gør svære problemer sværere.

Sig, at du ved, at det er NP-svært at skelne mellem et problem, du kan løse, og et, du for det meste kan løse. Parallel gentagelse giver dig mulighed for at bygge videre på det for at vise et meget stærkere hårdhedsresultat: at det også er NP-svært at skelne mellem et problem, du kan løse, og et, du næsten ikke kan løse overhovedet. "Dette ikke-intuitive, dybe fænomen ... er i maven af ​​en masse computervidenskab i dag," sagde Naor.

Men der er en fangst. Parallel gentagelse forstærker ikke altid et problems hårdhed så meget, som dataloger ønsker det. Især er der aspekter af max-cut-problemet, der "skaber en stor hovedpine for parallel gentagelse," sagde Regev.

Feige, Kindler og O'Donnell fokuserede på at vise, at parallel gentagelse kunne fungere på trods af hovedpinen. "Dette er en virkelig kompliceret ting at analysere," sagde Dana Moshkovitz, en teoretisk datalog ved University of Texas, Austin. "Men det her virkede fristende tæt på. Parallel gentagelse virkede som om det ville [hjælpe med at skabe] denne forbindelse fra max cut til unikke spil."

Som opvarmning forsøgte forskerne at forstå parallel gentagelse for et simpelt tilfælde af max cut, hvad Moshkovitz kaldte "det dummeste max cut." Overvej et ulige antal hjørner forbundet med kanter for at danne en cirkel eller "ulige cyklus". Du vil mærke hvert hjørne med en af ​​to farver, så intet par af tilstødende hjørner har samme farve. I dette tilfælde er det umuligt: ​​En kant vil altid forbinde hjørner af samme farve. Du skal slette den kant, "bryde" den ulige cyklus, for at få din graf til at tilfredsstille problemets begrænsning. I sidste ende vil du minimere den samlede brøkdel af kanter, du skal slette for at farve din graf korrekt.

Parallel gentagelse giver dig mulighed for at overveje en højdimensionel version af dette problem - en, hvor du skal bryde alle de ulige cyklusser, der opstår. Feige, Kindler og O'Donnell havde brug for at vise, at da antallet af dimensioner bliver meget stort, skal du slette en meget stor brøkdel af kanter for at bryde alle de ulige cyklusser. Hvis det var sandt, ville det betyde, at parallel gentagelse effektivt kunne forstærke hårdheden af ​​dette "dumme max-cut"-problem.

Det var da holdet opdagede en mærkelig tilfældighed: Der var en geometrisk måde at fortolke, om parallel gentagelse ville fungere, som de håbede, den ville. Hemmeligheden lå i overfladearealet af kubiske skum.

Fra citroner til limonade

Deres problem, omskrevet i skumsproget, gik ud på at vise, at sfæriske terninger ikke kan eksistere - at det er umuligt at opdele højdimensionelt rum langs heltalsgitteret i celler med overfladeareal meget mindre end terningens. (Et større overfladeareal svarer til at skulle slette flere "dårlige" kanter i ulige-cyklus-grafen, som datalogerne håbede at vise.)

"Vi var ligesom, åh, sikke et underligt geometriproblem, men det er nok sandt, ikke?" sagde O'Donnell. "Vi havde virkelig brug for, at det var det sande svar." Men han, Feige og Kindler kunne ikke bevise det. Så i 2007 gjorde de udgivet et papir beskriver, hvordan de planlagde at bruge dette problem til at hjælpe med at angribe UGC.

Snart nok gik deres håb op.

Ran Raz, en teoretisk datalog ved Princeton, som allerede havde bevist flere store resultater om parallel gentagelse, var fascineret af deres papir. Han besluttede at analysere parallel gentagelse for ulige cyklusproblemet, delvist på grund af forbindelsen til geometri, som Feige, Kindler og O'Donnell havde afsløret.

Raz startede ikke med skumproblemet, men angreb den computervidenskabelige version af spørgsmålet direkte. Han viste, at du kan slippe af sted med at slette langt færre kanter for at bryde alle de ulige cyklusser i en graf. Med andre ord kan parallel gentagelse ikke tilstrækkeligt forstærke hårdheden af ​​dette max-cut-problem. "De parametre, som man får fra parallel gentagelse nøjagtigt, mangler nøjagtigt at give dette," sagde Moshkovitz.

"Vores plan om at bruge parallel gentagelse for at vise hårdheden af ​​unikke spil virkede ikke engang i det mest simple tilfælde," sagde O'Donnell. "Denne slags brød hele planen."

Selvom det var skuffende, antydede Raz' resultat også eksistensen af ​​sfæriske terninger: former, der kan flisebelægges. n-dimensionelt rum med et overfladeareal, der skaleres i forhold til kvadratroden af n. "Vi var ligesom, ja, lad os lave limonade ud af citroner og tage dette skuffende tekniske resultat om parallel gentagelse og diskrete grafer, og gøre det til et pænt, interessant resultat i geometri," sagde O'Donnell.

Han og Kindler i samarbejde med datalogerne Anup Rao , Avi Wigderson, gennemsøgte Raz' bevis, indtil de havde lært dets teknikker godt nok til at oversætte dem til skumproblemet. Det viste de i 2008 sfæriske terninger er faktisk mulige.

"Det er en god måde at ræsonnere om problemet," sagde Mark Braverman af Princeton. "Det er smukt."

Og det rejste spørgsmål om geometrisiden af ​​historien. Fordi de havde brugt Raz' arbejde med parallel gentagelse til at konstruere deres fliseform, endte Kindler, O'Donnell, Rao og Wigderson med noget grimt og Frankenstein-agtigt. Flisen var rodet og fuld af fordybninger. I matematiske termer var det ikke konveks. Mens dette fungerede til deres formål, manglede den sfæriske terning egenskaber, som matematikere foretrækker - egenskaber, der gør en form mere konkret, lettere at definere og studere og mere egnet til potentielle anvendelser.

"Der er noget meget utilfredsstillende ved deres konstruktion," sagde Regev. "Det ligner en amøbe. Det ligner ikke, hvad du ville forvente, en flot flisebelægning.”

Det var, hvad han og Naor satte sig for at finde.

At bryde fri af buret

Fra starten indså Naor og Regev, at de skulle starte fra bunden. "Delvis fordi konvekse kroppe er så restriktive, havde ingen af ​​de tidligere teknikker nogen chance for at virke," sagde Dor Minzer, en teoretisk datalog ved Massachusetts Institute of Technology.

Faktisk var det helt plausibelt, at konveksitet ville være for restriktiv - at en konveks sfærisk terning simpelthen ikke eksisterer.

Men i sidste måned beviste Naor og Regev, at man kan opdele n-dimensionelt rum langs heltalskoordinater med en konveks form, hvis overfladeareal er ret tæt på kuglens. Og de gjorde det helt geometrisk - vendte problemet tilbage til dets matematiske rødder.

De skulle først rundt om en større forhindring. Det kubiske skumproblem kræver, at hver flise centreres ved heltalskoordinater. Men i heltalsgitteret er der meget korte afstande mellem nogle punkter - og de korte afstande forårsager problemer.

Overvej et punkt i det todimensionelle gitter. Den er placeret 1 enhed væk fra de nærmeste punkter i vandret og lodret retning. Men i den diagonale retning er det nærmeste punkt $latex sqrt{2}$ enheder væk - en uoverensstemmelse, der bliver værre i større rum. I den n-dimensionelle heltalsgitter, de nærmeste punkter er stadig 1 enhed væk, men disse "diagonale" punkter er nu $latex sqrt{n}$ enheder væk. I for eksempel 10,000 dimensioner betyder det, at den nærmeste "diagonale" nabo til ethvert punkt er 100 enheder væk, selvom der er 10,000 andre punkter (et i hver retning), der kun er 1 enhed væk.

I andre gitter vokser disse to slags afstande i forhold til hinanden. Matematikere har i årtier vidst, hvordan man fliser sådanne gitter med konvekse former med minimal overflade.

Men i heltalsgitteret vil de korteste afstande altid sidde fast på 1. Dette kommer i vejen for at konstruere en flot flise med optimal overflade. "De satte dig på en måde i det her bur," sagde Regev. "De gør alt meget tæt omkring dig."

Så Naor og Regev overvejede i stedet et stykke af det fulde n-dimensionelt rum. De valgte omhyggeligt dette underrum, så det stadig ville være rigt på heltalspunkter, men ingen af ​​disse punkter ville være for tæt på hinanden.

Det underrum, de endte med, var med andre ord netop den type, som matematikerne allerede vidste, hvordan man fliser optimalt.

Men dette var kun halvdelen af ​​arbejdet. Naor og Regev havde brug for at opdele hele rummet, ikke kun en del af det. At få en n-dimensionelle sfæriske terning, skulle de multiplicere deres effektive flise med en flise fra det resterende rum (tilsvarer hvordan man kan gange et todimensionelt kvadrat med et endimensionelt linjestykke for at få en tredimensionel terning). At gøre det ville løfte deres konstruktion tilbage til det oprindelige rum, men det ville også øge dets overfladeareal.

Parret skulle vise, at flisen fra den resterende plads, som ikke var så optimal, ikke tilføjede for meget til overfladen. Når de gjorde det, var deres konstruktion færdig. (Deres endelige forms overflade endte med at blive lidt større end den ikke-konvekse sfæriske terning, men de mener, at det måske er muligt at finde en konveks flise, der er lige så effektiv som dens ikke-konvekse modstykke.)

"Deres bevis er helt anderledes" fra tidligere arbejde med sfæriske terninger, sagde matematikeren Noga Alon. ”Og set i bakspejlet er det måske et mere naturligt bevis. Det er det, nogen måske burde have prøvet til at begynde med.”

"Når tingene gøres anderledes," tilføjede Raz, "nogle gange finder man interessante yderligere implikationer."

Håbet genopstod

Det er endnu ikke klart, hvad disse implikationer kan være - selvom arbejdet tager fat på den potentielle brug af heltalsgitter i kryptografi og andre applikationer. I betragtning af hvor forbundet dette problem er med andre områder, "vil det sandsynligvis føre til andre ting," sagde Alon.

I øjeblikket ser dataloger ikke en måde at fortolke det konvekse resultat på i sproget med parallel gentagelse og UGC. Men de har ikke helt opgivet den oprindelige plan om at bruge skumproblemet til at bevise formodningen. "Der er forskellige måder, du kan prøve at undergrave de åbenlyse barrierer, vi stødte på," sagde Kindler.

Braverman og Minzer prøvede en sådan måde, da de genbesøgte skum i 2020. I stedet for at kræve, at fliseformen skal være konveks, bad de om, at den skulle adlyde visse symmetrier, så den ser ens ud, uanset hvordan du vender dens koordinater. (I 2D ville en firkant fungere, men et rektangel ville ikke; heller ikke de højdimensionelle sfæriske terninger, der er beskrevet til dato.) Under denne nye begrænsning var parret i stand til at vise, hvad Kindler og andre havde håbet på 15 år tidligere: at man trods alt ikke kan gøre det meget bedre end terningens overfladeareal.

Dette svarede til en anden form for parallel gentagelse - en, der ville gøre det enkleste tilfælde af max cut så hårdt, som det skulle være. Selvom resultatet giver håb for denne forskningslinje, er det ikke klart, om denne version af parallel gentagelse vil fungere for alle max-cut-problemer. "Det betyder ikke, at du er færdig," sagde Braverman. "Det betyder bare, at du er tilbage i erhvervslivet."

"Der er et stort potentiale i geometri," sagde Minzer. "Det er bare, at vi ikke forstår det godt nok."