Un model d’OpenAI ha refutat una conjectura fonamental de la geometria discreta

Durant gairebé 80 anys, els matemàtics han estudiat una pregunta que, encara que sembli senzilla, no ho és: si col·loques $n$ punts al pla, quants parells de punts poden estar exactament a una distància $1$?

Aquest és el problema de les distàncies unitàries en el pla, plantejat per primera vegada per Paul Erdős el 1946. És una de les preguntes més conegudes de la geometria combinatòria, fàcil de formular i extraordinàriament difícil de resoldre. El llibre de 2005 Problemes d'investigació en geometria discreta, de Brass, Moser i Pach, diu que és "possiblement el problema més conegut (i més fàcil d’explicar) de la geometria combinatòria". Noga Alon, un destacat especialista en combinatòria de Princeton, el descriu com "un dels problemes preferits d’Erdős". Erdős fins i tot va oferir un premi en metàl·lic per resoldre aquest problema.

Avui compartim un avenç en el problema de la distància unitària. Des del treball original d’Erdős, la creença predominant ha estat que les construccions de «quadrícula quadrada» representades més avall eren essencialment òptimes per maximitzar el nombre de parells de distàncies unitàries. Un model intern d’OpenAI ha refutat aquesta conjectura de llarga durada, proporcionant una família infinita d’exemples que ofereixen una millora polinòmica. La demostració ha estat revisada per un grup de matemàtics externs. També han escrit un article complementari que explica l’argument i aporta més antecedents i context sobre la importància del resultat.

El resultat també és notable per la manera com es va trobar. La demostració va provenir d’un nou model de raonament de propòsit general, i no d’un sistema entrenat específicament per a les matemàtiques, estructurat per cercar estratègies de demostració o orientat en particular al problema de la distància unitària. Com a part d’un esforç més ampli per provar si els models avançats poden contribuir a la recerca d’avantguarda, el vam avaluar en una col·lecció de problemes d’Erdős. En aquest cas, va produir una demostració que resolia el problema obert.

Aquesta demostració és una fita important per a les comunitats de les matemàtiques i de la IA. És la primera vegada que un problema obert de gran rellevància, fonamental en una subbranca de les matemàtiques, ha estat resolt autònomament per la IA. També demostra la profunditat de raonament que aquests sistemes admeten ara. Les matemàtiques ofereixen un banc de proves especialment clar per al raonament: els problemes són precisos, les possibles demostracions es poden verificar, i un argument llarg només funciona si el raonament es manté coherent de principi a fi. El mètode amb què es va resoldre el problema també és notable. La demostració aplica idees inesperades i sofisticades de la teoria algebraica de nombres a una qüestió geomètrica elemental.

Tim Gowers, guanyador de la medalla Fields, en un article complementari qualifica el resultat de «fita en les matemàtiques de la IA». Arul Shankar, destacat teòric de nombres afirma que «aquest article demostra que els models actuals d’IA van més enllà de ser simples ajudants dels matemàtics humans: són capaços de tenir idees originals i enginyoses, i després portar-les a bon port».

La demostració està disponible aquí⁠(s'obre en una finestra nova). L’article complementari de destacats matemàtics externs està disponible aquí⁠(s'obre en una finestra nova). Pots trobar una versió abreujada de la cadena de pensament del model aquí⁠(s'obre en una finestra nova).

Definim $u(n)$ com el nombre més gran possible de parells a distància unitària entre $n$ punts del pla. És fàcil donar exemples que assoleixen una taxa de creixement lineal: si es col·loquen $n$ punts en una línia, s'obtenen $n-1$ parells, mentre que en una quadrícula quadrada se n'obtenen aproximadament $2n$ parells. La construcció anteriorment més coneguda, que prové d'una quadrícula quadrada reescalada, resulta que dóna encara més: $n^{1 + C / \log \log(n)}$ per a una constant $C$. Com que $\log \log(n)$ tendeix a infinit amb $n$, el terme addicional de l’exponent tendeix a $0$, cosa que significa que aquestes construccions només aconsegueixen un creixement lleugerament més ràpid que el lineal. Durant dècades, es creia de manera generalitzada que aquesta proporció era, essencialment, la millor possible i que cap construcció no podia millorar significativament la quadrícula quadrada. En termes tècnics, Erdős va conjecturar una cota superior de $n^{1+o(1)}$, en què el terme addicional $o(1)$ indica un terme que tendeix a $0$ amb $n$.

El nostre nou resultat refuta aquesta conjectura. Més precisament, per a infinits valors de $n$, la demostració construeix configuracions de $n$ punts amb almenys $n^{1+\delta}$ parells a distància unitària, per a algun exponent fix $\delta > 0$. (La demostració original de la IA no dona un $\delta$ explícit, però un refinament que publicarà pròximament el professor de matemàtiques de Princeton Will Sawin ha demostrat que es pot prendre $\delta=0,014$.)

La història del problema ajuda a veure per què el resultat és sorprenent. La millor cota inferior coneguda s'havia mantingut pràcticament inalterada des de la construcció original d’Erdős de 1946. La millor cota superior, $O(n^{4/3})$, es remunta a un treball de Spencer, Szemerédi i Trotter de 1984 i malgrat refinaments posteriors i treball estructural relacionat de Székely, Katz i Silier, Pach, Raz i Solymosi i d’altres, la cota superior s'ha mantingut pràcticament inalterada. Com a prova a favor de la conjectura, Matoušek i Alon-Bucić-Sauermann van estudiar el problema amb distàncies no euclidianes al pla, i van demostrar que "la majoria" d’aquestes distàncies no euclidianes obeeixen la conjectura en algun sentit.

Sorprenentment, els ingredients clau de la construcció provenen d’una part molt diferent de les matemàtiques, coneguda com a teoria algebraica de nombres, que estudia conceptes com la factorització en extensions dels enters conegudes com a cossos algebraics de nombres.

A grans trets, la demostració comença amb una idea geomètrica familiar i la porta en una direcció inesperada.

La cota inferior original d’Erdős es pot entendre a través dels enters gaussians: nombres de la forma $a+bi$, on $a$ i $b$ són enters i $i$ és l’arrel quadrada de $-1$. Els enters gaussians amplien els enters ordinaris i, com aquests, gaudeixen de propietats com ara una factorització única en nombres primers. Aquestes ampliacions dels enters o racionals es coneixen com a cossos de nombres algebraics. El nou argument substitueix els enters gaussians per generalitzacions més complicades de la teoria de nombres algebraics, amb simetries més riques que poden crear moltes més diferències de longitud unitària.

L’argument precís utilitza eines com torres de cossos de classe infinita i la teoria de Golod–Shafarevich per mostrar que els cossos de nombres necessaris per a l’argument existeixen realment. Aquestes idees eren ben conegudes pels teòrics de nombres algebraics, però va ser una gran sorpresa que aquests conceptes tinguessin implicacions per a qüestions geomètriques al pla euclidià.

Aquest resultat marca un moment important en la interacció entre la IA i les matemàtiques: un sistema d’IA ha resolt autònomament un problema obert de fa temps que és central en un camp de recerca actiu. També ofereix una primera visió d’un nou tipus de col·laboració entre la IA i els matemàtics humans. En aquest cas, el treball complementari dels matemàtics externs ofereix una imatge substancialment més rica que la solució original per si sola.

Com escriu Thomas Bloom a la nota complementària:

«Quan avaluo la importància i la influència d’una demostració generada per IA, una pregunta que em faig és: això ens ha ensenyat alguna cosa nova sobre el problema? Entenem millor ara la geometria discreta? Crec que la resposta és un sí amb matisos: això mostra que les construccions de teoria de nombres tenen molt més a dir sobre aquest tipus de qüestions del que sospitàvem; a més, que la teoria de nombres necessària pot ser molt profunda. Sens dubte, molts teòrics de nombres algebraics examinaran de prop altres problemes oberts de geometria discreta en els mesos vinents.»

La connexió inesperada entre la teoria de nombres algebraics i la geometria discreta revelada per la solució és part del que fa notable el resultat. No es limita a resoldre una conjectura específica, sinó que pot oferir als matemàtics un camí per començar a explorar altres problemes relacionats.

Bloom també apunta a una possibilitat més àmplia:

«Les fronteres del coneixement són molt irregulars, i sens dubte els mesos i anys vinents veuran èxits semblants en moltes altres àrees de les matemàtiques, on problemes oberts de fa temps es resolen gràcies a una IA que proposa connexions inesperades i porta la maquinària tècnica existent fins al seu límit. La IA ens està ajudant a explorar més plenament la catedral de les matemàtiques que hem construït al llarg dels segles; quines altres meravelles ocultes ens esperen entre bastidors?»

Aquest resultat ofereix un exemple prometedor: la IA contribueix no només amb una solució, sinó amb un descobriment matemàtic la importància del qual esdevé més clara i rica gràcies a la comprensió humana posterior.

La conclusió va més enllà d'aquest resultat concret. Un millor raonament matemàtic pot convertir la IA en un soci de recerca més potent: una cosa capaç de mantenir unides línies de pensament difícils, connectar idees entre àrees llunyanes del coneixement, fer aflorar camins prometedors que els experts potser no haurien prioritzat i ajudar els investigadors a avançar en problemes que, altrament, serien massa complexos o requeririen massa temps per abordar-los.

Aquestes capacitats són importants més enllà de les matemàtiques. Si un model és capaç de mantenir la coherència en un argument complicat, connectar idees entre àrees llunyanes del coneixement i produir feines que resisteixin l’escrutini dels experts, aquestes també són habilitats útils en biologia, física, ciència de materials, enginyeria i medicina, i formen part del nostre camí a més llarg termini cap a una recerca més automatitzada: sistemes que poden ajudar científics i enginyers a explorar més idees i abordar qüestions tècniques més difícils.

La IA està a punt de començar a assumir un paper molt seriós en les parts creatives de la recerca, i sobretot de la mateixa recerca en IA. Tot i que aquest progrés no és inesperat, reforça la urgència que sentim per entendre aquesta fase següent del desenvolupament de la IA, els reptes d’alinear sistemes molt intel·ligents i el futur de la col·laboració entre humans i IA.

Aquest futur continua depenent del judici humà. L’expertesa esdevé més valuosa, no menys. La IA pot ajudar a cercar, suggerir i verificar. Les persones trien els problemes que importen, interpreten els resultats i decideixen quines preguntes perseguir després.