Matematikere fullfører oppdraget for å bygge 'sfæriske kuber'

På det fjerde århundre berømmet den greske matematikeren Pappus fra Alexandria bier for deres «geometriske omtanke». Den sekskantede strukturen til bikaken deres virket som den optimale måten å dele opp todimensjonalt rom i celler med likt areal og minimal omkrets – slik at insektene kunne kutte ned på hvor mye voks de trengte å produsere, og bruke mindre tid og energi på å bygge bikube.

Eller slik antok Pappus og andre. I årtusener kunne ingen bevise at sekskanter var optimale - før til slutt, i 1999, viste matematikeren Thomas Hales at ingen annen form kunne gjøre det bedre. I dag vet fortsatt ikke matematikere hvilke former som kan flislegge tre eller flere dimensjoner med minst mulig overflate.

Dette "skum"-problemet har vist seg å ha omfattende bruksområder - for fysikere som studerer oppførselen til såpebobler (eller skum) og kjemikere som analyserer strukturen til krystaller, for matematikere som utforsker sfærepakkingsarrangementer og statistikere som utvikler effektive databehandlingsteknikker .

På midten av 2000-tallet fanget også en spesiell formulering av skumproblemet øynene til teoretiske informatikere, som til deres overraskelse oppdaget at det var dypt knyttet til et viktig åpent problem innen deres felt. De var i stand til å bruke den forbindelsen til å finne en ny høydimensjonal form med minimal overflate.

"Jeg elsker dette frem og tilbake," sa Assaf Naor ved Princeton University. «Noe gammel matematikk blir relevant for informatikk; informatikk betaler tilbake og løser spørsmålet i matematikk. Det er veldig hyggelig når dette skjer.»

Men den formen, selv om den var optimal, manglet noe viktig: et geometrisk fundament. Fordi dens eksistens hadde blitt bevist ved hjelp av teknikker fra informatikk, var dens faktiske geometri vanskelig å forstå. Det er det Naor sammen med Oded Regev, en informatiker ved Courant Institute ved New York University, tok sikte på å korrigere et bevis lagt ut på nettet forrige måned.

"Det er en veldig fin avslutning på historien," sa Regev.

Kubisk skum

Matematikere har vurdert andre versjoner av skumproblemet - inkludert hva som skjer hvis du bare har lov til å dele opp plass i henhold til det som kalles heltallsgitteret. I den versjonen av problemet tar du en firkantet rekke med jevnt fordelte punkter (hver enhet fra hverandre) og gjør hvert av disse punktene til midten av en form. Det "kubiske" skumproblemet spør hva det minimale overflatearealet vil være når du er pålagt å flislegge plass på denne måten.

Forskere var opprinnelig interessert i å pålegge denne begrensningen for å forstå egenskapene til topologiske rom kalt manifolder. Men spørsmålet fikk sitt eget liv, og ble relevant i dataanalyse og andre applikasjoner.

Det er også geometrisk interessant, fordi det endrer hva "optimal" kan bety. I to dimensjoner, for eksempel, kan vanlige sekskanter ikke lenger flislegge planet hvis de bare kan forskyves med hele tall i horisontal og vertikal retning. (Du må flytte dem med irrasjonelle mengder i en av de to retningene.)

Firkanter kan. Men er det det beste som kan gjøres? Som matematiker Jaigyoung Choe oppdaget i 1989, er svaret nei. Den optimale formen er i stedet en sekskant som har blitt klemt i en retning og forlenget i en annen. (Omkretsen til en slik sekskant er omtrent 3.86 når arealet er 1 - og slår ut kvadratets omkrets på 4.)

Disse forskjellene kan virke trivielle, men de blir mye større i høyere dimensjoner.

Blant alle former for et gitt volum, er den som minimerer overflatearealet sfæren. Som n, antall dimensjoner, vokser, sfærens overflateareal øker proporsjonalt med kvadratroten av n.

Men kuler kan ikke flislegge en plass uten å etterlate hull. På den annen side, en n-dimensjonal kube med volum 1 boks. Haken er at overflaten er 2n, vokser i direkte forhold til dimensjonen. En 10,000-dimensjonal kube med volum 1 har et overflateareal på 20,000 - mye større enn 400, det omtrentlige overflatearealet til en 10,000-dimensjonal kule.

Og derfor lurte forskere på om de kunne finne en "sfærisk kube" - en form som fliser n-dimensjonalt rom, som en kube, men hvis overflate vokser sakte, som en kules.

Det virket usannsynlig. "Hvis du vil at boblen nøyaktig skal fylle opp plass og være sentrert på dette kubiske rutenettet, er det vanskelig å tenke på hva du ville brukt bortsett fra en kubisk boble," sa Ryan O'Donnell, en teoretisk dataforsker ved Carnegie Mellon University. "Det ser virkelig ut til at kuben burde være den beste."

Vi vet nå at det ikke er det.

Hardheten til harde problemer

I flere tiår ble problemet med kubisk skum relativt uutforsket i høyere dimensjoner. De første forskerne som gjorde fremskritt på det kom ikke fra geometriens område, men fra teoretisk informatikk. De kom over det ved en tilfeldighet, mens de søkte etter en måte å bevise en sentral uttalelse innen deres felt kjent som unike spillformodninger. "Den unike spillformodningen," sa Regev, "er det jeg ser på for tiden som det største åpne spørsmålet innen teoretisk informatikk."

Foreslått i 2002 av Subhash Khot, en doktorgradsstudent på den tiden, antyder formodningen at hvis et bestemt problem – et som involverer å tilordne farger til nodene i et nettverk – ikke kan løses nøyaktig, så er det svært vanskelig å finne selv en omtrentlig løsning. Hvis det er sant, vil formodningen tillate forskere å forstå kompleksiteten til et stort utvalg av andre beregningsoppgaver i ett slag.

Dataforskere klassifiserer ofte oppgaver basert på om de kan løses med en effektiv algoritme, eller om de i stedet er "NP-harde" (som betyr at de ikke kan løses effektivt ettersom størrelsen på problemet vokser, så lenge en allment antatt men ubevist formodning om beregningsmessig kompleksitet er sann). For eksempel er problemet med reisende selger, som ber om den korteste veien for å besøke hver by i et nettverk bare én gang, NP-hardt. Det samme er å bestemme om en graf - en samling av hjørner forbundet med kanter - kan merkes med maksimalt tre farger slik at to tilkoblede hjørner har forskjellige farger.

Det viser seg at det er NP-vanskelig å finne selv en omtrentlig løsning på mange av disse oppgavene. La oss si at du vil merke toppunktene til en graf med forskjellige farger på en måte som tilfredsstiller en liste over begrensninger. Hvis det er NP-vanskelig å tilfredsstille alle disse begrensningene, hva med å prøve å oppfylle bare 90 % av dem, eller 75 % eller 50 %? Under en eller annen terskel kan det være mulig å komme opp med en effektiv algoritme, men over den terskelen blir problemet NP-hardt.

I flere tiår har informatikere jobbet med å finne terskler for ulike optimaliseringsproblemer av interesse. Men noen spørsmål unngår denne typen beskrivelse. Selv om en algoritme kan garantere 80 % av den beste løsningen, kan det være NP-vanskelig å oppnå 95 % av den beste løsningen, og etterlater uavklart spørsmålet om hvor nøyaktig mellom 80 % og 95 % problemet tipper inn i NP-hardt territorium.

Den unike spillformodningen, eller UGC, tilbyr en måte å umiddelbart finne svaret på. Den gir en uttalelse som til å begynne med virker mer begrenset: at det er NP-vanskelig å se forskjellen mellom en graf som du kan tilfredsstille nesten alle av et bestemt sett med fargebegrensninger (f.eks. mer enn 99%) og en graf for som du kan tilfredsstille knapt noen (f.eks. mindre enn 1%).

Men kort tid etter at UGC ble foreslått i 2002, viste forskere at hvis formodningen er sann, kan du enkelt beregne hardhetsterskelen for ethvert problem med tilfredshet med begrensning. (Dette er fordi UGC også antyder at en kjent algoritme oppnår best mulig tilnærming for alle disse problemene.) "Det var nettopp knutepunktet for alle disse optimaliseringsproblemene," sa O'Donnell.

Og så satte teoretiske dataforskere ut for å bevise UGC - en oppgave som til slutt førte til at noen av dem oppdaget sfæriske kuber.

Gjør vanskelige problemer vanskeligere

I 2005 jobbet O'Donnell hos Microsoft Research. Han og to kolleger - Uriel Feige, nå ved Weizmann Institute of Science, og Guy Kindler, nå ved det hebraiske universitetet i Jerusalem – gikk sammen for å takle UGC.

De hadde en vag idé om hvordan de ønsket å gå frem. De ville starte med et spørsmål om grafer - et som er veldig likt UGC. Det såkalte maksimale kutt ("max-cut")-problemet spør, når det gis en graf, hvordan man kan dele opp hjørnene i to sett (eller farger) slik at antallet kanter som forbinder disse settene er så stort som mulig. (Du kan tenke på max cut som et spørsmål om den beste måten å fargelegge en graf med to farger, slik at så få kanter som mulig kobler sammen hjørner av samme farge.)

Hvis UGC er sann, vil det innebære at gitt en tilfeldig graf, kan en effektiv tilnærmingsalgoritme bare komme innenfor omtrent 87 % av det sanne maksimale kuttet til den grafen. Å gjøre noe bedre ville være NP-hardt.

Feige, Kindler og O'Donnell ønsket i stedet å gå i motsatt retning: De håpet å vise at maksimalt kutt er vanskelig å anslå, og deretter bruke det til å bevise UGC. Planen deres var avhengig av styrken til en teknikk kalt parallell repetisjon - en smart strategi som gjør vanskelige problemer vanskeligere.

Si at du vet at det er NP-vanskelig å skille mellom et problem du kan løse og et du stort sett kan løse. Parallell repetisjon gjør at du kan bygge videre på det for å vise et mye sterkere hardhetsresultat: at det også er NP-vanskelig å skille mellom et problem du kan løse og et du knapt kan løse i det hele tatt. "Dette ikke-intuitive, dype fenomenet ... er i tarmene til mye datavitenskap i dag," sa Naor.

Men det er en hake. Parallell repetisjon forsterker ikke alltid et problems hardhet så mye som dataforskere vil ha det til. Spesielt er det aspekter ved max-cut-problemet som "skaper en stor hodepine for parallell repetisjon," sa Regev.

Feige, Kindler og O'Donnell fokuserte på å vise at parallell repetisjon kunne fungere til tross for hodepinen. "Dette er en veldig komplisert ting å analysere," sa Dana Moshkovitz, en teoretisk dataforsker ved University of Texas, Austin. "Men dette virket fristende nært. Parallell repetisjon virket som det ville [hjelpe til med] denne forbindelsen fra max cut til unike spill."

Som en oppvarming prøvde forskerne å forstå parallell repetisjon for et enkelt tilfelle av maks cut, det Moshkovitz kalte "det dummeste max cut." Tenk på et oddetall av hjørner forbundet med kanter for å danne en sirkel, eller "oddesyklus". Du vil merke hvert toppunkt med en av to farger slik at ingen par av tilstøtende toppunkter har samme farge. I dette tilfellet er det umulig: En kant vil alltid koble sammen hjørner av samme farge. Du må slette den kanten, "bryte" den odde syklusen, for å få grafen din til å tilfredsstille problemets begrensning. Til syvende og sist vil du minimere den totale brøkdelen av kanter du må slette for å farge grafen på riktig måte.

Parallell repetisjon lar deg vurdere en høydimensjonal versjon av dette problemet - en der du må bryte alle de rare syklusene som dukker opp. Feige, Kindler og O'Donnell trengte å vise at ettersom antallet dimensjoner blir veldig stort, må du slette en veldig stor brøkdel av kanter for å bryte alle de odde syklusene. Hvis det var sant, ville det bety at parallell repetisjon effektivt kunne forsterke hardheten til dette "dumme max-cut"-problemet.

Det var da teamet oppdaget en merkelig tilfeldighet: Det fantes en geometrisk måte å tolke om parallell repetisjon ville fungere slik de håpet. Hemmeligheten lå i overflaten av kubiske skum.

Fra sitroner til limonade

Problemet deres, omskrevet på skumspråket, gikk ned til å vise at sfæriske kuber ikke kan eksistere - at det er umulig å dele høydimensjonalt rom langs heltallsgitteret i celler med overflateareal mye mindre enn kubens. (Et større overflateareal tilsvarer å måtte slette flere "dårlige" kanter i oddesyklusgrafen, som dataforskerne håpet å vise.)

"Vi var som, å, for et merkelig geometriproblem, men det er sannsynligvis sant, ikke sant?" sa O'Donnell. "Vi trengte virkelig at det var det sanne svaret." Men han, Feige og Kindler kunne ikke bevise det. Så i 2007, de publisert et papir som skisserer hvordan de planla å bruke dette problemet til å angripe UGC.

Snart nok ble håpet deres knust.

Ran Raz, en teoretisk informatiker ved Princeton som allerede hadde bevist flere store resultater om parallell repetisjon, ble fascinert av papiret deres. Han bestemte seg for å analysere parallell repetisjon for odd-syklusproblemet, delvis på grunn av forbindelsen til geometri som Feige, Kindler og O'Donnell hadde avdekket.

Raz startet ikke med skumproblemet, men angrep den informatikkversjonen av spørsmålet direkte. Han viste at du kan komme unna med å slette langt færre kanter for å bryte alle de odde syklusene i en graf. Med andre ord, parallell repetisjon kan ikke tilstrekkelig forsterke hardheten til dette maks-cut-problemet. "Parameterne som man får fra parallell repetisjon nøyaktig, ikke gir dette," sa Moshkovitz.

"Vår plan om å bruke parallell repetisjon for å vise hardheten til unike spill fungerte ikke engang i det enkleste tilfellet," sa O'Donnell. "Dette brøt liksom hele planen."

Selv om det var skuffende, antydet Razs resultat også eksistensen av sfæriske kuber: former som kan flislegges n-dimensjonalt rom med et overflateareal som skaleres i forhold til kvadratroten av n. "Vi tenkte, vel, la oss lage limonade av sitroner og ta dette skuffende tekniske resultatet om parallelle repetisjoner og diskrete grafer, og gjøre det om til et pent, interessant resultat i geometri," sa O'Donnell.

Han og Kindler, i samarbeid med dataviterne Anup Rao og Avi Wigderson, gransket Raz sitt bevis til de hadde lært teknikkene godt nok til å oversette dem til skumproblemet. I 2008 viste de det sfæriske kuber er faktisk mulig.

"Det er en fin måte å resonnere om problemet," sa Mark Braverman av Princeton. "Det er vakkert."

Og det reiste spørsmål på geometrisiden av historien. Fordi de hadde brukt Raz sitt arbeid med parallelle repetisjoner for å konstruere sin fliseform, endte Kindler, O'Donnell, Rao og Wigderson opp med noe stygt og Frankenstein-aktig. Flisen var rotete og full av fordypninger. I matematiske termer var den ikke konveks. Mens dette fungerte for deres formål, manglet den sfæriske kuben egenskaper som matematikere foretrekker - egenskaper som gjør en form mer konkret, lettere å definere og studere, og mer egnet for potensielle bruksområder.

"Det er noe veldig utilfredsstillende med konstruksjonen deres," sa Regev. «Det ser ut som en amøbe. Det ser ikke ut som det du forventer, en fin flislagt kropp.»

Det var det han og Naor forsøkte å finne.

Å bryte seg løs fra buret

Fra første stund innså Naor og Regev at de måtte starte fra bunnen av. "Delvis fordi konvekse kropper er så restriktive, hadde ingen av de tidligere teknikkene noen sjanse til å fungere," sa Dor Minzer, en teoretisk dataforsker ved Massachusetts Institute of Technology.

Faktisk var det helt plausibelt at konveksitet ville være for restriktiv - at en konveks sfærisk kube rett og slett ikke eksisterer.

Men forrige måned beviste Naor og Regev at du kan dele opp n-dimensjonalt rom langs heltallskoordinater med en konveks form hvis overflate er ganske nær sfæren. Og de gjorde det helt geometrisk - og returnerte problemet til dets matematiske røtter.

De måtte først komme seg rundt et stort hinder. Det kubiske skumproblemet krever at hver flis er sentrert ved heltallskoordinater. Men i heltallsgitteret er det veldig korte avstander mellom noen punkter - og de korte avstandene forårsaker problemer.

Tenk på et punkt i det todimensjonale rutenettet. Den er plassert 1 enhet unna de nærmeste punktene i horisontal og vertikal retning. Men i diagonal retning er det nærmeste punktet $latex sqrt{2}$ enheter unna – et avvik som blir verre i større områder. I n-dimensjonalt heltallsgitter, de nærmeste punktene er fortsatt 1 enhet unna, men de "diagonale" punktene er nå $latex sqrt{n}$ enheter unna. I for eksempel 10,000 100 dimensjoner betyr dette at den nærmeste "diagonale" naboen til ethvert punkt er 10,000 enheter unna, selv om det er 1 XNUMX andre punkter (ett i hver retning) som bare er XNUMX enhet unna.

I andre gitter vokser disse to typene avstander i forhold til hverandre. Matematikere har i flere tiår visst hvordan man fliser slike gitter med konvekse former med minimal overflate.

Men i heltallsgitteret vil de korteste avstandene alltid være fast på 1. Dette kommer i veien for å konstruere en pen flis med optimal overflate. "De satte deg på en måte i dette buret," sa Regev. "De gjør alt veldig tett rundt deg."

Så Naor og Regev vurderte i stedet en bit av det fulle n-dimensjonalt rom. De valgte nøye dette underrommet slik at det fortsatt ville være rikt på heltallspunkter, men ingen av disse punktene ville være for nær hverandre.

Underrommet de endte opp med var med andre ord nettopp den typen matematikere allerede visste hvordan de skulle flislegge optimalt.

Men dette var bare halve arbeidet. Naor og Regev trengte å dele opp hele plassen, ikke bare en bit av den. For å få en n-dimensjonal sfærisk kube, måtte de multiplisere sin effektive flis med en flis fra det gjenværende rommet (i likhet med hvordan du kan multiplisere et todimensjonalt kvadrat med et endimensjonalt linjestykke for å få en tredimensjonal kube). Å gjøre det ville løfte konstruksjonen tilbake til det opprinnelige rommet, men det ville også øke overflaten.

Paret måtte vise at flisen fra den gjenværende plassen, som ikke var like optimal, ikke tilførte overflaten for mye. Når de gjorde det, var konstruksjonen deres fullført. (Deres endelige forms overflate endte opp med å bli litt større enn den ikke-konvekse sfæriske kuben, men de tror at det kan være mulig å finne en konveks flis som er like effektiv som dens ikke-konvekse motstykke.)

"Beviset deres er helt annerledes" fra tidligere arbeid med sfæriske kuber, sa matematikeren Noga Alon. «Og i ettertid er det kanskje et mer naturlig bevis. Dette er hva noen kanskje burde ha prøvd til å begynne med.»

"Når ting gjøres annerledes," la Raz til, "noen ganger finner du interessante tilleggsimplikasjoner."

Håpet tennes på nytt

Det er foreløpig ikke klart hva disse implikasjonene kan være - selv om arbeidet tar utgangspunkt i den potensielle bruken av heltallsgitter i kryptografi og andre applikasjoner. Gitt hvor knyttet dette problemet er til andre felt, "vil det sannsynligvis føre til andre ting," sa Alon.

For øyeblikket ser ikke informatikere en måte å tolke det konvekse resultatet i språket parallell repetisjon og UGC. Men de har ikke helt gitt opp den opprinnelige planen om å bruke skumproblemet til å bevise formodningen. "Det er forskjellige måter du kan prøve å undergrave de åpenbare barrierene vi møtte," sa Kindler.

Braverman og Minzer prøvde en slik måte da de revisit foams i 2020. I stedet for å kreve at flisformen skal være konveks, ba de om at den skulle følge visse symmetrier, slik at den ser lik ut uansett hvordan du snur koordinatene. (I 2D ville en firkant fungere, men et rektangel ville ikke; det ville heller ikke de høydimensjonale sfæriske kubene beskrevet til dags dato.) Under denne nye begrensningen var paret i stand til å vise hva Kindler og andre hadde håpet på 15 år tidligere: at du ikke kan gjøre mye bedre enn overflaten til kuben tross alt.

Dette tilsvarte en annen type parallell repetisjon - en som ville gjøre det enkleste tilfellet med maks cut så hardt som det måtte være. Mens resultatet gir et visst håp for denne forskningslinjen, er det ikke klart om denne versjonen av parallell repetisjon vil fungere for alle maks-kutt-problemer. "Det betyr ikke at du er ferdig," sa Braverman. "Det betyr bare at du er tilbake i virksomheten."

"Det er mye potensial i geometri," sa Minzer. "Det er bare det at vi ikke forstår det godt nok."