LLM и проблема Эрдеша1
Новое интересное утверждение о том, что LLM решили открытую проблему в математике, заслуживает внимания и подробного разбора. Я попытался разобраться и попытаюсь вкратце рассказать.
Для контекста надо объяснить вначале, что такое "список Эрдеша".
Пал Эрдёш был знаменитым венгерским математиком, невероятно продуктивным, автором более 1400 статей, почти все из них написаны в соавторстве (более 500 различных соавторов из десятков стран). Он коллекционировал и публиковал интересные нерешенные вопросы, чаще всего в теории чисел, комбинаторике, теории графов и теории вероятностей. Сайт "проблемы Эрдеша" собрал список из более 1100 таких нерешенных проблем и отслеживает публикации о них и их статус после его смерти в 1996 (около 40% решены до сих пор).
Не так давно промелькнула новость о том, что ChatGPT нашел решение одной из открытых проблем Эрдеша, и это восторженно обсуждали в соц. сетях полдня или день, пока не обнаружилось, что путем испорченного телефона пропал важный нюанс: он "нашел решение" в том смысле, что "нашел уже существующую старую статью, еще из 1960-х, в которой дается решение, и о которой не знал ни Эрдеш, ни автор сайта проблем". Это несомненно примечательно, и показывает мощь LLM в обработке огромного количества материала, на котором они были натренированы, но все-таки далеко не то же самое, что "сам нашел неизвестное ранее решение". Дошло до того, что один из вице-президентов OpenAI удалил твит, в котором хвастался этим достижением, а другие важные игроки в этой сфере постили саркастические замечания в этой связи.
Сегодняшняя новость не из таких. С помощью Aristotle, новой LLM, которая находит напрямую формальные доказательства математических утверждений (эти доказательства можно потом верифицировать, и если они проходят проверку, считать вопрос закрытым), решена другая открытая проблема с сайта Эрдеша, проблема номер 124. Там действительно не было известно решение. Но... есть нюанс.
В статье 1996 года Эрдеш с тремя соавторами (один из них - Рональд Грэм, другой знаменитый математик) рассмотрел следующую задачу. Возьмем какой-то набор натуральных чисел, например 3,4,5, и рассмотрим все их степени, расставленные по порядку. Эти степени: 3,9,27,81... 4,16,64... 5,25,125,... если их расставить по порядку, выйдет: 3,4,5,9,16,25,27,64,81,125...
Верно ли, что начиная с какого-то числа N, любое число больше N может быть представлено как сумма степеней из этого списка (каждую степень можно брать не больше 1 раза)?
Например, для этого набора 3,4,5 и этого списка степеней можно видеть, что 1,2,6,10 невозможно составить как сумму чисел из этого списка. Дальше есть еще несколько невозможностей, но самая большая из них - 79. В своей статье они доказали, что любое число больше 79 можно представить, как сумму: скажем, 80=64+16, 81=64+9+5+3 итд.
(в статье ошибочно указано 78 вместо 79, я исправил ошибку. 78=64+9+5, 79 нельзя представить)
Что если я возьму какой-то другой набор вместо 3,4,5, ну скажем 10,95,102? Будет ли и тогда, начиная с какого-то числа, возможно представить любое как сумму степеней? Для того, чтобы был шанс на это, нужно как минимум два требования к набору. Во-первых, чтобы наибольший общий делитель всех чисел был 1: скажем, если это не так, и все числа в наборе кратны 3, скажем 3,6,9, очевидно, что любая сумма степеней тоже кратна 3, и невозможно будет *любое* число начиная с какого-то представить как сумму. Это очевидно. Во-вторых, эти числа должны быть в некотором смысле "достаточно маленькими", иначе их степени имеют слишком много "дырок". А именно, должно выполняться неравенство: сумма 1/(x-1) по всем x из набора больше или равна 1. Скажем, набор 3,4,5 это условие выполняет: 1/2 + 1/3 + 1/4 больше 1. А набор 10,95,102 не выполняет, и поэтому с ним шанса нет. Это условие не так очевидно, но можно доказать, что оно необходимо, стандартными средствами теории чисел.
Так вот, если я возьму набор чисел, который выполняет эти два условия, будет ли ТОГДА гарантировано, что начиная с какого-то числа все можно записать как сумму степеней набора? Это и есть открытая проблема, которую сформулировали
Эрдеш с соавторами в этой статье. Они не смогли ее решить в общем случае - только для некоторых наборов, как например 3,4,5.
А новый LLM "Аристотель" от компании Harmonic смог ее решить, нашел доказательство там, где не справились Эрдеш, Грэм и еще двое математиков? Так? Не совсем так. Есть нюанс.
Когда я сказал "возьмем список всех степеней каждого числа из набора", я начал с ПЕРВОЙ степени: 3,9,27... 4,16,64... Можно понять это по-другому и начать с НУЛЕВОЙ степени, которая всегда равна 1: тогда список степеней будет такой: 1,1,1,3,4,5,9,16,25,27,64,81,125... Три единицы в начале, потому что отдельно можем брать нулевую степень от 3, 4 и 5. Зададим тот же вопрос: можно ли любое число, начиная с какого-то, записать как сумму степеней из этого списка, если набор выполняет два условия выше.
Именно в таком виде, "с единицами", статья сформулирована на сайте "проблемы Эрдеша". Как это вышло? Ну дело в том, что статья 1996 года не была единственным источником этой задачи; в следующем году Эрдеш опубликовал небольшую обзорную статью "Problems in Number Theory" в журнале новозеландской математики (публиковать во всяких рандомных журналах было для него нормальным делом), где свел вместе несколько нерешенных проблем, включая эту. В этой статье он не указал условие "наибольший общий делитель равен 1", а насчет того, какая степень первая, 0 или 1, написано немного неясно. Видимо, составитель сайта именно из этой статьи взял точную формулировку проблемы: у него тоже нет требования про наибольший общий делитель, а степень указана с нуля, т.е. список степеней "с единицами".
Так вот, оказывается, что у задачи "с единицами" есть очень простое элементарное доказательство, причем гораздо более сильного факта: что ЛЮБОЕ число (а не "начиная с какого-то") можно представить как сумму из списка степеней. И именно это доказательство нашел Аристотель. Единицы оказываются очень сильным подспорьем. И условие по наибольшему общему делителю тоже оказывается ненужным - нужно только по сумме 1/(1-x).
Что же в итоге доказано? Скажем так, есть исходная статья 1996 года, где соавторы сформулировали Г1 (Гипотезу-1). Есть статья Эрдеша 1997 года, где он дает немного другую формулировку, которую можно прочитать как Г2 (Гипотеза-2), хотя он говорит, что всего лишь повторяет задачу из статьи 1996 года. Именно в виде Г2 задача лежит много лет в списке нерешенных задач Эрдеша, со ссылкой на все три статьи, пока не приходит человек и с помощью LLM не находит очень простое решение.
Мне кажется, что в статье 1997 года Эрдеш просто небрежно сформулировал, но все-таки имел в виду Г1. А задача Г2, хоть и висела на сайте много лет, либо не получала почти внимания математиков, либо те шли читать исходную статью-1996 и пытались решать тяжелую задачу Г1. Если бы математик-специалист задумался именно над Г2, как над свежим отдельным утверждением, без контекста тяжелой задачи Г1 и сложных методов, которые к ней применялись, то скорее всего быстро бы решил ее.
В свете этого то, что найдено простое решение Г2, приятно и красиво, но гигантским шагом вперед я бы не назвал. Вот так примерно. Буду рад поправкам и предложениям от экспертов.
P.S. Вот суть простого доказательства Г2, которое нашел LLM. Сказать, что любое число можно представить в виде суммы из данного списка степеней, эквивалентно тому, что сумма первых N степеней из этого списка, для любого N, больше или равна следующей степени минус 1. Например, напомню список степеней "с единицами" для набора 3,4,5:
1,1,1,3,4,5,9,16,25,27...
Мы видим, чтo первое число не меньше второго минус 1. Сумма первого и второго не меньше третьего минус 1. И так далее, скажем 1+1+1+3+4+5+9 >= 16-1. Если мы это докажем для любого n, из этого легко следует, что любое число можно представить как сумму (подробности опускаю, но могу объяснить, если надо).
Но сумму скажем первых десяти членов можно разбить на геометрические прогрессии: 1+3+9+27, 1+4+16, 1+5+25. Сумма каждой прогрессии равна (d^n-1)/(d-1), это из школьной программы: в данном случае это (81-1)/(3-1), (64-1)/(4-3), (125-1)/(5-1). Если мы в этой сумме все числители заменим на наименьший из них, тут это 64-1, то получим что-то меньше. Вынеся это за скобки, получим сумму по всем числам набора 1/(x-1), которая по условию больше или равна 1, так что заменив всю сумму на 1, опять уменьшим.
Короче, число 64-1 меньше, чем вся эта сумма первых десяти членов. Но следующее число в списке как раз наименьшее из еще отсутствующих в нем степеней - как раз 64 в этом примере. Поэтому сумма первых десяти больше или равна одиннадцатому минус 1, 64-1. И так для любой суммы первых n членов.
Ссылки по теме: страница на сайте проблем Эрдеша, статья 1996 года, статья 1997 года.
