Wiskundigen voltooien missie om 'sferische kubussen' te bouwen

In de vierde eeuw prees de Griekse wiskundige Pappus van Alexandrië bijen om hun 'geometrische vooruitziende blik'. De zeshoekige structuur van hun honingraat leek de optimale manier om tweedimensionale ruimte te verdelen in cellen van gelijke oppervlakte en minimale omtrek - waardoor de insecten konden bezuinigen op de hoeveelheid was die ze nodig hadden om te produceren, en minder tijd en energie konden besteden aan het bouwen van hun bijenkorf.

Of dat veronderstelden Pappus en anderen. Duizenden jaren lang kon niemand bewijzen dat zeshoeken optimaal waren - totdat uiteindelijk, in 1999, de wiskundige Thomas Hales aantoonde dat geen enkele andere vorm beter kon. Tegenwoordig weten wiskundigen nog steeds niet welke vormen drie of meer dimensies met een zo klein mogelijke oppervlakte kunnen betegelen.

Dit "schuim" -probleem bleek brede toepassingen te hebben - voor natuurkundigen die het gedrag van zeepbellen (of schuimen) bestuderen en scheikundigen die de structuur van kristallen analyseren, voor wiskundigen die sferische opstellingen onderzoeken en statistici die effectieve gegevensverwerkingstechnieken ontwikkelen .

Halverwege de jaren 2000 trok een bepaalde formulering van het schuimprobleem ook de aandacht van theoretische computerwetenschappers, die tot hun verbazing ontdekten dat het nauw verbonden was met een belangrijk open probleem in hun vakgebied. Ze waren in staat om die verbinding te gebruiken om een ​​nieuwe hoogdimensionale vorm met een minimale oppervlakte te vinden.

"Ik hou van dit heen en weer," zei Assaf Naor van Princeton University. “Sommige oude wiskunde wordt relevant voor de informatica; informatica betaalt terug en lost de vraag in de wiskunde op. Het is heel fijn als dit gebeurt.”

Maar die vorm, hoewel optimaal, miste iets belangrijks: een geometrische basis. Omdat het bestaan ​​ervan was bewezen met behulp van technieken uit de informatica, was de feitelijke geometrie moeilijk te vatten. Dat is wat Naor, samen met Oded Regev, een computerwetenschapper aan het Courant Institute van de New York University, trachtte in te corrigeren een bewijs dat vorige maand online is geplaatst.

"Het is een heel mooi einde van het verhaal," zei Regev.

Kubusvormige Schuimen

Wiskundigen hebben andere versies van het schuimprobleem overwogen - inclusief wat er gebeurt als je de ruimte alleen mag verdelen volgens wat het rooster met gehele getallen wordt genoemd. In die versie van het probleem neem je een vierkante reeks gelijkmatig verdeelde punten (elk 1 eenheid uit elkaar) en maak van elk van die punten het middelpunt van een vorm. Het "kubusvormige" schuimprobleem vraagt ​​wat de minimale oppervlakte zal zijn wanneer u op deze manier ruimte moet betegelen.

Onderzoekers waren aanvankelijk geïnteresseerd in het opleggen van deze beperking om eigenschappen te begrijpen van topologische ruimten die variëteiten worden genoemd. Maar de vraag ging een eigen leven leiden en werd relevant in data-analyse en andere toepassingen.

Het is ook geometrisch interessant, omdat het verandert wat "optimaal" zou kunnen betekenen. In twee dimensies kunnen regelmatige zeshoeken bijvoorbeeld niet langer het vlak betegelen als ze alleen in horizontale en verticale richting met gehele getallen kunnen worden verschoven. (Je moet ze met irrationele hoeveelheden in een van de twee richtingen verplaatsen.)

Pleinen kunnen. Maar is dat het beste wat er gedaan kan worden? Als de wiskundige Jaigyoung Choe ontdekt in 1989, is het antwoord nee. De optimale vorm is in plaats daarvan een zeshoek die in de ene richting is samengedrukt en in de andere richting langwerpig. (De omtrek van zo'n zeshoek is ongeveer 3.86 als de oppervlakte 1 is, waarmee de omtrek van het vierkant van 4 wordt overtroffen.)

Deze verschillen lijken misschien triviaal, maar ze worden veel groter in hogere dimensies.

Van alle vormen van een bepaald volume is degene die het oppervlak minimaliseert de bol. Als n, het aantal dimensies, groeit, de oppervlakte van de bol neemt toe in verhouding tot de vierkantswortel van n.

Maar bollen kunnen een ruimte niet betegelen zonder gaten achter te laten. Aan de andere kant, een n-dimensionale kubus van volume 1 blikje. De vangst is dat de oppervlakte 2 isn, groeiend in directe verhouding tot zijn dimensie. Een 10,000-dimensionale kubus van volume 1 heeft een oppervlakte van 20,000 - veel groter dan 400, de geschatte oppervlakte van een 10,000-dimensionale bol.

En dus vroegen onderzoekers zich af of ze een "bolvormige kubus" konden vinden - een vorm die betegelt n-dimensionale ruimte, zoals een kubus, maar waarvan het oppervlak langzaam groeit, zoals dat van een bol.

Het leek onwaarschijnlijk. "Als je wilt dat je bubbel precies de ruimte opvult en gecentreerd is op dit kubusvormige raster, is het moeilijk na te denken over wat je anders zou gebruiken dan een kubusvormige bubbel," zei Ryan O'Donnell, een theoretisch computerwetenschapper aan de Carnegie Mellon University. "Het lijkt er echt op dat de kubus de beste zou moeten zijn."

We weten nu dat dat niet zo is.

De hardheid van moeilijke problemen

Decennialang bleef het kubische schuimprobleem relatief onontgonnen in hogere dimensies. De eerste onderzoekers die er vooruitgang mee boekten, kwamen niet uit de meetkunde, maar uit de theoretische informatica. Ze kwamen het toevallig tegen, terwijl ze op zoek waren naar een manier om een ​​centrale uitspraak in hun vakgebied, bekend als de uniek spelvermoeden. "Het unieke vermoeden van games," zei Regev, "is wat ik momenteel beschouw als de grootste open vraag in de theoretische informatica."

Voorgesteld in 2002 door Subhash Khot, een afgestudeerde student in die tijd, stelt het vermoeden dat als een bepaald probleem - een probleem dat betrekking heeft op het toewijzen van kleuren aan de knooppunten van een netwerk - niet precies kan worden opgelost, het erg moeilijk is om zelfs maar een benaderende oplossing te vinden. Als het waar is, zou het vermoeden onderzoekers in staat stellen om in één klap de complexiteit van een groot aantal andere computertaken te begrijpen.

Computerwetenschappers classificeren taken vaak op basis van of ze kunnen worden opgelost met een efficiënt algoritme, of dat ze in plaats daarvan "NP-hard" zijn (wat betekent dat ze niet efficiënt kunnen worden opgelost naarmate het probleem groter wordt, zolang een algemeen aangenomen maar onbewezen vermoedens over computationele complexiteit zijn waar). Het handelsreizigersprobleem, dat vraagt ​​naar de kortste weg die nodig is om elke stad in een netwerk slechts één keer te bezoeken, is bijvoorbeeld NP-moeilijk. Dat geldt ook voor het bepalen of een grafiek - een verzameling hoekpunten verbonden door randen - kan worden gelabeld met maximaal drie kleuren, zodat twee verbonden hoekpunten verschillende kleuren hebben.

Het blijkt dat het NP-moeilijk is om zelfs maar een benaderende oplossing te vinden voor veel van deze taken. Stel dat u de hoekpunten van een grafiek met verschillende kleuren wilt labelen op een manier die voldoet aan een lijst met beperkingen. Als het NP-moeilijk is om aan al die beperkingen te voldoen, hoe zit het dan met het proberen om slechts 90% ervan te vervullen, of 75%, of 50%? Onder een bepaalde drempel is het misschien mogelijk om een ​​efficiënt algoritme te bedenken, maar boven die drempel wordt het probleem NP-hard.

Decennia lang hebben computerwetenschappers gewerkt aan het vaststellen van drempels voor verschillende interessante optimalisatieproblemen. Maar sommige vragen onttrekken zich aan dit soort beschrijvingen. Hoewel een algoritme 80% van de beste oplossing kan garanderen, kan het NP-moeilijk zijn om 95% van de beste oplossing te bereiken, waardoor de vraag onbeantwoord blijft waar precies tussen 80% en 95% het probleem in NP-hard gebied terechtkomt.

Het unieke vermoeden van games, of UGC, biedt een manier om onmiddellijk het antwoord te vinden. Het legt een verklaring af die op het eerste gezicht beperkter lijkt: dat het NP-moeilijk is om het verschil te zien tussen een grafiek waarvoor u aan bijna alle kleurbeperkingen kunt voldoen (zeg, meer dan 99%) en een grafiek voor waaraan u nauwelijks kunt voldoen (zeg maar minder dan 1%).

Maar kort nadat de UGC in 2002 was voorgesteld, toonden onderzoekers aan dat als het vermoeden waar is, je gemakkelijk de hardheidsdrempel kunt berekenen voor elk probleem met beperkingstevredenheid. (Dit komt omdat de UGC ook impliceert dat een bekend algoritme de best mogelijke benadering voor al deze problemen bereikt.) "Het was precies de spil voor al deze optimalisatieproblemen," zei O'Donnell.

En dus probeerden theoretische computerwetenschappers de UGC te bewijzen - een taak die er uiteindelijk toe leidde dat sommigen van hen bolvormige kubussen ontdekten.

Moeilijke problemen moeilijker maken

In 2005 werkte O'Donnell bij Microsoft Research. Hij en twee collega's Uriël Feige, nu aan het Weizmann Institute of Science, en Kerel Kindler, nu aan de Hebreeuwse Universiteit van Jeruzalem - samen om de UGC aan te pakken.

Ze hadden een vaag idee van hoe ze verder wilden. Ze zouden beginnen met een vraag over grafieken - een die erg lijkt op de UGC. Het zogenaamde maximale snede ("max-cut") probleem vraagt, wanneer een grafiek wordt gegeven, hoe de hoekpunten ervan in twee sets (of kleuren) moeten worden verdeeld, zodat het aantal randen dat die sets verbindt zo groot mogelijk is. (Je kunt max cut zien als een vraag over de beste manier om een ​​grafiek met twee kleuren te kleuren, zodat zo min mogelijk randen hoekpunten van dezelfde kleur met elkaar verbinden.)

Als de UGC waar is, zou dit impliceren dat, gegeven een willekeurige grafiek, een efficiënt benaderingsalgoritme slechts binnen ongeveer 87% van de werkelijke maximale snede van die grafiek kan komen. Beter doen zou NP-moeilijk zijn.

Feige, Kindler en O'Donnell wilden in plaats daarvan in de tegenovergestelde richting gaan: ze hoopten te laten zien dat max cut moeilijk te benaderen is, en dat vervolgens te gebruiken om de UGC te bewijzen. Hun plan was gebaseerd op de kracht van een techniek die parallelle herhaling wordt genoemd - een slimme strategie die moeilijke problemen moeilijker maakt.

Stel dat u weet dat het NP-moeilijk is om onderscheid te maken tussen een probleem dat u kunt oplossen en een probleem dat u grotendeels kunt oplossen. Parallelle herhaling stelt je in staat daarop voort te bouwen om een ​​veel sterker hardheidsresultaat te laten zien: dat het ook NP-moeilijk is om onderscheid te maken tussen een probleem dat je kunt oplossen en een probleem dat je nauwelijks kunt oplossen. "Dit niet-intuïtieve, diepe fenomeen ... zit tegenwoordig in de ingewanden van veel computerwetenschap, " zei Naor.

Maar er zit een addertje onder het gras. Parallelle herhaling versterkt de moeilijkheid van een probleem niet altijd zoveel als computerwetenschappers willen. Er zijn met name aspecten van het max-cut-probleem die "een grote hoofdpijn veroorzaken voor parallelle herhaling", zei Regev.

Feige, Kindler en O'Donnell concentreerden zich op het laten zien dat parallelle herhaling ondanks de hoofdpijn kon werken. "Dit is echt ingewikkeld om te analyseren," zei Dana Moshkovitz, een theoretisch computerwetenschapper aan de Universiteit van Texas, Austin. 'Maar dit leek verleidelijk dichtbij. Parallelle herhaling leek deze verbinding te [helpen maken] van max cut naar unieke games.

Als warming-up probeerden de onderzoekers parallelle herhaling te begrijpen voor een eenvoudig geval van max cut, wat Moshkovitz 'de domste max cut' noemde. Beschouw een oneven aantal hoekpunten verbonden door randen om een ​​cirkel of "oneven cyclus" te vormen. U wilt elk hoekpunt labelen met een van de twee kleuren, zodat geen enkel paar aangrenzende hoekpunten dezelfde kleur heeft. In dit geval is dat onmogelijk: één rand verbindt altijd hoekpunten met dezelfde kleur. Je moet die rand verwijderen, de oneven cyclus 'doorbreken', om ervoor te zorgen dat je grafiek voldoet aan de beperking van het probleem. Uiteindelijk wilt u het totale aantal randen minimaliseren dat u moet verwijderen om uw grafiek correct te kleuren.

Parallelle herhaling stelt je in staat om een ​​hoog-dimensionale versie van dit probleem te overwegen - een waarin je alle oneven cycli die verschijnen moet doorbreken. Feige, Kindler en O'Donnell moesten laten zien dat als het aantal dimensies erg groot wordt, je een heel groot deel van de randen moet verwijderen om alle oneven cycli te doorbreken. Als dat waar was, zou dat betekenen dat parallelle herhaling de hardheid van dit "domme max-cut"-probleem effectief zou kunnen versterken.

Toen ontdekte het team een ​​merkwaardig toeval: er was een geometrische manier om te interpreteren of parallelle herhaling zou werken zoals ze hoopten. Het geheim lag in het oppervlak van kubisch schuim.

Van citroenen tot limonade

Hun probleem, herschreven in de taal van schuimen, kwam neer op het aantonen dat bolvormige kubussen niet kunnen bestaan ​​- dat het onmogelijk is om hoog-dimensionale ruimte langs het gehele rooster te verdelen in cellen met een oppervlak dat veel kleiner is dan dat van de kubus. (Een groter oppervlak komt overeen met de noodzaak om meer "slechte" randen in de grafiek met oneven cycli te verwijderen, zoals de computerwetenschappers hoopten aan te tonen.)

"We hadden zoiets van, oh, wat een raar geometrieprobleem, maar dat is waarschijnlijk waar, toch?" zei O'Donnell. "Dat hadden we echt nodig om het echte antwoord te zijn." Maar hij, Feige en Kindler konden het niet bewijzen. Dus in 2007, zij een paper gepubliceerd waarin ze uiteenzetten hoe ze van plan waren dit probleem te gebruiken om de UGC aan te vallen.

Al snel werd hun hoop de bodem ingeslagen.

Ran Razo, een theoretisch computerwetenschapper aan Princeton die al verschillende belangrijke resultaten over parallelle herhaling had bewezen, was geïntrigeerd door hun artikel. Hij besloot parallelle herhaling te analyseren voor het oneven cyclusprobleem, deels vanwege het verband met geometrie dat Feige, Kindler en O'Donnell hadden ontdekt.

Raz begon niet met het schuimprobleem, maar viel de computerwetenschappelijke versie van de vraag frontaal aan. Hij liet zien dat je weg kunt komen door veel minder randen te verwijderen om alle oneven cycli in een grafiek te doorbreken. Met andere woorden, parallelle herhaling kan de hardheid van dit max-cut probleem niet voldoende versterken. "De parameters die men krijgt van parallelle herhaling, schieten precies tekort om dit te geven," zei Moshkovitz.

"Ons plan om parallelle herhaling te gebruiken om de hardheid van unieke spellen te laten zien, werkte in het eenvoudigste geval niet eens", zei O'Donnell. "Dit heeft het hele plan doorbroken."

Hoewel het resultaat van Raz teleurstellend was, duidde het ook op het bestaan ​​van bolvormige kubussen: vormen die kunnen worden betegeld n-dimensionale ruimte met een oppervlakte die geschaald wordt in verhouding tot de vierkantswortel van n. "We hadden zoiets van, nou, laten we limonade maken van citroenen en dit teleurstellende technische resultaat over parallelle herhaling en discrete grafieken nemen en er een mooi, interessant resultaat in geometrie van maken," zei O'Donnell.

Hij en Kindler, in samenwerking met de computerwetenschappers Anup Rao en Avi Wigderson, verdiepte zich in het bewijs van Raz totdat ze de technieken ervan goed genoeg hadden geleerd om ze te vertalen naar het schuimprobleem. Dat hebben ze in 2008 laten zien bolvormige kubussen zijn inderdaad mogelijk.

"Het is een leuke manier om over het probleem te redeneren," zei Mark Braverman van Princeton. "Het is mooi."

En het riep vragen op over de geometrische kant van het verhaal. Omdat ze het werk van Raz over parallelle herhaling hadden gebruikt om hun tegelvorm te construeren, eindigden Kindler, O'Donnell, Rao en Wigderson met iets lelijks en Frankenstein-achtigs. De tegel was rommelig en vol inkepingen. In wiskundige termen was het niet convex. Hoewel dit werkte voor hun doeleinden, ontbrak het de bolvormige kubus aan eigenschappen waar wiskundigen de voorkeur aan geven - eigenschappen die een vorm concreter maken, gemakkelijker te definiëren en te bestuderen, en geschikter voor potentiële toepassingen.

"Er is iets heel onbevredigends aan hun constructie," zei Regev. 'Het lijkt op een amoebe. Het ziet er niet uit zoals je zou verwachten, een mooi betegelend lichaam.”

Dat is wat hij en Naor gingen zoeken.

Loskomen van de kooi

Vanaf het begin beseften Naor en Regev dat ze helemaal opnieuw moesten beginnen. "Gedeeltelijk omdat convexe lichamen zo beperkend zijn, had geen van de eerdere technieken enige kans om te werken," zei Dor Minzer, een theoretisch computerwetenschapper aan het Massachusetts Institute of Technology.

In feite was het volkomen aannemelijk dat convexiteit te beperkend zou zijn - dat een convexe bolvormige kubus gewoon niet bestaat.

Maar vorige maand hebben Naor en Regev bewezen dat je kunt partitioneren n-dimensionale ruimte langs gehele coördinaten met een convexe vorm waarvan het oppervlak vrij dicht bij dat van de bol ligt. En ze deden het volledig geometrisch - ze brachten het probleem terug naar zijn wiskundige wortels.

Ze moesten eerst een groot obstakel omzeilen. Het kubusvormige schuimprobleem vereist dat elke tegel wordt gecentreerd op gehele coördinaten. Maar in het rooster met gehele getallen zijn er zeer korte afstanden tussen sommige punten - en die korte afstanden veroorzaken problemen.

Beschouw een punt in het tweedimensionale raster. Het bevindt zich 1 eenheid verwijderd van de dichtstbijzijnde punten in horizontale en verticale richting. Maar in diagonale richting is het dichtstbijzijnde punt $latex sqrt{2}$ eenheden verwijderd — een verschil dat erger wordt in grotere ruimtes. In de n-dimensionaal integer rooster, de dichtstbijzijnde punten zijn nog steeds 1 eenheid verwijderd, maar die "diagonale" punten zijn nu $latex sqrt{n}$ eenheden verwijderd. In bijvoorbeeld 10,000 dimensies betekent dit dat de dichtstbijzijnde "diagonale" buur van een punt 100 eenheden verwijderd is, ook al zijn er 10,000 andere punten (één in elke richting) die slechts 1 eenheid verwijderd zijn.

In andere roosters groeien die twee soorten afstanden in verhouding tot elkaar. Wiskundigen weten al tientallen jaren hoe ze dergelijke roosters moeten betegelen met convexe vormen met een minimaal oppervlak.

Maar in het geheeltallige rooster blijven de kortste afstanden altijd op 1 steken. Dit staat het construeren van een mooie tegel met een optimaal oppervlak in de weg. 'Ze hebben je min of meer in deze kooi gestopt', zei Regev. "Ze maken alles heel strak om je heen."

Dus overwogen Naor en Regev in plaats daarvan een deel van het volledige n-dimensionale ruimte. Ze kozen deze deelruimte zorgvuldig zodat deze nog steeds rijk zou zijn aan gehele punten, maar geen van die punten zou te dicht bij elkaar liggen.

Met andere woorden, de deelruimte waarmee ze eindigden was precies het type dat wiskundigen al wisten hoe ze optimaal moesten betegelen.

Maar dit was slechts het halve werk. Naor en Regev moesten de hele ruimte indelen, niet slechts een deel ervan. Om een n-dimensionale bolvormige kubus, moesten ze hun efficiënte tegel vermenigvuldigen met een tegel uit de resterende ruimte (vergelijkbaar met hoe je een tweedimensionaal vierkant zou vermenigvuldigen met een eendimensionaal lijnsegment om een ​​driedimensionale kubus te krijgen). Hierdoor zou hun constructie terug in de oorspronkelijke ruimte worden getild, maar het zou ook de oppervlakte vergroten.

Het paar moest laten zien dat de tegel uit de resterende ruimte, die niet zo optimaal was, niet teveel toevoegde aan het oppervlak. Toen ze dat eenmaal hadden gedaan, was hun constructie voltooid. (Het oppervlak van hun uiteindelijke vorm was uiteindelijk iets groter dan dat van de niet-convexe bolvormige kubus, maar ze geloven dat het misschien mogelijk is om een ​​convexe tegel te vinden die net zo efficiënt is als zijn niet-convexe tegenhanger.)

"Hun bewijs is compleet anders" dan eerder werk aan bolvormige kubussen, zei de wiskundige Noga Alon. 'En achteraf gezien is het misschien een natuurlijker bewijs. Dit is wat iemand misschien had moeten proberen om mee te beginnen.

"Als dingen anders worden gedaan," voegde Raz eraan toe, "vind je soms interessante aanvullende implicaties."

Hoop opnieuw aangewakkerd

Het is nog niet duidelijk wat die implicaties kunnen zijn, hoewel het werk gebruikmaakt van het potentiële gebruik van integer-roosters in cryptografie en andere toepassingen. Gezien hoe verbonden dit probleem is met andere velden, "zal het waarschijnlijk tot andere dingen leiden", zei Alon.

Op dit moment zien computerwetenschappers geen manier om het convexe resultaat te interpreteren in de taal van parallelle herhaling en de UGC. Maar ze hebben het oorspronkelijke plan om het schuimprobleem te gebruiken om het vermoeden te bewijzen, niet helemaal opgegeven. "Er zijn verschillende manieren waarop je kunt proberen de voor de hand liggende barrières die we tegenkwamen te ondermijnen", zei Kindler.

Braverman en Minzer probeerden een dergelijke manier toen ze herziene schuimen in 2020. In plaats van te eisen dat de tegelvorm convex moet zijn, vroegen ze dat het bepaalde symmetrieën zou gehoorzamen, zodat het er hetzelfde uitziet, ongeacht hoe je de coördinaten omdraait. (In 2D zou een vierkant werken, maar een rechthoek niet; evenmin zouden de hoogdimensionale bolvormige kubussen die tot nu toe zijn beschreven.) Onder deze nieuwe beperking kon het paar laten zien wat Kindler en anderen 15 jaar eerder hadden gehoopt: dat je toch niet veel beter kunt dan de oppervlakte van de kubus.

Dit kwam overeen met een ander soort parallelle herhaling - een die het eenvoudigste geval van max cut zo moeilijk zou maken als nodig was. Hoewel het resultaat enige hoop biedt voor deze onderzoekslijn, is het niet duidelijk of deze versie van parallelle herhaling zal werken voor alle max-cut problemen. 'Het betekent niet dat je klaar bent,' zei Braverman. "Het betekent gewoon dat je weer back in business bent."

"Er is veel potentieel in geometrie," zei Minzer. "Alleen begrijpen we het nog niet goed genoeg."