Модел на 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$. Гаусовите цели числа разширяват обикновените цели числа и подобно на тях притежават свойства като единствено разлагане на прости множители. Такива разширения на обикновените цели или рационални числа са известни като алгебрични числови полета. Новият аргумент заменя гаусовите цели числа с по-сложни обобщения от алгебричната теория на числата с по-богати симетрии, които могат да създадат много повече разлики с единична дължина.

Строгият аргумент използва инструменти като безкрайни кули от класови полета и теорията на Голод–Шафаревич, за да покаже, че числовите полета, необходими за аргумента, действително съществуват. Тези идеи бяха добре известни на специалистите по алгебрична теория на числата, но се оказа голяма изненада, че тези понятия имат значение за геометрични въпроси в евклидовата равнина.

Този резултат бележи важен момент във взаимодействието между ИИ и математиката: система с ИИ самостоятелно е разрешила дългогодишен нерешен проблем в центъра на една активна област. То също така дава ранна представа за нов вид сътрудничество между ИИ и математиците хора. В този случай придружаващата работа на външни математици очертава значително по-богата картина от самото оригинално решение.

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

„Когато оценявам значимостта и влиянието на доказателство, генерирано от ИИ, въпросът, който си задавам, е: научи ли ни това нещо ново за проблема? Разбираме ли дискретната геометрия по-добре сега? Мисля, че отговорът е умерено „да“: това показва, че конструкциите от теорията на числата могат да допринесат много повече за такива въпроси, отколкото подозирахме; освен това необходимата теория на числата може да бъде много задълбочена. Несъмнено през следващите месеци много специалисти по алгебрична теория на числата ще разгледат внимателно други нерешени проблеми в дискретната геометрия.“

Неочакваната връзка между алгебричната теория на числата и дискретната геометрия, разкрита от решението, е част от това, което прави резултата забележителен. То не просто доказва конкретна хипотеза, а може да предостави на математиците мост, който да им позволи да започнат да изследват други свързани проблеми.

Блум посочва и една по-широка възможност:

„Авангардните области на знанието са много неравни и назъбени и без съмнение през идните месеци и години ще видим подобни успехи в много други области на математиката, където дългогодишни отворени проблеми ще бъдат решени от ИИ, разкриващ неочаквани връзки и довеждащ съществуващите технически машини до предела им. ИИ ни помага да изследваме по-пълно катедралата на математиката, която сме изграждали през вековете; какви други невидими чудеса чакат зад кулисите?“

Този резултат е обещаващ пример: ИИ допринася не само за решение, но и за математическо откритие, чието значение става по-ясно и по-богато чрез последващо човешко разбиране.

Изводът е по-значим от този конкретен резултат. По-доброто математическо структурирано анализиране може да направи ИИ по-силен партньор в изследователската работа: нещо, което може да свързва сложни ходове на мисълта, да свързва идеи от отдалечени области на знанието, да откроява обещаващи посоки, които експертите може да не са поставили сред приоритетите си, и да помага на изследователите да постигат напредък по проблеми, които иначе биха били твърде сложни или изискващи твърде много време за решаване.

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

Изкуственият интелект е на път да започне да играе много сериозна роля в творческите аспекти на научните изследвания и най-вече в самите изследвания върху изкуствения интелект. Въпреки че този напредък не е изненадващ, той засилва усещането ни за неотложност относно разбирането на тази следваща фаза от развитието на ИИ, предизвикателствата при съгласуването на много интелигентни системи и бъдещето на сътрудничеството между хората и ИИ.

Това бъдеще все още зависи от човешката преценка. Експертизата става по-ценна, а не по-малко ценна. ИИ може да помага за търсенето, предлагането и проверката. Хората избират значимите проблеми, интерпретират резултатите и решават кои въпроси да проучат по-нататък.