Število 15 opisuje skrivno mejo neskončne mreže

Kot dodiplomski študent Univerze v Čilu, Bernardo Subercaseaux slabo gledal na uporabo računalnikov za matematiko. Zdelo se je v nasprotju z resničnim intelektualnim odkritjem.

"Nek instinkt ali čustvena reakcija je proti uporabi računalnikov za reševanje vaših težav, kot da je to v nasprotju z idealno lepoto ali eleganco fantastičnega argumenta," je dejal.

Toda leta 2020 se je Subercaseaux zaljubil in kot se pogosto zgodi, so se njegove prioritete spremenile. Predmet njegove obsedenosti je bilo vprašanje, ki ga je videl na spletnem forumu. Večino problemov je pregledal in pozabil, ta pa mu je padel v oči. Potegnil je desno.

"Prvo, kar sem naredil, je bilo, da sem všečkal objavo v skupini na Facebooku, v upanju, da bom pozneje prejel obvestilo, ko bo nekdo drug objavil rešitev," je dejal.

Vprašanje je bilo o polnjenju neskončne mreže s števili. Kot se je izkazalo, to ni bil problem, ki bi ga človek rešil na škrjančku. Da bi to naredil, je moral Subercaseaux zapustiti Čile in se odpraviti na podiplomski študij na univerzo Carnegie Mellon.

Tam se je avgusta 2021 naključno srečal z Marijn Heule, računalničar, ki uporablja ogromno računalniško moč za reševanje težkih matematičnih vprašanj. Subercaseaux je vprašal Heuleja, ali želi poskusiti rešiti problem, s čimer se je začelo sodelovanje, ki je doseglo vrhunec januarja letos dokaz kar lahko povzamemo z eno samo številko: 15.

Na vse možne načine

V 2002, Wayne Goddard z Univerze Clemson in nekateri podobno misleči matematiki so pljuvali po problemih v kombinatoriki in poskušali najti nove zasuke o glavnih vprašanjih tega področja o barvanju zemljevidov ob določenih omejitvah.

Sčasoma so pristali na problemu, ki se začne z mrežo, kot list milimetrskega papirja, ki traja večno. Cilj je, da ga napolnimo s številkami. Obstaja samo ena omejitev: razdalja med vsako pojavitvijo istega števila mora biti večja od števila samega. (Razdalja se meri s seštevanjem navpične in vodoravne ločitve, metrika, znana kot razdalja "taksi kabina", ker spominja na premikanje po mrežastih mestnih ulicah.) Par 1 ne more zasesti sosednjih celic, ki imajo razdaljo taksija 1, lahko pa jih postavimo v neposredno diagonalne celice, ki imajo razdaljo 2.

Sprva so Goddard in njegovi sodelavci želeli vedeti, ali je sploh mogoče zapolniti neskončno mrežo s končno množico števil. Toda do takrat, ko on in njegovi štirje sodelavci objavil to težavo z "barvanjem embalaže". v reviji Ars Combinatoria leta 2008 so dokazali, da jo je mogoče rešiti z 22 številkami. Vedeli so tudi, da je ni mogoče rešiti s samo petimi številkami. To je pomenilo, da je dejanski odgovor na problem – minimalno število potrebnih številk – ležal nekje vmes.

Raziskovalci pravzaprav niso zapolnili neskončne mreže. Ni jim bilo treba. Namesto tega je dovolj, da vzamete majhno podmnožico mreže - recimo kvadrat 10 krat 10 - to napolnite s številkami, nato pa pokažete, da lahko kopije izpolnjene podmnožice postavite eno poleg druge, tako kot bi pokrili tla s kopijami ploščic.

Ko je Subercaseaux prvič izvedel za težavo, je začel iskati ploščice s peresom in papirjem. Skiciral bi mrežo številk, jih prečrtal, poskusil znova. Kmalu se je naveličal tega pristopa in prosil prijatelja, naj oblikuje spletno orodje, ki je spominjalo na igro Minolovec in mu omogočalo hitrejše preizkušanje kombinacij. Po še nekaj tednih dela se je prepričal, da mreže z osmimi številkami ni mogoče zapakirati, vendar ni mogel priti dlje od tega – bilo je preprosto preveč možnih oblik, ki bi jih ploščice lahko sprejele, in preveč različne načine, kako bi jih lahko napolnili s številkami.

Težava, kot bo kasneje postalo jasno, je v tem, da je veliko težje pokazati, da mreže ni mogoče pokriti z določenim nizom števil, kot pokazati, da lahko. "Ne kaže le, da en način ne deluje, ampak kaže, da vsi možni načini ne delujejo," je dejal Goddard.

Potem ko je Subercaseaux začel delati na CMU in prepričal Heuleja, da sodeluje z njim, so hitro našli način, kako pokriti mrežo s 15 številkami. Prav tako jim je uspelo izključiti možnost rešitve problema le z 12 številkami. Toda njun občutek zmagoslavja je bil kratkotrajen, saj sta ugotovila, da sta zgolj reproducirala rezultate, ki so bili prisotni že dolgo časa: že leta 2017 so raziskovalci vedeli, da odgovor ni nižji od 13 ali višji od 15. .

Za študenta prvega letnika, ki je uspešnega profesorja zvabil k reševanju njegove težave s hišnimi ljubljenčki, je bilo to vznemirljivo odkritje. »Bil sem zgrožen. V bistvu sem več mesecev delal na problemu, ne da bi se tega zavedal, in še huje, naredil sem Marijna zapravlja svoj čas za to!« Subercaseaux Napisal v objavi v spletnem dnevniku, ki povzame njihovo delo.

Heule pa je našel odkritje preteklih rezultatov poživljajoče. Dokazal je, da se je drugim raziskovalcem problem zdel dovolj pomemben, da so na njem delali, in zanj potrdil, da je edini rezultat, ki ga je vredno doseči, popolna rešitev problema.

"Ko smo ugotovili, da smo na tem problemu delali 20 let, je to popolnoma spremenilo sliko," je dejal.

Izogibanje vulgarnemu

Z leti je Heule naredil kariero z iskanjem učinkovitih načinov iskanja med številnimi možnimi kombinacijami. Njegov pristop se imenuje reševanje SAT - okrajšava za "satisfiability". Vključuje sestavo dolge formule, imenovane logična formula, ki ima lahko dva možna rezultata: 0 ali 1. Če je rezultat 1, je formula resnična in je težava rešena.

Za problem barvanja pakiranja lahko vsaka spremenljivka v formuli predstavlja, ali je dana celica zasedena z danim številom. Računalnik išče načine dodeljevanja spremenljivk, da bi zadostil formuli. Če računalnik to zmore, veste, da je mogoče zapakirati mrežo pod pogoji, ki ste jih nastavili.

Na žalost bi lahko preprosto kodiranje problema barvanja embalaže kot logična formula segalo na več milijonov izrazov - računalnik ali celo flota računalnikov bi lahko večno delovala in preizkušala vse različne načine dodeljevanja spremenljivk v njem.

"Če bi poskušali izvajati to surovo silo, bi trajalo, dokler vesolje ne konča, če bi to storili naivno," je dejal Goddard. "Torej potrebujete nekaj kul poenostavitev, da bi zadevo znižali na nekaj, kar je sploh mogoče."

Poleg tega vsakič, ko problemu barvanja embalaže dodate številko, postane približno 100-krat težji zaradi načina, kako se možne kombinacije množijo. To pomeni, da če bi skupina računalnikov, ki delujejo vzporedno, lahko izključila 12 v enem samem dnevu izračuna, bi potrebovala 100 dni časa za izračun, da bi izključila 13.

Heule in Subercaseaux sta menila, da je razširitev računalniškega pristopa s surovo silo na nek način vulgarna. »Imeli smo več obetavnih zamisli, zato smo razmišljali 'Poskušajmo optimizirati naš pristop, dokler tega problema ne rešimo v manj kot 48 urah računanja v gruči,'« je dejal Subercaseaux.

Da bi to naredili, so morali najti načine, kako omejiti število kombinacij, ki jih mora poskusiti računalniški grozd.

"[Oni] tega ne želijo samo rešiti, ampak ga želijo rešiti na impresiven način," je dejal Aleksander Soifer Univerze Colorado, Colorado Springs.

Heule in Subercaseaux sta ugotovila, da je veliko kombinacij v bistvu enakih. Če poskušate ploščico v obliki diamanta zapolniti z osmimi različnimi številkami, ni pomembno, ali je prva številka, ki jo postavite, ena zgoraj in ena desno od sredinskega kvadrata ali ena spodaj in ena levo od sredinski trg. Obe postavitvi sta med seboj simetrični in omejujeta vašo naslednjo potezo na povsem enak način, zato ni razloga, da bi preverili obe.

Heule in Subercaseaux sta dodala pravila, ki so računalniku omogočila, da obravnava simetrične kombinacije kot enakovredne, kar je zmanjšalo skupni čas iskanja za faktor osem. Uporabili so tudi tehniko, ki jo je Heule razvil v prejšnjem delu, imenovano kocka in osvoji, kar jim je omogočilo, da preizkusijo več kombinacij vzporedno med seboj. Če veste, da mora določena celica vsebovati 3, 5 ali 7, lahko razdelite problem in preizkusite vsako od treh možnosti hkrati na različnih skupinah računalnikov.

Do januarja 2022 so te izboljšave Heuleju in Subercaseauxu omogočile, da sta izključila 13 kot odgovor na težavo z barvanjem embalaže v poskusu, ki je zahteval manj kot dva dni računalniškega časa. Tako sta imela dva možna odgovora: 14 ali 15.

Velik plus

Da bi izključili 14 - in rešili težavo - sta morala Heule in Subercaseaux najti dodatne načine za pospešitev računalniškega iskanja.

Sprva so napisali logično formulo, ki je dodelila spremenljivke vsaki posamezni celici v mreži. Toda septembra 2022 so ugotovili, da jim ni treba nadaljevati od celice do celice. Namesto tega so ugotovili, da je bolj učinkovito upoštevati majhne regije, sestavljene iz petih celic v obliki znaka plus.

Prepisali so svojo logično formulo, tako da je več spremenljivk predstavljalo vprašanja, kot so: Ali obstaja 7 nekje v tem območju v obliki plus? Računalniku ni bilo treba natančno identificirati, kje v regiji bi lahko bila 7. Samo ugotoviti je bilo treba, ali je bil notri ali ne - vprašanje, ki za odgovor zahteva bistveno manj računalniških virov.

"Imeti spremenljivke, ki govorijo le o plusih namesto o določenih lokacijah, se je izkazalo za veliko boljše kot govoriti o njih v določenih celicah," je dejal Heule.

S pomočjo učinkovitosti iskanja plus sta Heule in Subercaseaux novembra 14 v računalniškem eksperimentu izključila 2022, ki je na koncu vzel manj časa za izvedbo kot tisti, ki sta ga uporabila za izključitev 13. Naslednje štiri mesece sta preverjala, da ugotovitev računalnika je bila pravilna – skoraj toliko časa, kot so porabili, da so računalniku sploh omogočili, da je prišel do tega zaključka.

"Razveseljivo je bilo razmišljati, da je tisto, kar smo ustvarili kot stransko vprašanje v neki naključni reviji, povzročilo, da so skupine ljudi porabile, kot se je izkazalo, mesece svojega časa, ko so poskušale ugotoviti, kako to rešiti," Goddard rekel.

Za Subercaseauxa je bil to prvi pravi triumf v njegovi raziskovalni karieri. In čeprav to morda ni bila vrsta odkritja, ki ga je idealiziral, ko je prvič razmišljal o delu z matematiko, je ugotovil, da je na koncu imelo svoje lastne intelektualne nagrade.

"Ne razumem obrazca, če mi daš tablo in ti lahko pokažem, zakaj je 15," je dejal. »Vendar smo pridobili razumevanje, kako delujejo omejitve problema, koliko bolje je imeti 6 tukaj ali 7 tam. Pridobili smo veliko intuitivnega razumevanja.«