Модель OpenAI спростувала центральну гіпотезу в дискретній геометрії

Майже 80 років математики вивчали оманливо просте запитання: якщо розмістити $n$ точок на площині, скільки пар точок можуть перебувати точно на відстані $1$ одна від одної?

Це задача про одиничні відстані на площині, яку вперше сформулював Пауль Ердеш у 1946 році. Це одне з найвідоміших питань комбінаторної геометрії: його легко сформулювати, але напрочуд важко розв’язати. У книжці 2005 року Research Problems in Discrete Geometry Брасса, Мозера та Паха її названо «можливо, найвідомішою (і найпростішою для пояснення) задачею в комбінаторній геометрії». Ноґа Алон, провідний математик із Принстонського університету, що спеціалізується на комбінаториці, описує її як «одну з улюблених задач Ердеша». Ердеш навіть призначив грошову винагороду за розв’язання цієї задачі.

Сьогодні ми ділимося проривом у задачі про одиничні відстані. Від часу опублікування оригінальної роботи Ердеша панувало переконання, що побудови на «квадратній ґратці», зображені нижче, є по суті оптимальними для максимізації кількості пар на одиничній відстані. Внутрішня модель 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$. Гаусові цілі числа розширюють звичайні цілі числа і, як і вони, мають такі властивості, як-от єдина факторизація на прості множники. Такі розширення звичайних цілих або раціональних чисел називаються алгебраїчними числовими полями. Новий аргумент замінює гаусові цілі числа складнішими узагальненнями з алгебраїчної теорії чисел із багатшими симетріями, які можуть створювати значно більше різниць одиничної довжини.

Точний аргумент використовує такі інструменти, як нескінченні вежі класових полів і теорія Голода-Шафаревича, щоб показати, що числові поля, потрібні для аргументу, справді існують. Ці ідеї були добре відомі фахівцям з алгебраїчної теорії чисел, але стало великою несподіванкою, що ці поняття мають наслідки для геометричних питань в евклідовій площині.

Цей результат знаменує важливий момент у взаємодії між ШІ та математикою: система ШІ автономно розв’язала давню відкриту проблему в центрі активної галузі. Він також дає раннє уявлення про новий тип співпраці між ШІ та математиками-людьми. У цьому випадку супровідна робота зовнішніх математиків малює значно багатшу картину, ніж саме лише початкове розв’язання.

Як пише Томас Блум у супровідній примітці:

«Оцінюючи важливість і вплив доведення, згенерованого ШІ, я ставлю собі таке запитання: чи навчило воно нас чогось нового про цю задачу? Чи краще ми тепер розуміємо дискретну геометрію? Думаю, відповідь — стримане “так”: воно показує, що конструкції з теорії чисел можуть сказати про такі питання набагато більше, ніж ми підозрювали; більш того, потрібна для цього теорія чисел може бути дуже глибокою. Без сумніву, багато фахівців з алгебраїчної теорії чисел у найближчі місяці уважно придивлятимуться до інших відкритих проблем дискретної геометрії.»

Несподіваний зв’язок між алгебраїчною теорією чисел і дискретною геометрією, виявлений цим розв’язанням, є частиною того, що робить результат примітним. Він не просто розв’язує конкретну гіпотезу, а може дати математикам місток для подальшого дослідження пов’язаних проблем.

Блум також вказує на ширшу можливість:

«Межі знання дуже нерівні, і без сумніву найближчі місяці та роки принесуть подібні успіхи в багатьох інших галузях математики, де давні відкриті проблеми буде розв’язано завдяки тому, що ШІ виявлятиме несподівані зв’язки й доводитиме наявний технічний апарат до межі його можливостей. ШІ допомагає нам повніше досліджувати собор математики, який ми будували століттями; які ще небачені дива чекають за лаштунками?»

Цей результат дає багатообіцяльний приклад: ШІ робить внесок не лише у вигляді розв’язання, а й у вигляді математичного відкриття, значущість якого стає яснішою й багатшою завдяки подальшому людському осмисленню.

Висновок ширший за цей конкретний результат. Краще математичне міркування може зробити ШІ сильнішим партнером у дослідженнях: тим, що здатне утримувати складні лінії думки, поєднувати ідеї з далеких галузей знання, виявляти перспективні шляхи, яким експерти могли не надати пріоритету, і допомагати дослідникам просуватися в задачах, які інакше були б надто складними або вимагали б забагато часу.

Ці можливості важливі й поза математикою. Якщо модель може зберігати цілісність складної аргументації, поєднувати ідеї з далеких галузей знання та створювати роботу, що витримує експертну перевірку, то це корисні здібності і в біології, фізиці, матеріалознавстві, інженерії та медицині, і вони є частиною нашого довгострокового шляху до більш автоматизованих досліджень: систем, які можуть допомагати науковцям та інженерам досліджувати більше ідей і братися за складніші технічні питання.

ШІ ось-ось почне відігравати дуже серйозну роль у творчих частинах досліджень, а найважливіше — і в самих дослідженнях ШІ. Хоча цей прогрес не є несподіваним, він підсилює відчуття нагальності щодо розуміння наступної фази розвитку ШІ, викликів узгодження дуже інтелектуальних систем і майбутнього співпраці людей та ШІ.

Це майбутнє все ще залежить від людського судження. Експертиза стає не менш, а більш цінною. ШІ може допомагати шукати, пропонувати та перевіряти. Люди обирають важливі проблеми, інтерпретують результати й вирішують, які питання досліджувати далі.