Egy OpenAI modell megcáfolta a diszkrét geometria egyik központi sejtését

Közel 80 éve a matematikusok egy megtévesztően egyszerű kérdést vizsgálnak: ha $n$ pontot helyezünk el a síkon, legfeljebb hány pontpár lehet egymástól pontosan $1$ távolságra?

Ez a síkbeli egységtávolság-probléma, amelyet először Erdős Pál vetett fel 1946-ban. A kombinatorikus geometria egyik legismertebb kérdése, könnyű megfogalmazni és rendkívül nehéz megoldani. A Brass, Moser és Pach által írt 2005-ös Research Problems in Discrete Geometry című könyv „talán a kombinatorikus geometria legismertebb (és legegyszerűbben elmagyarázható) problémájának” nevezi ezt a kérdést. Noga Alon, a Princeton Egyetem kiemelkedő kombinatorikusa, „Erdős egyik kedvenc problémájaként” írja le. Erdős még pénzjutalmat is felajánlott a probléma megoldásáért.

Ma áttörést osztunk meg az egységtávolság-problémával kapcsolatban. Erdős eredeti munkája óta az uralkodó nézet az volt, hogy a lejjebb bemutatott „négyzetrács” konstrukciók lényegében optimálisak az egységtávolságú pontpárok számának maximalizálására. Egy belső OpenAI modell megcáfolta ezt a régóta fennálló sejtést, példák egy végtelen családját adva, amelyek polinomiális javulást eredményeznek. A bizonyítást külső matematikusok egy csoportja ellenőrizte. Írtak egy kísérő tanulmányt is, amely elmagyarázza az érvelést, és további hátteret és kontextust ad az eredmény jelentőségéhez.

Az eredmény abból a szempontból is figyelemre méltó, ahogyan megszületett. A bizonyítás egy új, általános célú érvelési modellből származott, nem pedig egy kifejezetten matematikára tanított rendszerből, amelyet bizonyítási stratégiák keresésére építettek fel, vagy amelyet kifejezetten az egységtávolság-problémára céloztak. Annak a szélesebb erőfeszítésnek a részeként, hogy teszteljük, a fejlett modellek hozzájárulhatnak-e az élvonalbeli kutatáshoz, Erdős-problémák egy gyűjteményén értékeltük. Ebben az esetben a nyitott problémát megoldó bizonyítást állított elő.

Ez a bizonyítás fontos mérföldkő a matematika és az AI közössége számára. Ez az első alkalom, hogy egy kiemelkedő, nyitott problémát, amely a matematika egy részterületének központi kérdése, autonóm módon oldott meg az AI. Azt is megmutatja, milyen mély érvelést támogatnak ma már ezek a rendszerek. A matematika különösen világos tesztkörnyezetet ad az érveléshez: a problémák pontosak, a lehetséges bizonyítások ellenőrizhetők, és egy hosszú érvelés csak akkor működik, ha az elejétől a végéig egyben marad. Az a módszer is figyelemre méltó, amellyel a problémát megoldották. A bizonyítás váratlan, kifinomult ötleteket alkalmaz az algebrai számelméletből egy elemi geometriai kérdésre.

A Fields-éremmel kitüntetett Tim Gowers a kísérő tanulmányban „mérföldkőnek az AI-matematikában” nevezi az eredményt. A vezető számelmélet-kutató Arul Shankar szerint „Véleményem szerint ez a tanulmány azt mutatja, hogy a jelenlegi AI-modellek túlmutatnak azon, hogy pusztán az emberi matematikusok segítői legyenek – képesek eredeti, zseniális ötletekre, majd azok sikeres végigvitelére”.

A bizonyítás itt⁠(új ablakban nyílik meg) érhető el. A vezető külső matematikusok által írt kísérő tanulmány itt⁠(új ablakban nyílik meg) érhető el. A modell gondolatmenetének rövidített változata itt⁠(új ablakban nyílik meg) található.

Legyen $u(n)$ a síkban elhelyezett $n$ pont között az egységtávolságú pontpárok lehető legnagyobb száma. A lineáris növekedési rátát elérő példákat könnyű megkonstruálni: ha $n$ pontot egy egyenesre helyezünk, $n-1$ párt kapunk, míg egy négyzetrács körülbelül $2n$ párt ad. A korábban legjobbnak ismert konstrukció, amely egy átméretezett négyzetrácsból származik, még ennél is többet ad: $n^{1 + C / \log \log(n)}$ valamely $C$ konstansra. Mivel $\log \log(n)$ $n$-nel együtt a végtelenhez tart, a kitevőben szereplő további tag $0$-hoz tart, vagyis ezek a konstrukciók csak kissé gyorsabban növekednek, mint lineárisan. Évtizedeken át széles körben úgy vélték, hogy ez a ráta lényegében a lehető legjobb, és egyetlen konstrukció sem javíthat jelentősen a négyzetrácson. Technikai értelemben Erdős egy $n^{1+o(1)}$ felső korlátot sejtett, ahol a további $o(1)$ egy $n$-nel együtt $0$-hoz tartó tagot jelöl.

Új eredményünk megcáfolja ezt a sejtést. Pontosabban, végtelen sok $n$ értékre a bizonyítás $n$ pont olyan konfigurációit konstruálja meg, amelyekben legalább $n^{1+\delta}$ egységtávolságú pontpár van, valamely rögzített $\delta > 0$ kitevőre. (Az eredeti AI-bizonyítás nem ad meg explicit $\delta$-t, de a Princeton matematikaprofesszora, Will Sawin által készített közelgő finomítás megmutatta, hogy vehető $\delta=0.014$.)

A probléma története segít megérteni, miért meglepő az eredmény. A legjobb ismert alsó korlát Erdős eredeti, 1946-os konstrukciója óta lényegében változatlan maradt. A legjobb felső korlát, $O(n^{4/3})$, Spencer, Szemerédi és Trotter 1984-es munkájából származik, és a későbbi finomítások, valamint Székely, Katz és Silier, Pach, Raz és Solymosi, illetve mások kapcsolódó strukturális eredményei ellenére is lényegében változatlan maradt. A sejtés melletti bizonyítékként Matoušek és Alon-Bucić-Sauermann a síkbeli nem euklideszi távolságokkal vizsgálta a problémát, és bebizonyította, hogy e nem euklideszi távolságok „többsége” bizonyos értelemben engedelmeskedik a sejtésnek.

Meglepő módon a konstrukció kulcsfontosságú összetevői a matematika egy egészen más területéről, az algebrai számelméletből származnak, amely olyan fogalmakat vizsgál, mint a faktorizáció az egész számok algebrai számtesteknek nevezett bővítéseiben.

Magas szinten nézve a bizonyítás egy ismerős geometriai ötlettel indul, és váratlan irányba viszi tovább.

Erdős eredeti alsó korlátja a Gauss-egészeken keresztül érthető meg: ezek az $a+bi$ alakú számok, ahol $a$ és $b$ egészek, $i$ pedig $-1$ négyzetgyöke. A Gauss-egészek kiterjesztik a szokásos egészeket, és hozzájuk hasonlóan olyan tulajdonságokkal rendelkeznek, mint a prímtényezőkre való egyértelmű felbontás. A szokásos egészek vagy racionális számok ilyen kiterjesztéseit algebrai számtesteknek nevezik. Az új érvelés a Gauss-egészeket algebrai számelméleti, bonyolultabb általánosításokkal helyettesíti, amelyek gazdagabb szimmetriákkal rendelkeznek, és sokkal több egységhosszúságú különbséget hozhatnak létre.

A pontos érvelés olyan eszközöket használ, mint a végtelen osztálytesttorony és a Golod–Safarevics-elmélet, hogy megmutassa: az érveléshez szükséges számtestek valóban léteznek. Ezek az ötletek jól ismertek voltak az algebrai számelmélettel foglalkozók előtt, de nagy meglepetést okozott, hogy ezeknek a fogalmaknak következményei vannak az euklideszi sík geometriai kérdéseire.

Ez az eredmény fontos pillanatot jelent az AI és a matematika kölcsönhatásában: egy AI-rendszer autonóm módon oldott meg egy régóta nyitott problémát egy aktív kutatási terület középpontjában. Korai bepillantást nyújt az AI és az emberi matematikusok közötti együttműködés egy új fajtájába is. Ebben az esetben a külső matematikusok kísérő munkája lényegesen gazdagabb képet fest, mint önmagában az eredeti megoldás.

Ahogy Thomas Bloom írja a kísérő jegyzetben:

„Amikor egy AI által generált bizonyítás fontosságát és hatását értékelem, azt a kérdést teszem fel magamnak: tanított-e nekünk valami újat a problémáról? Jobban értjük-e most a diszkrét geometriát? Szerintem a válasz egy visszafogott igen: ez azt mutatja, hogy a számelméleti konstrukcióknak sokkal több mondanivalójuk van az efféle kérdésekről, mint gondoltuk; ráadásul a szükséges számelmélet nagyon mély lehet. Kétségtelen, hogy sok algebrai számelmélettel foglalkozó matematikus fogja a következő hónapokban alaposan szemügyre venni a diszkrét geometria más nyitott problémáit.”

A megoldás által feltárt váratlan kapcsolat az algebrai számelmélet és a diszkrét geometria között része annak, ami figyelemre méltóvá teszi ezt az eredményt. Nem egyszerűen egy konkrét sejtést rendez le, hanem hidat is adhat a matematikusoknak további kapcsolódó problémák feltárásához.

Bloom egy tágabb lehetőségre is rámutat:

„A tudás határai nagyon egyenetlenek, és kétségtelen, hogy a következő hónapok és évek sok más matematikai területen is hasonló sikereket hoznak majd, ahol régóta nyitott problémákat old meg az AI azzal, hogy váratlan kapcsolatokat tár fel, és a meglévő technikai apparátust a végsőkig feszíti. Az AI segít nekünk teljesebben bejárni a matematika katedrálisát, amelyet évszázadok alatt építettünk; vajon milyen más, eddig nem látott csodák várnak még a háttérben?”

Ez az eredmény ígéretes példát ad: az AI nemcsak megoldással járul hozzá, hanem olyan matematikai felfedezéssel is, amelynek jelentősége a későbbi emberi megértés révén válik világosabbá és gazdagabbá.

A tanulság túlmutat ezen a konkrét eredményen. A jobb matematikai érvelés erősebb kutatási partnerré teheti az AI-t: olyasmivé, ami képes egyben tartani nehéz gondolatmeneteket, összekapcsolni ötleteket a tudás távoli területei között, ígéretes irányokat felszínre hozni, amelyeket a szakértők talán nem részesítettek előnyben, és segíteni a kutatókat olyan problémákban előrehaladni, amelyek egyébként túl összetettek vagy túl időigényesek lennének.

Ezek a képességek a matematikán túl is számítanak. Ha egy modell képes koherensen tartani egy bonyolult érvelést, összekapcsolni ötleteket a tudás távoli területei között, és olyan munkát létrehozni, amely kiállja a szakértői vizsgálatot, akkor ezek a képességek a biológiában, fizikában, anyagtudományban, mérnöki területeken és az orvostudományban is hasznosak, és hosszabb távú utunk részét képezik az automatizáltabb kutatás felé: olyan rendszerek felé, amelyek segíthetnek a tudósoknak és mérnököknek több ötletet feltárni és nehezebb technikai kérdéseket követni.

Az AI hamarosan nagyon komoly szerepet kezd játszani a kutatás kreatív részeiben, és ami a legfontosabb, magában az AI-kutatásban is. Bár ez az előrelépés nem váratlan, megerősíti, mennyire sürgetőnek érezzük az AI-fejlesztés következő szakaszának megértését, a nagyon intelligens rendszerek összehangolásának kihívásait és az ember–AI együttműködés jövőjét.

Ez a jövő továbbra is emberi ítélőképességen múlik. A szakértelem értékesebbé válik, nem kevésbé. Az AI segíthet keresni, javasolni és ellenőrizni. Az emberek választják ki a fontos problémákat, értelmezik az eredményeket, és eldöntik, milyen kérdéseket kövessenek tovább.