Presenetljiv dokaz računalništva osupnil matematike

V nedeljo, 5. februarja, sta Olof Sisask in Thomas Bloom prejela e-poštno sporočilo z osupljivim odkritjem o največjem nerešenem problemu na njunem področju. Zander Kelley, podiplomski študent na Univerzi Illinois, Urbana-Champaign, je poslal Sisaska in Blooma članek, ki ga je napisal z Raghu Meka s Kalifornijske univerze v Los Angelesu. Oba, Kelley in Meka, sta bila računalničarja, intelektualni svet, ločen od aditivne kombinatorike, ki jo preučujeta Sisask in Bloom.

»Moje misli so bile preprosto navdušene. Kot, počakajte, ali so to res storili?« je dejal Sisask, predavatelj na univerzi v Stockholmu. Kelley in Meka, avtsajderja na področju kombinatorike, sta povedala, da sta odkrila novo – in dramatično nižjo – omejitev velikosti nabora celih števil, v katerem nobena tri niso enakomerno razporejena (izključuje kombinacije, kot so 3, 8 in 13). ali 101, 201 in 301).

Trditev Kelleyja in Meke je podrla prejšnji rekord, dosežen leta 2020 Sisask in Bloom, ki je raziskovalec na Univerzi v Oxfordu. »Delo Blooma in Sisaska – zelo močno delo – res je dalo vtis, da ga je izjemno težko izboljšati,« je dejal Ben Green, Bloomov kolega na Oxfordu. "Izgledalo je zelo zataknjeno tam, kjer je."

Čeprav sta imela Bloom in Sisask druge nujne zadeve v času, ko sta prejela e-pošto – Bloom je pravkar posvojil kužka, medtem ko je bil Sisask sredi selitve – sta se hitro lotila preverjanja novega dokumenta.

V nekaj dneh sta bila Bloom in Sisask prepričana, da je novi dokaz pravilen. Sisask je to označil za "največji rezultat na tem območju v zadnjih 20 letih." V želji, da bi drugi cenili Kelleyjeve in Mekine zamisli, sta pripravila Poročilo razlago dokaza z izrazi, ki so bolj znani matematikom.

Meka je dejal, da je bil odziv skupnosti »bolj pozitiven, kot sem mislil. Čudovito je videti vse povratne informacije.”

Dolgotrajen napredek

Zaporedja enakomerno razporejenih števil, ki sta se jim Kelley in Meka skušala izogniti, se imenujejo aritmetične progresije. Lahko trajajo večno ali vsebujejo le nekaj izrazov. Kelley in Meka sta se osredotočila na napredovanja, sestavljena iz samo treh števil, pri čemer sta sledila liniji raziskav, ki so pogosto sledile Papir 1936 avtorja Paul Erdős in Paul Turán.

Erdős in Turán sta želela vedeti, koliko števil je manjših od neke zgornje meje N lahko vstavite v niz, ne da bi ustvarili tričlenske aritmetične progresije. N lahko 1,000, 1 milijon ali kakšno nepredstavljivo veliko število. Domnevali so, da kot N naraščal, bi moral nabor brez napredovanja treh členov postati neverjetno redek. Ustvarjanje takšnega kompleta bi bilo kot zbiranje čevljev, pri čemer bi vztrajali, da noben par ni enake barve. Morda bi lahko nadaljevali v nedogled, a ko je vaša zbirka postajala večja, bi jo vedno počasneje dodajali.

"Obstaja neka struktura, ki se bo pojavila v nizu, ne glede na to, kako ste izbrali niz," je pojasnil Meka. "Kako velik komplet resnično potrebujete, da zagotovite, da imate to strukturo notri?"

Leta 1946 Felix Behrend našli način za sestavo množic števil med 1 in N brez kakršnega koli napredovanja v treh členih. Njegova metoda je povzročila nize, ki so postali večji N naredil, a boleče počasi. Kdaj N je 100,000, Behrendova množica vsebuje le 171 elementov. Kdaj N je 1 milijon, ima njegov niz 586 števil — manj kot 0.06 % števil med 1 in 1 milijonom.

Behrendovi nizi so matematikom dali podlago za delo: največji niz brez tričlenskega napredovanja bi moral biti vsaj tako velik kot Behrendov. Leta 1953 je Klaus Roth zagotovil zgornjo mejo, iskanje praga, čez katerega mora niz neizogibno vsebovati napredovanje treh členov.

Roth je dokazal domnevo Erdősa in Turána s tem, da je pokazal, da kot N postane večji, bo niz brez napredovanja treh členov vseboval vedno manjši del števil med 1 in N. Toda Rothova zgornja meja je bila daleč od Behrendovega dna. Behrend je pokazal, da se lahko 0.06 % elementov med 1 in 1 milijonom prilega v niz brez napredovanja. Čeprav je Rothovo formulo težko natančno izračunati, še zdaleč ni tako nizka – po grobi oceni je odstotek omejen na približno 40 %.

Toda bolj opazno kot ta posebna vrzel je bilo splošno obnašanje obeh formul. Narišite delež elementov med 1 in N ki jih predstavlja vsaka formula, in videli boste, da se Behrendovo število hitro skrči na nič N raste. Rothov ulomek pa drsi proti ničli, vendar počasi in nežno. Dve krivulji sta zelo različnih oblik in pravi delež elementov, ki ležijo v množici brez aritmetičnih progresij, bi lahko, kolikor so vedeli matematiki, ležal kjerkoli med njima.

Z začetkom v osemdesetih letih prejšnjega stoletja je "veliko število resnično slavnih matematikov naredilo dolgo zaporedje precej postopnih izboljšav," je dejal Green. Vsake toliko časa je kdo Rothovo zgornjo mejo potisnil za las ali dva navzdol, sčasoma pa se je precej znižala. Nasprotno pa se Behrendova spodnja meja ni premaknila desetletja. Matematiki so začeli razmišljati, da Behrend morda ni bil daleč od pravega odgovora, je dejal Bloom.

Dokler Kelley in Meka nista prispela v začetku leta 2023, je bila največja velikost niza brez napredovanja zapisana od spodaj z Behrendovo formulo, od zgoraj pa z Bloomovo in Sisaskovo formulo. Članek Blooma in Sisaska iz julija 2020 je presegel kritični "logaritemski" prag s tem, da je pokazal, da mora niz brez napredovanja imeti bistveno manj kot N/(dnevnik N) elementi. Toda njihov rezultat je bil še vedno visoko nad Behrendovim. Nova zgornja meja Kelleyja in Meke je drastično bližje tlom, ki jih je postavil Behrend.

"Meka in Kelley sta nekako preskočila ves ta postopni napredek," je dejal Terence Tao, ugledni matematik na UCLA.

Njihova formula je skoraj enaka Behrendovi, le z nekaj spremenjenimi parametri. Kot N približuje neskončnosti, se bo graf Kelleyjeve in Mekove formule sčasoma usedel v krivuljo, ki je podobna Behrendovi krivulji. "Vsaka vezava te oblike se je prej zdela kot nemogoče sanje," je dejal Bloom.

"Resnično sem bil čisto osupel, da so naredili takšno izboljšavo," je dejal Green.

Drugačen pristop

 Čeprav se Kelley in Meka še nikoli nista v celoti lotila čistih matematičnih raziskav, so jima bile aritmetične progresije znane, ko sta začela. Na splošno računalniški znanstveniki "lačno iščejo tehnike, ki bi rešile naše težave," je dejal Kelley. Orodja, ki so se v preteklosti uporabljala za preučevanje velikosti niza brez napredovanja, so postala široko uporabljena v podpodročju teorije kompleksnosti računalništva. Problem zmanjševanja velikosti takšne množice je teoretikom kompleksnosti dobro znan kot najpomembnejši primer uporabe tehnik, ki preiskujejo notranjo strukturo množic.

Konec leta 2021 sta Kelley in Meka analizirala možnosti, da bi ekipa igralcev v določeni igri sodelovanja lahko zmagala, kar je standardna vrsta računalniškega problema. Prišlo jim je na misel, da bi bile lahko v pomoč tehnike iz raziskav o velikosti sklopov brez napredovanja. Vendar so ugotovili, da je lažje neposredno preučevati te tehnike kot jih uporabiti v igri sodelovanja. "Moja najboljša zamisel o tem, kako doseči napredek pri tej težavi [je] bila, da dejansko izboljšam samo orodje, ne pa da ga uporabim na bolj pameten način," je dejal Kelley.

"V nekem trenutku smo se le odločili, da bomo neposredno obravnavali to vprašanje," se je spomnil Meka. Šest mesecev kasneje sta oba raziskovalca ugotovila svojo strategijo in sta morala samo ugotoviti, kako svojo metodo uporabiti pri obravnavanem problemu.

Če želite videti, kako so prišli do svoje nove zgornje meje, vzemite kateri koli niz številk med 1 in N. Pokliči A. Gostota A je odstotek števil med 1 in N ki vključuje. Ker obstaja veliko možnih aritmetičnih progresij med 1 in N, če ne izberete elementov za A previdno, poljubno A z visoko gostoto bo verjetno vseboval veliko aritmetičnih progresij.

Kelley in Meka sta si v svojem dokazu to predstavljala A imel malo ali nič aritmetičnih napredovanj, zato so poskušali izslediti posledice. če A je bila dovolj gosta, so pokazale, da odsotnost napredovanj zahteva raven strukture znotraj A to bi neizogibno povzročilo protislovje, kar pomeni, da A mora navsezadnje vsebovati vsaj eno napredovanje.

Da bi razumeli to strukturo, so upoštevali niz A + A, ki je sestavljena iz vseh števil, sestavljenih s seštevanjem dveh elementov A. Opazili so, da če A vsebuje sorazmerno malo aritmetičnih napredovanj, kar pomeni redundanco med elementi A + A: Različni pari številk iz A pogosto seštejejo isto število.

Gostoto lahko definiramo ne le v primerjavi z vsemi celimi števili med 1 in N ampak v primerjavi z neko podmnožico - recimo samo soda cela števila v tem intervalu ali samo večkratniki 3. Kelley in Meka sta uporabila odvečne vrednosti v A + A najti podmnožico celih števil, kjer so elementi A so bili še posebej pogosti.

Če bi A vseboval na primer nesorazmerno veliko večkratnikov števila 3, bi se Kelley in Meka nato osredotočila na del, ki vključuje večkratnike števila 3. To strategijo sta ponavljala znova in znova. Vsakič, ko so našli manjše in manjše podmnožice celih števil, nad katerimi Agostota bi še naprej rasla in rasla. na primer A lahko vsebuje 10 % celih števil med 1 in N, 15 % večkratnikov števila 3 v tem intervalu in 25 % sodih večkratnikov števila 3.

Zgodi se nekaj zanimivega, ko A je velik. Če postopek ponavljamo, se gostota A v neki podmnožici presega 100 %. To je seveda nemogoče. A lahko vsebuje, recimo, vse večkratnike 24, vendar ne more vsebovati več kot vseh. Ta paradoks nastane le, če A je na začetku dovolj velik, ko pa se, pomeni predpostavko, da A ne vsebuje nobene aritmetične progresije je moralo biti napačno.

To je "zmagajoč argument", ko A je velik, je rekel Meka. Bodisi A vključuje veliko aritmetičnih progresij ali pa je v njej veliko odvečnosti A + A — v tem primeru bi lahko uporabili postopek iskanja podmnožic (imenovan »strategija povečanja gostote«), da pokažejo, da se mora v A. Čeprav je strategija povečevanja gostote dobro preizkušen načrt na terenu, je Kelleyju in Meki uspelo, da deluje za manjše Aje kot kdaj koli prej. S tem so odkrili novo zgornjo mejo za velikost niza brez napredovanja.

Kelley in Meka sta ustvarila edinstveno kombinacijo idej iz načrta povečanja gostote. Namesto da bi pripravili popolnoma nov okvir, so ponovno razmislili o načinu, kako so našli svojo gosto podmnožico. Za to so uporabili tehniko, ki so jo poimenovali "presejanje", ki je sestavljena iz premika njihovega niza za konstantno količino, njegovega sekanja s samim seboj in ponavljanja postopka veliko, velikokrat. Kar ostane po številnih krogih preseka, je visoko strukturiran niz s predvidljivimi lastnostmi. Čeprav je bilo presejanje uporabljeno v drugih dokumentih, ga nikoli niso preizkusili pri problemu napredovanja treh členov.

gledati nazaj

Kelley in Meka sta šokantno znižala omejitev velikosti nabora brez napredovanja, tako da sta v tradicionalne metode vnesla zanemarjena orodja, kot je presejanje. "Kelley in Meka sta nam pokazala, da so nekako te tehnike, ki so sedele tam na prostem, veliko močnejše, kot smo domnevali," je dejal Bloom. Glede na novo odkrito učinkovitost teh orodij je dodal, "moramo se vrniti in ponovno pregledati vse."

Strategija povečanja gostote se je prvič pojavila v Rothovem članku pred 70 leti in se od takrat uporablja v večini člankov o aritmetičnih progresijah. Green je bil presenečen, da je ogrodje mogoče uporabiti za dokazovanje tako nizke meje, kot sta Kelley in Meka. "Mislil sem, da bo potrebno nekaj popolnoma, radikalno drugačnega," je dejal.

Kelley je navdušen nad nadaljevanjem svojega pohoda v matematiko. "Ne manjka mi upanja in sanj o številnih različnih težavah, za katere bi menil, da so vsaj duhovno povezane s tem," je dejal.

To, da sta Kelley in Meka uspela opaziti moč nekoč spregledanih idej, kaže na pogosto moteno naravo matematičnega napredka - lastnost, ki je za Taa bolj blagoslov kot prekletstvo. »Ni vedno tako, da matematika postaja vedno težja in težja,« je dejal. "Hvala bogu."