Модел на OpenAI поби централна претпоставка во дискретната геометрија

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

Ова е проблемот на единични растојанија во рамнината, првпат поставен од Пол Ердеш во 1946 година. Тоа е едно од најпознатите прашања во комбинаторната геометрија, лесно за формулирање и извонредно тешко за разрешување. Книгата „Истражувачки проблеми во дискретна геометрија“ од Брас, Мозер и Пах од 2005 година го нарекува „веројатно најпознатиот (и наједноставен за објаснување) проблем во комбинаторната геометрија“. Нога Алон, водечки комбинаторичар на Принстон, го опишува како „еден од омилените проблеми на Ердеш“. Ердеш дури понудил парична награда за решавање на овој проблем.

Денес споделуваме пробив во проблемот за единечно растојание. Од првичната работа на Ердеш наваму, преовладувачкото верување беше дека конструкциите со „квадратна мрежа“ прикажани подолу во суштина се оптимални за максимизирање на бројот на парови на единечно растојание. Внатрешен модел на OpenAI ја поби оваа долгогодишна претпоставка, обезбедувајќи бесконечно семејство примери што даваат полиномско подобрување. Доказот беше проверен од група надворешни математичари. Тие исто така напишаа придружен труд што го објаснува аргументот и дава дополнителна позадина и контекст за значењето на резултатот.

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

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

Добитникот на Филдсов медал Тим Гауерс, пишувајќи во придружниот труд, го нарекува резултатот „пресвртница во ВИ математиката“. Според водечкиот теоретичар на броеви Арул Шанкар, „Според мене, овој труд покажува дека сегашните ВИ модели одат подалеку од тоа да бидат само помошници на човечките математичари – тие се способни да имаат оригинални генијални идеи, а потоа и да ги доведат до остварување“.

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

Нека $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$. (Оригиналниот ВИ доказ не дава експлицитно $\delta$, но претстојно доусовршување од професорот по математика на Принстон, Вил Савин, покажа дека може да се земе $\delta=0.014$.)

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

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

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

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

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

Овој резултат означува важен момент во интеракцијата меѓу ВИ и математиката: ВИ систем автономно реши долгогодишен отворен проблем во центарот на активно поле. Тој нуди и ран увид во нов вид соработка меѓу ВИ и човечките математичари. Во овој случај, придружната работа на надворешните математичари дава суштински побогата слика отколку само оригиналното решение.

Како што пишува Томас Блум во придружната белешка:

„Кога ја проценувам важноста и влијанието на доказ генериран од ВИ, прашањето што си го поставувам е: дали ова нè научи нешто ново за проблемот? Дали сега подобро ја разбираме дискретната геометрија? Мислам дека одговорот е умерено да: ова покажува дека конструкциите од теоријата на броеви имаат многу повеќе да кажат за вакви прашања отколку што претпоставувавме; згора на тоа, потребната теорија на броеви може да биде многу длабока. Несомнено многу алгебарски теоретичари на броеви во наредните месеци внимателно ќе разгледуваат други отворени проблеми во дискретната геометрија.“

Неочекуваната врска меѓу алгебарската теорија на броеви и дискретната геометрија што ја откри решението е дел од она што го прави резултатот значаен. Тој не само што разрешува конкретна претпоставка, туку може и да им обезбеди на математичарите мост за да почнат да истражуваат понатамошни сродни проблеми.

Блум укажува и на поширока можност:

„Границите на знаењето се многу нерамни, и без сомнение наредните месеци и години ќе донесат слични успеси во многу други области на математиката, каде долгогодишни отворени проблеми ќе бидат решавани од ВИ што открива неочекувани врски и ја турка постојната техничка машинерија до нејзините граници. ВИ ни помага поцелосно да ја истражиме катедралата на математиката што сме ја изградиле низ вековите; какви други невидени чуда нè чекаат зад сцената?“

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

Поуката е поголема од овој конкретен резултат. Подоброто математичко расудување може да ја направи ВИ посилен истражувачки партнер: нешто што може да одржи тешки линии на мисла, да поврзува идеи низ оддалечени области на знаење, да открива ветувачки насоки што експертите можеби не ги приоритизирале и да им помогне на истражувачите да напредуваат со проблеми што инаку би биле премногу сложени или одземале премногу време.

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

ВИ е на прагот да преземе многу сериозна улога во креативните делови на истражувањето, а најважно и во самото ВИ истражување. Иако овој напредок не е неочекуван, тој ја засилува итноста што ја чувствуваме околу разбирањето на оваа следна фаза од развојот на ВИ, предизвиците на усогласување на многу интелигентни системи и иднината на соработката меѓу луѓето и ВИ.

Таа иднина сè уште зависи од човечката проценка. Експертизата станува повредна, не помалку вредна. ВИ може да помогне во пребарување, предлагање и проверка. Луѓето ги избираат проблемите што се важни, ги толкуваат резултатите и одлучуваат кои прашања да ги следат понатаму.