Sissejuhatus
Oktoobri keskel, Justin Gilmer lendas Californiast New Yorki, et osaleda sõbra pulmas. Idarannikul viibides külastas ta oma endist nõunikku, Michael Saks, matemaatik Rutgersi ülikoolis, kus Gilmer oli saanud doktorikraadi seitse aastat varem.
Saks ja Gilmer jõudsid lõuna ajal järele, kuid nad ei rääkinud matemaatikast. Tegelikult polnud Gilmer pärast Rutgersi ülikooli lõpetamist 2015. aastal matemaatikale tõsiselt mõelnud. Siis otsustas ta, et ei taha akadeemilist karjääri teha, ja hakkas selle asemel programmeerima. Kui tema ja Saks sõid, rääkis Gilmer oma vanale mentorile oma tööst Google'is, kus ta tegeleb masinõppe ja tehisintellektiga.
Päeval, mil Gilmer Rutgersit külastas, oli päikesepaisteline. Ringi kõndides meenutas ta, kuidas ta 2013. aastal veetis suurema osa aastast samadel ülikoolilinnakutel kõndides, mõeldes probleemile, mida nimetatakse ametiühingu suletud oletuseks. See oli fikseerimine, ehkki viljatu: kogu oma pingutuse peale oli Gilmeril õnnestunud vaid endale selgeks teha, miks lihtsana näivat numbrihulkade probleemi oli nii raske lahendada.
"Ma arvan, et paljud inimesed mõtlevad probleemile, kuni nad on rahul, et saavad aru, miks see raske on. Ma kulutasin sellele tõenäoliselt rohkem aega kui enamik inimesi, ”ütles Gilmer.
Pärast tema oktoobrikuist visiiti juhtus midagi ootamatut: ta sai uue idee. Gilmer hakkas mõtlema viisidele, kuidas rakendada infoteooriast pärit tehnikaid, et lahendada liidu suletud oletus. Ta jätkas seda ideed kuu aega, oodates igal sammul selle läbikukkumist. Kuid selle asemel avanes tee tõestuseni. Lõpuks 16. novembril ta postitas esimese omalaadse tulemuse mis annab matemaatikutele suure osa teest täieliku oletuse tõestamiseks.
Leht pani hoo sisse järeltööle. Oxfordi ülikooli, Massachusettsi tehnoloogiainstituudi ja edasijõudnute uuringute instituudi matemaatikud põhinesid kiiresti Gilmeri uudsetel meetoditel. Kuid enne seda küsisid nad endalt küsimuse: kes see mees on?
Pooltäis
Suletud liidu oletus puudutab arvude kogumeid, mida nimetatakse hulkadeks, nagu {1, 2} ja {2, 3, 4}. Saate teha komplektidega toiminguid, sealhulgas võtta nende liite, mis tähendab nende kombineerimist. Näiteks {1, 2} ja {2, 3, 4} liit on {1, 2, 3, 4}.
Komplektide kogu või perekond loetakse "suletud liiduks", kui perekonna mis tahes kahe komplekti liit võrdub perekonna mis tahes olemasoleva komplektiga. Näiteks vaadake seda neljast komplektist koosnevat perekonda:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Kombineerige suvaline paar ja saate komplekti, mis on juba perekonnas, muutes pereliidu suletuks.
Matemaatikud vestlesid liidu suletud oletuse versioonidest juba 1960. aastatel, kuid see sai oma esimese ametliku avalduse 1979. aastal artiklis Péter Frankl, Ungari matemaatik, kes emigreerus 1980. aastatel Jaapanisse ja kelle tegevusaladeks on tänavaesinemised.
Frankl oletas, et kui hulkade perekond on liitsuletud, peab sellel olema vähemalt üks element (või arv), mis esineb vähemalt pooltes hulgades. See oli loomulik lävi kahel põhjusel.
Esiteks on kergesti kättesaadavad näited ametiühinguga suletud peredest, kus kõik elemendid esinevad täpselt 50% kogumitest. Nagu kõik erinevad komplektid, mida saate teha näiteks numbritest 1 kuni 10. Selliseid komplekte on 1,024, mis moodustavad suletud perekonna, ja igaüks neist 10 elemendist esineb 512-s. Ja teiseks, sel ajal, kui Frankl oletuse tegi, polnud keegi kunagi toonud näidet ametiühinguga suletud perekonnast, kus oletus ei kehtinud.
Nii et 50% tundus õige ennustus.
See ei tähendanud, et seda oleks lihtne tõestada. Frankli paberile järgnenud aastate jooksul on tulemusi olnud vähe. Enne Gilmeri tööd suutsid need paberid kehtestada ainult künnised, mis varieerusid sõltuvalt perekonna komplektide arvust (erinevalt sellest, et igas suuruses komplektide perede jaoks oli sama 50% lävi).
"Tundub, et see peaks olema lihtne ja sarnaneb paljude probleemidega, mis on lihtsad, kuid on rünnakutele vastu pidanud," ütles ta. Will Sawin Columbia ülikoolist.
Edu puudumine peegeldas nii probleemi keerulist olemust kui ka seda, et paljud matemaatikud eelistasid sellele mitte mõelda; nad muretsesid, et kaotavad aastaid oma karjäärist jahtides võluvat probleemi, mida oli võimatu lahendada. Gilmer mäletab päeva 2013. aastal, kui ta läks Saksa kontorisse ja tõi välja ametiühingu suletud oletuse. Tema nõunik – kes oli varem ise selle probleemiga maadelnud – viskas ta peaaegu ruumist välja.
"Mike ütles: "Justin, sa paned mind uuesti sellele probleemile mõtlema ja ma ei taha seda teha," ütles Gilmer.
Ülevaade ebakindlusest
Pärast Rutgersi külaskäiku veeretas Gilmer seda probleemi oma mõtetes, püüdes mõista, miks see nii raske oli. Ta ajendas end ühe põhitõega: kui teie peres on 100 komplekti, on 4,950 erinevat võimalust kahe valimiseks ja nende liitmiseks. Seejärel küsis ta endalt: kuidas on võimalik, et 4,950 erinevat liitu kaardistavad tagasi vaid 100 komplekti, kui nendes ühendustes ei esine elemente vähemalt teatud sagedusega?
Isegi sel hetkel oli ta teel tõestuse poole, kuigi ta seda veel ei teadnud. Infoteooria tehnikad, mis annavad range mõtteviisi selle kohta, mida oodata, kui tõmbate juhuslikult objektipaari, viiksid ta sinna.
Infoteooria arenes välja 20. sajandi esimesel poolel, kõige tuntum Claude Shannoni 1948. aasta artikliga “Kommunikatsiooni matemaatiline teooria.” Paber pakkus täpse viisi sõnumi saatmiseks vajaliku teabe arvu arvutamiseks, võttes aluseks ebakindluse selle ümber, mida sõnum täpselt ütleb. See link — teabe ja ebakindluse vahel — oli Shannoni tähelepanuväärne ja põhjapanev arusaam.
Mänguasja näitena kujutan ette, et viskan viis korda münti ja saadan saadud jada teile. Kui see on tavaline münt, kulub selle edastamiseks viis bitti teavet. Aga kui see on laetud münt – näiteks 99% tõenäosusega, et see langeb pea peale –, kulub selleks palju vähem. Näiteks võime enne tähtaega kokku leppida, et saadan teile 1 (üks bitt teavet), kui laetud münt langeb kõik viis korda, mis on väga tõenäoline. Õiglase mündiviske tulemuses on rohkem üllatust kui erapooliku puhul ja seega rohkem teavet.
Sama mõtlemine kehtib ka numbrihulkades sisalduva teabe kohta. Kui mul on suletud komplektide perekond – näiteks 1,024 komplekti, mis on tehtud numbritest 1 kuni 10 –, võiksin valida kaks komplekti juhuslikult. Siis saaksin teile edastada iga komplekti elemendid. Selle sõnumi saatmiseks kuluv teabe hulk peegeldab ebakindlust nende elementide ümber: Näiteks on 50% tõenäosus, et esimese komplekti esimene element on 1 (kuna 1 esineb pooltes komplektides perekond), nii nagu on 50% tõenäosus, et ausate mündiviskete jada esimene tulemus on pead.
Infoteooria esineb sageli kombinatoorikas, matemaatika valdkonnas, mis on seotud objektide loendamisega, mida Gilmer oli õppinud kraadiõppurina. Kuid koju Californiasse lennates muretses ta, et viis, kuidas ta arvas infoteooriat kinnise liidu oletusega siduda, oli amatööri naiivne arusaam: kindlasti olid töötavad matemaatikud selle läikiva objektiga varem kokku puutunud ja tunnistasid selle lolli kullaks. .
"Ausalt öeldes olen natuke üllatunud, et keegi sellele varem ei mõelnud," ütles Gilmer. "Aga võib-olla ma ei peaks imestama, sest ma ise olin sellele aasta aega mõelnud ja teadsin infoteooriat."
Tõenäolisem kui mitte
Gilmer tegeles probleemiga öösel, pärast töö lõpetamist Google'is, ja nädalavahetustel oktoobri teisel poolel ja novembri alguses. Teda julgustasid ideed, mida rühm matemaatikuid oli uurinud aastaid varem aastal avatud koostöö silmapaistva matemaatiku Tim Gowersi ajaveebis. Ta töötas ka nii, et tema kõrval oli õpik, et saaks otsida valemeid, mille oli unustanud.
„Arvate, et keegi, kes saavutab suurepärase tulemuse, ei peaks tutvuma 2. peatükiga Infoteooria elemendid, aga ma tegin seda,” ütles Gilmer.
Gilmeri strateegia oli ette kujutada ametiühinguga suletud perekonda, kus ühtki elementi ei esinenud isegi 1% kõigist kogumitest – vastunäide, mis kui see tõesti eksisteeriks, võltsiks Frankli oletuse.
Oletame, et valite sellest perekonnast juhuslikult kaks komplekti A ja B ning kaalute ükshaaval elemente, mis nendes komplektides võiksid olla. Nüüd küsige: kui suur on tõenäosus, et komplekt A sisaldab arvu 1? Ja määrata B? Kuna igal elemendil on veidi väiksem kui 1% tõenäosus esineda mis tahes antud komplektis, ei eeldaks, et ei A ega B sisaldaks 1. Mis tähendab, et kui saate teada, et kumbki tegelikult pole, siis üllatust ja teavet on vähe. teeb.
Järgmiseks mõelge võimalusele, et A ja B liit sisaldab 1. See on siiski ebatõenäoline, kuid tõenäolisem kui tõenäosus, et see esineb kummaski üksikus komplektis. See on A-s ilmumise tõenäosuse ja B-s ilmumise tõenäosuse summa, millest on lahutatud tõenäosus, et see ilmub mõlemas. Seega võib-olla veidi alla 2%.
See on endiselt madal, kuid see on lähemal 50–50 pakkumisele. See tähendab, et tulemuse jagamiseks on vaja rohkem teavet. Teisisõnu, kui on olemas suletud perekond, milles ükski element ei esine vähemalt 1% kõigist komplektidest, on kahe komplekti ühenduses rohkem teavet kui kummaski komplektis endas.
„Idee paljastada asju elementide kaupa ja vaadata õpitava teabe hulka on äärmiselt nutikas. See on tõestuse põhiidee,” ütles Ryan Alweiss Princetoni ülikoolist.
Sel hetkel hakkas Gilmer Frankli oletustele lähenema. Selle põhjuseks on asjaolu, et on lihtne näidata, et suletud perekonnas sisaldab kahe komplekti liit tingimata vähem teavet kui komplektid ise – mitte rohkem.
Et näha, miks, mõelge sellele liidu suletud perekonnale, mis sisaldab 1,024 erinevat komplekti, mille saate luua numbritest 1 kuni 10. Kui valite neist juhuslikult kaks komplekti, saate keskmiselt viit elementi sisaldavate komplektideni. (Neist 1,024 komplektist 252 sisaldavad viit elementi, mis teeb sellest kõige tavalisema komplekti suuruse.) Samuti on tõenäoline, et tulemuseks on liit, mis sisaldab umbes seitset elementi. Kuid seitset elementi sisaldavate komplektide tegemiseks on ainult 120 erinevat viisi.
Asi on selles, et kahe juhuslikult valitud komplekti sisu osas on ebakindlust rohkem kui nende liidu suhtes. Liit kaldub suurematele, rohkemate elementidega komplektidele, mille jaoks on vähem võimalusi. Kui võtate kahe komplekti ühendamise ametiühinguga suletud perekonnas, siis teate, mida te saate – näiteks kui viskate kõrvale kallutatud mündi –, mis tähendab, et liit sisaldab vähem teavet kui komplektid, millest see koosneb.
Sellega oli Gilmeril tõend. Ta teadis, et kui ühtki elementi ei esine isegi 1% komplektidest, on liit sunnitud sisaldama rohkem teavet. Kuid ametiühing peab sisaldama vähem teavet. Seetõttu peab olema vähemalt üks element, mis esineb vähemalt 1% kogumitest.
Tõuge 50-le
Kui Gilmer postitas oma tõendi 16. novembril, lisas ta märkuse, et tema arvates on tema meetodit võimalik kasutada täieliku oletuse tõestusele veelgi lähemale jõudmiseks, mis võib tõsta künnise 38%ni.
Viis päeva hiljem, kolm erinev rühmade matemaatikud postitasid mõne tunni jooksul üksteisest töid, mis tuginesid Gilmeri tööle. Täiendavad lisad dokumendid Järgneb, kuid näib, et esialgne puhang on Gilmeri meetodid viinud nii kaugele kui võimalik; 50% saavutamine nõuab tõenäoliselt uusi ideid.
Siiski oli mõne järeltöö autori jaoks 38% saavutamine suhteliselt lihtne ja nad imestasid, miks Gilmer seda lihtsalt ise ei teinud. Õigeks osutus lihtsaim seletus: pärast enam kui poole aastakümne matemaatika õppimist ei teadnud Gilmer lihtsalt, kuidas teha osa tehnilisest analüütilisest tööst, mis oli vajalik selle õnnestumiseks.
"Ma olin veidi roostes ja ausalt öeldes jäin ummikusse," ütles Gilmer. "Kuid ma ootasin innukalt, kuhu kogukond selle viib."
Kuid Gilmer arvab, et samad asjaolud, mis jätsid ta praktikast välja, tegid tõenäoliselt tema tõestuse võimalikuks.
"See on ainus viis, kuidas ma saan seletada, miks ma aspirantuuris aasta aega sellele probleemile mõtlesin ja edu ei saavutanud, jätsin matemaatika pooleks kuueks aastaks, siis pöördusin probleemi juurde ja tegin läbimurde," ütles ta. "Ma ei tea, kuidas seda seletada muul viisil, kui masinõppes olemine kallutas mu mõtlemist."
Parandus: Jaanuar 3, 2023
Algne pealkiri viitas Gilmerile kui "Google'i insenerile". Tegelikult on ta teadlane.
