Numărul 15 descrie limita secretă a unei rețele infinite

Ca student la Universitatea din Chile, Bernardo Subercaseaux a avut o vedere slabă despre utilizarea computerelor pentru a face matematică. Părea în antiteză cu adevărata descoperire intelectuală.

„Există un instinct sau o reacție instinctă împotriva folosirii computerelor pentru a-ți rezolva problemele, ca și cum ar fi împotriva frumuseții sau eleganței ideale a unui argument fantastic”, a spus el.

Dar apoi, în 2020, Subercaseaux s-a îndrăgostit și, așa cum se întâmplă adesea, prioritățile lui s-au schimbat. Obiectul obsesiei sale a fost o întrebare pe care a văzut-o pe un forum online. Cele mai multe probleme le-a scanat și le-a uitat, dar aceasta i-a atras atenția. A glisat spre dreapta.

„Primul lucru pe care l-am făcut a fost să dau like postării din grupul Facebook, sperând să primesc o notificare mai târziu, când altcineva a postat o soluție”, a spus el.

Întrebarea era despre umplerea unei grile infinite cu numere. După cum s-a dovedit, nu a fost genul de problemă pe care o rezolvăm pe o ciocârlă. Pentru a face acest lucru, Subercaseaux a trebuit să părăsească Chile pentru o școală absolventă la Universitatea Carnegie Mellon.

Acolo, în august 2021, a avut o întâlnire fortuită cu Marijn Heule, un informatician care folosește puterea masivă de calcul pentru a rezolva întrebări grele de matematică. Subercaseaux l-a întrebat pe Heule dacă vrea să încerce problema, demarând o colaborare care a culminat în ianuarie o dovada care poate fi rezumat cu un singur număr: 15.

Fiecare Mod Posibil

În 2002, Wayne Goddard de la Universitatea Clemson și unii matematicieni care aveau păreri asemănătoare au pus probleme în combinatorică, încercând să vină cu noi răsturnări de situație la întrebările de bază ale domeniului despre hărțile de colorat, având în vedere anumite constrângeri.

În cele din urmă, au ajuns la o problemă care începe cu o grilă, ca o foaie de hârtie milimetrică care continuă pentru totdeauna. Scopul este să-l umpleți cu numere. Există o singură constrângere: distanța dintre fiecare apariție a aceluiași număr trebuie să fie mai mare decât numărul în sine. (Distanța este măsurată prin adunarea separării verticale și orizontale, o măsură cunoscută sub denumirea de distanță „taxicab” pentru felul în care seamănă cu deplasarea pe străzile urbane grilaje.) O pereche de 1 nu poate ocupa celulele alăturate, care au o distanță de taxi de 1, dar pot fi plasate în celule direct diagonale, care au o distanță de 2.

Inițial, Goddard și colaboratorii săi au vrut să știe dacă este chiar posibil să umple o grilă infinită cu un set finit de numere. Dar până atunci el și cei patru colaboratori ai săi a publicat această problemă de „colorare a ambalajului”. în revista Ars Combinatoria în 2008, au demonstrat că poate fi rezolvată folosind 22 de numere. De asemenea, știau că nu există nicio modalitate de a se rezolva cu doar cinci numere. Asta însemna că răspunsul real la problemă - numărul minim de numere necesare - se afla undeva la mijloc.

Cercetătorii nu au umplut de fapt o grilă infinită. Nu trebuiau. În schimb, este suficient să luați un mic subset al grilei - să zicem un pătrat de 10 pe 10 - umpleți-l cu numere, apoi arătați că copiile subsetului umplut pot fi plasate una lângă alta, așa cum ați acoperi un podea cu copii ale unei plăci.

Când Subercaseaux a aflat prima dată de problemă, a început să caute plăci folosind pix și hârtie. Schița grile de numere, le tăia și încerca din nou. S-a săturat curând de această abordare și i-a cerut unui prieten să proiecteze un instrument bazat pe web care să semene cu jocul Minesweeper și să-i permită să testeze combinații mai rapid. După încă câteva săptămâni de muncă, se convinsese că nu există nicio modalitate de a împacheta o grilă cu opt numere, dar nu a putut ajunge mai departe de atât – erau prea multe forme potențiale pe care plăcile le puteau lua și prea multe. moduri diferite în care ar putea fi umplute cu numere.

Problema, după cum va deveni clar mai târziu, este că este mult mai dificil să arăți că grila nu poate fi acoperită de un anumit set de numere decât să arăți că poate. „Nu arată doar că o singură cale nu funcționează, ci arată că toate modurile posibile nu funcționează”, a spus Goddard.

După ce Subercaseaux a început la CMU și l-a convins pe Heule să lucreze cu el, au găsit rapid o modalitate de a acoperi grila cu 15 numere. De asemenea, au putut exclude posibilitatea de a rezolva problema cu doar 12 numere. Dar sentimentele lor de triumf au fost de scurtă durată, deoarece și-au dat seama că au reprodus doar rezultate care existau de mult timp: încă din 2017, cercetătorii știau că răspunsul nu era mai mic de 13 sau mai mare de 15. .

Pentru un student de licență din primul an care a împins un profesor de mare anvergură să lucreze la problema lui de companie, a fost o descoperire neliniștitoare. „Am fost îngrozit. Practic lucram de câteva luni la o problemă fără să-mi dau seama de asta și și mai rău, o făcusem pe Marijn pierde timpul cu asta!” Subercaseaux scris într-o postare de blog recapitulând munca lor.

Heule a considerat totuși că descoperirea rezultatelor trecute este revigorantă. Acesta a demonstrat că alți cercetători au găsit problema suficient de importantă pentru a putea lucra și a confirmat pentru el că singurul rezultat care merită obținut a fost rezolvarea completă a problemei.

„Odată ce ne-am dat seama că au fost 20 de ani de muncă la problemă, asta a schimbat complet imaginea”, a spus el.

Evitarea Vulgarului

De-a lungul anilor, Heule și-a făcut o carieră prin găsirea unor modalități eficiente de a căuta printre vaste combinații posibile. Abordarea sa se numește SAT solving - prescurtare de la „satisfăcăre”. Implică construirea unei formule lungi, numită formulă booleană, care poate avea două rezultate posibile: 0 sau 1. Dacă rezultatul este 1, formula este adevărată, iar problema este satisfăcută.

Pentru problema de colorare a împachetarii, fiecare variabilă din formulă poate reprezenta dacă o celulă dată este ocupată de un număr dat. Un computer caută modalități de atribuire a variabilelor pentru a satisface formula. Dacă computerul o poate face, știți că este posibil să împachetați grila în condițiile pe care le-ați setat.

Din păcate, o codificare simplă a problemei de colorare a împachetarii ca o formulă booleană s-ar putea extinde la multe milioane de termeni - un computer, sau chiar o flotă de computere, ar putea testa pentru totdeauna toate modalitățile diferite de atribuire a variabilelor în cadrul acestuia.

„A încerca să faci această forță brută ar dura până când universul se va termina dacă ai face-o naiv”, a spus Goddard. „Așa că aveți nevoie de niște simplificări grozave pentru a reduce totul la ceva care este chiar posibil.”

Mai mult, de fiecare dată când adaugi un număr la problema colorării ambalajului, aceasta devine de aproximativ 100 de ori mai greu, datorită modului în care se înmulțesc combinațiile posibile. Aceasta înseamnă că, dacă o bancă de computere care lucrează în paralel ar putea exclude 12 într-o singură zi de calcul, ar avea nevoie de 100 de zile de timp de calcul pentru a exclude 13.

Heule și Subercaseaux au considerat extinderea unei abordări computaționale cu forță brută ca fiind vulgară, într-un fel. „Am avut câteva idei promițătoare, așa că ne-am gândit: „Să încercăm să ne optimizăm abordarea până când vom putea rezolva această problemă în mai puțin de 48 de ore de calcul pe cluster”, a spus Subercaseaux.

Pentru a face asta, au trebuit să vină cu modalități de a limita numărul de combinații pe care clusterul de calcul trebuia să le încerce.

„[Ei] vor nu doar să o rezolve, ci să o rezolve într-un mod impresionant”, a spus Alexandru Soifer de la Universitatea din Colorado, Colorado Springs.

Heule și Subercaseaux au recunoscut că multe combinații sunt în esență aceleași. Dacă încercați să umpleți o placă în formă de romb cu opt numere diferite, nu contează dacă primul număr pe care îl plasați este unul în sus și unul la dreapta pătratului central sau unul în jos și unul la stânga pătratul central. Cele două plasări sunt simetrice una cu cealaltă și constrâng următoarea mișcare exact în același mod, așa că nu există niciun motiv să le verificați pe amândouă.

Heule și Subercaseaux au adăugat reguli care au permis computerului să trateze combinațiile simetrice ca echivalente, reducând timpul total de căutare cu un factor de opt. Ei au folosit, de asemenea, o tehnică pe care Heule a dezvoltat-o ​​în lucrările anterioare numită cub and conquer, care le-a permis să testeze mai multe combinații în paralel. Dacă știți că o anumită celulă trebuie să conțină fie 3, 5 sau 7, puteți împărți problema și puteți testa fiecare dintre cele trei posibilități simultan pe diferite seturi de computere.

Până în ianuarie 2022, aceste îmbunătățiri au permis lui Heule și Subercaseaux să excludă 13 ca răspuns la problema colorării ambalajului într-un experiment care a necesitat mai puțin de două zile de timp de calcul. Acest lucru le-a lăsat cu două răspunsuri posibile: 14 sau 15.

Un mare plus

Pentru a exclude 14 - și pentru a rezolva problema - Heule și Subercaseaux au trebuit să găsească modalități suplimentare de a accelera căutarea pe computer.

Inițial, ei au scris o formulă booleană care atribuie variabile fiecărei celule individuale din grilă. Dar în septembrie 2022, ei și-au dat seama că nu trebuie să procedeze celulă cu celulă. În schimb, ei au descoperit că a fost mai eficient să ia în considerare regiuni mici compuse din cinci celule sub forma unui semn plus.

Ei și-au rescris formula booleană astfel încât mai multe variabile să reprezinte întrebări precum: Există un 7 undeva în această regiune în formă de plus? Computerul nu trebuia să identifice exact unde ar putea fi cei 7 în regiune. Trebuia doar să determine dacă era acolo sau nu - o întrebare la care necesită mult mai puține resurse de calcul pentru a răspunde.

„A avea variabile care vorbesc doar despre plusuri în loc de locații specifice s-a dovedit a fi mult mai bine decât să vorbim despre ele în anumite celule”, a spus Heule.

Ajutați de eficiența căutării plus, Heule și Subercaseaux au exclus 14 într-un experiment pe computer din noiembrie 2022, care a sfârșit prin a dura mai puțin timp decât cel pe care îl folosiseră pentru a exclude 13. Au petrecut următoarele patru luni verificând că concluzia computerului a fost corectă – aproape la fel de mult timp pe care îl petrecuseră, permițând computerului să ajungă la acea concluzie în primul rând.

„A fost îmbucurător să cred că ceea ce am generat ca un fel de întrebare secundară într-un jurnal aleatoriu a făcut ca grupuri de oameni să petreacă, după cum sa dovedit, luni din timpul lor încercând să descopere cum să o rezolve”, Goddard. a spus.

Pentru Subercaseaux, a fost primul triumf real al carierei sale de cercetare. Și, deși s-ar putea să nu fi fost tipul de descoperire pe care a idealizat-o atunci când a gândit pentru prima dată să lucreze în matematică, a descoperit că, în cele din urmă, aceasta avea propriile sale recompense intelectuale.

„Nu este înțelegerea formularului în care îmi dai o tablă și pot să-ți arăt de ce este 15”, a spus el. „Dar am înțeles cum funcționează constrângerile problemei, cât de bine este să ai un 6 aici sau un 7 acolo. Am dobândit multă înțelegere intuitivă.”