I matematici completano la missione per costruire "cubi sferici"

Nel IV secolo, il matematico greco Pappo di Alessandria elogiò le api per la loro "previsione geometrica". La struttura esagonale del loro nido d'ape sembrava il modo ottimale per suddividere lo spazio bidimensionale in celle di uguale area e perimetro minimo, consentendo agli insetti di ridurre la quantità di cera necessaria per produrre e di dedicare meno tempo ed energia alla costruzione del loro nido d'ape. alveare.

O così ipotizzarono Pappo e altri. Per millenni, nessuno ha potuto dimostrare che gli esagoni fossero ottimali, fino a quando finalmente, nel 1999, il matematico Thomas Hales ha dimostrato che nessun'altra forma poteva fare di meglio. Oggi i matematici non sanno ancora quali forme possono affiancare tre o più dimensioni con la superficie più piccola possibile.

Questo problema della "schiuma" si è rivelato avere applicazioni ad ampio raggio: per i fisici che studiano il comportamento delle bolle di sapone (o schiume) e i chimici che analizzano la struttura dei cristalli, per i matematici che esplorano le disposizioni di imballaggio delle sfere e gli statistici che sviluppano efficaci tecniche di elaborazione dei dati .

A metà degli anni 2000, una particolare formulazione del problema della schiuma attirò anche l'attenzione degli informatici teorici, che scoprirono, con loro sorpresa, che era profondamente connessa a un importante problema aperto nel loro campo. Sono stati in grado di utilizzare quella connessione per trovare una nuova forma ad alta dimensione di superficie minima.

"Adoro questo avanti e indietro", ha detto Assaf Naor dell'Università di Princeton. “Alcuni vecchi matematici diventano rilevanti per l'informatica; l'informatica ripaga e risolve la questione in matematica. È molto bello quando questo accade.”

Ma a quella forma, sebbene ottimale, mancava qualcosa di importante: una base geometrica. Poiché la sua esistenza era stata dimostrata utilizzando tecniche informatiche, la sua geometria reale era difficile da afferrare. Questo è ciò che Naor, insieme a Oded Regev, un informatico del Courant Institute della New York University, ha deciso di correggersi una prova pubblicata online il mese scorso.

“È una bella conclusione per la storia”, ha detto Regev.

Schiume cubiche

I matematici hanno preso in considerazione altre versioni del problema della schiuma, incluso ciò che accade se ti è consentito suddividere lo spazio solo in base a quello che viene chiamato reticolo intero. In quella versione del problema, prendi una matrice quadrata di punti equidistanti (ciascuno a 1 unità di distanza) e rendi ciascuno di quei punti il ​​centro di una forma. Il problema della schiuma "cubica" chiede quale sarà la superficie minima quando ti verrà richiesto di piastrellare lo spazio in questo modo.

I ricercatori erano inizialmente interessati a imporre questa restrizione per comprendere le proprietà degli spazi topologici chiamati varietà. Ma la domanda ha assunto una vita propria, diventando rilevante nell'analisi dei dati e in altre applicazioni.

È anche interessante dal punto di vista geometrico, perché cambia il significato di "ottimale". In due dimensioni, ad esempio, gli esagoni regolari non possono più affiancare il piano se possono essere spostati solo di quantità intere nelle direzioni orizzontale e verticale. (Devi spostarli di quantità irrazionali in una delle due direzioni.)

I quadrati possono. Ma è il meglio che si può fare? Come il matematico Jaigyoung Choe scoperto nel 1989, la risposta è no. La forma ottimale è invece un esagono schiacciato in una direzione e allungato in un'altra. (Il perimetro di un tale esagono è di circa 3.86 quando la sua area è 1, battendo il perimetro del quadrato di 4.)

Queste differenze potrebbero sembrare banali, ma diventano molto più grandi nelle dimensioni superiori.

Tra tutte le forme di un dato volume, quella che minimizza la superficie è la sfera. COME n, il numero di dimensioni, cresce, la superficie della sfera aumenta in proporzione alla radice quadrata di n.

Ma le sfere non possono affiancare uno spazio senza lasciare dei vuoti. D'altra parte, un ncubo dimensionale del volume 1 can. Il problema è che la sua superficie è 2n, crescendo in proporzione diretta alla sua dimensione. Un cubo di 10,000 dimensioni di volume 1 ha una superficie di 20,000, molto più grande di 400, la superficie approssimativa di una sfera di 10,000 dimensioni.

E così i ricercatori si sono chiesti se potevano trovare un "cubo sferico" - una forma che piastrella nspazio dimensionale, come un cubo, ma la cui superficie cresce lentamente, come quella di una sfera.

Sembrava improbabile. "Se vuoi che la tua bolla riempia esattamente lo spazio e sia centrata su questa griglia cubica, è difficile pensare a cosa useresti tranne che per una bolla cubica", ha detto Ryan O'Donnell, scienziato informatico teorico alla Carnegie Mellon University. "Sembra davvero che il cubo dovrebbe essere il migliore."

Ora sappiamo che non lo è.

La durezza dei problemi difficili

Per decenni, il problema della schiuma cubica è rimasto relativamente inesplorato nelle dimensioni superiori. I primi ricercatori a fare progressi su di esso non provenivano dal regno della geometria ma dall'informatica teorica. Si sono imbattuti in esso per caso, mentre cercavano un modo per dimostrare un'affermazione centrale nel loro campo nota come il congettura di giochi unici. "La congettura dei giochi unici", ha detto Regev, "è ciò che considero attualmente la più grande questione aperta nell'informatica teorica".

Proposto nel 2002 da Subhash Khot, all'epoca uno studente laureato, la congettura postula che se un particolare problema - uno che implica l'assegnazione di colori ai nodi di una rete - non può essere risolto esattamente, allora trovare anche una soluzione approssimativa è molto difficile. Se vera, la congettura consentirebbe ai ricercatori di comprendere la complessità di un vasto assortimento di altri compiti computazionali in un colpo solo.

Gli informatici spesso classificano le attività in base al fatto che possano essere risolte con un algoritmo efficiente o se invece sono "NP-difficili" (nel senso che non possono essere risolte in modo efficiente con l'aumentare delle dimensioni del problema, fintanto che si crede ampiamente ma la congettura non dimostrata sulla complessità computazionale è vera). Ad esempio, il problema del venditore ambulante, che richiede il percorso più breve necessario per visitare una sola volta ogni città in una rete, è NP-difficile. Così sta determinando se un grafico - una raccolta di vertici collegati da bordi - può essere etichettato con al massimo tre colori in modo che due vertici collegati abbiano colori diversi.

Si scopre che è NP-difficile trovare anche una soluzione approssimativa a molti di questi compiti. Supponi di voler etichettare i vertici di un grafico con colori diversi in modo da soddisfare un elenco di vincoli. Se è NP-difficile soddisfare tutti questi vincoli, che ne dici di provare a soddisfarne solo il 90%, o il 75% o il 50%? Al di sotto di una certa soglia, potrebbe essere possibile elaborare un algoritmo efficiente, ma al di sopra di tale soglia il problema diventa NP-difficile.

Per decenni, gli informatici hanno lavorato per fissare soglie per diversi problemi di ottimizzazione di interesse. Ma alcune domande sfuggono a questo tipo di descrizione. Sebbene un algoritmo possa garantire l'80% della soluzione migliore, potrebbe essere NP-difficile ottenere il 95% della soluzione migliore, lasciando irrisolta la questione di dove esattamente tra l'80% e il 95% il problema si sposti nel territorio NP-difficile.

La congettura dei giochi unici, o UGC, offre un modo per individuare immediatamente la risposta. Fa un'affermazione che a prima vista sembra più limitata: che è NP-difficile distinguere tra un grafico per il quale è possibile soddisfare quasi tutto un certo insieme di vincoli di colorazione (diciamo, più del 99%) e un grafico per che puoi soddisfare a malapena (diciamo, meno dell'1%).

Ma poco dopo la proposta dell'UGC nel 2002, i ricercatori hanno dimostrato che se la congettura è vera, è possibile calcolare facilmente la soglia di durezza per qualsiasi problema di soddisfazione dei vincoli. (Questo perché l'UGC implica anche che un algoritmo noto raggiunga la migliore approssimazione possibile per tutti questi problemi.) "Era proprio il fulcro di tutti questi problemi di ottimizzazione", ha detto O'Donnell.

E così gli informatici teorici si sono proposti di dimostrare l'UGC, un compito che alla fine ha portato alcuni di loro a scoprire cubi sferici.

Rendere i problemi difficili più difficili

Nel 2005, O'Donnell lavorava presso Microsoft Research. Lui e due colleghi - Uriel Feige, ora al Weizmann Institute of Science, e Ragazzo Kindler, ora all'Università Ebraica di Gerusalemme, si sono uniti per affrontare l'UGC.

Avevano una vaga idea di come volevano procedere. Inizierebbero con una domanda sui grafici, molto simile all'UGC. Il cosiddetto problema del taglio massimo ("taglio massimo") chiede, quando viene fornito un grafo, come partizionare i suoi vertici in due insiemi (o colori) in modo che il numero di archi che collegano questi insiemi sia il più grande possibile. (Puoi pensare a max cut come a una domanda sul modo migliore per colorare un grafico con due colori, in modo che il minor numero possibile di spigoli colleghi i vertici dello stesso colore.)

Se l'UGC è vero, implicherebbe che, dato un grafico casuale, un algoritmo di approssimazione efficiente può arrivare solo all'interno di circa l'87% del vero taglio massimo di quel grafico. Fare di meglio sarebbe NP-difficile.

Feige, Kindler e O'Donnell volevano invece andare nella direzione opposta: speravano di mostrare che il taglio massimo è difficile da approssimare, e poi usarlo per dimostrare l'UGC. Il loro piano si basava sulla forza di una tecnica chiamata ripetizione parallela, una strategia intelligente che rende più difficili i problemi difficili.

Dì che sai che è NP-difficile distinguere tra un problema che puoi risolvere e uno che puoi risolvere principalmente. La ripetizione parallela ti consente di basarti su questo per mostrare un risultato di durezza molto più forte: che è anche NP-difficile distinguere tra un problema che puoi risolvere e uno che riesci a malapena a risolvere. "Questo fenomeno non intuitivo e profondo... è nelle viscere di molta informatica oggi", ha detto Naor.

Ma c'è un problema. La ripetizione parallela non sempre amplifica la durezza di un problema tanto quanto vogliono gli informatici. In particolare, ci sono aspetti del problema del taglio massimo che "creano un grosso grattacapo per la ripetizione parallela", ha detto Regev.

Feige, Kindler e O'Donnell si sono concentrati sul mostrare che la ripetizione parallela poteva funzionare nonostante i mal di testa. "Questa è una cosa davvero complicata da analizzare", ha detto Dana Moshkovitz, scienziato informatico teorico presso l'Università del Texas, Austin. “Ma questo sembrava allettantemente vicino. La ripetizione parallela sembrava [aiutare a creare] questa connessione dal taglio massimo a giochi unici.

Come riscaldamento, i ricercatori hanno cercato di comprendere la ripetizione parallela per un semplice caso di max cut, quello che Moshkovitz chiamava "il max cut più stupido". Considera un numero dispari di vertici collegati da bordi per formare un cerchio, o "ciclo dispari". Vuoi etichettare ogni vertice con uno dei due colori in modo che nessuna coppia di vertici adiacenti abbia lo stesso colore. In questo caso, è impossibile: un bordo collegherà sempre i vertici dello stesso colore. Devi eliminare quel bordo, "rompendo" il ciclo dispari, per fare in modo che il tuo grafico soddisfi il vincolo del problema. In definitiva, vuoi ridurre al minimo la frazione totale di spigoli che devi eliminare per colorare correttamente il tuo grafico.

La ripetizione parallela ti consente di considerare una versione ad alta dimensione di questo problema, una in cui devi interrompere tutti i cicli dispari che appaiono. Feige, Kindler e O'Donnell dovevano dimostrare che quando il numero di dimensioni diventa molto grande, devi eliminare una frazione molto grande di spigoli per interrompere tutti i cicli dispari. Se ciò fosse vero, significherebbe che la ripetizione parallela potrebbe effettivamente amplificare la durezza di questo problema di "stupido taglio massimo".

Fu allora che il team scoprì una curiosa coincidenza: c'era un modo geometrico per interpretare se la ripetizione parallela avrebbe funzionato come speravano. Il segreto risiedeva nella superficie delle schiume cubiche.

Dai limoni alla limonata

Il loro problema, riscritto nel linguaggio delle schiume, si riduceva a mostrare che i cubi sferici non possono esistere - che è impossibile suddividere lo spazio ad alta dimensione lungo il reticolo intero in celle con un'area superficiale molto più piccola di quella del cubo. (Una superficie più ampia corrisponde alla necessità di eliminare più bordi "cattivi" nel grafico dei cicli dispari, come speravano di mostrare gli scienziati informatici.)

"Eravamo tipo, oh, che strano problema di geometria, ma probabilmente è vero, giusto?" disse O'Donnell. "Avevamo davvero bisogno che fosse la vera risposta." Ma lui, Feige e Kindler non potevano provarlo. Quindi nel 2007, loro pubblicato un documento delineando come hanno pianificato di utilizzare questo problema per aiutare ad attaccare l'UGC.

Abbastanza presto, le loro speranze furono deluse.

Ran Raz, uno scienziato informatico teorico a Princeton che aveva già dimostrato diversi importanti risultati sulla ripetizione parallela, era incuriosito dal loro articolo. Decise di analizzare la ripetizione parallela per il problema dei cicli dispari, in parte a causa della connessione con la geometria che Feige, Kindler e O'Donnell avevano scoperto.

Raz non ha iniziato con il problema della schiuma, ma ha attaccato frontalmente la versione informatica della domanda. Ha dimostrato che puoi farla franca eliminando molti meno spigoli per interrompere tutti i cicli dispari in un grafico. In altre parole, la ripetizione parallela non può amplificare a sufficienza la durezza di questo problema di max-cut. "I parametri che si ottengono esattamente dalla ripetizione parallela, esattamente non sono all'altezza di dare questo", ha detto Moshkovitz.

"Il nostro piano di utilizzare la ripetizione parallela per mostrare la durezza dei giochi unici non ha funzionato nemmeno nel caso più semplice", ha detto O'Donnell. "Questo tipo di ha rotto l'intero piano."

Sebbene deludente, il risultato di Raz ha anche accennato all'esistenza di cubi sferici: forme capaci di piastrellarsi nspazio dimensionale con una superficie scalata in proporzione alla radice quadrata di n. "Eravamo tipo, beh, facciamo la limonata con i limoni e prendiamo questo deludente risultato tecnico sulla ripetizione parallela e sui grafici discreti, e trasformiamolo in un risultato pulito e interessante in geometria", ha detto O'Donnell.

Lui e Kindler, in collaborazione con gli informatici Anup Rao ed Avi Wigderson, studiarono attentamente la dimostrazione di Raz finché non ne impararono le tecniche abbastanza bene da tradurle nel problema della schiuma. Nel 2008, lo hanno dimostrato i cubi sferici sono davvero possibili.

"E 'un bel modo di ragionare sul problema", ha detto Marco Bravermann di Princeton. "È bellissimo."

E ha sollevato domande sul lato geometrico della storia. Poiché avevano utilizzato il lavoro di Raz sulla ripetizione parallela per costruire la loro forma di piastrellatura, Kindler, O'Donnell, Rao e Wigderson sono finiti con qualcosa di brutto e simile a Frankenstein. La piastrella era disordinata e piena di rientranze. In termini matematici, non era convesso. Anche se questo funzionava per i loro scopi, il cubo sferico mancava delle proprietà preferite dai matematici: proprietà che rendono una forma più concreta, più facile da definire e studiare e più adatta a potenziali applicazioni.

"C'è qualcosa di molto insoddisfacente nella loro costruzione", ha detto Regev. «Sembra un'ameba. Non sembra quello che ti aspetteresti, un bel corpo piastrellato.

Questo è ciò che lui e Naor hanno deciso di trovare.

Liberarsi dalla gabbia

Fin dall'inizio, Naor e Regev si sono resi conto che avrebbero dovuto ricominciare da capo. "In parte perché i corpi convessi sono così restrittivi, nessuna delle tecniche precedenti aveva alcuna possibilità di funzionare", ha detto Dor Minzer, scienziato informatico teorico presso il Massachusetts Institute of Technology.

In effetti, era del tutto plausibile che la convessità fosse troppo restrittiva, che un cubo sferico convesso semplicemente non esistesse.

Ma il mese scorso, Naor e Regev hanno dimostrato che si può dividere nspazio dimensionale lungo coordinate intere con una forma convessa la cui superficie è abbastanza vicina a quella della sfera. E lo hanno fatto in modo interamente geometrico, riportando il problema alle sue radici matematiche.

Prima hanno dovuto aggirare un grosso ostacolo. Il problema della schiuma cubica richiede che ogni piastrella sia centrata su coordinate intere. Ma nel reticolo intero ci sono distanze molto brevi tra alcuni punti e quelle brevi distanze causano problemi.

Considera un punto nella griglia bidimensionale. Si trova a 1 unità di distanza dai suoi punti più vicini nelle direzioni orizzontale e verticale. Ma nella direzione diagonale, il punto più vicino è a $latex sqrt{2}$ unità di distanza, una discrepanza che peggiora negli spazi più grandi. Nel nreticolo intero dimensionale, i punti più vicini sono ancora a 1 unità di distanza, ma quei punti "diagonali" ora sono $latex sqrt{n}$ unità di distanza. In, diciamo, 10,000 dimensioni, ciò significa che il vicino "diagonale" più vicino a qualsiasi punto è a 100 unità di distanza anche se ci sono altri 10,000 punti (uno in ciascuna direzione) che distano solo 1 unità.

In altri reticoli, questi due tipi di distanze crescono in proporzione l'uno all'altro. I matematici sanno da decenni come affiancare tali reticoli con forme convesse di superficie minima.

Ma nel reticolo intero, le distanze più brevi saranno sempre bloccate su 1. Questo ostacola la costruzione di una bella tessera di superficie ottimale. "In un certo senso ti hanno messo in questa gabbia", ha detto Regev. "Rendono tutto molto stretto intorno a te."

Quindi Naor e Regev hanno invece considerato una fetta del pieno nspazio dimensionale. Hanno scelto con cura questo sottospazio in modo che fosse ancora ricco di punti interi, ma nessuno di quei punti sarebbe stato troppo vicino tra loro.

In altre parole, il sottospazio a cui sono finiti era proprio il tipo che i matematici sapevano già come tessere in modo ottimale.

Ma questa era solo metà del lavoro. Naor e Regev avevano bisogno di suddividere l'intero spazio, non solo una parte di esso. Per ottenere un ncubo sferico bidimensionale, dovevano moltiplicare la loro tessera efficiente con una tessera dello spazio rimanente (simile a come si potrebbe moltiplicare un quadrato bidimensionale con un segmento di linea unidimensionale per ottenere un cubo tridimensionale). In questo modo la loro costruzione si riporterebbe nello spazio originale, ma ne aumenterebbe anche la superficie.

La coppia ha dovuto dimostrare che la piastrella dello spazio rimanente, che non era ottimale, non aggiungeva troppo alla superficie. Una volta fatto ciò, la loro costruzione era completa. (L'area della superficie della loro forma finale è finita per essere un po' più grande di quella del cubo sferico non convesso, ma credono che potrebbe essere possibile trovare una piastrella convessa altrettanto efficiente della sua controparte non convessa.)

"La loro dimostrazione è completamente diversa" dal precedente lavoro sui cubi sferici, ha detto il matematico Noga Alon. “E in retrospettiva, è forse una prova più naturale. Questo è ciò con cui qualcuno forse avrebbe dovuto provare per cominciare.

"Quando le cose vengono fatte in modo diverso", ha aggiunto Raz, "a volte trovi interessanti implicazioni aggiuntive".

Speranza riaccesa

Non è ancora chiaro quali potrebbero essere queste implicazioni, sebbene il lavoro attinga al potenziale utilizzo di reticoli interi nella crittografia e in altre applicazioni. Dato quanto questo problema sia connesso ad altri campi, "è probabile che porti ad altre cose", ha detto Alon.

Al momento, gli informatici non vedono un modo per interpretare il risultato convesso nel linguaggio della ripetizione parallela e dell'UGC. Ma non hanno rinunciato del tutto al piano originale di utilizzare il problema della schiuma per dimostrare la congettura. "Ci sono vari modi in cui puoi provare a sovvertire le ovvie barriere che abbiamo incontrato", ha detto Kindler.

Braverman e Minzer hanno provato uno di questi modi quando loro schiume rivisitate nel 2020. Invece di richiedere che la forma della piastrellatura fosse convessa, hanno chiesto che obbedisse a determinate simmetrie, in modo che appaia uguale indipendentemente da come si capovolgano le sue coordinate. (In 2D, un quadrato funzionerebbe, ma un rettangolo no; nemmeno i cubi sferici ad alta dimensione descritti fino ad oggi.) Sotto questo nuovo vincolo, la coppia è stata in grado di mostrare ciò che Kindler e altri avevano sperato 15 anni prima: che dopotutto non puoi fare molto meglio della superficie del cubo.

Ciò corrispondeva a un diverso tipo di ripetizione parallela, che avrebbe reso il caso più semplice di taglio massimo duro quanto doveva essere. Sebbene il risultato offra qualche speranza per questa linea di ricerca, non è chiaro se questa versione della ripetizione parallela funzionerà per tutti i problemi di max-cut. "Non significa che hai finito", ha detto Braverman. "Significa solo che sei tornato in affari."

"C'è molto potenziale nella geometria", ha detto Minzer. "È solo che non lo capiamo abbastanza bene."