Bevezetés
Október közepén Justin Gilmer Kaliforniából New Yorkba repült, hogy részt vegyen egy barátja esküvőjén. A keleti parton meglátogatta korábbi tanácsadóját, Michael Saks, a Rutgers Egyetem matematikusa, ahol Gilmer hét évvel korábban doktorált.
Saks és Gilmer ebéd közben utolérte, de nem beszéltek matekról. Valójában Gilmer nem gondolt komolyan a matematikára, amióta 2015-ben végzett a Rutgersnél. Ekkor döntötte el, hogy nem akar egyetemi karriert, és inkább programozni kezdett. Miközben ő és Saks ettek, Gilmer mesélt régi mentorának a Google-nál végzett munkájáról, ahol gépi tanulással és mesterséges intelligenciával foglalkozik.
Napsütéses volt aznap, amikor Gilmer meglátogatta Rutgerst. Séta közben felidézte, hogyan töltötte 2013-ban egy év nagy részét ugyanazokat az egyetemi utakat járva, és egy olyan problémára gondolt, amelyet a szakszervezeti zárt sejtésnek neveztek. Rögzítés volt, bár eredménytelen: Gilmernek minden erőfeszítése ellenére csak sikerült megtanítania magát, hogy miért olyan nehéz megoldani a számhalmazokkal kapcsolatos egyszerűnek tűnő problémát.
„Azt hiszem, sokan addig gondolkodnak a problémán, amíg meg nem elégednek azzal, hogy megértik, miért nehéz. Valószínűleg több időt töltöttem vele, mint a legtöbb ember” – mondta Gilmer.
Októberi látogatása után váratlan dolog történt: új ötlete támadt. Gilmer azon kezdett gondolkodni, hogyan alkalmazhatna az információelméletből származó technikákat a szakszervezettel zárt sejtés megoldására. Egy hónapig folytatta az ötletet, és minden alkalommal arra számított, hogy kudarcot vall. Ehelyett azonban folyamatosan nyílt az út a bizonyításhoz. Végül november 16-án ő a maga nemében első eredményt tett közzé ami a matematikusok nagy részét a teljes sejtés bizonyítása felé viszi.
A lap az utómunkálatok rohamát indította el. Más intézmények mellett az Oxfordi Egyetem, a Massachusetts Institute of Technology és az Institute for Advanced Study matematikusai gyorsan építettek Gilmer új módszereire. Mielőtt azonban megtették volna, feltették a maguk kérdését: Ki ez a srác?
Félig tele
Az unió zárt sejtése halmazoknak nevezett számok gyűjteményeiről szól, mint például {1, 2} és {2, 3, 4}. A halmazokon műveleteket hajthat végre, beleértve az egyesülésüket, ami azt jelenti, hogy kombinálja őket. Például az {1, 2} és a {2, 3, 4} uniója {1, 2, 3, 4}.
A halmazok gyűjteménye vagy családja „zártnak” minősül, ha a család bármely két halmazának egyesülése megegyezik a család bármely létező halmazával. Vegyük például ezt a négy készletből álló családot:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Bármelyik pár kombinálásával olyan készletet kap, amely már a családban van, így a családi unió zárttá válik.
A matematikusok már az 1960-as években csevegtek az unió által zárt sejtés változatairól, de az első hivatalos nyilatkozatát 1979-ben kapta meg egy közleményben. Frankl Péter, az 1980-as években Japánba emigrált magyar matematikus, aki az utcai fellépést is elfoglaltságai között tartja számon.
Frankl úgy sejtette, hogy ha egy halmazcsalád uniózárt, akkor legalább egy elemének (vagy számának) kell lennie, amely a halmazok legalább felében szerepel. Ez két okból is természetes küszöb volt.
Először is vannak könnyen elérhető példák a szakszervezeti zárt családokra, amelyekben minden elem pontosan a halmazok 50%-ában szerepel. Mint az összes különböző készlet, amelyet például 1-től 10-ig készíthet. 1,024 ilyen halmaz létezik, amelyek egy unió-zárt családot alkotnak, és mind a 10 elem 512-ben szerepel. Másodszor pedig abban az időben, amikor Frankl azt a sejtést fogalmazta meg, senki sem hozott példát olyan szakszervezeti zárt családra, amelyben a sejtés nem érvényesült.
Tehát az 50% jó előrejelzésnek tűnt.
Ez nem jelentette azt, hogy könnyű volt bizonyítani. A Frankl írása óta eltelt években kevés eredmény született. Gilmer munkája előtt ezekben a papírokban csak olyan küszöbértékeket sikerült megállapítaniuk, amelyek a családban lévő halmazok számától függően változtak (ellentétben azzal, hogy minden méretű halmazcsalád esetében ugyanaz az 50%-os küszöb).
„Úgy tűnik, ennek könnyűnek kell lennie, és sok olyan problémához hasonlít, amelyek könnyűek, de ellenáll a támadásoknak” – mondta. Will Sawin a Columbia Egyetemen.
Az előrehaladás hiánya a probléma trükkös természetét és azt a tényt egyaránt tükrözte, hogy sok matematikus inkább nem gondolt rá; attól tartottak, hogy éveket veszítenek el karrierjükből egy olyan elbűvölő probléma után, amelyet lehetetlen megoldani. Gilmer emlékszik egy napra 2013-ban, amikor elment Saks irodájába, és felhozta a szakszervezet által bezárt sejtést. Tanácsadója – aki korábban maga is birkózott a problémával – kis híján kidobta a szobából.
„Mike azt mondta: „Justin, újra elgondolkodtatsz ezzel a problémával, és én nem akarom ezt” – mondta Gilmer.
A bizonytalanság bepillantása
Rutgersnél tett látogatását követően Gilmer körbeforgatta a problémát a fejében, és megpróbálta megérteni, miért olyan nehéz. Egy alapvető ténnyel sürgette magát: Ha egy 100 készletből álló családod van, akkor 4,950 különböző módon választhatsz kettőt, és csatlakozhatsz egymáshoz. Aztán feltette magának a kérdést: Hogyan lehetséges, hogy 4,950 különböző unió mindössze 100 halmazra leképeződik, ha ezekben az uniókban egyetlen elem sem jelenik meg legalább bizonyos gyakorisággal?
Még akkor is a bizonyítás felé tartott, bár még nem tudta. Az információelmélet technikái, amelyek szigorú gondolkodási módot adnak arról, hogy mire számíthatunk, ha véletlenszerűen húzunk egy pár tárgyat, elvezetnék őt.
Az információelmélet a 20. század első felében alakult ki, leghíresebb Claude Shannon 1948-as cikkével, „A kommunikáció matematikai elmélete.” A lap pontos módszert adott az üzenet elküldéséhez szükséges információmennyiség kiszámítására, a bizonytalanság mértéke alapján, hogy pontosan mit mond az üzenet. Ez a link - információ és bizonytalanság között – volt Shannon figyelemre méltó, alapvető meglátása.
Hogy egy játék példáját vegyük, képzeld el, hogy ötször feldobok egy érmét, és elküldöm neked a kapott sorozatot. Ha ez egy normál érme, akkor öt bit információra van szükség az átvitelhez. De ha ez egy betöltött érme – mondjuk 99%-os valószínűséggel a fejen landol –, akkor sokkal kevesebbre van szükség. Például előre megállapodhatunk abban, hogy 1-est (egyetlen információ) küldök, ha a betöltött érme mind az ötször fejjel landol, ami nagy valószínűséggel meg is történik. A tisztességes érmefeldobásban több meglepetés ér, mint egy elfogultnál, és ezért több az információ.
Ugyanez a gondolkodás vonatkozik a számkészletekben található információkra is. Ha van egy zárt készletcsaládom – mondjuk az 1,024-től 1-ig tartó 10 készlet – véletlenszerűen kiválaszthatok két készletet. Akkor közölhetném veled az egyes készletek elemeit. Az üzenet elküldéséhez szükséges információ mennyisége tükrözi az elemek körüli bizonytalanság mértékét: 50% az esélye például annak, hogy az első halmaz első eleme 1 (mivel az 1 a halmazok felében jelenik meg a család), ahogyan 50% esély van arra is, hogy a tisztességes érmefeldobások sorozatának első eredménye fejek.
Az információelmélet gyakran megjelenik a kombinatorikában, a matematikának az objektumok megszámlálásával foglalkozó területén, amit Gilmer végzős hallgatóként tanult. Ám amikor hazarepült Kaliforniába, attól tartott, hogy az amatőr naiv belátása volt, ahogyan az információelméletet a zárt unió sejtéseivel összekapcsolja: a dolgozó matematikusok bizonyára találkoztak már ezzel a fényes tárgykal, és a bolond aranyának tekintették. .
„Hogy őszinte legyek, kissé meglepett, hogy ez korábban senkinek nem jutott eszébe” – mondta Gilmer. – De talán nem kell meglepődnöm, mert én magam is egy éve gondolkodtam ezen, és ismertem az információelméletet.
Valószínűbb, mint nem
Gilmer éjszaka dolgozott a problémán, miután befejezte a Google-nál végzett munkáját, és hétvégenként október második felében és november elején. Olyan ötletek ösztönözték, amelyeket matematikusok egy csoportja évekkel korábban egy nyílt együttműködés egy Tim Gowers nevű prominens matematikus blogján. Egy tankönyvvel is dolgozott mellette, hogy megkeresse az elfelejtett képleteket.
„Azt hinné az ember, aki nagyszerű eredményt produkál, nem kellene elolvasnia a 2. fejezetet Az információelmélet elemei, de megtettem – mondta Gilmer.
Gilmer stratégiája az volt, hogy egy szakszervezeti zárt családot képzeljen el, amelyben egyetlen elem sem szerepel az összes halmaz 1%-ában – ez egy ellenpélda, amely, ha valóban létezne, meghamisítaná Frankl sejtését.
Tegyük fel, hogy ebből a családból véletlenszerűen választ ki két halmazt, az A-t és a B-t, és egyenként mérlegeli azokat az elemeket, amelyek ezekben a halmazokban lehetnek. Most kérdezd meg: Mennyi az esély arra, hogy az A halmaz tartalmazza az 1-es számot? És a B-t? Mivel minden elemnek kicsivel kevesebb, mint 1% az esélye, hogy egy adott halmazban megjelenjen, nem számítana arra, hogy sem A, sem B 1-et tartalmaz. Ami azt jelenti, hogy nem sok meglepetés – és kevés információ nyerhető –, ha megtudja, hogy valójában egyik sem csinál.
Ezután gondolja át annak esélyét, hogy A és B uniója 1-et tartalmaz. Ez még mindig nem valószínű, de nagyobb valószínűséggel, mint az esély, hogy megjelenik az egyes halmazok bármelyikében. Ez annak a valószínűségnek az összege, hogy megjelenik A-ban, és annak a valószínűségnek, hogy megjelenik B-ben, mínusz az a valószínűség, hogy mindkettőben megjelenik. Tehát talán 2% alatt.
Ez még mindig alacsony, de közelebb van az 50-50-es ajánlathoz. Ez azt jelenti, hogy több információra van szükség az eredmény megosztásához. Más szóval, ha van egy zárt unió család, amelyben egyetlen elem sem jelenik meg az összes halmaz legalább 1%-ában, akkor több információ van a két halmaz egyesülésében, mint magában a halmazokban.
„Rendkívül okos az ötlet, hogy elemről elemre tárjuk fel a dolgokat, és nézzük a tanult információ mennyiségét. Ez a bizonyíték fő gondolata” – mondta Ryan Alweiss a Princetoni Egyetemen.
Ezen a ponton Gilmer kezdett közelíteni Frankl sejtéséhez. Ez azért van így, mert könnyen kimutatható, hogy egy szakszervezettel zárt családban a két halmaz egyesülése szükségszerűen kevesebb információt tartalmaz, mint maguk a halmazok – nem többet.
Hogy megtudd, miért, gondolj arra a szakszervezettel zárt családra, amely azt az 1,024 különböző halmazt tartalmazza, amelyeket az 1-től 10-ig tartó számokból összeállíthatsz. Ha véletlenszerűen választasz ki kettőt ezek közül, átlagosan öt elemet tartalmazó halmazt kapsz. (Ebből az 1,024 halmazból 252 öt elemet tartalmaz, így ez a legelterjedtebb halmazméret.) Valószínűleg egy körülbelül hét elemből álló uniót is kapsz. De csak 120 különböző módja van a hét elemet tartalmazó készletek készítésének.
A lényeg az, hogy több a bizonytalanság két véletlenszerűen kiválasztott halmaz tartalmát illetően, mint az egyesülésükkel kapcsolatban. Az unió a nagyobb, több elemet tartalmazó készletek felé hajlik, amelyekre kevesebb lehetőség van. Ha egy szakszervezettel zárt családban két halmaz egyesülését veszed, akkor nagyjából tudod, hogy mit fogsz kapni – például amikor feldobsz egy elfogult érmét –, ami azt jelenti, hogy az unió kevesebb információt tartalmaz, mint a halmazok, amelyekből áll.
Ezzel Gilmernek bizonyítéka volt. Tudta, ha a halmazok akár 1%-ában sem jelenik meg elem, az unió kénytelen több információt tartalmazni. De a szakszervezetnek kevesebb információt kell tartalmaznia. Ezért legalább egy olyan elemnek kell lennie, amely a halmazok legalább 1%-ában szerepel.
Lépj 50-re
Amikor Gilmer november 16-án közzétette a bizonyítékát, egy megjegyzést tett hozzá, hogy úgy gondolta, hogy módszere segítségével még közelebb kerülhet a teljes sejtés bizonyításához, ami potenciálisan 38%-ra emelheti a küszöböt.
Öt nappal később, három különböző csoportok A matematikusok közül néhány órán belül egymás után közzétettek olyan dolgozatokat, amelyek Gilmer munkájára építettek. További papírok követ, de úgy tűnik, hogy a kezdeti robbanás egészen messzire vitte Gilmer módszereit; 50% elérése valószínűleg további új ötleteket igényel.
Ennek ellenére a nyomon követési cikkek szerzőinek egy része számára viszonylag egyszerű volt elérni a 38%-ot, és azon töprengtek, hogy Gilmer miért nem tette meg ezt egyszerűen. A legegyszerűbb magyarázat bizonyult a helyesnek: több mint fél évtizednyi matematika után Gilmer egyszerűen nem tudta, hogyan végezze el a sikerhez szükséges technikai elemző munkát.
„Kicsit rozsdás voltam, és hogy őszinte legyek, elakadtam” – mondta Gilmer. „De alig vártam, hogy a közösség hova viszi ezt.”
Gilmer mégis úgy gondolja, hogy ugyanazok a körülmények, amelyek kihagyták a gyakorlatból, valószínűleg először is lehetővé tették a bizonyítást.
„Csak így tudom megmagyarázni, hogy miért gondolkodtam a problémán egy évig a posztgraduális iskolában, és nem jutottam előre, hat évre otthagytam a matematikát, majd visszatértem a feladathoz, és sikerült áttörést hoznom” – mondta. „Nem tudom, hogyan magyarázzam el, azon kívül, hogy a gépi tanulásban való részvétel elfogult a gondolkodásomban.”
Javítás: Január 3, 2023
Az eredeti címsor Gilmerre „Google mérnökként” hivatkozott. Valójában kutató.
