Predstavitev
Sredi oktobra, Justin Gilmer letel iz Kalifornije v New York, da bi se udeležil prijateljeve poroke. Medtem ko je bil na vzhodni obali, je obiskal svojega nekdanjega svetovalca, Michael Saks, matematik na univerzi Rutgers, kjer je Gilmer doktoriral sedem let prej.
Saks in Gilmer sta se srečala med kosilom, vendar nista govorila o matematiki. Pravzaprav Gilmer ni resno razmišljal o matematiki, odkar je leta 2015 končal študij na Rutgersu. Takrat se je odločil, da ne želi kariere v akademskem svetu, in se je namesto tega sam začel učiti programiranja. Ko sta s Saksom jedla, je Gilmer svojemu staremu mentorju povedal o svoji službi pri Googlu, kjer dela na področju strojnega učenja in umetne inteligence.
Dan, ko je Gilmer obiskal Rutgers, je bil sončen. Ko je hodil naokoli, se je spomnil, kako je leta 2013 preživel večji del leta, ko je hodil po istih poteh kampusa in razmišljal o problemu, imenovanem sindikalno zaprta domneva. To je bila fiksacija, čeprav brezplodna: Gilmerju se je kljub vsemu trudu le uspelo naučiti, zakaj je navidezno preprost problem množic števil tako težko rešiti.
»Mislim, da veliko ljudi razmišlja o problemu, dokler ne postanejo zadovoljni, da razumejo, zakaj je težko. Verjetno sem za to porabil več časa kot večina ljudi,« je dejal Gilmer.
Po oktobrskem obisku se je zgodilo nekaj nepričakovanega: dobil je novo idejo. Gilmer je začel razmišljati o načinih uporabe tehnik iz informacijske teorije za rešitev unijsko zaprte domneve. Za idejo se je ukvarjal mesec dni in na vsakem koraku pričakoval, da bo propadla. Toda namesto tega se je vedno znova odpirala pot do dokaza. Končno je 16. novembra ga objavil prvi rezultat te vrste to matematikom pripelje veliko poti do dokazovanja popolne domneve.
Časopis je sprožil val nadaljnjega dela. Matematiki na Univerzi v Oxfordu, Tehnološkem inštitutu v Massachusettsu in Inštitutu za napredne študije so med drugimi institucijami hitro nadgradili Gilmerjeve nove metode. A preden so to storili, so se sami vprašali: kdo je ta tip?
Na pol poln
Unijsko zaprta domneva se nanaša na zbirke števil, imenovane množice, kot so {1, 2} in {2, 3, 4}. Na množicah lahko izvajate operacije, vključno z njihovo združitvijo, kar pomeni njihovo združevanje. Na primer, zveza {1, 2} in {2, 3, 4} je {1, 2, 3, 4}.
Zbirka ali družina nizov se šteje za "unijsko zaprto", če je zveza katerih koli dveh nizov v družini enaka kateremu koli obstoječemu nizu v družini. Na primer, razmislite o tej družini štirih nizov:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Kombinirajte kateri koli par in dobite komplet, ki je že v družini, zaradi česar je družinska zveza zaprta.
Matematiki so o različicah unijsko zaprte domneve klepetali že v šestdesetih letih 1960. stoletja, vendar je svojo prvo uradno izjavo prejela leta 1979 v članku Péter Frankl, madžarski matematik, ki je v osemdesetih letih prejšnjega stoletja emigriral na Japonsko in med svoje dejavnosti šteje ulično nastopanje.
Frankl je domneval, da če je družina množic unijsko zaprta, mora imeti vsaj en element (ali število), ki se pojavlja v vsaj polovici množic. To je bil naravni prag iz dveh razlogov.
Prvič, na voljo so primeri sindikalno zaprtih družin, v katerih se vsi elementi pojavljajo v natanko 50 % nizov. Tako kot vsi različni kompleti, ki jih lahko sestavite na primer iz številk od 1 do 10. Takšnih množic, ki tvorijo unijsko zaprto družino, je 1,024, vsak od 10 elementov pa se pojavlja v 512 izmed njih. In drugič, v času, ko je Frankl izrekel domnevo, še nihče ni predstavil primera sindikalno zaprte družine, v kateri domneva ne bi držala.
Torej se je 50 % zdelo prava napoved.
To ni pomenilo, da je bilo enostavno dokazati. V letih po Franklovem prispevku je bilo malo rezultatov. Pred Gilmerjevim delom je tem dokumentom uspelo vzpostaviti samo pragove, ki so se spreminjali glede na število nizov v družini (v nasprotju z enakim 50-odstotnim pragom za družine nizov vseh velikosti).
"Zdi se, kot da bi moralo biti enostavno, in podobno je številnim težavam, ki so enostavne, vendar se je uprlo napadom," je dejal Will Sawin univerze Columbia.
Pomanjkanje napredka je odražalo tako kočljivo naravo problema kot dejstvo, da mnogi matematiki o njem raje niso razmišljali; skrbelo jih je, da bodo izgubili leta svoje kariere v lovljenju zapeljivega problema, ki ga ni bilo mogoče rešiti. Gilmer se spominja dneva leta 2013, ko je šel v Saksovo pisarno in omenil domnevo o zaprtosti sindikatov. Njegov svetovalec - ki se je v preteklosti sam ubadal s tem problemom - ga je skoraj vrgel iz sobe.
"Mike je rekel, 'Justin, znova me boš prisilil v razmišljanje o tem problemu in tega nočem storiti,'" je dejal Gilmer.
Vpogled v negotovost
Po obisku pri Rutgersu je Gilmer v mislih vrtel težavo in poskušal razumeti, zakaj je tako težko. Pozval se je z osnovnim dejstvom: če imate družino s 100 skupinami, obstaja 4,950 različnih načinov, kako izbrati dva in sprejeti njuno združitev. Nato se je vprašal: Kako je mogoče, da se 4,950 različnih zvez preslika nazaj na samo 100 sklopov, če se v teh zvezah ne pojavi noben element z vsaj določeno frekvenco?
Tudi takrat je bil na poti k dokazu, čeprav tega še ni vedel. Tja bi ga pripeljale tehnike iz informacijske teorije, ki zagotavlja strog način razmišljanja o tem, kaj lahko pričakujete, ko naključno potegnete par predmetov.
Informacijska teorija se je razvila v prvi polovici 20. stoletja, najbolj znana s člankom Clauda Shannona iz leta 1948, “Matematična teorija komunikacije.” Prispevek je zagotovil natančen način za izračun količine informacij, potrebnih za pošiljanje sporočila, na podlagi količine negotovosti glede tega, kaj točno bi sporočilo sporočilo. Ta povezava — med informacijo in negotovostjo — je bil Shannonin izjemen, temeljni vpogled.
Za primer igrače si predstavljajte, da petkrat vržem kovanec in vam pošljem nastalo zaporedje. Če gre za običajen kovanec, je za prenos potrebnih pet bitov informacij. Če pa gre za naložen kovanec — recimo, z 99-odstotno verjetnostjo, da bo pristal na glavah — je potrebno veliko manj. Na primer, lahko bi se vnaprej dogovorili, da vam bom poslal 1 (en sam delček informacije), če naloženi kovanec vseh petkrat pade na glavo, kar je zelo verjetno. Izid poštenega meta kovanca je bolj presenečen kot pri pristranskem in zato več informacij.
Enako razmišljanje velja za informacije, ki jih vsebujejo nizi števil. Če imam družino unijsko zaprtih množic - recimo 1,024 množic, sestavljenih iz števil od 1 do 10 - bi lahko naključno izbral dva množice. Potem bi vam lahko sporočil elemente vsakega sklopa. Količina informacij, potrebnih za pošiljanje tega sporočila, odraža količino negotovosti glede tega, kateri elementi so: obstaja na primer 50-odstotna verjetnost, da je prvi element v prvem nizu 1 (ker se 1 pojavi v polovici nizov v družina), tako kot obstaja 50-odstotna možnost, da je prvi rezultat v nizu poštenih metov kovancev glava.
Teorija informacij se pogosto pojavlja v kombinatoriki, področju matematike, ki se ukvarja s štetjem predmetov, kar je Gilmer študiral kot podiplomski študent. Ko pa je letel nazaj domov v Kalifornijo, ga je skrbelo, da je bil način, kako je mislil povezati informacijsko teorijo s predpostavko o zaprti uniji, naiven vpogled amaterja: Zagotovo so delujoči matematiki že kdaj naleteli na ta sijoči predmet in ga prepoznali kot zlato za norce. .
»Če sem iskren, sem nekoliko presenečen, da tega prej ni nihče pomislil,« je dejal Gilmer. "Mogoče pa me ne bi smelo presenetiti, saj sem sam o tem razmišljal eno leto in sem poznal informacijsko teorijo."
Bolj verjetno kot ne
Gilmer je s težavo delal ponoči, po končanem delu pri Googlu, in ob koncih tedna v drugi polovici oktobra in začetku novembra. Spodbudile so ga ideje, ki jih je leta prej raziskovala skupina matematikov v an odprto sodelovanje na blogu uglednega matematika Tima Gowersa. Delal je tudi z učbenikom ob sebi, da je lahko poiskal formule, ki jih je pozabil.
»Mislili bi si, da nekomu, ki pride do odličnega rezultata, ne bi bilo treba pogledati 2. poglavja Elementi teorije informacij, ampak sem,« je rekel Gilmer.
Gilmerjeva strategija je bila zamisliti sindikalno zaprto družino, v kateri se noben element ne pojavi niti v 1 % vseh sklopov – protiprimer, ki bi, če bi res obstajal, ponaredil Franklovo domnevo.
Recimo, da iz te družine naključno izberete dva niza, A in B, in razmislite o elementih, ki bi lahko bili v teh nizih, enega za drugim. Zdaj vprašajte: Kakšne so možnosti, da niz A vsebuje številko 1? In niz B? Ker ima vsak element malo manj kot 1-odstotno možnost, da se pojavi v katerem koli danem nizu, ne bi pričakovali, da bosta bodisi A bodisi B vsebovala 1. Kar pomeni, da ni presenečenja – in pridobljenih malo informacij – če izveš, da ne eno ne drugo v resnici počne.
Nato razmislite o možnosti, da zveza A in B vsebuje 1. Še vedno je malo verjetno, vendar je bolj verjetno kot verjetnost, da se pojavi v katerem koli od posameznih nizov. Je vsota verjetnosti, da se pojavi v A, in verjetnosti, da se pojavi v B minus verjetnost, da se pojavi v obeh. Torej, morda slaba 2%.
To je še vedno nizko, vendar je bližje predlogu 50-50. To pomeni, da je za skupno rabo rezultata potrebnih več informacij. Z drugimi besedami, če obstaja unijsko zaprta družina, v kateri se noben element ne pojavi v vsaj 1 % vseh nizov, je v uniji dveh nizov več informacij kot v katerem koli izmed samih nizov.
»Zamisel o razkrivanju stvari element za elementom in opazovanju količine informacij, ki jih izveš, je izjemno pametna. To je glavna ideja dokaza,« je dejal Ryan Alweiss univerze Princeton.
Na tej točki se je Gilmer začel približevati Franklovi domnevi. To je zato, ker je enostavno dokazati, da v unijsko zaprti družini zveza dveh nizov nujno vsebuje manj informacij kot nizi sami - ne več.
Če želite razumeti, zakaj, pomislite na to sindikalno zaprto družino, ki vsebuje 1,024 različnih nizov, ki jih lahko sestavite iz številk od 1 do 10. Če naključno izberete dva od teh nizov, boste v povprečju dobili nize, ki vsebujejo pet elementov. (Od teh 1,024 nizov jih 252 vsebuje pet elementov, zaradi česar je to najpogostejša velikost niza.) Verjetno boste tudi na koncu dobili zvezo, ki vsebuje približno sedem elementov. Obstaja pa samo 120 različnih načinov izdelave sklopov, ki vsebujejo sedem elementov.
Bistvo je, da je več negotovosti glede vsebine dveh naključno izbranih množic kot glede njune združitve. Zveza se nagiba k večjim sklopom z več elementi, za katere je manj možnosti. Ko vzamete zvezo dveh množic v družini, ki je zaprta z zvezo, nekako veste, kaj boste dobili – kot ko vržete pristranski kovanec – kar pomeni, da zveza vsebuje manj informacij kot množice, iz katerih je sestavljena.
S tem je imel Gilmer dokaz. Vedel je, da če se noben element ne pojavi niti v 1 % sklopov, je zveza prisiljena vsebovati več informacij. Toda zveza mora vsebovati manj informacij. Zato mora obstajati vsaj en element, ki se pojavi v vsaj 1 % nizov.
Pritisk do 50
Ko je Gilmer 16. novembra objavil svoj dokaz, je vključil opombo, da meni, da je mogoče uporabiti njegovo metodo, da bi se še bolj približal dokazu popolne domneve, s čimer bi lahko dvignil prag na 38 %.
Pet dni kasneje, 3 drugačen skupine matematikov je v nekaj urah drug za drugim objavilo članke, ki so temeljili na Gilmerjevem delu, da bi dosegli prav to. Dodatne članki sledili, vendar se zdi, da je začetni izbruh Gilmerjeve metode pripeljal tako daleč; da bi dosegli 50 %, bodo verjetno potrebne dodatne nove zamisli.
Kljub temu je bilo za nekatere avtorje nadaljnjih dokumentov doseganje 38 % razmeroma preprosto in spraševali so se, zakaj Gilmer tega ni naredil sam. Najpreprostejša razlaga se je izkazala za pravilno: po več kot pol desetletja brez matematike Gilmer preprosto ni vedel, kako opraviti nekaj tehničnega analitičnega dela, ki je potrebno za to.
"Bil sem nekoliko zarjavel in če sem iskren, sem bil obtičal," je dejal Gilmer. "Ampak komaj sem želel videti, kam bo skupnost pripeljala."
Vendar Gilmer meni, da so iste okoliščine, zaradi katerih je bil izključen iz prakse, verjetno omogočile njegov dokaz.
"To je edini način, da lahko razložim, zakaj sem eno leto na podiplomskem študiju razmišljal o problemu in nisem napredoval, šest let sem pustil matematiko, nato pa sem se vrnil k problemu in naredil ta preboj," je dejal. "Ne vem, kako naj to razložim, razen tega, da je strojno učenje vplivalo na moje razmišljanje."
Popravek: Januar 3, 2023
Prvotni naslov je Gilmerja imenoval "Googlov inženir". Pravzaprav je raziskovalec.
