Introducere
La mijlocul lunii octombrie, Justin Gilmer a zburat din California la New York pentru a participa la nunta unui prieten. În timp ce se afla pe Coasta de Est, și-a vizitat fostul consilier, Michael Saks, un matematician la Universitatea Rutgers, unde Gilmer și-a luat doctoratul cu șapte ani mai devreme.
Saks și Gilmer au ajuns din urmă la prânz, dar nu au vorbit despre matematică. De fapt, Gilmer nu se gândise serios la matematică de când a terminat la Rutgers în 2015. Atunci a decis că nu vrea o carieră în mediul academic și în schimb a început să învețe singur să programeze. În timp ce el și Saks mâncau, Gilmer i-a spus vechiului său mentor despre slujba lui la Google, unde lucrează la învățarea automată și la inteligența artificială.
Era soare în ziua în care Gilmer a vizitat Rutgers. În timp ce se plimba, și-a amintit că în 2013 și-a petrecut cea mai mare parte a unui an mergând pe aceleași cărări din campus, gândindu-se la o problemă numită conjectura închisă de sindicat. Fusese o fixare, deși inutilă: cu tot efortul său, Gilmer reușise doar să se învețe singur de ce era atât de greu de rezolvat problema simplă a setului de numere.
„Cred că mulți oameni se gândesc la problemă până când devin mulțumiți că înțeleg de ce este greu. Probabil că am petrecut mai mult timp cu ea decât majoritatea oamenilor”, a spus Gilmer.
În urma vizitei sale din octombrie, s-a întâmplat ceva neașteptat: i-a venit o idee nouă. Gilmer a început să se gândească la modalități de a aplica tehnici din teoria informației pentru a rezolva conjectura uniune închisă. A urmărit ideea timp de o lună, așteptându-se la fiecare pas să eșueze. Dar, în schimb, drumul către o dovadă continua să se deschidă. În cele din urmă, pe 16 noiembrie el a postat un rezultat primul de acest fel asta determină matematicienii o mare parte din calea spre demonstrarea completă a conjecturii.
Lucrarea a declanșat o serie de lucrări ulterioare. Matematicienii de la Universitatea din Oxford, Institutul de Tehnologie din Massachusetts și Institutul de Studii Avansate, printre alte instituții, au construit rapid pe metodele noi ale lui Gilmer. Dar înainte să o facă, și-au pus o întrebare: cine este acest tip?
Jumatate plin
Conjectura uniune închisă se referă la colecții de numere numite mulțimi, cum ar fi {1, 2} și {2, 3, 4}. Puteți efectua operații pe decoruri, inclusiv luarea unirii acestora, ceea ce înseamnă combinarea lor. De exemplu, uniunea dintre {1, 2} și {2, 3, 4} este {1, 2, 3, 4}.
O colecție, sau o familie, de seturi este considerată „închisă prin unire” dacă unirea oricăror două seturi din familie este egală cu orice set existent în familie. De exemplu, luați în considerare această familie de patru seturi:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Combinați orice pereche și obțineți un set care este deja în familie, făcând uniunea familială închisă.
Matematicienii au discutat despre versiuni ale conjecturii închise de uniune încă din anii 1960, dar aceasta a primit prima declarație oficială în 1979, într-o lucrare scrisă de Péter Frankl, un matematician maghiar care a emigrat în Japonia în anii 1980 și care numără performanțele stradale printre activitățile sale.
Frankl a presupus că, dacă o familie de mulțimi este uniune închisă, trebuie să aibă cel puțin un element (sau număr) care apare în cel puțin jumătate din mulțimi. A fost un prag firesc din două motive.
În primul rând, există exemple ușor disponibile de familii închise de uniuni în care toate elementele apar în exact 50% din seturi. La fel ca toate seturile diferite pe care le puteți face de la numerele de la 1 la 10, de exemplu. Există 1,024 de astfel de seturi, care formează o familie închisă de uniune, iar fiecare dintre cele 10 elemente apare în 512 dintre ele. Și în al doilea rând, în momentul în care Frankl a făcut presupunerea, nimeni nu a produs vreodată un exemplu de familie închisă de uniuni în care conjectura să nu se susțină.
Deci 50% părea a fi predicția corectă.
Asta nu însemna că era ușor de demonstrat. În anii de după lucrarea lui Frankl, au existat puține rezultate. Înainte de munca lui Gilmer, acele lucrări au reușit să stabilească doar praguri care variau în funcție de numărul de seturi din familie (spre deosebire de a fi același prag de 50% pentru familiile seturi de toate dimensiunile).
„Se pare că ar trebui să fie ușor și este similar cu o mulțime de probleme care sunt ușoare, dar a rezistat atacurilor”, a spus Will Sawin de la Universitatea Columbia.
Lipsa progresului a reflectat atât natura complicată a problemei, cât și faptul că mulți matematicieni au preferat să nu se gândească la ea; își făceau griji că își vor pierde ani de carieră urmărind o problemă ademenitoare care era imposibil de rezolvat. Gilmer își amintește o zi din 2013 când a mers la biroul lui Saks și a adus în discuție conjectura închisă de sindicat. Consilierul său – care în trecut se luptase el însuși cu problema – aproape l-a dat afară din cameră.
„Mike a spus: „Justin, mă vei face să mă gândesc din nou la această problemă și nu vreau să fac asta”, a spus Gilmer.
O perspectivă a incertitudinii
După vizita lui la Rutgers, Gilmer și-a răscolit problema în minte, încercând să înțeleagă de ce era atât de greu. El s-a îndemnat cu un fapt de bază: dacă ai o familie de 100 de seturi, există 4,950 de moduri diferite de a alege două și de a lua uniunea lor. Apoi s-a întrebat: Cum este posibil ca 4,950 de uniuni diferite să se mapeze înapoi pe doar 100 de seturi dacă niciun element nu apare în acele uniuni cu cel puțin o anumită frecvență?
Chiar și în acel moment era în drum spre o dovadă, deși nu știa încă. Tehnicile din teoria informației, care oferă un mod riguros de a gândi la ce să te aștepți atunci când tragi o pereche de obiecte la întâmplare, l-ar duce acolo.
Teoria informației dezvoltată în prima jumătate a secolului al XX-lea, cel mai faimos cu lucrarea lui Claude Shannon din 20, „O teorie matematică a comunicării.” Lucrarea a oferit o modalitate precisă de calculare a cantității de informații necesare pentru a trimite un mesaj, pe baza cantității de incertitudine cu privire la ceea ce va spune exact mesajul. Acest link - între informaţie şi incertitudine — a fost percepția remarcabilă și fundamentală a lui Shannon.
Pentru a lua un exemplu de jucărie, imaginați-vă că arunc o monedă de cinci ori și vă trimit secvența rezultată. Dacă este o monedă normală, este nevoie de cinci biți de informații pentru a fi transmisă. Dar dacă este o monedă încărcată – să zicem, 99% probabil să cadă în cap – este nevoie de mult mai puțin. De exemplu, am putea conveni dinainte că vă voi trimite un 1 (un singur bit de informație) dacă moneda încărcată aterizează capetele de cinci ori, ceea ce este foarte probabil să facă. Există mai multă surpriză în rezultatul unei răsturnări corecte de monede decât este cu una părtinitoare și, prin urmare, mai multe informații.
Aceeași gândire se aplică și informațiilor conținute în seturi de numere. Dacă am o familie de seturi închise de uniune - să zicem cele 1,024 de seturi făcute de la numerele de la 1 la 10 - aș putea alege două seturi la întâmplare. Atunci aș putea să vă comunic elementele fiecărui set. Cantitatea de informații necesare pentru a trimite acel mesaj reflectă cantitatea de incertitudine în ceea ce privește elementele respective: există o șansă de 50%, de exemplu, ca primul element din primul set să fie un 1 (deoarece 1 apare în jumătate din seturi din familie), la fel cum există o șansă de 50% ca primul rezultat dintr-o secvență de răsturnări corecte de monede să fie capete.
Teoria informației apare adesea în combinatorică, o zonă a matematicii preocupată de numărarea obiectelor, ceea ce Gilmer studiase ca student absolvent. Dar, în timp ce zbura înapoi acasă, în California, și-a făcut griji că modul în care a gândit să conecteze teoria informațiilor cu conjectura uniunii închise era înțelegerea naivă a unui amator: cu siguranță matematicienii care lucrează au dat peste acest obiect strălucitor și l-au recunoscut ca pe aurul prostului. .
„Ca să fiu sincer, sunt puțin surprins că nimeni nu s-a gândit la asta înainte”, a spus Gilmer. „Dar poate nu ar trebui să fiu surprins, pentru că eu însumi mă gândisem la asta timp de un an și cunoșteam teoria informației.”
Mai probabil decât nu
Gilmer a lucrat la problemă noaptea, după ce și-a terminat munca la Google, și în weekenduri, în a doua jumătate a lunii octombrie și începutul lunii noiembrie. El a fost încurajat de ideile pe care un grup de matematicieni le explorase cu ani în urmă într-un colaborare deschisă pe blogul unui matematician proeminent pe nume Tim Gowers. De asemenea, a lucrat cu un manual lângă el pentru a putea căuta formule pe care le-a uitat.
„Ați crede că cineva care vine cu un rezultat grozav nu ar trebui să consulte Capitolul 2 din Elemente de teoria informației, dar am făcut-o”, a spus Gilmer.
Strategia lui Gilmer a fost să-și imagineze o familie închisă de uniuni în care nici măcar 1% din toate seturile nu apărea niciun element – un contraexemplu care, dacă ar exista cu adevărat, ar falsifica conjectura lui Frankl.
Să presupunem că alegeți două mulțimi, A și B, din această familie la întâmplare și luați în considerare elementele care ar putea fi în acele mulțimi, pe rând. Acum întrebați: Care sunt șansele ca setul A să conțină numărul 1? Și setul B? Deoarece fiecare element are o șansă mai mică de 1% de a apărea într-un anumit set, nu te-ai aștepta ca nici A sau B să conțină 1. Ceea ce înseamnă că există puțină surpriză - și puține informații obținute - dacă înveți că nici de fapt. face.
Apoi, gândiți-vă la șansa ca uniunea dintre A și B să conțină 1. Este încă puțin probabil, dar este mai probabil decât șansele ca acesta să apară în oricare dintre seturile individuale. Este suma probabilității ca să apară în A și probabilitatea ca să apară în B minus probabilitatea ca să apară în ambele. Deci, poate puțin sub 2%.
Acesta este încă scăzut, dar este mai aproape de o propunere de 50-50. Asta înseamnă că este nevoie de mai multe informații pentru a partaja rezultatul. Cu alte cuvinte, dacă există o familie închisă de uniuni în care niciun element nu apare în cel puțin 1% din toate seturile, există mai multe informații în unirea a două seturi decât în oricare dintre seturile în sine.
„Ideea de a dezvălui lucrurile element cu element și de a analiza cantitatea de informații pe care o înveți este extrem de inteligentă. Aceasta este ideea principală a dovezii”, a spus Ryan Alweiss de la Universitatea Princeton.
În acest moment, Gilmer începea să se apropie de conjectura lui Frankl. Acest lucru se datorează faptului că este ușor să demonstrezi că într-o familie închisă, unirea a două seturi conține în mod necesar mai puține informații decât seturile în sine - nu mai multe.
Pentru a vedea de ce, gândiți-vă la acea familie închisă de uniuni care conține cele 1,024 de seturi diferite pe care le puteți face de la numerele de la 1 la 10. Dacă alegeți două dintre acele seturi la întâmplare, în medie, veți ajunge la seturi care conțin cinci elemente. (Din acele 1,024 de seturi, 252 conțin cinci elemente, ceea ce face din aceasta dimensiunea cea mai comună a setului.) De asemenea, este posibil să ajungeți la o uniune care conține aproximativ șapte elemente. Dar există doar 120 de moduri diferite de a face seturi care conțin șapte elemente.
Ideea este că există mai multă incertitudine cu privire la conținutul a două seturi alese aleatoriu decât este cu privire la unirea lor. Unirea se înclină spre seturi mai mari cu mai multe elemente, pentru care există mai puține posibilități. Când iei unirea a două seturi într-o familie închisă, știi cumva ce vei obține - ca atunci când arunci o monedă părtinitoare - ceea ce înseamnă că uniunea conține mai puține informații decât seturile din care este compusă.
Cu asta, Gilmer a avut o dovadă. Știa că dacă nici măcar în 1% din seturi nu apare niciun element, uniunea este nevoită să conțină mai multe informații. Dar sindicatul trebuie să conțină mai puține informații. Prin urmare, trebuie să existe cel puțin un element care să apară în cel puțin 1% din seturi.
Impingerea la 50
Când Gilmer și-a postat dovada pe 16 noiembrie, a inclus o notă în care credea că este posibil să folosească metoda sa pentru a se apropia și mai mult de o dovadă a conjecturei complete, potențial ridicând pragul la 38%.
Cinci zile mai târziu, trei diferit Grupuri dintre matematicieni au postat lucrări la câteva ore unul de celălalt, care s-au bazat pe munca lui Gilmer pentru a face exact asta. Suplimentar lucrări a urmat, dar explozia inițială pare să fi dus metodele lui Gilmer cât de departe vor merge; a ajunge la 50% va fi probabil nevoie de idei noi suplimentare.
Totuși, pentru unii dintre autorii lucrărilor ulterioare, a ajunge la 38% a fost relativ simplu și s-au întrebat de ce Gilmer nu a făcut-o doar el însuși. Cea mai simplă explicație s-a dovedit a fi cea corectă: după mai bine de o jumătate de deceniu fără matematică, Gilmer pur și simplu nu știa cum să facă o parte din munca analitică tehnică necesară pentru a reuși.
„Eram puțin ruginit și, să fiu sincer, am rămas blocat”, a spus Gilmer. „Dar eram nerăbdător să văd unde o va duce comunitatea.”
Cu toate acestea, Gilmer crede că aceleași circumstanțe care l-au lăsat în afara exercițiului probabil au făcut posibilă demonstrarea lui în primul rând.
„Este singurul mod în care pot explica de ce m-am gândit la problemă timp de un an la absolvire și nu am făcut niciun progres, am părăsit matematica timp de șase ani, apoi m-am întors la problemă și am făcut această descoperire”, a spus el. „Nu știu cum să explic, în afară de faptul că învățarea automată mi-a părtinit gândirea.”
Corecţie: Ianuarie 3, 2023
Titlul original se referea la Gilmer drept „inginer Google”. De fapt, el este cercetător.
