Matematiker slutför uppdraget för att bygga "sfäriska kuber"

På XNUMX-talet berömde den grekiske matematikern Pappus från Alexandria bin för deras "geometriska förutseende". Den hexagonala strukturen på deras bikaka verkade vara det optimala sättet att dela upp tvådimensionellt utrymme i celler med lika stor yta och minimal omkrets – vilket gör det möjligt för insekterna att skära ner på hur mycket vax de behövde producera, och att lägga mindre tid och energi på att bygga sina bikupa.

Eller så antog Pappus och andra. I årtusenden kunde ingen bevisa att hexagoner var optimala - tills äntligen, 1999, visade matematikern Thomas Hales att ingen annan form kunde göra det bättre. Idag vet matematiker fortfarande inte vilka former som kan belägga tre eller fler dimensioner med minsta möjliga yta.

Detta "skum"-problem har visat sig ha omfattande tillämpningar - för fysiker som studerar beteendet hos såpbubblor (eller skum) och kemister som analyserar strukturen hos kristaller, för matematiker som utforskar sfärförpackningsarrangemang och statistiker som utvecklar effektiva databehandlingstekniker .

I mitten av 2000-talet fångade en speciell formulering av skumproblemet även teoretiska datavetare, som till sin förvåning upptäckte att det var djupt kopplat till ett viktigt öppet problem inom deras område. De kunde använda den kopplingen för att hitta en ny högdimensionell form med minimal yta.

"Jag älskar det här fram och tillbaka," sa Assaf Naor från Princeton University. ”En del gammal matematik blir relevant för datavetenskap; datavetenskap betalar tillbaka och löser frågan i matematik. Det är väldigt skönt när det här händer.”

Men den formen, även om den var optimal, saknade något viktigt: en geometrisk grund. Eftersom dess existens hade bevisats med hjälp av tekniker från datavetenskap var dess faktiska geometri svår att förstå. Det är vad Naor, tillsammans med Oded Regev, en datavetare vid Courant Institute vid New York University, tänkte korrigera in ett bevis som lades ut online förra månaden.

"Det är ett mycket trevligt slut på historien," sa Regev.

Kubiska skum

Matematiker har övervägt andra versioner av skumproblemet - inklusive vad som händer om du bara får dela upp utrymmet enligt det som kallas heltalsgittret. I den versionen av problemet tar du en kvadratisk grupp med jämnt fördelade punkter (med 1 enhet från varandra) och gör var och en av dessa punkter till mitten av en form. Det "kubiska" skumproblemet frågar vad den minimala ytan kommer att vara när du måste kakla utrymme på detta sätt.

Forskare var från början intresserade av att införa denna begränsning för att förstå egenskaperna hos topologiska utrymmen som kallas grenrör. Men frågan fick sitt eget liv och blev relevant i dataanalys och andra tillämpningar.

Det är också geometriskt intressant, eftersom det ändrar vad "optimal" kan betyda. I två dimensioner, till exempel, kan vanliga hexagoner inte längre belägga planet om de bara kan förskjutas med heltalsbelopp i horisontell och vertikal riktning. (Du måste flytta dem med irrationella mängder i en av de två riktningarna.)

Rutor kan. Men är det det bästa som kan göras? Som matematiker Jaigyoung Choe upptäcktes 1989 är svaret nej. Den optimala formen är istället en hexagon som har klämts åt ena hållet och förlängts åt en annan. (Omkretsen av en sådan hexagon är ungefär 3.86 när dess area är 1 - vilket slår ut kvadratens omkrets på 4.)

Dessa skillnader kan verka triviala, men de blir mycket större i högre dimensioner.

Bland alla former av en given volym är den som minimerar ytan sfären. Som n, antalet dimensioner, växer, sfärens yta ökar i proportion till kvadratroten av n.

Men sfärer kan inte kakla ett utrymme utan att lämna luckor. Å andra sidan, en n-dimensionell kub med volym 1 burk. Haken är att dess yta är 2n, växer i direkt proportion till dess dimension. En 10,000 1-dimensionell kub med volym 20,000 har en yta på 400 10,000 - mycket större än XNUMX, den ungefärliga ytan av en XNUMX XNUMX-dimensionell sfär.

Och så undrade forskare om de kunde hitta en "sfärisk kub" - en form som kakel n-dimensionellt utrymme, som en kub, men vars yta växer långsamt, som en klots.

Det verkade osannolikt. "Om du vill att din bubbla exakt ska fylla upp utrymmet och vara centrerad på detta kubiska rutnät, är det svårt att tänka på vad du skulle använda förutom en kubisk bubbla," sa Ryan O'Donnell, en teoretisk datavetare vid Carnegie Mellon University. "Det verkar verkligen som att kuben borde vara den bästa."

Vi vet nu att det inte är det.

Hårdheten hos hårda problem

I decennier gick problemet med kubiskt skum relativt outforskat i högre dimensioner. De första forskarna som gjorde framsteg på det kom inte från geometrins område utan från teoretisk datavetenskap. De kom över det av en slump, medan de letade efter ett sätt att bevisa ett centralt uttalande inom sitt område som kallas unika spel gissningar. "Den unika spelförmodan," sa Regev, "är vad jag för närvarande ser som den största öppna frågan inom teoretisk datavetenskap."

Föreslog 2002 av Subhash Khot, en doktorand vid den tiden, antyder gissningen att om ett visst problem - ett som involverar att tilldela färger till noderna i ett nätverk - inte kan lösas exakt, så är det mycket svårt att hitta ens en ungefärlig lösning. Om det är sant, skulle gissningen göra det möjligt för forskare att förstå komplexiteten i ett stort urval av andra beräkningsuppgifter i ett slag.

Datavetare klassificerar ofta uppgifter baserat på om de kan lösas med en effektiv algoritm, eller om de istället är "NP-hårda" (vilket innebär att de inte kan lösas effektivt när problemets storlek växer, så länge som en allmänt trott men obevisade gissningar om beräkningskomplexitet är sanna). Till exempel är problemet med resande säljare, som kräver den kortaste vägen som behövs för att besöka varje stad i ett nätverk endast en gång, NP-svårt. Så är att bestämma om en graf - en samling av hörn sammankopplade med kanter - kan märkas med högst tre färger så att två sammankopplade hörn har olika färger.

Det visar sig att det är NP-svårt att hitta ens en ungefärlig lösning på många av dessa uppgifter. Säg att du vill märka toppen av en graf med olika färger på ett sätt som uppfyller en lista med begränsningar. Om det är NP-svårt att uppfylla alla dessa begränsningar, vad sägs om att försöka uppfylla bara 90 % av dem, eller 75 % eller 50 %? Under någon tröskel kan det vara möjligt att komma på en effektiv algoritm, men över den tröskeln blir problemet NP-svårt.

I decennier har datavetare arbetat med att spika ner trösklar för olika optimeringsproblem av intresse. Men vissa frågor undviker den här typen av beskrivningar. Även om en algoritm kan garantera 80 % av den bästa lösningen, kan det vara NP-svårt att uppnå 95 % av den bästa lösningen, vilket gör frågan om exakt var mellan 80 % och 95 % problemet tippar in i NP-hårt territorium.

Den unika spelförmodan, eller UGC, erbjuder ett sätt att omedelbart hitta svaret. Den gör ett uttalande som till en början verkar mer begränsat: att det är NP-svårt att se skillnaden mellan en graf för vilken du kan uppfylla nästan alla av en viss uppsättning färgbegränsningar (säg mer än 99 %) och en graf för som du kan tillfredsställa knappt någon (säg mindre än 1%).

Men kort efter att UGC föreslogs 2002, visade forskare att om gissningarna är sanna kan du enkelt beräkna hårdhetströskeln för alla problem med begränsningstillfredsställelse. (Detta beror på att UGC också innebär att en känd algoritm uppnår bästa möjliga approximation för alla dessa problem.) "Det var just nyckeln för alla dessa optimeringsproblem," sa O'Donnell.

Och så teoretiska datavetare satte sig för att bevisa UGC - en uppgift som i slutändan ledde till att några av dem upptäckte sfäriska kuber.

Att göra svåra problem svårare

2005 arbetade O'Donnell på Microsoft Research. Han och två kollegor - Uriel Feige, nu vid Weizmann Institute of Science, och Guy Kindler, nu vid hebreiska universitetet i Jerusalem — gick ihop för att ta itu med UGC.

De hade en vag uppfattning om hur de ville gå vidare. De skulle börja med en fråga om grafer - en som är väldigt lik UGC. Det så kallade maximum cut ("max-cut")-problemet frågar, när det ges en graf, hur man delar upp dess hörn i två uppsättningar (eller färger) så att antalet kanter som förbinder dessa uppsättningar är så stort som möjligt. (Du kan tänka på max cut som en fråga om det bästa sättet att färglägga en graf med två färger, så att så få kanter som möjligt kopplar samman hörn av samma färg.)

Om UGC är sant, skulle det innebära att, givet någon slumpmässig graf, en effektiv approximationsalgoritm endast kan komma inom cirka 87 % av det verkliga maxsnittet för den grafen. Att göra bättre skulle vara NP-svårt.

Feige, Kindler och O'Donnell ville istället gå i motsatt riktning: de hoppades visa att max cut är svårt att uppskatta, och sedan använda det för att bevisa UGC. Deras plan förlitade sig på styrkan hos en teknik som kallas parallell upprepning - en smart strategi som gör svåra problem svårare.

Säg att du vet att det är NP-svårt att skilja mellan ett problem du kan lösa och ett du mest kan lösa. Parallell upprepning gör att du kan bygga vidare på det för att visa ett mycket starkare hårdhetsresultat: att det också är NP-svårt att skilja mellan ett problem du kan lösa och ett du knappt kan lösa alls. "Detta icke-intuitiva, djupa fenomen ... finns i magen av mycket datavetenskap idag," sa Naor.

Men det finns en hake. Parallell upprepning förstärker inte alltid ett problems hårdhet så mycket som datavetare vill ha det. I synnerhet finns det aspekter av max-cut-problemet som "skapar en stor huvudvärk för parallell upprepning", sa Regev.

Feige, Kindler och O'Donnell fokuserade på att visa att parallell upprepning kunde fungera trots huvudvärken. "Det här är en riktigt komplicerad sak att analysera," sa Dana Moshkovitz, en teoretisk datavetare vid University of Texas, Austin. "Men det här verkade lockande nära. Parallell upprepning verkade som om det skulle [hjälpa till] denna koppling från max cut till unika spel."

Som en uppvärmning försökte forskarna förstå parallell upprepning för ett enkelt fall av max cut, vad Moshkovitz kallade "det dummaste max cut." Betrakta ett udda antal hörn förbundna med kanter för att bilda en cirkel, eller "udda cykel". Du vill märka varje vertex med en av två färger så att inget par intilliggande hörn har samma färg. I det här fallet är det omöjligt: ​​En kant kommer alltid att ansluta hörn av samma färg. Du måste ta bort den kanten, "bryta" den udda cykeln, för att få din graf att uppfylla problemets begränsning. I slutändan vill du minimera den totala bråkdelen av kanter du behöver ta bort för att färga grafen korrekt.

Parallell upprepning låter dig överväga en högdimensionell version av detta problem - en där du måste bryta alla udda cykler som dyker upp. Feige, Kindler och O'Donnell behövde visa att när antalet dimensioner blir mycket stort måste du ta bort en mycket stor del av kanterna för att bryta alla udda cykler. Om det var sant skulle det betyda att parallell upprepning effektivt skulle kunna förstärka hårdheten i detta "dumma max-cut"-problem.

Det var då teamet upptäckte ett märkligt sammanträffande: Det fanns ett geometriskt sätt att tolka om parallell upprepning skulle fungera som de hoppades. Hemligheten låg i ytan av kubiska skum.

Från citroner till lemonad

Deras problem, omskrivet på skumspråket, gick ut på att visa att sfäriska kuber inte kan existera - att det är omöjligt att dela upp högdimensionellt utrymme längs heltalsgittret i celler med ytarea mycket mindre än kubens. (En större yta motsvarar att behöva ta bort fler "dåliga" kanter i grafen för udda cykler, som datavetarna hoppades visa.)

"Vi var som, åh, vilket konstigt geometriproblem, men det är förmodligen sant, eller hur?" sa O'Donnell. "Vi behövde verkligen det för att vara det sanna svaret." Men han, Feige och Kindler kunde inte bevisa det. Så 2007 gjorde de publicerade ett papper beskriver hur de planerade att använda detta problem för att hjälpa till att attackera UGC.

Snart nog grusades deras förhoppningar.

Sprang Raz, en teoretisk datavetare vid Princeton som redan hade bevisat flera viktiga resultat om parallell upprepning, blev fascinerad av deras uppsats. Han bestämde sig för att analysera parallell upprepning för problemet med udda cykel, delvis på grund av kopplingen till geometri som Feige, Kindler och O'Donnell hade upptäckt.

Raz började inte med skumproblemet utan attackerade den datavetenskapliga versionen av frågan direkt. Han visade att man kan komma undan med att ta bort mycket färre kanter för att bryta alla udda cykler i en graf. Med andra ord kan parallell upprepning inte tillräckligt förstärka hårdheten i detta max-cut-problem. "De parametrar som man får från parallell upprepning exakt, saknar exakt det här," sa Moshkovitz.

"Vår plan att använda parallell upprepning för att visa hårdheten i unika spel fungerade inte ens i det enklaste fallet," sa O'Donnell. "Det här bröt liksom hela planen."

Även om det var en besvikelse, antydde Raz resultat också förekomsten av sfäriska kuber: former som kan kaklas n-dimensionellt utrymme med en yta som skalas i proportion till kvadratroten av n. "Vi tänkte, ja, låt oss göra lemonad av citroner och ta det här nedslående tekniska resultatet om parallellupprepning och diskreta grafer och förvandla det till ett snyggt, intressant resultat i geometri," sa O'Donnell.

Han och Kindler, i samarbete med datavetarna Anup Rao och Avi Wigderson, granskade Raz bevis tills de hade lärt sig dess tekniker tillräckligt bra för att översätta dem till skumproblemet. 2008 visade de det sfäriska kuber är verkligen möjliga.

"Det är ett bra sätt att resonera kring problemet," sa Mark Braverman av Princeton. "Det är vackert."

Och det väckte frågor om geometrisidan av historien. Eftersom de hade använt Raz arbete med parallell upprepning för att konstruera sin kakelform, slutade Kindler, O'Donnell, Rao och Wigderson med något fult och Frankenstein-liknande. Kakelplattan var rörig och full av fördjupningar. I matematiska termer var det inte konvext. Även om detta fungerade för deras syften, saknade den sfäriska kuben egenskaper som matematiker föredrar - egenskaper som gör en form mer konkret, lättare att definiera och studera och mer lämpad för potentiella tillämpningar.

"Det är något mycket otillfredsställande med deras konstruktion," sa Regev. "Det ser ut som en amöba. Det ser inte ut som vad du kan förvänta dig, en snygg kakelkropp.”

Det var vad han och Naor försökte hitta.

Att bryta sig loss från buren

Redan från början insåg Naor och Regev att de måste börja om från början. "Delvis eftersom konvexa kroppar är så restriktiva, hade ingen av de tidigare teknikerna någon chans att fungera", sa Dor Minzer, en teoretisk datavetare vid Massachusetts Institute of Technology.

Faktum är att det var helt troligt att konvexitet skulle vara för restriktiv - att en konvex sfärisk kub helt enkelt inte existerar.

Men förra månaden bevisade Naor och Regev att man kan partitionera n-dimensionellt utrymme längs heltalskoordinater med en konvex form vars yta är ganska nära sfärens. Och de gjorde det helt geometriskt - återförde problemet till dess matematiska rötter.

De fick först ta sig runt ett stort hinder. Problemet med kubiskt skum kräver att varje bricka centreras på heltalskoordinater. Men i heltalsgittret är det väldigt korta avstånd mellan vissa punkter - och de korta avstånden orsakar problem.

Betrakta en punkt i det tvådimensionella rutnätet. Den är placerad 1 enhet bort från dess närmaste punkter i horisontell och vertikal riktning. Men i diagonal riktning är den närmaste punkten $latex sqrt{2}$ enheter bort – en avvikelse som blir värre i större utrymmen. I den n-dimensionellt heltalsgitter, de närmaste punkterna är fortfarande 1 enhet bort, men de "diagonala" punkterna är nu $latex sqrt{n}$ enheter bort. I säg 10,000 100 dimensioner betyder detta att den närmaste "diagonala" grannen till någon punkt är 10,000 enheter bort även om det finns 1 XNUMX andra punkter (en i varje riktning) som bara är XNUMX enhet bort.

I andra galler växer dessa två typer av avstånd i proportion till varandra. Matematiker har i årtionden vetat hur man kakel sådana galler med konvexa former med minimal yta.

Men i heltalsgittret kommer de kortaste avstånden alltid att sitta fast vid 1. Detta kommer i vägen för att konstruera en snygg platta med optimal yta. "De sätter dig typ i den här buren," sa Regev. "De gör allt väldigt tätt runt dig."

Så Naor och Regev ansåg istället en del av det fulla n-dimensionellt utrymme. De valde noggrant detta delutrymme så att det fortfarande skulle vara rikt på heltalspunkter, men ingen av dessa punkter skulle vara för nära varandra.

Med andra ord, underrummet de hamnade i var just den typ som matematiker redan visste hur man kaklade optimalt.

Men detta var bara halva arbetet. Naor och Regev behövde dela upp hela utrymmet, inte bara en bit av det. Att få en n-dimensionell sfärisk kub, var de tvungna att multiplicera sin effektiva bricka med en bricka från det återstående utrymmet (liknande hur du kan multiplicera en tvådimensionell kvadrat med ett endimensionellt linjesegment för att få en tredimensionell kub). Att göra det skulle lyfta deras konstruktion tillbaka till det ursprungliga utrymmet, men det skulle också öka dess yta.

Paret fick visa att plattan från det återstående utrymmet, som inte var lika optimalt, inte tillförde ytan för mycket. När de väl gjorde det var deras konstruktion klar. (Deras slutliga forms yta blev lite större än den för den icke-konvexa sfäriska kuben, men de tror att det kan vara möjligt att hitta en konvex platta som är lika effektiv som sin icke-konvexa motsvarighet.)

"Deras bevis är helt annorlunda" från tidigare arbete med sfäriska kuber, sa matematikern Noga Alon. ”Och i efterhand är det kanske ett mer naturligt bevis. Det här är vad någon kanske borde ha försökt till att börja med.”

"När saker görs annorlunda," tillade Raz, "ibland hittar man intressanta ytterligare implikationer."

Hoppet väcktes igen

Det är ännu inte klart vad dessa implikationer kan vara - även om arbetet utnyttjar den potentiella användningen av heltalsgitter i kryptografi och andra applikationer. Med tanke på hur kopplat detta problem är till andra områden, "kommer det sannolikt att leda till andra saker", sa Alon.

För tillfället ser datavetare inte ett sätt att tolka det konvexa resultatet i språket parallellupprepning och UGC. Men de har inte helt gett upp den ursprungliga planen att använda skumproblemet för att bevisa gissningen. "Det finns olika sätt du kan försöka undergräva de uppenbara barriärerna som vi stött på," sa Kindler.

Braverman och Minzer försökte ett sådant sätt när de återbesökt skum 2020. Istället för att kräva att kakelformen skulle vara konvex bad de att den skulle följa vissa symmetrier, så att den ser likadan ut oavsett hur du vänder på dess koordinater. (I 2D skulle en kvadrat fungera, men en rektangel skulle inte fungera; inte heller de högdimensionella sfäriska kuberna som beskrivits hittills.) Under denna nya begränsning kunde paret visa vad Kindler och andra hade hoppats på 15 år tidigare: att man trots allt inte kan göra mycket bättre än kubens yta.

Detta motsvarade en annan typ av parallell upprepning - en som skulle göra det enklaste fallet med max cut så hårt som det behövde vara. Även om resultatet ger ett visst hopp för denna forskningslinje, är det inte klart om denna version av parallell upprepning kommer att fungera för alla max-cut-problem. "Det betyder inte att du är klar," sa Braverman. "Det betyder bara att du är tillbaka i verksamheten."

"Det finns mycket potential i geometri," sa Minzer. "Det är bara det att vi inte förstår det tillräckligt bra."