Introduzione
A metà ottobre, Justin Gilmer volato dalla California a New York per partecipare al matrimonio di un amico. Mentre si trovava sulla costa orientale fece visita al suo ex consigliere, Michael Sak, un matematico della Rutgers University, dove Gilmer aveva conseguito il dottorato sette anni prima.
Saks e Gilmer si sono incontrati a pranzo, ma non hanno parlato di matematica. In effetti, Gilmer non aveva pensato seriamente alla matematica da quando finì alla Rutgers nel 2015. Fu allora che decise che non voleva una carriera nel mondo accademico e iniziò invece a insegnare da solo a programmare. Mentre lui e Saks mangiavano, Gilmer ha raccontato al suo vecchio mentore del suo lavoro in Google, dove si occupa di machine learning e intelligenza artificiale.
C'era il sole il giorno in cui Gilmer ha visitato Rutgers. Mentre camminava, si ricordò di come nel 2013 avesse trascorso la maggior parte dell'anno percorrendo gli stessi sentieri del campus, pensando a un problema chiamato congettura del sindacato chiuso. Era stata una fissazione, anche se infruttuosa: nonostante tutti i suoi sforzi, Gilmer era riuscito solo a insegnare a se stesso perché il problema apparentemente semplice sugli insiemi di numeri fosse così difficile da risolvere.
“Penso che molte persone riflettano sul problema fino a quando non si convincono di aver capito perché è difficile. Probabilmente ci ho passato più tempo della maggior parte delle persone", ha detto Gilmer.
Dopo la sua visita di ottobre, accadde qualcosa di inaspettato: ebbe una nuova idea. Gilmer iniziò a pensare a modi per applicare le tecniche della teoria dell'informazione per risolvere la congettura del sindacato chiuso. Ha perseguito l'idea per un mese, aspettandosi ogni volta che fallisse. Ma invece, la strada per una prova continuava ad aprirsi. Infine, il 16 novembre lui ha pubblicato un risultato unico nel suo genere questo porta i matematici in gran parte sulla strada per dimostrare la congettura completa.
Il documento ha dato il via a una raffica di lavoro di follow-up. I matematici dell'Università di Oxford, del Massachusetts Institute of Technology e dell'Institute for Advanced Study, tra le altre istituzioni, si sono rapidamente basati sui nuovi metodi di Gilmer. Ma prima di farlo, hanno posto una loro domanda: chi è questo ragazzo?
Mezzo pieno
La congettura a unione chiusa riguarda insiemi di numeri chiamati insiemi, come {1, 2} e {2, 3, 4}. Puoi eseguire operazioni sugli insiemi, inclusa la loro unione, il che significa combinarli. Ad esempio, l'unione di {1, 2} e {2, 3, 4} è {1, 2, 3, 4}.
Una raccolta, o famiglia, di insiemi è considerata "unione chiusa" se l'unione di due insiemi qualsiasi nella famiglia è uguale a qualsiasi insieme esistente nella famiglia. Ad esempio, considera questa famiglia di quattro set:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Combina qualsiasi coppia e ottieni un set che è già in famiglia, chiudendo l'unione familiare.
I matematici hanno discusso delle versioni della congettura a sindacato chiuso fin dagli anni '1960, ma ha ricevuto la sua prima dichiarazione formale nel 1979, in un articolo di Peter Frankl, un matematico ungherese emigrato in Giappone negli anni '1980 e che annovera le esibizioni di strada tra le sue attività.
Frankl ha ipotizzato che se una famiglia di insiemi è chiusa dall'unione, deve avere almeno un elemento (o numero) che appare in almeno metà degli insiemi. Era una soglia naturale per due motivi.
In primo luogo, sono facilmente disponibili esempi di famiglie con unione chiusa in cui tutti gli elementi compaiono esattamente nel 50% degli insiemi. Come tutti i diversi set che puoi creare dai numeri da 1 a 10, per esempio. Ci sono 1,024 di questi insiemi, che formano una famiglia chiusa dall'unione, e ciascuno dei 10 elementi appare in 512 di essi. E in secondo luogo, all'epoca in cui Frankl fece la congettura nessuno aveva mai prodotto un esempio di famiglia unificata chiusa in cui la congettura non reggesse.
Quindi il 50% sembrava la previsione giusta.
Ciò non significava che fosse facile da dimostrare. Negli anni trascorsi dall'articolo di Frankl, ci sono stati pochi risultati. Prima del lavoro di Gilmer, quei documenti riuscivano solo a stabilire soglie che variavano con il numero di set nella famiglia (invece di essere la stessa soglia del 50% per famiglie di set di tutte le dimensioni).
"Sembra che dovrebbe essere facile, ed è simile a molti problemi facili, ma ha resistito agli attacchi", ha detto Will Sawin della Columbia University.
La mancanza di progressi rifletteva sia la natura delicata del problema sia il fatto che molti matematici preferivano non pensarci; temevano di perdere anni della loro carriera inseguendo un problema affascinante e impossibile da risolvere. Gilmer ricorda un giorno del 2013 in cui andò nell'ufficio di Saks e sollevò l'ipotesi della chiusura del sindacato. Il suo consigliere - che in passato aveva affrontato lui stesso il problema - lo ha quasi buttato fuori dalla stanza.
"Mike ha detto: 'Justin, mi farai pensare di nuovo a questo problema e non voglio farlo'", ha detto Gilmer.
Una visione dell'incertezza
Dopo la sua visita alla Rutgers, Gilmer si rigirò il problema nella mente, cercando di capire perché fosse così difficile. Si è spinto con un fatto fondamentale: se hai una famiglia di 100 set, ci sono 4,950 modi diversi di sceglierne due e accettare la loro unione. Poi si è chiesto: com'è possibile che 4,950 diverse unioni si ricolleghino a soli 100 insiemi se nessun elemento appare in quelle unioni con almeno una certa frequenza?
Anche a quel punto era sulla buona strada per una prova, anche se ancora non lo sapeva. Le tecniche della teoria dell'informazione, che fornisce un modo rigoroso di pensare a cosa aspettarsi quando si estraggono un paio di oggetti a caso, lo porterebbero lì.
La teoria dell'informazione si sviluppò nella prima metà del 20° secolo, il più famoso con l'articolo di Claude Shannon del 1948, "Una teoria matematica di comunicazione.” Il documento ha fornito un modo preciso per calcolare la quantità di informazioni necessarie per inviare un messaggio, in base alla quantità di incertezza su cosa avrebbe detto esattamente il messaggio. Questo link - tra informazione e incertezza - è stata la straordinaria e fondamentale intuizione di Shannon.
Per fare un esempio di giocattolo, immagina di lanciare una moneta cinque volte e di inviarti la sequenza risultante. Se si tratta di una moneta normale, sono necessari cinque bit di informazioni per essere trasmessi. Ma se è una moneta carica - diciamo, il 99% di probabilità che esca testa - ci vuole molto meno. Ad esempio, potremmo concordare in anticipo che ti invierò un 1 (un singolo bit di informazione) se la moneta caricata esce testa tutte e cinque le volte, cosa che è molto probabile che accada. C'è più sorpresa nel risultato di un lancio di una moneta leale che in uno distorto, e quindi più informazioni.
Lo stesso ragionamento si applica alle informazioni contenute nelle serie di numeri. Se ho una famiglia di insiemi a unione chiusa, diciamo i 1,024 insiemi composti dai numeri da 1 a 10, potrei scegliere due insiemi a caso. Quindi potrei comunicarti gli elementi di ogni set. La quantità di informazioni necessarie per inviare quel messaggio riflette la quantità di incertezza su quali siano questi elementi: c'è una probabilità del 50%, ad esempio, che il primo elemento nel primo set sia un 1 (perché 1 appare in metà dei set in la famiglia), proprio come c'è una probabilità del 50% che il primo risultato in una sequenza di lanci di monete regolari sia testa.
La teoria dell'informazione appare spesso nella combinatoria, un'area della matematica che si occupa del conteggio degli oggetti, che è ciò che Gilmer aveva studiato da studente laureato. Ma mentre tornava a casa in California, temeva che il modo in cui pensava di collegare la teoria dell'informazione alla congettura del sindacato chiuso fosse l'ingenua intuizione di un dilettante: sicuramente i matematici che lavorano si erano già imbattuti in questo oggetto luccicante e lo avevano riconosciuto come l'oro degli sciocchi .
"Ad essere onesto, sono un po' sorpreso che nessuno ci abbia pensato prima", ha detto Gilmer. "Ma forse non dovrei essere sorpreso, perché io stesso ci pensavo da un anno e conoscevo la teoria dell'informazione."
Più probabile che no
Gilmer ha lavorato al problema di notte, dopo aver terminato il suo lavoro in Google, e nei fine settimana per tutta la seconda metà di ottobre e l'inizio di novembre. Fu incoraggiato dalle idee che un gruppo di matematici aveva esplorato anni prima in un collaborazione aperta sul blog di un eminente matematico di nome Tim Gowers. Ha anche lavorato con un libro di testo al suo fianco in modo da poter cercare formule che aveva dimenticato.
“Penseresti che qualcuno che ottiene un grande risultato non dovrebbe consultare il capitolo 2 di Elementi di teoria dell'informazione, ma l'ho fatto ", ha detto Gilmer.
La strategia di Gilmer consisteva nell'immaginare una famiglia chiusa dal sindacato in cui nessun elemento comparisse nemmeno nell'1% di tutti i set: un controesempio che, se esistesse davvero, falsificherebbe la congettura di Frankl.
Diciamo che scegli due insiemi, A e B, da questa famiglia a caso e consideri gli elementi che potrebbero essere in quegli insiemi, uno alla volta. Ora chiedi: quali sono le probabilità che l'insieme A contenga il numero 1? E l'insieme B? Poiché ogni elemento ha poco meno dell'1% di probabilità di apparire in un dato set, non ti aspetteresti che A o B contengano 1. Il che significa che c'è poca sorpresa - e poche informazioni ottenute - se impari che nessuno dei due in realtà fa.
Successivamente, pensa alla possibilità che l'unione di A e B contenga 1. È ancora improbabile, ma è più probabile delle probabilità che appaia in uno dei singoli insiemi. È la somma della probabilità che appaia in A e della probabilità che appaia in B meno la probabilità che appaia in entrambi. Quindi, forse poco meno del 2%.
Questo è ancora basso, ma è più vicino a una proposta 50-50. Ciò significa che sono necessarie più informazioni per condividere il risultato. In altre parole, se c'è una famiglia chiusa dall'unione in cui nessun elemento appare in almeno l'1% di tutti gli insiemi, ci sono più informazioni nell'unione di due insiemi che in uno degli insiemi stessi.
“L'idea di rivelare le cose elemento per elemento e osservare la quantità di informazioni che apprendi è estremamente intelligente. Questa è l'idea principale della prova”, ha detto Ryan Alweiss dell'Università di Princeton.
A questo punto Gilmer stava cominciando ad avvicinarsi alla congettura di Frankl. Questo perché è facile dimostrare che in una famiglia chiusa dall'unione, l'unione di due insiemi contiene necessariamente meno informazioni degli insiemi stessi, non di più.
Per capire perché, pensa a quella famiglia unificata chiusa contenente i 1,024 diversi insiemi che puoi creare dai numeri da 1 a 10. Se scegli due di questi insiemi a caso, in media ti ritroverai con insiemi contenenti cinque elementi. (Di quei 1,024 insiemi, 252 contengono cinque elementi, rendendola la dimensione dell'insieme più comune.) È anche probabile che tu finisca con un'unione contenente circa sette elementi. Ma ci sono solo 120 modi diversi di creare insiemi contenenti sette elementi.
Il punto è che c'è più incertezza sul contenuto di due insiemi scelti a caso che sulla loro unione. L'unione tende a insiemi più grandi con più elementi, per i quali ci sono meno possibilità. Quando prendi l'unione di due insiemi in una famiglia chiusa dall'unione, in un certo senso sai cosa otterrai, come quando lanci una moneta distorta, il che significa che l'unione contiene meno informazioni degli insiemi di cui è composta.
Con ciò, Gilmer aveva una prova. Sapeva che se nessun elemento appare nemmeno nell'1% dei set, il sindacato è costretto a contenere più informazioni. Ma il sindacato deve contenere meno informazioni. Pertanto deve esserci almeno un elemento che compare in almeno l'1% degli insiemi.
La spinta a 50
Quando Gilmer ha pubblicato la sua dimostrazione il 16 novembre, ha incluso una nota che pensava fosse possibile utilizzare il suo metodo per avvicinarsi ancora di più a una dimostrazione della piena congettura, alzando potenzialmente la soglia al 38%.
Cinque giorni dopo, tre diverso gruppi dei matematici ha pubblicato documenti a poche ore l'uno dall'altro che si basavano sul lavoro di Gilmer per fare proprio questo. aggiuntivo documenti seguito, ma l'esplosione iniziale sembra aver portato i metodi di Gilmer fino in fondo; arrivare al 50% richiederà probabilmente ulteriori nuove idee.
Tuttavia, per alcuni degli autori degli articoli successivi, arrivare al 38% è stato relativamente semplice e si sono chiesti perché Gilmer non l'abbia fatto da solo. La spiegazione più semplice si è rivelata quella corretta: dopo più di mezzo decennio senza matematica, Gilmer non sapeva come svolgere parte del lavoro tecnico analitico necessario per farcela.
"Ero un po' arrugginito e, a dire il vero, ero bloccato", ha detto Gilmer. "Ma ero ansioso di vedere dove l'avrebbe portata la comunità".
Eppure Gilmer pensa che le stesse circostanze che lo hanno lasciato fuori pratica abbiano probabilmente reso possibile la sua prova in primo luogo.
"È l'unico modo in cui posso spiegare perché ho pensato al problema per un anno alla scuola di specializzazione e non ho fatto progressi, ho lasciato la matematica per sei anni, poi sono tornato al problema e ho fatto questa svolta", ha detto. "Non so come spiegarlo a parte il fatto che l'apprendimento automatico ha influenzato il mio modo di pensare".
Correzione: Gennaio 3, 2023
Il titolo originale si riferiva a Gilmer come a un "ingegnere di Google". In effetti, è un ricercatore.
