utnapishti

Новое интересное утверждение о том, что 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 членов.

Ссылки по теме:
Страница на сайте проблем Эрдеша: https://www.erdosproblems.com/forum/thread/124

Статья 1996 года: http://matwbn.icm.edu.pl/ksiazki/aa/aa77/aa7722.pdf
Статья 1997 года: https://web.archive.org/web/20231014020015/https://www.thebookshelf.auckland.ac.nz/document.php?action=null&wid=2560

Видео из Дженина, где израильские пограничники расстреливают двоих сдавшихся в плен подозреваемых террористов, выглядит очень плохо. И то, что им приказывают обратно перейти в темный дверной проем, после того, как они уже стояли на коленях в двух метрах от него, у стены - похоже, чтобы расстрел выглядел "естественно". И то, что другие солдаты, не участвовавшие в расстреле, вообще никак на это не реагируют.

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

Книги: Ursula le Guin, "The Lathe of Heaven"

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

Ле Гуин продумывает и прорабатывает эту идею, доходя до психоделических сцен, напоминающих лучшее из творчества Ф.К.Дика, но сохраняя при этом стройность сюжета. Недостатком при этом я бы назвал то, что по сути есть только три персонажа, а также избыток психологии/психотерапии в тексте романа (хоть и необходимой по сюжету). Все равно очень понравилось, оценка 5/6.

О названии романа. The Lathe of Heaven, буквально "Токарный станок небес" - результат неверного перевода афоризма из древней китайской книги "Чжуан-цзы" (написанной, когда не было никаких токарных станков). Ле Гуин цитирует афоризм в такой форме (в одном из переводов):

"Кто в познании сумеет остановиться на непознаваемом, тот и достиг совершенства. А кто не пожелает этого сделать, того ждет незавидная участь — брызнуть стружкой из-под резца небес."

А в переводе (переводчица Л.Д.Позднеева) "Чжуан-цзы" на русский это выглядит так:

"[Тот, кто] в знании отступает там, где не способен [познать], [обладает] истинным знанием. Того, кто к этому не приближается, разбивает естественное равновесие."

Возможно, поэтому у романа так много разных названий в переводах (только "Основание" Азимова может с этим соревноваться, подозреваю):

Резец небесный
Станок небес
Гончарный круг неба
Оселок небес
Небесный поток
Жернова неба

Остап Кармоди правильно пишет про единственный честный ответ насчет экономики России и войны в Украине:

"На широко обсуждаемый сейчас вопрос, могут ли накапливающиеся экономические проблемы России помешать ей вести войну, есть только один честный ответ: "Хуй его знает".

С одной стороны, в Северной Корее и в Китае при Мао люди буквально ели траву, но устойчивость режима это никак не подорвало.

С другой, Россия уже два раза, в 1917 и 1991, разваливалась из-за экономических проблем.

Такие вещи зависят от огромного количества факторов, как внутренних, так и внешних, и учесть их все, чтобы сделать точное предсказание, просто невозможно. Так что лучше не гадать, а просто делать всё от нас зависящее и надеяться на лучшее."

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

Кроме искусственного интеллекта. В этом вопросе ничего не ясно уже начиная с одного месяца в будущем.

Меня очень расстроил этот твит от Андрея Карпати:

"Я начинаю входить в привычку читать всё (блоги, статьи, главы книг и т.д.) с помощью LLM. Обычно первый проход — ручной, затем второй проход — «объясни/резюмируй», третий проход — вопросы и ответы. В итоге я обычно получаю лучшее/более глубокое понимание, чем если бы просто двигался дальше. Становится одним из главных вариантов использования.

С другой стороны, если вы писатель, пытающийся что-то объяснить/донести, мы можем всё чаще наблюдать смену мышления с «я пишу это для другого человека» на «я пишу это для LLM». Потому что как только LLM «понимает», он может затем таргетировать, персонализировать и подавать идею своему пользователю."

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

Я вполне использую языковые модели для помощи при чтении, но только технически сложных мест, и только после того, как сам постарался понять. Мне кажется, есть огромная разница между "когда нужна помощь" и "вообще все - прочитал, потом попросил модель объяснить/резюмировать". Если так поступать всегда, то первый проход неизбежно со временем будет более поверхностным, менее серьезным, потому что за углом уже ждет модель, чтобы "объяснить и резюмировать".

(А авторы, которые пишут для LLM, это вообще антиутопия какая-то).

И еще раз: это Карпати, т.е. интеллектуальная верхушка; в переложении для масс эта идея неизбежно приобретет черты фарса. В комментариях это уже заметно, процитирую один из них:

"Я часто спрашиваю Grok, как я могу применить конкретный урок из определённой ситуации в книге к своей жизни (например: «Одиссей ослепляет Полифема и спасается, цепляясь за овец. В чём тут главный урок и как я могу применить его к своей жизни?»)"

Видимо, это тот прекрасный новый мир, который мы заслужили.

Грустно.

Был вчера с экскурсией в киббуце Беэри, 4км от границы с Газой, где 7 октября было одно из самых тяжелых мест. Разрушенные и спаленные дома в основном стоят до сих пор, хотя некоторые снесли и строят новые. В свои дома вернулись около 20% жителей из 1200 жителей киббуца, в том числе А., который показывал нам все (вся его обширная семья, около 20 человек, 7 октября была за границей в ежегодном семейном отпуске). Остальные в основном живут во временных домах в небольшом поселке около Беер-Шевы, 40 километров от Беэри. Через год-два, когда будут достроены дома и целый новый район, ожидается массовое возвращение.

Самая страшная из историй была про семью Х., кототая жила в двух домах на расстоянии 300 метров, оба были захвачены хамасовцами, в одном жильца застрелили, в другом над членами семьи издевались, женщин насиловали, перед уходом всех убили, история закончилась фразой "Из всей семьи осталась в живых одна 85-летняя бабушка".

Другая история была про молодую пару с 9-месячным ребенком, которых уже посадили в машину, чтобы везти в Газу, машина поехала, но звуки перестрелки отвлекли хамасовцев, они затормозили, и заложники выпрыгнули и начали бежать. Жена поняла, что не сможет бежать, кинула ребенка вперед мужу и крикнула ему бежать дальше, сама остановилась и вернулась обратно в плен, затормозив хамасовцев. Ее вернули в первом обмене через несколько месяцев. Муж с младенцем на руках забился под кусты в какой-то канаве и дождался наших солдат.

А. показал нам знаменитый дом, где террористы собрали 14 заложников и отстреливались от солдат, и где под вечер наш танк выстрелил в дом и всех террористов и заложников, кроме одной женщины, нашли мертвыми (о правомерности этого выстрела и о том, скольких из заложников он убил, велись яростные споры). Дома уже нет, на его месте строят новый.

Он сказал, что его мнение, которое разделяют многие в киббуце - это что расследование боевых действий после того, как армия вошла в киббуц - это абсурд и ерунда, что все понимают, что после того, как 300 террористов спокойно зашли и укрепились в такой плотно заселенной местности и в каждом доме в укрепленной комнате прячутся жильцы, не может быть хороших результатов. То, на что не был дан нормальный ответ, и требуется его дать - это как они смогли прорвать забор и такими силами войти в Израиль и добраться до киббуцев без военного ответа, во-первых, и как может быть, что СЕМЬ ЧАСОВ практически никакие солдаты не добрались до Беэри, который находится на расстоянии часа езды от Тель-Авива, вообще-то. Эти семь часов почти полностью безнаказанного контроля террористов над киббуцем - главное, что жители не могут понять и принять до сих пор.

"В 2002-м я помогал спланировать размещение танков возле забора на нашем участке границы с Газой. Каждые 1-2 километра на возвышении стоял танк и отвечал за этот участок забора. Когда наблюдательницы (следящие за камерами обзора) видели, что кто-то приблизился к забору или пытается его сломать, они подавали сигнал танку, он стрелял в эту точку и на это все заканчивалось. 20 лет спустя этих танков нигде не было. Никакого ответа на массивное вторжение сквозь забор в десятках мест не было. Ничего не было."