"A-Team" di matematica dimostra un collegamento fondamentale tra addizioni e insiemi | Rivista Quanti

In un insieme di numeri scelti a caso, l'addizione può diventare selvaggia.

Somma tutte le coppie di questo insieme e ti ritroverai con un nuovo elenco che probabilmente conterrà molti più numeri di quello con cui hai iniziato. Inizia con 10 numeri casuali e questa nuova lista (chiamata somma) avrà circa 50 elementi. Inizia con 100 e il totale sarà probabilmente intorno ai 5,000; 1,000 numeri iniziali casuali compongono un insieme lungo 500,000 numeri.

Ma se il tuo insieme iniziale ha una struttura, l'insieme può finire con meno numeri di questo. Consideriamo un altro insieme di 10 numeri: tutti i numeri pari da 2 a 20. Poiché coppie diverse daranno come somma lo stesso numero (10 + 12 è uguale a 8 + 14 e 6 + 16) l'insieme ha solo 19 numeri, non 50. Questa differenza diventa sempre più profonda man mano che gli insiemi diventano più grandi. Un elenco strutturato di 1,000 numeri potrebbe contenere un insieme di soli 2,000 numeri.

Negli anni '1960, un matematico di nome Gregorio Freimann iniziarono a studiare gli insiemi con piccole somme nel tentativo di sondare il legame tra addizione e struttura degli insiemi, una connessione cruciale che definisce il campo matematico della combinatoria additiva. Freiman fece progressi impressionanti, dimostrando che un insieme con un piccolo sumset deve essere contenuto da un insieme più grande i cui elementi sono distanziati secondo uno schema altamente regolare. Ma poi il campo ristagnava. “La dimostrazione originale di Freiman era straordinariamente difficile da comprendere, al punto che nessuno era assolutamente sicuro che fosse corretta. Quindi non ha avuto l'impatto che avrebbe potuto avere", ha detto Timothy Gowers, matematico al Collège de France e all'Università di Cambridge e medaglia Fields. "Ma allora Imre Ruzsa irruppe sulla scena”.

In una serie di seconda documenti negli anni '1990, Ruzsa ridimostrò il teorema di Freiman con una nuova ed elegante argomentazione. Pochi anni dopo, Katalin Marton, un influente matematico ungherese morto nel 2019, ha modificato la questione di cosa implica una piccola somma sulla struttura dell'insieme originale. Ha sostituito i tipi di elementi che apparivano nell'insieme e il tipo di struttura che i matematici dovrebbero cercare, pensando che ciò avrebbe consentito ai matematici di estrarre ancora più informazioni. La congettura di Marton ha collegamenti con i sistemi di dimostrazione, la teoria dei codici e la crittografia, e occupa un posto elevato nella combinatoria additiva.

La sua congettura "sembra davvero una delle cose più basilari che non abbiamo capito", ha detto Ben Verde, matematico dell'Università di Oxford. "Ha semplicemente sostenuto molte cose a cui tengo".

Green ha unito le forze con Gowers, Le buone maniere di Freddie dell'Università della California, San Diego, e Terence tao, medaglia Fields presso l'Università della California, a Los Angeles, per formare quello che è il matematico e blogger israeliano Gil kalai chiamato un "Una squadra"dei matematici. Hanno dimostrato una versione della congettura in un articolo condiviso il 9 novembre.

Reti Katz, un matematico della Rice University che non è stato coinvolto nel lavoro, descrive la dimostrazione come “meravigliosamente semplice” – e “più o meno completamente inaspettata”.

Tao ha quindi avviato uno sforzo per formalizzare la dimostrazione Piega, un linguaggio di programmazione che aiuta i matematici a verificare i teoremi. In poche settimane, questo sforzo ha avuto successo. Martedì mattina presto del 5 dicembre, annunciò Tao che Lean aveva dimostrato la congettura senza alcun “scusa” – l'affermazione standard che appare quando il computer non riesce a verificare un certo passaggio. Questo è l'uso di più alto profilo di questo tipo strumenti di verifica dal 2021, e segna un punto di svolta nel modo in cui i matematici scrivono dimostrazioni in termini comprensibili a un computer. Se questi strumenti diventassero abbastanza facili da usare per i matematici, potrebbero essere in grado di sostituire il processo di revisione tra pari, spesso lungo e oneroso, ha affermato Gowers.

Gli ingredienti della prova stavano bollendo da decenni. Gowers ha concepito i suoi primi passi all'inizio degli anni 2000. Ma ci sono voluti 20 anni per dimostrare quello che Kalai chiamava “il Santo Graal” del campo.

Il gruppo

Per comprendere la congettura di Marton è utile conoscere il concetto di gruppo, un oggetto matematico costituito da un insieme e da un'operazione. Pensa ai numeri interi – un insieme infinito di numeri – e all’operazione di addizione. Ogni volta che sommi due numeri interi, ottieni un altro numero intero. L'addizione obbedisce anche ad alcune altre regole delle operazioni di gruppo, come l'associatività, che consente di modificare l'ordine delle operazioni: 3 + (5 + 2) = (3 + 5) + 2.

All'interno di un gruppo, a volte puoi trovare insiemi più piccoli che soddisfano tutte le proprietà del gruppo. Ad esempio, se aggiungi due numeri pari, otterrai un altro numero pari. I numeri pari costituiscono un gruppo a sé stante, il che li rende un sottogruppo degli interi. I numeri dispari, al contrario, non sono un sottogruppo. Se sommi due numeri dispari, ottieni un numero pari, non presente nella serie originale. Ma puoi ottenere tutti i numeri dispari semplicemente aggiungendo 1 a ogni numero pari. Un sottogruppo spostato come questo è chiamato coset. Non ha tutte le proprietà di un sottogruppo, ma ne mantiene la struttura in molti modi. Ad esempio, proprio come i numeri pari, i numeri dispari sono tutti equidistanti.

Marton supponeva che se avessi un apparecchio lo chiameremo A composto da elementi di gruppo il cui insieme non è molto più grande di A stesso, allora esiste un sottogruppo: chiamalo G - con una proprietà speciale. Spostare G alcune volte per creare i set, e quei set, presi insieme, conterranno il set originale A. Inoltre, supponeva che il numero di coset non crescesse molto più velocemente della dimensione della somma: riteneva che dovesse essere correlato da un fattore polinomiale, invece che da una crescita esponenziale molto più rapida.

Potrebbe sembrare una curiosità altamente tecnica. Ma poiché si tratta di un test semplice: cosa succede quando aggiungi solo due elementi nell'insieme? — per la struttura generale di un sottogruppo, è molto importante per matematici e informatici. La stessa idea generale emerge quando gli informatici tentano di crittografare i messaggi in modo da poter decodificare solo una parte del messaggio alla volta. Appare anche nelle prove verificabili probabilisticamente, una forma di prova che gli informatici possono verificare controllando solo pochi frammenti isolati di informazione. In ognuno di questi casi, lavori solo con un paio di punti in una struttura - decodificando solo pochi bit da un lungo messaggio o verificando una piccola parte di una dimostrazione complicata - e concludi qualcosa su una struttura più ampia e di livello superiore.

"Puoi far finta che tutto sia un ampio sottoinsieme di un gruppo", ha detto Tom Sanders, un ex studente di Gowers che ora è collega di Green a Oxford, oppure puoi “ottenere tutto ciò che volevi dall'esistenza di molte coincidenze additive. Entrambe queste prospettive sono utili”.

Ruzsa ha pubblicato la congettura di Marton nel 1999, dandole tutto il merito. "È arrivata a questa congettura indipendentemente da me e Freiman, e probabilmente prima di noi", ha detto. "Ecco perché, quando le ho parlato, ho deciso di chiamarla la sua congettura." Tuttavia, i matematici ora la chiamano congettura polinomiale di Freiman-Ruzsa, o PFR.

Zero e uno

I gruppi, come molti oggetti matematici, assumono molte forme diverse. Marton supponeva che la sua congettura fosse vera per tutti i gruppi. Questo deve ancora essere mostrato. Il nuovo articolo lo dimostra per un particolare tipo di gruppo, che prende come elementi elenchi di numeri binari come (0, 1, 1, 1, 0). Poiché i computer funzionano in binario, questo gruppo è cruciale nell'informatica. Ma è stato utile anche nella combinatoria additiva. "È come un'ambientazione giocattolo in cui puoi giocare e provare cose", ha detto Sanders. "L'algebra è molto, molto più bella" che lavorare con i numeri interi, ha aggiunto.

Le liste hanno lunghezze fisse e ogni bit può essere 0 o 1. Li sommate aggiungendo ciascuna voce alla sua controparte in un'altra lista, con la regola che 1 + 1 = 0. Quindi (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). Il PFR è un tentativo di capire come può apparire un insieme se non è proprio un sottogruppo ma ha alcune caratteristiche simili a un gruppo.

Per rendere PFR preciso, immagina di avere una serie di elenchi binari chiamati A. Ora prendi ogni coppia di elementi da A e sommarli. Le somme risultanti costituiscono la somma di A, chiamato A + A. Se gli elementi di A vengono scelti in modo casuale, quindi la maggior parte delle somme sono diverse l'una dall'altra. Se ci sono k elementi in A, ciò significa che ci sarà in giro k²/2 elementi nell'insieme. Quando k è grande - diciamo, 1,000 - k²/2 è molto più grande di k. Ma se A è un sottogruppo, ogni elemento di A + A è in A, intendendo che A + A ha le stesse dimensioni di A stessa.

PFR considera gli insiemi che non sono casuali, ma non sono nemmeno sottogruppi. In questi insiemi, il numero di elementi in A + A è piuttosto piccolo, diciamo 10k, O 100k. "È davvero utile quando la tua nozione di struttura è molto più ricca di una semplice struttura algebrica esatta", ha affermato Shachar Lovett, scienziato informatico presso l'Università della California, San Diego.

Tutti gli insiemi che i matematici conoscevano e che obbedivano a questa proprietà “sono abbastanza vicini ai sottogruppi reali”, ha detto Tao. "L'intuizione è stata quella: non c'erano altri tipi di gruppi falsi in giro." Freiman aveva dimostrato una versione di questa affermazione nel suo lavoro originale. Nel 1999, Ruzsa ha esteso il teorema di Freiman dagli interi all'impostazione delle liste binarie. Lo ha dimostrato che quando il numero di elementi in A + A è un multiplo costante della dimensione di A, A è contenuto in un sottogruppo.

Ma il teorema di Ruzsa richiedeva che il sottogruppo fosse enorme. L'intuizione di Marton fu quella di postulare che, invece di essere contenuti in un gigantesco sottogruppo, A potrebbe essere contenuto in un numero polinomiale di coset di un sottogruppo non più grande dell'insieme originale A.

"Conosco un'idea reale quando vedo un'idea reale"

Verso la fine del millennio, Gowers si imbatté nelle dimostrazioni di Ruzsa del teorema di Freiman mentre studiava un problema diverso sugli insiemi contenenti stringhe di numeri equidistanti. "Avevo bisogno di qualcosa del genere, di ottenere informazioni strutturali da informazioni molto più vaghe su un determinato insieme", ha detto Gowers. "Sono stato molto fortunato che non molto tempo prima Ruzsa abbia prodotto questa prova assolutamente meravigliosa."

Gowers iniziò a elaborare una potenziale dimostrazione della versione polinomiale della congettura. La sua idea era di iniziare con un set A il cui insieme era relativamente piccolo, quindi manipolarlo gradualmente A in un sottogruppo. Se fosse riuscito a dimostrare che il sottogruppo risultante era simile al set originale A, avrebbe potuto facilmente concludere che la congettura era vera. Gowers condivise le sue idee con i colleghi, ma nessuno riuscì a trasformarle in una dimostrazione completa. Sebbene la strategia di Gowers abbia avuto successo in alcuni casi, in altri le manipolazioni hanno avuto successo A più lontano dalla conclusione desiderata della congettura polinomiale di Freiman-Ruzsa.

Alla fine, il campo è andato avanti. Nel 2012, Sanders PFR quasi dimostrato. Ma il numero di sottogruppi spostati di cui aveva bisogno era superiore al livello polinomiale, anche se solo di poco. "Una volta fatto ciò, significava che diventava una cosa meno urgente, ma pur sempre un problema davvero carino per il quale ho una grande passione", ha detto Gowers.

Ma le idee di Gowers sopravvivevano nei ricordi e nei dischi rigidi dei suoi colleghi. "C'è una vera idea lì", ha detto Green, che era stato anche uno studente di Gowers. "Conosco un'idea reale quando vedo un'idea reale." Quest'estate Green, Manners e Tao hanno finalmente liberato le idee di Gowers dal loro purgatorio.

Green, Tao e Manners collaboravano da 37 pagine prima di pensare di tornare alle idee ventenni di Gowers. In un 20 giugno carta, avevano utilizzato con successo un concetto della teoria della probabilità chiamato variabili casuali per sondare la struttura degli insiemi con piccoli insiemi. Effettuando questo passaggio, il gruppo ha potuto manipolare i propri set con maggiore finezza. "Trattare con variabili casuali è in qualche modo molto meno rigido che trattare con insiemi", ha detto Manners. Con una variabile casuale, “posso modificare una delle probabilità di una piccola quantità e questo potrebbe darmi una variabile casuale migliore”.

Usando questa prospettiva probabilistica, Green, Manners e Tao potrebbero passare dal lavorare con il numero di elementi in un insieme alla misurazione dell'informazione contenuta in una variabile casuale, una quantità chiamata entropia. L’entropia non era nuova alla combinatoria additiva. In effetti, Tao aveva tentato per rendere popolare il concetto alla fine degli anni 2000. Ma nessuno aveva ancora provato ad usarlo sulla congettura del polinomio di Freiman-Ruzsa. Green, Manners e Tao scoprirono che era potente. Ma non riuscivano ancora a dimostrare la congettura.

Mentre il gruppo rifletteva sui nuovi risultati, si rese conto di aver finalmente creato un ambiente in cui le idee dormienti di Gowers potevano prosperare. Se misurassero la dimensione di un insieme utilizzando la sua entropia, anziché il numero di elementi, i dettagli tecnici potrebbero funzionare molto meglio. "Ad un certo punto ci siamo resi conto che queste vecchie idee di Tim di 20 anni fa avevano in realtà più probabilità di funzionare rispetto a quelle che stavamo provando", ha detto Tao. “E così abbiamo riportato Tim nel progetto. E poi tutti i pezzi si incastrano sorprendentemente bene”.

Tuttavia, c'erano molti dettagli da capire prima che arrivasse una prova. "Era un po' sciocco che tutti e quattro fossimo incredibilmente impegnati con altre cose", ha detto Manners. "Vuoi pubblicare questo grande risultato e raccontarlo al mondo, ma in realtà devi ancora scrivere i tuoi esami intermedi." Alla fine, il gruppo riuscì a farcela e il 9 novembre pubblicò il suo articolo. Lo hanno dimostrato se A + A non è più grande di k volte la dimensione di A, poi A può essere coperto da non più di circa k¹² spostamenti di un sottogruppo non più grande di A. Si tratta di un numero potenzialmente enorme di turni. Ma è un polinomio, quindi non cresce esponenzialmente più velocemente come k diventa più grande, come se k erano all'esponente.

Pochi giorni dopo, Tao ha cominciato a formalizzare la prova. Ha gestito il progetto di formalizzazione in modo collaborativo, utilizzando il pacchetto di controllo della versione GitHub per coordinare i contributi 25 volontari in tutto il mondo. Hanno usato uno strumento chiamato Cianografia sviluppato da Patrizio Massot, matematico dell'Università Paris-Saclay, per organizzare gli sforzi per tradurre da ciò che Tao detto “L’inglese matematico” nel codice informatico. Il progetto può, tra le altre cose, creare a grafico raffigurante i vari passaggi logici coinvolti nella dimostrazione. Una volta che tutte le bolle furono ricoperte da quella che Tao chiamava una “bella tonalità di verde”, il team aveva finito. Hanno scoperto alcuni errori di battitura molto minori nel giornale, in un servizio online messaggio, Tao ha osservato che "le parti matematicamente più interessanti del progetto erano relativamente semplici da formalizzare, ma sono stati i passaggi tecnici 'ovvi' a richiedere più tempo."

Marton morì pochi anni prima che la sua famosa congettura fosse dimostrata, ma la prova le fa eco il lavoro della vita sull’entropia e sulla teoria dell’informazione. "Tutto funziona molto meglio quando lo fai in questo quadro entropico che nel quadro che stavo cercando di fare", ha detto Gowers. "A me sembra ancora un po' magico."

Quanta sta conducendo una serie di sondaggi per servire meglio il nostro pubblico. Prendi il nostro Sondaggio tra i lettori di matematica e potrai partecipare alla vincita gratuita Quanta Merch.