OpenAI модел је оповргао кључну претпоставку у дискретној геометрији

Скоро 80 година математичари проучавају једно варљиво једноставно питање: ако поставите $n$ тач. у равни, колико парова тачака може бити тачно на растојању $1$?

Ово је проблем јединичних растојања у равни, који је први поставио Пол Ердеш 1946. године. То је једно од најпознатијих питања у комбинаторној геометрији, лако за формулисање и изузетно тешко за решавање. Књига из 2005. Research Problems in Discrete Geometry, аутора Brass, Moser и Pach, назива га „можда најпознатијим (и најједноставнијим за објашњавање) проблемом у комбинаторној геометрији”. Нога Алон, водећи комбинаторичар са Принстона, описује га као „један од Ердешевих омиљених проблема”. Ердеш је чак понудио новчану награду за решавање овог проблема.

Данас делимо пробој у проблему јединичног растојања. Од Ердешовог изворног рада, преовлађујуће уверење било је да су конструкције „квадратне мреже” приказане ниже у суштини оптималне за максимизовање броја парова на јединичном растојању. Интерни OpenAI модел оповргао је ову дуготрајну претпоставку, дајући бесконачну фамилију примера који доносе полиномско побољшање. Доказ је проверила група спољних математичара. Они су такође написали пратећи рад који објашњава аргумент и пружа додатну позадину и контекст значаја резултата.

Резултат је значајан и по томе како је пронађен. Доказ је дошао од новог општенаменског модела резоновања, а не од система обученог посебно за математику, надограђеног да претражује стратегије доказивања, или усмереног баш на проблем јединичног растојања. Као део ширег напора да тестирамо да ли напредни модели могу да допринесу граничним истраживањима, проценили смо га на збирци Ердешових проблема. У овом случају, произвео је доказ који решава отворени проблем.

Овај доказ је важна прекретница за математичку и AI заједницу. Ово је први пут да је истакнут отворени проблем, централни за једну подобласт математике, AI аутономно решио. То такође показује дубину резоновања коју ови системи сада подржавају. Математика пружа нарочито јасно окружење за тестирање резоновања: проблеми су прецизни, потенцијални докази могу да се провере, а дуг аргумент функционише само ако резоновање држи целину од почетка до краја. Значајан је и метод којим је проблем решен. Доказ примењује неочекиване, софистициране идеје из алгебарске теорије бројева на једно елементарно геометријско питање.

Добитник Филдсове медаље Тим Гауерс, пишући у пратећем раду, назива резултат „прекретницом у AI математици”. Према речима водећег теоретичара бројева Арула Шанкара: „По мом мишљењу, овај рад показује да садашњи AI модели превазилазе улогу пуких помоћника људским математичарима – способни су да имају оригиналне генијалне идеје, а затим и да их доведу до остварења.”

Доказ је доступан овде⁠(отвара се у новом прозору). Пратећи рад водећих спољних математичара доступан је овде⁠(отвара се у новом прозору). Скраћену верзију начина резоновања модела можете пронаћи овде⁠(отвара се у новом прозору).

Нека $u(n)$ буде највећи могући број парова на јединичном растојању међу $n$ тач. у равни. Примере који постижу линеарну стопу раста лако је конструисати: постављање $n$ тач. на праву даје $n–1$ парова, док квадратна мрежа даје око $2n$ пар(ов)а. Испоставља се да раније најбоља позната конструкција, која потиче из рескалиране квадратне мреже, даје још више: $n^{1 + C / \log \log(n)}$ за неку константу $C$. Пошто $\log \log(n)$ тежи бесконачности са $n$, додатни члан у експоненту тежи ка $0$, што значи да ове конструкције постижу раст само незнатно бржи од линеарног. Деценијама се широко веровало да је ова стопа у суштини најбоља могућа и да ниједна конструкција не може значајно да надмаши квадратну мрежу. Технички речено, Ердеш је претпоставио горњу границу $n^{1+o(1)}$, у којој додатни $o(1)$ означава члан који тежи ка $0$ са $n$.

Наш нови резултат оповргава ову претпоставку. Прецизније, за бесконачно много вредности $n$, доказ конструише конфигурације од $n$ тачака са најмање $n^{1+\delta}$ парова на јединичном растојању, за неки фиксни експонент $\delta > 0$. (Оригинални AI доказ не даје експлицитно $\delta$, али предстојеће усавршавање професора математике са Принстона Вила Савина показало је да се може узети $\delta=0.014$.)

Историјат проблема помаже да се увиди зашто је резултат изненађујући. Најбоља позната доња граница остала је у суштини непромењена још од Ердешове изворне конструкције из 1946. Најбоља горња граница, $O(n^{4/3})$, потиче из рада Спенсера, Семередија и Тротера из 1984, и упркос каснијим усавршавањима и сродном структурном раду Секеља, Каца и Силијера, Паха, Раза и Шољмошија и других, горња граница је остала у суштини непромењена. Као доказ у прилог претпоставци, Матушек и Алон–Буцић–Сауерман проучавали су проблем са нееуклидским растојањима у равни и доказали да „већина” тих нееуклидских растојања у извесном смислу поштује претпоставку.

Изненађујуће, кључни састојци конструкције долазе из сасвим другог дела математике познатог као алгебарска теорија бројева, која проучава појмове као што је факторизација у проширењима целих бројева познатим као алгебарска бројевна поља.

На високом нивоу, доказ почиње познатом геометријском идејом и гура је у неочекиваном правцу.

Ердешова изворна доња граница може се разумети кроз Ердешова целе бројеве: бројеве облика $a+bi$, где су $a$ и $b$ цели бројеви, а $i$ квадратни корен из $–1$. Гаусови цели бројеви проширују обичне целе бројеве и, као и они, имају својства као што је јединствена факторизација на просте бројеве. Таква проширења обичних целих или рационалних бројева позната су као алгебарска бројевна поља. Нови аргумент замењује Гаусове целе бројеве сложенијим уопштењима из алгебарске теорије бројева са богатијим симетријама које могу створити много више разлика јединичне дужине.

Прецизан аргумент користи алате као што су бесконачни торњеви класних поља и Голод–Шафаревичева теорија да покаже да бројевна поља потребна за аргумент заиста постоје. Ове идеје биле су добро познате алгебарским теоретичарима бројева, али је било велико изненађење што ти појмови имају последице за геометријска питања у Еуклидској равни.

Овај резултат означава важан тренутак у интеракцији између AI-ја и математике: AI систем је аутономно решио дуготрајан отворени проблем у средишту активне области. Он такође нуди рани увид у нову врсту сарадње између AI-ја и људских математичара. У овом случају, пратећи рад спољних математичара даје знатно богатију слику него само оригинално решење.

Како Томас Блум пише у пратећој белешци:

„Када процењујем важност и утицај доказа који је генерисао AI, постављам себи питање: да ли нас је ово научило нечем новом о проблему? Да ли сада боље разумемо дискретну геометрију? Мислим да је одговор умерено да: ово показује да конструкције из теорије бројева имају много више да кажу о оваквим питањима него што смо претпостављали; штавише, да потребна теорија бројева може бити веома дубока. Нема сумње да ће многи алгебарски теоретичари бројева у наредним месецима пажљиво погледати друге отворене проблеме у дискретној геометрији.”

Неочекивана веза између алгебарске теорије бројева и дискретне геометрије коју је решење открило део је онога што овај резултат чини значајним. Он не само да разрешава одређену претпоставку, већ математичарима може пружити мост за почетак истраживања даљих сродних проблема.

Блум такође указује на ширу могућност:

„Границе знања су веома назубљене, и нема сумње да ће наредни месеци и године донети сличне успехе у многим другим областима математике, где ће дуготрајни отворени проблеми бити решени тако што ће AI открити неочекиване везе и довести постојећи технички апарат до његових граница. AI нам помаже да потпуније истражимо катедралу математике коју смо градили током векова; која још невиђена чуда чекају иза кулиса?”

Овај резултат пружа обећавајући пример: AI доприноси не само решењем, већ и математичким открићем чији значај постаје јаснији и богатији кроз накнадно људско разумевање.

Поука је већа од овог конкретног резултата. Боље математичко резоновање може учинити AI снажнијим истраживачким партнером: нечим што може да одржи тешке токове мишљења на окупу, повеже идеје из удаљених области знања, изнесе обећавајуће правце којима стручњаци можда нису дали приоритет и помогне истраживачима да напредују на проблемима који би иначе били превише сложени или временски захтевни.

Те способности су важне и изван математике. Ако модел може да одржи сложен аргумент кохерентним, повеже идеје из удаљених области знања и произведе рад који издржи стручну проверу, онда су то корисне способности и у биологији, физици, науци о материјалима, инжењерству и медицини, и оне су део нашег дугорочнијег пута ка аутоматизованијем истраживању: системима који могу помоћи научницима и инжењерима да истраже више идеја и баве се тежим техничким питањима.

AI ускоро почиње да преузима веома озбиљну улогу у креативним деловима истраживања, а најважније и самог AI истраживања. Иако овај напредак није неочекиван, он појачава хитност коју осећамо у вези са разумевањем ове наредне фазе развоја AI-ја, изазова усклађивања веома интелигентних система и будућности сарадње људи и AI-ја.

Та будућност и даље зависи од људског расуђивања. Стручност постаје вреднија, не мање вредна. AI може да помогне у претрази, предлагању и провери. Људи бирају проблеме који су важни, тумаче резултате и одлучују којим питањима ће се даље бавити.