Un model OpenAI a infirmat o conjectură centrală din geometria discretă

Timp de aproape 80 de ani, matematicienii au studiat o întrebare înșelător de simplă: dacă plasezi $n$ puncte în plan, câte perechi de puncte pot fi exact la distanța $1$ una de alta?

Aceasta este problema distanței unitare în plan, formulată pentru prima dată de Paul Erdős în 1946. Este una dintre cele mai cunoscute întrebări din geometria combinatorică, ușor de enunțat și remarcabil de greu de rezolvat. Cartea Research Problems in Discrete Geometry din 2005, de Brass, Moser și Pach, o numește „posibil cea mai cunoscută (și cea mai simplu de explicat) problemă din geometria combinatorică”. Noga Alon, un important specialist în combinatorică de la Princeton, o descrie drept „una dintre problemele preferate ale lui Erdős”. Erdős a oferit chiar și un premiu în bani pentru rezolvarea acestei probleme.

Astăzi, prezentăm un progres major privind problema distanței unitare. De la lucrarea originală a lui Erdős, convingerea dominantă a fost că construcțiile de tip „grilă pătrată” ilustrate mai jos erau în esență optime pentru maximizarea numărului de perechi aflate la distanță unitară. Un model intern OpenAI a infirmat această conjectură veche, oferind o familie infinită de exemple care aduc o îmbunătățire polinomială. Demonstrația a fost verificată de un grup de matematicieni externi. Ei au scris și un articol însoțitor care explică argumentul și oferă informații suplimentare și context despre semnificația rezultatului.

Rezultatul este remarcabil și prin modul în care a fost găsit. Demonstrația a provenit dintr-un nou model de raţionament de uz general, nu dintr-un sistem antrenat special pentru matematică, orchestrat pentru a căuta strategii de demonstrație sau orientat în mod special către problema distanței unitare. Ca parte a unui efort mai amplu de a testa dacă modelele avansate pot contribui la cercetarea de frontieră, l-am evaluat pe o colecție de probleme ale lui Erdős. În acest caz, a produs o demonstrație care rezolvă problema deschisă.

Această demonstrație este o bornă importantă pentru comunitățile de matematică și AI. Este pentru prima dată când o problemă deschisă importantă, centrală pentru un subdomeniu al matematicii, a fost rezolvată autonom de AI. De asemenea, demonstrează profunzimea raţionamentului pe care aceste sisteme îl susțin acum. Matematica oferă un teren de testare deosebit de clar pentru raţionament: problemele sunt precise, demonstrațiile potențiale pot fi verificate, iar un argument lung funcționează doar dacă raţionamentul rămâne coerent de la început până la sfârșit. Și metoda prin care a fost rezolvată problema este remarcabilă. Demonstrația aplică unei întrebări geometrice elementare idei neașteptate și sofisticate din teoria algebrică a numerelor.

Medaliatul Fields Tim Gowers, scriind în articolul însoțitor, numește rezultatul „o bornă în matematica AI”. Potrivit importantului teoretician al numerelor Arul Shankar, „După părerea mea, acest articol demonstrează că modelele AI actuale depășesc rolul de simpli ajutoare pentru matematicienii umani – ele sunt capabile să aibă idei originale și ingenioase, iar apoi să le ducă la bun sfârșit”.

Demonstrația este disponibilă aici⁠(se deschide într-o fereastră nouă). Articolul însoțitor al unor matematicieni externi de prim rang este disponibil aici⁠(se deschide într-o fereastră nouă). O versiune prescurtată a lanțului de gândire al modelului se găsește aici⁠(se deschide într-o fereastră nouă).

Fie $u(n)$ cel mai mare număr posibil de perechi aflate la distanță unitară dintre $n$ puncte din plan. Exemple care ating o rată de creștere liniară sunt ușor de construit: plasarea a $n$ puncte pe o linie dă $n-1$ perechi, în timp ce o grilă pătrată dă aproximativ $2n$ perechi. Construcția cunoscută anterior ca fiind cea mai bună, provenită dintr-o grilă pătrată redimensionată, se dovedește că oferă și mai mult: $n^{1 + C / \log \log(n)}$ pentru o constantă $C$. Deoarece $\log \log(n)$ tinde la infinit odată cu $n$, termenul suplimentar din exponent tinde la $0$, ceea ce înseamnă că aceste construcții obțin o creștere doar puțin mai rapidă decât cea liniară. Timp de decenii, s-a crezut pe scară largă că această rată era în esență cea mai bună posibilă și că nicio construcție nu putea îmbunătăți semnificativ grila pătrată. În termeni tehnici, Erdős a conjecturat o limită superioară de $n^{1+o(1)}$, în care termenul suplimentar $o(1)$ indică un termen care tinde la $0$ odată cu $n$.

Noul nostru rezultat infirmă această conjectură. Mai precis, pentru infinit de multe valori ale lui $n$, demonstrația construiește configurații de $n$ puncte cu cel puțin $n^{1+\delta}$ perechi aflate la distanță unitară, pentru un exponent fix $\delta > 0$. (Demonstrația IA originală nu oferă un $\delta$ explicit, dar o rafinare viitoare datorată profesorului de matematică de la Princeton Will Sawin a arătat că se poate lua $\delta=0.014$.)

Istoricul problemei ajută la înțelegerea motivului pentru care rezultatul este surprinzător. Cea mai bună limită inferioară cunoscută rămăsese în esență neschimbată de la construcția originală a lui Erdős din 1946. Cea mai bună limită superioară, $O(n^{4/3})$, datează din lucrările lui Spencer, Szemerédi și Trotter din 1984 și, în ciuda rafinărilor ulterioare și a lucrărilor structurale conexe ale lui Székely, Katz și Silier, Pach, Raz și Solymosi și ale altora, limita superioară a rămas în esență neschimbată. Ca dovadă în favoarea conjecturii, Matoušek și Alon-Bucić-Sauermann au studiat problema pentru distanțe neeuclidiene în plan și au demonstrat că „majoritatea” acestor distanțe neeuclidiene respectă conjectura într-un anumit sens.

În mod surprinzător, ingredientele-cheie ale construcției provin dintr-o parte foarte diferită a matematicii, cunoscută drept teoria algebrică a numerelor, care studiază concepte precum factorizarea în extensii ale întregilor cunoscute ca corpuri algebrice de numere.

La nivel înalt, demonstrația începe cu o idee geometrică familiară și o împinge într-o direcție neașteptată.

Limita inferioară originală a lui Erdős poate fi înțeleasă prin întregii gaussiani: numere de forma $a+bi$, unde $a$ și $b$ sunt întregi, iar $i$ este rădăcina pătrată a lui $-1$. Întregii gaussiani extind întregii obișnuiți și, asemenea acestora, au proprietăți precum factorizarea unică în numere prime. Astfel de extensii ale întregilor obișnuiți sau ale raționalelor sunt cunoscute drept corpuri algebrice de numere. Noul argument înlocuiește întregii gaussiani cu generalizări mai complicate din teoria algebrică a numerelor, cu simetrii mai bogate care pot crea mult mai multe diferențe de lungime unitară.

Argumentul precis folosește instrumente precum turnuri infinite de corpuri de clasă și teoria Golod–Shafarevich pentru a arăta că acele corpuri de numere necesare argumentului chiar există. Aceste idei erau bine cunoscute teoreticienilor algebrici ai numerelor, dar a fost o mare surpriză că aceste concepte au implicații pentru întrebări geometrice din planul euclidian.

Acest rezultat marchează un moment important în interacțiunea dintre AI și matematică: un sistem AI a rezolvat autonom o problemă deschisă veche, aflată în centrul unui domeniu activ. De asemenea, oferă o primă privire asupra unui nou tip de colaborare între AI și matematicienii umani. În acest caz, lucrarea însoțitoare a matematicienilor externi oferă o imagine substanțial mai bogată decât soluția originală de una singură.

După cum scrie Thomas Bloom în nota însoțitoare:

„Când evaluez importanța și influența unei demonstrații generate de AI, o întrebare pe care mi-o pun este: ne-a învățat aceasta ceva nou despre problemă? Înțelegem acum mai bine geometria discretă? Cred că răspunsul este un da moderat: asta arată că structurile din teoria numerelor au mult mai multe de spus despre astfel de întrebări decât bănuiam; mai mult, teoria numerelor necesară poate fi foarte profundă. Fără îndoială, mulți teoreticieni algebrici ai numerelor vor analiza îndeaproape alte probleme deschise din geometria discretă în lunile următoare.”

Legătura neașteptată dintre teoria algebrică a numerelor și geometria discretă, dezvăluită de soluție, este o parte din ceea ce face rezultatul remarcabil. Nu doar tranșează o conjectură specifică, ci le poate oferi matematicienilor o punte pentru a începe explorarea altor probleme conexe.

Bloom indică și o posibilitate mai largă:

„Frontierele cunoașterii sunt foarte zimțate și, fără îndoială, lunile și anii următori vor aduce succese similare în multe alte domenii ale matematicii, unde probleme deschise vechi sunt rezolvate de o AI care dezvăluie conexiuni neașteptate și împinge aparatul tehnic existent la limită. AI ne ajută să explorăm mai deplin catedrala matematicii pe care am construit-o de-a lungul secolelor; ce alte minuni nevăzute ne mai așteaptă în culise?”

Acest rezultat oferă un exemplu promițător: AI contribuie nu doar cu o soluție, ci cu o descoperire matematică a cărei semnificație devine mai clară și mai bogată prin înțelegerea umană ulterioară.

Concluzia este mai amplă decât acest rezultat particular. Un raţionament matematic mai bun poate face din AI un partener de cercetare mai puternic: ceva care poate menține coerente linii dificile de gândire, poate conecta idei din zone îndepărtate ale cunoașterii, poate scoate la iveală direcții promițătoare pe care experții poate nu le-au prioritizat și poate ajuta cercetătorii să avanseze în probleme care altfel ar fi prea complexe sau ar consuma prea mult timp.

Aceste capacități contează dincolo de matematică. Dacă un model poate păstra coerența unui argument complicat, poate conecta idei din zone îndepărtate ale cunoașterii și poate produce lucrări care rezistă examinării experților, atunci acestea sunt abilități utile și în biologie, fizică, știința materialelor, inginerie și medicină și fac parte din drumul nostru pe termen lung către o cercetare mai automatizată: sisteme care îi pot ajuta pe oamenii de știință și pe ingineri să exploreze mai multe idei și să abordeze întrebări tehnice mai dificile.

AI este pe punctul de a începe să joace un rol foarte serios în părțile creative ale cercetării și, cel mai important, ale cercetării în AI însăși. Deși acest progres nu este neașteptat, el întărește urgența pe care o simțim în privința înțelegerii acestei faze următoare a dezvoltării AI, a provocărilor alinierii unor sisteme foarte inteligente și a viitorului colaborării dintre oameni și AI.

Acel viitor depinde în continuare de judecata umană. Expertiza devine mai valoroasă, nu mai puțin valoroasă. AI poate ajuta la căutare, sugestii și verificare. Oamenii aleg problemele care contează, interpretează rezultatele și decid ce întrebări să urmărească în continuare.