Na-disprove ng OpenAI model ang isang mahalagang conjecture sa discrete geometry

Halos 80 years nang pinag-aaralan ng mga mathematician ang isang simpleng tanong na tricky: kapag naglagay ka ng mga $n$ point sa isang plane, ilang pair ng mga point ang magiging $1$ unit apart?

Ito ang planar unit distance problem, na unang inilahad ni Paul Erdős noong 1946. Isa ito sa mga pinakakilalang tanong sa combinatorial geometry, madaling ilahad at lubhang mahirap lutasin. Sa 2005 na aklat na Research Problems in Discrete Geometry, nina Brass, Moser, at Pach, tinawag ito na “posibleng ang kilalang pinakamagandang problema (at pinakasimpleng ipaliwanag) sa combinatorial geometry.” Inilalarawan ito ni Noga Alon, isang nangungunang dalubhasa sa kombinatorika sa Princeton, bilang “isa sa mga paboritong problema ni Erdős.” Nag-alok pa nga si Erdős ng gantimpalang salapi para sa paglutas sa problemang ito.

Ngayon, ishe-share namin ang isang breakthrough sa unit distance problem. Mula sa original work ni Erdős, karaniwang pinaniniwalaan na ang “square grid” constructions na ipinapakita sa ibaba ang halos pinakamaganda para ma-maximize ang bilang ng mga unit distance pair. Na-disprove ng isang internal OpenAI model ang matagal nang pinanghahawakang conjecture na ito. Nakapagbigay iyon ng infinite na set ng mga example na nakapag-produce ng polynomial improvement. Isang group ng mga external mathematician ang nag-check sa proof. Nagsulat din sila ng companion paper na nagpapaliwanag sa argument at nagbibigay ng karagdagang background at context sa significance ng resulta.

Kapansin-pansin din kung paano natuklasan ang resulta. Ang proof ay nanggaling sa isang bagong general-purpose na reasoning model, imbes na sa isang system na na-train sa mathematics, dinisenyo para mag-search sa mga proof strategy, o naka-focus sa distance problem. Bilang bahagi ng mas malawak na pagsisikap na ma-test kung makatutulong sa frontier research ang mga advanced model, in-evaluate namin ito gamit ang isang collection ng mga Erdős problem. Sa case na ito, nakapag-produce ito ng proof na nilulutas ang open o hindi pa naso-solve na problem.

Mahalagang milestone ang proof na ito para sa math at AI communities. Ito ang unang pagkakataon na ang isang prominent na open problem, na napakahalaga sa subfield ng mathematics, ay na-solve ng AI nang mag-isa. Ipinapakita rin nito ang lalim ng reasoning na kayang gawin ng mga system na ito ngayon. Magandang pang-test ng reasoning ang mathematics: precise ang mga problem, puwedeng ma-check ang potensyal na mga proof, at magiging tama lang ang mga long argument kung kung logical pa rin ang reasoning mula umpisa hanggang dulo. Kapansin-pansin din ang method na ginamit sa pag-solve sa problem. Gumamit ang proof ng di-inaasahan at sophisticated na mga idea mula sa algebraic number theory para i-solve ang isang elementary geometric question.

Sa isinulat na companion paper, tinawag ng Fields medalist na si Tim Gowers, ang resulta bilang “isang milestone sa AI mathematics.” Ayon sa nangungunang number theorist na si Arul Shankar, “Sa opinyon ko, ipinapakita ng paper na ito na ang mga AI model sa ngayon ay hindi lang mga helper sa mga human mathematician – kaya nilang magkaroon ng mga original at ingenious na idea, at matagumpay na i-execute ang mga iyon”.

Available rito⁠(magbubukas sa bagong window) ang proof. Ang companion paper ng mga nangungunang external mathematician ay available rito⁠(magbubukas sa bagong window). Makikita mo ang pinaikling version ng chain of thought ng model dito⁠(magbubukas sa bagong window).

Ang $u(n)$ ang magiging pinakamalaking posibleng numero ng mga unit-distance pair ng mga $n$ point sa plane. Madaling gumawa ng mga halimbawa na may linear growth rate: kapag inilagay ang mga $n$ point sa linya magpo-produce ito ng mga $n-1$ pair, samantalang ang square grid ay magpo-produce ng humigit-kumulang $2n$ pair. Ang dating kilalang pinakamahusay na construction na nagmula sa ini-rescale na square grid, ay lumilitaw na nagbibigay pa ng higit: $n^{1 + C / \log \log(n)}$ para sa constant na $C$. Dahil ang $\log \log(n)$ ay nadaragdagan nang infinite habang lumalaki ang $n$, ang karagdagang term sa exponent ay unti-unting nagiging $0$, ibig sabihin, ang growth sa mga construction na ito ay mas mabilis lang nang kaunti kaysa sa linear. Maraming dekada nang pinaniniwalaan ng marami na ito na ang halos pinakamagandang rate na posible, at walang nang construction na hihigit pa sa square grid. Sa teknikal na pananalita, ang conjecture ni Erdős ay isang upper bound na $n^{1+o(1)}$ kung saan ang karagdagang $o(1)$ ay nagpapahiwatig ng termino na unti-unting nagiging $0$ habang nadaragdagan ang $n$.

Na-disprove ng bagong resulta namin ang conjecture na ito. Mas tiyak, para sa walang katapusang maraming halaga ng $n$, bumubuo ang patunay ng mga pagsasaayos ng $n$ na mga punto na may hindi bababa sa $n^{1+\delta}$ na mga pares na may unit-distance, para sa takdang exponent na $\delta > 0$. (Hindi nagbibigay ang orihinal na patunay ng AI ng tahasang halaga ng $\delta$, pero ipinapakita ng nalalapit na pagsasaayos mula sa propesor ng matematika sa Princeton na si Will Sawin na puwedeng gamitin ang $\delta=0.014$.)

Nakakatulong ang kasaysayan ng suliranin para makita kung bakit nakakagulat ang resulta. Mula sa original na 1946 construction ni Erdős, halos hindi nagbago ang nakilalang pinaka the best na lower bound. Ang pinakamabuting upper bound, $O(n^{4/3})$, ay nagmula sa gawa nina Spencer, Szemerédi, at Trotter noong 1984. Sa kabila ng mga sumunod na pagsasaayos at kaugnay na istruktural na gawain nina Székely, Katz at Silier, Pach, Raz, at Solymosi at iba pa, nanatiling halos hindi nagbago ang upper bound na ito. Bilang ebidensya na pabor sa conjecture, pinag-aralan nina Matoušek at Alon-Bucić-Sauermann ang problem gamit ang mga non-Euclidean distance sa plane. Pinatunayan nito na sinunod ng "karamihan" sa mga non-Euclidean distance na ito sa ilang aspeto ang conjecture.

Nakakagulat, ang mahahalagang bahagi ng construction na ito ay nagmula sa napakanaiibang bahagi ng mathematics na kilala bilang algebraic number theory, na ang pinag-aaralan ay mga konsepto na gaya ng factorization sa mga extension ng mga integer na kilala bilang mga algebraic number field.

Sa mas simpleng paliwanag, nagsimula ang proof sa isang pamilyar na geometric idea pagkatapos nagpunta ito sa isang di-inaasahang direksiyon.

Ang original na lower bound ni Erdős ay maiintindihan sa pamamagitan ng Gaussian integers: mga number na nasa form na $a+bi$, kung saan ang $a$ at $b$ ay mga integer at ang $i$ ay ang square root ng $-1$. Ini-extend ng Gaussian integers ang mga ordinary integer at, gaya ng mga ito, may mga property ito na gaya ng unique factorization sa mga prime. Ang ganitong mga extension ng mga ordinary integer o mga rational ay kilala bilang algebraic number fields. Sa bagong argument, ang Gaussian integers ay pinapalitan ng mas complicated na mga generalization mula sa algebraic number theory at may mas rich na mga symmetry na makakagawa pa ng mas maraming unit-length na differences.

Ang precise na argument ay gumagamit ng mga tool na gaya ng infinite class field towers at Golod–Shafarevich theory para ipakita ang mga number field na kailangan para mag-exist ang argument. Alam na alam ng mga algebraic number theorist ang mga idea na ito, pero talagang nakakagulat makita na may implications ang mga concept na ito sa mga geometric problem sa Euclidean plane.

Mahalagang pangyayari ito sa interaction ng AI at mathematics: nalutas ng AI system nang independent ang isang matagal nang open problem sa pinakasentro ng isang active na larangan. Naipapakita rin nito ang isang bagong uri ng collaboration sa pagitan ng AI at mga human mathematician. Sa case na ito, mas magandang picture ang naipapakita ng companion work ng mga external mathematician kumpara sa mismong original na solution.

Gaya ng isinulat ni Thomas Bloom sa kasamang note:

“Kapag ina-assess ko ang importansya at influence ng isang AI-generated na proof, ito ang itinatanong ko sa sarili ko: may bago ba itong itinuro sa atin tungkol sa problem? Mas maiintindihan na ba natin ngayon ang discrete geometry? Sa tingin ko, masasabing ang sagot ay oo: ipinapakita nito na mas marami pang puwedeng masabi ang mga number theoretic construction na ito tungkol sa ganitong mga tanong kaysa sa iniisip natin; bukod dito, maaaring napakalalim ng kinakailangang number theory para dito. Sa mga susunod na buwan, siguradong pag-aaralan ng maraming algebraic number theorist ang iba pang mga open problem sa discrete geometry.”

Ang di-inaasahang connection ng algebraic number theory at ng discrete geometry, na naipakita ng solution, ang isang dahilan kung bakit naging kapansin-pansin ang resultang ito. Hindi lang nito nalutas ang isang specific na conjecture, posible ring makapagbukas ito ng daan para ma-explore na ng mga mathematician ang ibang problem na related dito.

Idiniin din ni Bloom ang isang mas malawak na posibilidad:

“Marami pa tayong dapat malaman, at tiyak na sa susunod na mga buwan at mga taon, makakakita tayo ng mga katulad na tagumpay sa maraming iba pang larangan ng mathematics, kung saan ang matatagal nang open problem ay nalulutas dahil sa mga di-inaasahang connection na naipakita ng AI at paggamit sa existing na technical machinery na ito hanggang sa limit nito. Tinutulungan tayo ng AI na mas lalong ma-explore ang kabuuan ng na-build nating mathematics sa loob nang ilang daang taon; ano pa kayang mga kahanga-hangang bagay ang malalaman natin?”

May ipinakikitang promising na example ang resultang ito: hindi lang solution ang naico-contribute ng AI, kundi mathematical discovery na mas lalong nagiging malinaw at kapaki-pakinabang ang halaga habang unti-unti itong naiintindihan ng mga tao.

Higit pa sa resultang ito ang matututuhan natin dito. Makakatulong ang mahuhusay na mathematical reasoning para maging mas magaling na research partner ang AI: isang bagay na kayang mapanatiling magkakaugnay ang mahihirap na mga kaisipan, mai-connect sa isa't isa ang mga idea mula sa magkakaibang larangan ng kaalaman, mapalitaw ang mga promising path na baka hindi napa-prioritize ng mga expert, at kayang tumulong sa mga researcher na magkaroon ng progress sa mga problem na napaka-complex o nangangailangan ng maraming panahon para malutas.

Hindi lang sa mathematics mahalaga ang mga capability na ito. Kung kaya ng isang model na panatilihing magkakaugnay ang isang complicated na argument, i-connect sa isa't isa ang mga idea mula sa iba't ibang larangan ng kaalaman, at makagawa ng resulta na tama matapos itong suriin ng mga expert, makakatulong din ang mga kakayahang iyon sa biology, physics, materials science, engineering, at medisina, at ang mga ito ay bahagi ng mas long-term na plano namin para sa mas automated na research: mga system na makatutulong sa mga scientist at engineer na mag-explore ng mas marami pang idea at mapag-aralan ang mas mahihirap na technical problem.

Malapit nang gumanap ng napakaseryosong papel sa mga creative part ng research ang AI, at ang pinakamahalaga, nire-research mismo ng AI ang sarili nito. Bagaman di-inaasahan ang progress na ito, pinatatag nito ang urgency na nararamdaman namin tungkol sa pag-unawa sa susunod na phase na ito ng AI development, mga challenge na i-align ang napakatatalinong mga system, at sa kinabukasan ng pagtutulungan ng tao at AI.

Nakadepende pa rin sa judgment ng tao ang kinabukasang iyan. Sa halip na mabalewala, mas nagiging mahalaga ngayon ang expertise. Makakatulong ang AI sa pagse-search, pagsa-suggest, at pag-verify. Ang mga tao naman ang pumipili kung anong mga problema ang mahalaga, nag-i-interpret ng mga resulta, at nagpapasya kung anong mga tanong ang susunod na lulutasin.