Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 Формальные доказательства с помощью моделей
Нактнулся тут на адрес

https://lean-lang.org/eval/

Там дан список (нетривиальных) теорем и для каждой из них фиксируются попытки формально доказать их в Lean с помощью нейронок. Теорему Ферма, понятное дело, не доказал (не успел доказать) никто, но потрясла одна вещь.

https://lean-lang.org/eval/problems/feit_thompson/

Теорема Фейта-Томпсона о разрешимости групп нечетного порядка. В 2012 году ее формальное доказательство в Coq (ныне Rocq) было подвигом. Сейчас ее в Lean с помощью нейронок доказали уже четверо. Я, правда, до конца не понял, кто доказывал на основе текста, а кто просто отпортил доказательство Coq, но у кого-то из четверых я, кажется, встречал упоминание "потребовалась еще пара книжек, формализуем и их тоже".

 Re: Формальные доказательства с помощью моделей
Теорема Ферма всё. Клод формализовал ее доказательство в Lean за 11 дней.

https://www-cdn.anthropic.com/9e431dff0 ... 3da263.pdf
https://github.com/anthropics/fermats-last-theorem

Kevin Buzzard, получивший в свое время грант на формализацию до 2029 года, конечно, поздравил (тем более что часть его работы была использована здесь), но, видимо, остался без гранта.
Лем писал(а):
Скажи мне, лорд Рассел, что осталось у тебя от дивной поры молодой? Три тома "Principia Mathematica", вымученных за долгие годы. Так вот: спешу сообщить, что Чанг Вэнь или другой какой-нибудь Пинг-Понг - не запоминаю я этих китайских имен - запрограммировал компьютер так, что все доказанное Б.Расселом в его пресловутых "Принципах" машина доказала за восемь минут со средней скоростью самоубийцы, который бросился с девяностого этажа на Юпитере, где, как известно, сила тяжести во столько же раз больше земной, сколько раз домработница господина Тичи ошиблась в счетах из прачечной в свою пользу.

(Оффтоп)

Цитата:
Доказать теорему Ферма
В выходной, да еще задарма
В придорожной харчевне
Средь гуляющей черни -
Словно жемчуг добыть из дерьма

 Re: Формальные доказательства с помощью моделей
Аватара пользователя
tolstopuz в сообщении #1733085 писал(а):
Клод формализовал ее доказательство в Lean за 11 дней.
Я не знаю, как работает Lean. Есть ли опасность, что Клод формализовал доказательство с пропусками, пробелами или вообще не того утверждения, а Lean это "проглотил"?

 Re: Формальные доказательства с помощью моделей
Anton_Peplov в сообщении #1733087 писал(а):
Я не знаю, как работает Lean. Есть ли опасность, что Клод формализовал доказательство с пропусками, пробелами или вообще не того утверждения, а Lean это "проглотил"?
Недавно вышла вполне себе художественная книга про Lean, где популярно рассказывается в том числе и об этих сомнениях.
https://www.quantabooks.org/books/the-p ... -the-code/ (если порыться в интернете, можно найти в epub)
Если кратко - пропуски и пробелы в многотомном бумажном доказательстве возможны на каждом шагу и определяются консенсусом математиков, а в формальном сводятся к верификации небольшого ядра, относящегося к области логики, а не предметной области доказательства. К тому же ядро одно и то же для разных доказательств. Кстати, этой проблеме посвящено несколько абзацев в README.md.
Проблема доказательства вообще не того утверждения существует, но с теоремой Ферма не стоит так остро:
Код:
theorem fermat_last_theorem (n : ℕ) (hn : 3 ≤ n) (a b c : ℕ) (ha : 0 < a) (hb : 0 < b) (hc : 0 < c) : a ^ n + b ^ n ≠ c ^ n

 Re: Формальные доказательства с помощью моделей
Аватара пользователя
tolstopuz в сообщении #1733090 писал(а):
Если кратко - пропуски и пробелы в многотомном бумажном доказательстве возможны на каждом шагу и определяются консенсусом математиков
Так ведь формализация для того и нужна, чтобы заполнить все возможные пробелы и подтвердить, что консенсус математиков правилен. Если формальные доказательства страдают от пробелов так же, как неформальные, то в формализации нет смысла.

tolstopuz в сообщении #1733090 писал(а):
а в формальном сводятся к верификации небольшого ядра, относящегося к области логики
Это настолько кратко, что я не понял.

 Re: Формальные доказательства с помощью моделей
Аватара пользователя
Anton_Peplov в сообщении #1733092 писал(а):
Если формальные доказательства страдают от пробелов так же, как неформальные, то в формализации нет смысла.
Не страдают:
tolstopuz в сообщении #1733090 писал(а):
а в формальном сводятся к верификации небольшого ядра, относящегося к области логики, а не предметной области доказательства. К тому же ядро одно и то же для разных доказательств.
Другими словами: если мы доверяем ядру Lean, то построенное формальное доказательство не может иметь никаких незакрытых пробелов. А это ядро маленькое и доступное для человеческой проверки (и многократно проверенное), это не ИИ.

 Re: Формальные доказательства с помощью моделей
Аватара пользователя
Ок, понял. Т.е. раз движок проглотил формальное доказательство, то оно корректное, пока и поскольку мы доверяем движку. Главное убедиться, что доказываемое утверждение - именно то, что мы хотим доказать, но в случае ВТФ это просто.

Что ж, если Клод действительно формализовал доказательство Уайлса, то это показывает по крайней мере одну нишу LLM в математике: формализация готовых доказательств (то, чем люди занимаются мало, неохотно и медленно). Это можно поставить на поток.

Было бы интересно, если бы он в итоге нашел ошибку в каком-нибудь признанном сообществом доказательстве.

 Re: Формальные доказательства с помощью моделей
Anton_Peplov в сообщении #1733094 писал(а):
Главное убедиться, что доказываемое утверждение - именно то, что мы хотим доказать, но в случае ВТФ это просто.

Давным-давно слушал курс типа "Верификация программ", тоже удивлялся - как можно проверить, что программа работает неправильно (ну, если она скомпилирована без ошибок)? Она делает ровно то, что написал программист, а что он хотел - это ж надо описывать на каком-то метаязыке, а как убедиться, что на нём написано правильно? )))
Я не в курсе, что там Claude написал на Lean (уверен, что не пойму), но может кто-то откомментирует?
Легко убедиться, что правильно записано условие ВТФ, но ведь наверняка используется гипотеза Таниямы-Симуры, а это уже совсем другой уровень понимания эквивалентности записи.
Или это новое доказательство, отличное от доказательства Уайлза?

 Re: Формальные доказательства с помощью моделей
Аватара пользователя
Booker48 в сообщении #1733100 писал(а):
Легко убедиться, что правильно записано условие ВТФ, но ведь наверняка используется гипотеза Таниямы-Симуры
В верифицированных доказательствах могут использоваться только уже верифицированные ранее теоремы. В частности, перед тем как переходить к верификации теоремы Ферма, нужно было вначале верифицировать (и построить формальные доказательства) для всех используемых там теорем и лемм, что и было сделано. Таким образом, гарантировано, что теорема Ферма верна и её построенное формальное доказательство не слишком сильно отличается от доказательства Уайлса по своей структуре и последовательности. И это как раз то, что нужно.
Более того, я слышал про планы постепенной верификации вообще всех доказательств в arXiv (а значит, и в журналах). Токенов на это не жалеют, потому что любая верификация - сложная для ИИ задача, а значит, полезная для обучения и соревнования новых моделей ИИ.

 Re: Формальные доказательства с помощью моделей
Mikhail_K
Я таки осмелился глянуть одним глазком в pdf-ку из сообщения tolstopuz.
Там в самом начале некий временной график по этапам доказательства Клодом.
Насколько я понимаю, исторической последовательности он не соответствует.
Так-то вроде (все сведения из вики) Г. Фрей в 1985 заметил связь между ВТФ и гипотезой Таниямы-Симуры (ГТС).
Потом Ж.-П. Серр (которому через 10 дней исполняется 100 лет, кстати :shock: ) сформулировал эпсилон-гипотезу (ЭГ) и показал, что из ЭГ и ГТС следует ВТФ.
Через год К.Рибет доказал ЭГ.
И, наконец, в 90-е, Э.Уайлз (с присоединившимся на завершающем этапе Р.Тейлором) доказал ГТС.

 Re: Формальные доказательства с помощью моделей
Mikhail_K в сообщении #1733102 писал(а):
Токенов на это не жалеют, потому что любая верификация - сложная для ИИ задача, а значит, полезная для обучения и соревнования новых моделей ИИ.


Теорема Ферма получила больше внимания, чем остальные теоремы. Она одна из самых известных и у всех на слуху. Математики неоднократно ее проверили и перепроверили, давно достигнув консенсуса. Отдельные части теоремы были верифицированы в Coq и Lean 4.

У меня создается впечатление, что подобные задачи выбирается не столько из-за их приорететной научной полезности, сколько потому, что громкизвестные задачи демонстрируют возможности новых моделей. Делается это для собственной рекламы . Можно вспомнить недавний контрпример к известной гипотезе якобиана.
Прямо сейчас по сети расходятся сообщения о том, что Anthropic расшифровала шифр 17 века, остававшийся неразгаданным 373 года.

Что касается верификации теоремы Ферма - 13 миллионов строк Lean 4, около 29,5 тысячи промежуточных теорем в окончательном доказательстве и примерно 6 миллиардов токенов на выходе. Если просто пересчитать эти токены по нынешнему публичному тарифу Fable 5.1 - 50 дол. за миллион токенов на выходе - получится около 300 тыс. Это не фактическая стоимость верификации, а эквивалент по публичному API за токен на выходе . Результат серьезный и впечатляющий. Только насколько это решение было продиктовано приоритетом полезности для науки и насколько рекламной ценностью для компании?

 Re: Формальные доказательства с помощью моделей
Mikhail_K в сообщении #1733102 писал(а):
В верифицированных доказательствах могут использоваться только уже верифицированные ранее теоремы.
Нет, можно, например, написать формулировку гипотезы Римана, вместо доказательства поставить sorry и начать ей пользоваться. Поэтому здесь специально об этом говорят:

Цитата:
No module contains axiom, sorry, native_decide, unsafe, extern, implemented_by, partial def or #eval (Challenge.lean uses sorry by design and is not part of the package).


-- добавлено через 8 минут --

Klein в сообщении #1733134 писал(а):
Что касается верификации теоремы Ферма - 13 миллионов строк Lean 4, около 29,5 тысячи промежуточных теорем в окончательном доказательстве
Кроме того, доказательство получилось нечитаемым, многие промежуточные теоремы доказаны только для частных случаев и так далее. Предстоит большая (пока ручная) работа по разгребанию и инкорпорации в библиотеки, чтобы от этого доказательства была реальная польза, кроме самого факта, что теорема доказана. Правда, так как в программировании модели уже делают вполне приличные PR, не за горами и выдача доказательств в более читаемом виде.
Klein в сообщении #1733134 писал(а):
и примерно 6 миллиардов токенов на выходе. Если просто пересчитать эти токены по нынешнему публичному тарифу Fable 5.1 - 50 дол. за миллион токенов на выходе - получится около 300 тыс. только за токены на выходе Это не фактическая стоимость верификации, а эквивалент по публичному API за токен на выходе.
Подписка творит чудеса, она примерно в 20 раз эффективнее оплаты по токенам. Кучка 200-долларовых подписок - и теорема доказана даже не сотрудником Anthropic.

 Re: Формальные доказательства с помощью моделей
tolstopuz в сообщении #1733136 писал(а):
Подписка творит чудеса, она примерно в 20 раз эффективнее оплаты по токенам. Кучка 200-долларовых подписок - и теорема доказана даже не сотрудником Anthropic.


Подписка у Антропика - это морковка на верeвке. Даже за 200 в месяц. Мало что получится профессионально довести на ней до конца. Либо доплачивать, либо регулярно ждать 5-ти часового и недельного сброса лимита. Люди перманентно сидят в недельном лимите. Пользователи пишут, что при нормальной работе недельный лимит можно израсходовать за считаные часы . Три часа и токены закончились на подписке за 200. Максимум 5 часов и весь недельный лимит. Сейчас дорогим и сильным моделям делегируют архитектуру (дизайн и планирование), само кодирование - на дешевые китайские или даже на локальные. Финальную проверку снова проводят на сильных дорогих моделях. Это уже стало отдельной большой темой как правильно распределять работу между моделями.

 Re: Формальные доказательства с помощью моделей
Математик Кевин Баззард получил грант в размере около одного миллиона фунтов стерлингов на формализацию и верификацию теоремы Ферма (2024-2029гг)/ Его сообщение после того, как Антропик заявила о завершении формализации и верификации теоремы в Lean 4.
https://xenaproject.wordpress.com/2026/ ... -me-to-it/

Текст перевел ИИ.

Цитата:
ВТФ: Anthropic меня опередила

Опубликовано 4 сентября 2026 года автором xenaproject

Полагаю, технически первым миру об этом сообщил один кофейный магазин в Ислингтоне через Instagram, но час спустя Anthropic сделала официальное объявление: одна из их внутренних моделей, используя платформу prove2.me, формализовала в Lean полное доказательство Великой теоремы Ферма (ВТФ, FLT).

Это последняя теорема из знаменитого списка 100 задач по формализации Фрека Вейдейка (Freek Wiedijk), которая оставалась неформализованной; таким образом, этот двадцатилетний бенчмарк теперь полностью завершён. Поздравляю Anthropic!

Математические детали

Доказательство — не современное, которое я сам формализую, следуя идеям Khare, Taylor и других, а изложение Darmon–Diamond–Taylor 1995 года аргумента Wiles–Taylor–Wiles, использующего теорему Langlands–Tunnell и теорему Рибе о понижении уровня.

В репозитории Anthropic развивается теория Фонтена — для изучения плоских деформаций представлений Галуа — и формализуется достаточная часть работ Мазура об эйзенштейновом идеале, чтобы доказать, что никакая кривая Фрея не может иметь точку порядка p ≥ 17.

Это означает, что их доказательство ВТФ работает только для p ≥ 17. Однако ВТФ уже была формализована для нечётных регулярных простых в работе Best–Birkbeck–Brasca–Rodriguez–van-der-Velde–Yang, а наименьшее нерегулярное простое равно 37, так что всё в порядке.

Кодовая база

Я скомпилировал кодовую базу и запустил на ней comparator — проверка проходит успешно.

Это гигантское доказательство — более 13,4 миллиона строк кода, — и его компиляция занимает почти в 20 раз больше времени, чем компиляция математической библиотеки Lean (на машине с 96 ядрами!).

Lean может работать довольно медленно при переходах от файла к файлу в репозитории такого размера — даже на машине с 500 ГБ оперативной памяти, доступ к которой Anthropic мне также предоставила. Однако Anthropic также передала мне несколько HTML-документов, по которым на практике ориентироваться проще: клонируйте репозиторий и откройте их в веб-браузере.

Что представляет собой эта работа — и чем она не является

В настоящее время EPSRC финансирует мою работу по формализации доказательства Великой теоремы Ферма, и наивной реакцией на приведённую выше новость могло бы быть предположение, что теперь мне больше нечего делать. Это не так.

Эта работа, безусловно, достигает некоторых целей проекта EPSRC и действительно идёт значительно дальше по объёму формализованного материала. Я обещал EPSRC лишь свести ВТФ к результатам 1980-х годов; этот же репозиторий доказывает её полностью.

Но я также обещал EPSRC несколько других вещей. Во-первых, я должен отправлять pull request'ы в математическую библиотеку Lean, добавляя фундаментальные объекты современной теории чисел; эта работа продолжается.

Во-вторых — и, возможно, это самое важное, — я должен создать динамический документ, позволяющий людям исследовать современное доказательство. Полагаю, маловероятно, что Anthropic станет этим заниматься: скорее всего, они сочтут свою работу завершённой после формализации (к тому же современное доказательство они всё равно не формализовали).

Заметьте, что с математической точки зрения эта работа Anthropic практически ничего нового нам не сообщает. Я публично говорил, что на 99,9% уверен в корректности доказательства ВТФ, а большинство специалистов по теории чисел уверены в нём на 100% (формализация сделала меня более подозрительным по отношению к математической литературе, чем большинство моих коллег).

Насколько я понимаю этот аргумент, формализация просто добросовестно следует ранней литературе, посвящённой доказательству, и ничего к ней не добавляет.

Но эта работа действительно показывает нам, что теперь возможно в области автоматической формализации.

Если уже сегодня некая система из множества ИИ способна за 11 дней от начала до конца формализовать тысячи страниц математической литературы, то в будущем мы начнём видеть формализацию современных исследований практически по мере их появления.

Мы также узнаем, оправдана ли моя паранойя относительно нынешнего состояния программы Ленглендса, когда машины начнут проверять её и безжалостно отмечать неполные аргументы.

Возможность автоматически формализовать сложный материал в конечном счёте сделает процесс рецензирования математических статей гораздо менее мучительным.

Кроме того, это заставит нас быть предельно честными и аккуратными: существуют статьи, которые опираются на результаты, якобы «известные специалистам», и будет интересно увидеть, что именно на самом деле предполагается в доказательствах различных важных результатов в моей области.

Вот почему эта новость так меня радует!

Мне выделили £1 млн на выполнение моего проекта в течение пяти лет; Anthropic понадобилось всего 11 дней, хотя мне всё-таки интересно, не потратили ли они больше денег…

Небольшая история

Мне показалось, что будет неплохо закончить личной историей.

В 1993 году Уайлс объявил о своём доказательстве ВТФ в Институте Ньютона в ходе серии из трёх лекций. Я присутствовал на первой — тогда я был аспирантом второго года обучения — и не понял практически ничего, поэтому две следующие лекции пропустил и вместо этого уехал отдыхать в Ирландию со своей новой девушкой.

Я был настолько влюблён, что совершенно забыл обо всех слухах, и только вернувшись через неделю в Кембридж, узнал новость о том, что теорема доказана.

Что-то странно похожее произошло и на этот раз.

Когда мне пришло письмо от Anthropic, я находился в Уэльсе на музыкальном фестивале Green Man с той же самой девушкой, но мобильная связь там была очень плохой.

В короткий момент, когда появился 4G, я всё-таки заметил письмо от человека, о котором никогда прежде не слышал, с темой «End-to-end Lean formalization of Fermat's Last Theorem» («Полная сквозная формализация Великой теоремы Ферма в Lean»), но решил, что его написал какой-то чудак!

Лишь неделю спустя, разбирая почти тысячу непрочитанных писем, накопившихся за время моего отсутствия, я узнал эту новость.

 Re: Формальные доказательства с помощью моделей
Что ж, ждем, когда формализуют или опровергнут inter-universal Teichmüller theory.

 [ Сообщений: 27 ]  На страницу 1, 2  След.


Соглашение о конфиденциальности | Общие правила

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group