Ни о какой безапелляционности в моих высказываниях не может быть и речи!

"Мужик пишет письмо на спичечную фабрику: «Я на протяжении 10 лет покупаю спички вашей фабрики и считаю количество спичек в коробке. Вы их кладёте то 59, то 60 штук, иногда 61, а вчера положили 56. Вы что там, совсем с ума посходили?»"

Купил недавно на Амазоне важную вещь для хозяйства - набор из 360 заточенных карандашей. Сегодня пришли. В картонной коробке лежат в 10 слоев.

(не спрашивайте, зачем. Во-первых, доставка в Израиль была бесплатная. Во-вторых, не спрашивайте, зачем)

Смотрю на них.

И еще смотрю на них.

Смотрю и смотрю на них.

... и думаю, надо посчитать.

Достаю из коробки и считаю. Чувствую некоторую нелепость происходящего. Думаю, ладно, сейчас выйдет 356 или 361 и я хоть напишу об этом запись, процитирую анекдот про спичечную фабрику.

Досчитал, а их ровно 360.

(На фотографии не все карандаши! Не пересчитывайте!)

Новое интересное утверждение о том, что 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, буквально "Токарный станок небес" - результат неверного перевода афоризма из древней китайской книги "Чжуан-цзы" (написанной, когда не было никаких токарных станков). Ле Гуин цитирует афоризм в такой форме (в одном из переводов):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Грустно.

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

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

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

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

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

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

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

Миша Вербицкий написал очень интересное (для меня по крайней мере) о сомнительном основании у некоторых частей современной математики:

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

Вот тут чудесные очерки крестового похода, который
ведет знаменитый математик Алекс Зингер, разоблачая
попытки обосновать пачку фундаментальных результатов
симплектической геометрии:
https://www.math.stonybrook.edu/~azinger/

Вот еще статья, про другую проблему, с аналогичным статусом:
https://www.quantamagazine.org/the-fight-to-fix-symplectic-geometry-20170209/

(несколько коллективов весьма великих ученых заявляют, что они-то все строго построили, при этом разоблачают аналогичные утверждения конкурентов; по факту, какая-то степень строгости есть у каждого, но до настоящего доказательства им очень далеко).

Вот тут это обсуждают
https://www.reddit.com/r/math/comments/kwp2de/controversy_in_symplectic_geometry_zinger_ruan_li/
https://www.reddit.com/r/math/comments/5t3n48/a_fight_to_fix_symplectic_geometrys_foundations/

Сами результаты, конечно, верны, а ученые, которые эти тексты написали, люди весьма уважаемые и квалифицированные, несмотря на ошибки, местами неприличные; но фундамент у сей науки осутствует и по сей день. Куча народу заявляет, что у них оно есть, но по факту что-то доказано только в весьма ограниченной ситуации, либо вообще толком не доказано. Знающие люди знают, чем можно пользоваться, а чем нет, и существенных противоречий в математике доселе не накопали. Но в принципе, могут, конечно, накопать, и тогда какие-то из статей придется переписывать."

Я почитал некоторые из полемик Зингера по ссылке, это действительно эпично выглядит - и достаточно неприглядно.

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

Но я не знал, что есть что-то похожее в наше время (кроме спора о гипотезе ABC, но это немного другое).

Из текстов нам известно, что в туалетах древнего Рима была такая штука, ксилоспонгий, буквально "губка на палке".



Долгое время его считали орудием для вытирания задницы после дефекации. Считалось, что после использования промокали в соленой воде или уксусе, и потом следующий пользователь, так сказать, вооружался той же палкой.

СЯУ, что в 2009-м году вышла ученая статья историка-античника, убедительно это опровергающая. Она проходится по всему небольшому числу текстов, где упоминается xylospongium (самый знаменитый - у Сенеки, где описывается, как гладиатор покончил жизнь самоубийством, затолкав себе эту губку в горло), и показывает, что нигде прямо не говорится, что этим вытирали зад. Альтернативная теория, что это было устройство для очистки самого туалета, гораздо более логично выглядит.

В эпическом комментарии на Реддите (англ.) пересказывают основные пункты статьи. Не буду цитировать подробные обсуждения источниках, ограничусь только здравым смыслом, мне понравилось:

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

Кажется, "Волшебник Земноморья" Урсулы ле Гуин - это действительно самый ранний, самый первый пример идеи "школы для волшебников", подробно описанной.

Мне попалось это утверждение в случайном месте, и удивило. Я попытался найти что-то раньше - вроде бы нет. Есть средневековые легенды о школе черной магии Scholomance, она упомянута в "Дракуле" Стокера, но подробного описания там нет. Есть несколько рассказов с похожей темой до романа ле Гуин, но опять-таки немного о другом. В рассказе Роберта Шекли "Бухгалтер" ребенок отказывается изучать черную магию, как заведено в его семье, потому что мечтает стать бухгалтером. В рассказе Теодора Когсвелла "Стена вокруг мира" люди изучают магию в школах и им запрещено заниматься наукой, а ребенок мечтает построить летательный аппарат на научных принципах, чтобы перелететь через странную стену, окружающую весь мир.

Так, чтобы показать школу/университет магии вблизи (в мире, где есть также обычные школы и их большинство), объяснить их устройство и предметы обучения и отношения учеников с учителями и как заканчивается учеба и все такое - это 1968 год, Урсула ле Гуин, "Волшебник Земноморья". Замечательная книга, не потускневшая совершенно за почти 60 лет, оригинальная в своих идеях и не подчиненная образам и метафорам Толкина.

Борьба добра со злом.