Congettura di geometria di 31 anni dimostrata con Microsoft Research

Dal 1995, una domanda di geometria ad alta dimensione separa i matematici da una risposta netta su come i cammini aleatori esplorano una distribuzione. La congettura di Kannan–Lovász–Simonovits chiede se, per un'ampia classe di distribuzioni di probabilità, il miglior taglio piatto sia quasi altrettanto efficace del miglior taglio di forma qualsiasi. Microsoft Research annuncia ora che due ricercatori, tra cui Xinzhi Zhang del suo gruppo di apprendimento automatico e ottimizzazione, l'hanno dimostrata: la differenza tra i due tipi di taglio resta sotto un limite fisso, qualunque sia il numero di dimensioni.

Un taglio piatto è una sezione di una figura fatta con una lama piatta, cioè un iperpiano in termini matematici. Per le distribuzioni log-concave, un'ampia famiglia di distribuzioni di probabilità, la congettura prevede che il miglior taglio piatto differisca dal miglior taglio di forma qualsiasi di non più di una costante universale, qualunque sia il numero di dimensioni. La geometria di questi tagli determina la velocità con cui un cammino aleatorio può esplorare la distribuzione, ed è per questo che il problema occupa il centro del campionamento ad alta dimensione, la famiglia di metodi che estraggono punti casuali da distribuzioni complesse.

Il problema era riconosciuto come centrale molto prima di cadere. Il Mathematical Sciences Research Institute lo ha definito «un problema aperto centrale nella geometria convessa ad alta dimensione» nel suo rapporto annuale 2017-18, e il Simons Institute lo ha descritto come «uno dei problemi aperti più importanti della geometria convessa». Il miglior risultato noto, stabilito nel luglio 2026, faceva crescere lentamente il limite al crescere delle dimensioni. Gli autori l'hanno prima affinato: nella versione pubblicata il 1° ottobre 2026, la dipendenza dalla dimensione si era ridotta al logaritmo iterato, una funzione che cresce molto lentamente ma che continua a crescere, sicché la congettura non era ancora risolta.

Gli ultimi passi sono venuti da un flusso di lavoro insolito. Lavorando con agenti di IA in un processo strutturato e guidato dall'uomo, gli autori hanno esplorato oltre 100 approcci candidati, molti dei quali comportavano lunghi calcoli con tensori di ordine superiore. Uno di essi ha prodotto un nuovo criterio che è diventato il fondamento della dimostrazione. La mossa finale è stata ripetere l'intero perfezionamento ricorsivo invece di applicarlo una sola volta, un'idea ispirata al lavoro precedente degli autori sugli algoritmi veloci per la programmazione lineare. Hanno mostrato che i piccoli errori introdotti a ogni fase si riducono abbastanza rapidamente da fare in modo che il loro totale resti limitato da una costante universale, indipendente dalla dimensione. La versione pubblicata il 4 ottobre 2026 ha completato la dimostrazione. Secondo gli autori, gli strumenti di IA hanno aiutato a esplorare, dedurre e verificare, mentre i ricercatori hanno scelto la direzione, selezionato le idee e verificato l'argomentazione.

L'affermazione ha suscitato lavori paralleli. Lo stesso giorno in cui il team di Microsoft ha pubblicato la dimostrazione completa, un gruppo separato di esperti di primo piano ha pubblicato una dimostrazione completa sviluppata in parallelo, definendo la prima versione di Microsoft «il passo cruciale della dimostrazione». Una terza dimostrazione, pubblicata quel giorno, si basa su un'idea strettamente correlata. Il post di Microsoft riferisce inoltre che diversi ricercatori indipendenti hanno convalidato il lavoro e che è seguita una verifica formale controllata da macchina. Non dice se l'articolo sia già stato accettato da una rivista.

Per i ricercatori che costruiscono e analizzano metodi di campionamento e ottimizzazione, il cambiamento riguarda le garanzie: un limite che non cresce più con la dimensione sostituisce uno che cresceva, per quanto lentamente. Il post presenta questo risultato come la rimozione di un importante ostacolo teorico alla comprensione dell'efficienza degli algoritmi randomizzati usati in tutta la scienza e l'informatica. Non fissa alcuna data per un effetto pratico e non dice se il risultato si tradurrà in strumenti più veloci.