Вы давеча накидали мне так много реакций, что я не мог не откликнуться на этот запрос. Тем более что в итоге оказалось, что довольно много чего о гипотезе Эрдёша, которую давеча опроверг GPT, действительно можно объяснить на пальцах! Конечно, далеко не всё, но я старался:

GPT и единичные расстояния: опровержение гипотезы Эрдёша

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

Приведу здесь оглавление и (сокращённое) заключение.

1. Введение

2. Что такое задача о единичных расстояниях

— Постановка задачи
— Грубые оценки
— Эрдёш, 1946 (нижняя оценка чуть лучше линейной)
— Гипотеза Эрдёша
— Простейшая верхняя оценка: O(n^{3/2})

3. Текущая верхняя оценка O(n^{4/3})

— Что такое число пересечений
— Конструкция Секеля

4. Почему задача такая сложная и почему ей нужна теория чисел

5. Что именно сделал GPT

6. Кольца, решётки и сумма двух квадратов

— Что такое кольцо
— Гауссовы целые Z[i]
— Решётка из целых поля Q(\sqrt{2})
— Как нижняя оценка Эрдёша устроена через кольца
— Идея GPT
— Проекция
— Почему из этого следует n^{1+\delta}

7. Детали конструкции: где взять такие поля

(эту часть непрофессионалам лучше пропустить, а профессионалам — рассказать мне, где я там налажал)

8. Почему же люди этого не сделали?

9. Реакции: «I would accept it for any journal without hesitation»

10. Заключение: что всё это значит

Попытаюсь подытожить общую картину. Гипотеза Эрдёша о единичных расстояниях, простоявшая с 1946 года и широко считавшаяся верной, была опровергнута контрпримером, который полностью автоматически построила внутренняя модель OpenAI (но именно чистая LLM, без внешних инструментов вроде Lean). См. таймлайн на последней картинке.

Само доказательство — это “обычная математика”, которую могли бы создать и живые математики: оно совмещает известные ингредиенты в новое целое. Доказательство перепроверили и упростили живые математики, и финальная версия вполне читаема, да и на самом деле не так уж сложна. [...]

Лично меня в этой истории больше всего впечатляет именно то, что первый выдающийся LLM-результат оказался таким “чистым”, аккуратным и понятным. Интуитивно ведь ждёшь, что первые такие истории будут чем-то вроде доказательства ABC-гипотезы, с сомнениями в корректности и огромными нечеловеческими доказательствами. Но нет: доказательство короткое и изящное, никаких сомнений нет...

Конечно, из этого пока не следует, что все живые математики скоро останутся без работы, и у этой конкретной задачи есть ряд свойств, делающих её особенно подверженной такому решению; мы их тоже обсудили. Скорее всего, большинство важных открытых проблем устроены не так... но, с другой стороны, откуда нам знать? Об этой задаче мы тоже такого не предполагали. Видимо, часть открытых задач — довольно большая часть, как мне кажется по итогам этой истории, — окажется решённой AI-системами в относительно близком будущем. [...]

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

Что дальше, коллеги?

#blog #ai #math #longreads

Канал берёт новую высоту; теперь у меня 4000 подписчиков! Ура!

И прекрасная Ира @fuesis, конечно же, за этим следит и отмечает. Смотрите, какая красота.) Видимо, это уже традиция, ведь они с Инной уже дарили мне такой тортик на предыдущий, трёхтысячный юбилей. На этот раз, говорят, на тортике изображён Арагац, как раз около 4000 метров.

Спасибо Ире! И спасибо вам всем за то, что читаете, лайкаете и комментируете. Для канала с таким контентом, как у меня, 4К подписчиков - это не так уж и мало. Спасибо, и очень надеюсь, что смогу вас чем-нибудь радовать ещё долго.

#lifestyle #blog

Сегодня поговорим о редком для меня стратегическом жанре; пожалуй, только про Lessaria я когда-то писал в блоге. Впрочем, это не просто стратегия, а roguelike-стратегия, с метапрогрессией. Игра эта получила немало хайпа на релизе, вот теперь и я до неё добрался; давайте посмотрим, с чем её едят.

Длинный обзор, здесь сильно сокращён, читайте по ссылке:

The King is Watching
(и вот выложил на DTF)

Делали The King is Watching наши люди, маленькая студия Hypnohead [...] из Белграда. [...]

Кстати, геймдизайнер Hypnohead Семён Гурий регулярно пишет посты на DTF; вот большой пост с его историей и историей The King is Watching. Пост горячо рекомендую, а вот этот комментарий прекрасно отражает его суть. [...]

Игровое поле — это маленькое квадратное королевство (поначалу 4х4), на котором вы расставляете здания. [...]

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

Зато есть главная фишка геймплея, отражённая в названии игры. Чтобы что-то работало, нужно, чтобы король, то есть вы, туда смотрели. У вас есть king’s gaze, область на карте, на которую вы “смотрите” — и работают только те здания, которые попадают в ваше поле зрения! Остальные тупо простаивают. [...]

А ещё здесь есть элементы roguelike. Много элементов! Вы открываете новых королей с их собственными механиками, новых советников, новые здания, новые апгрейды, Здесь сразу четыре разных дерева метапрогрессии с пассивными бонусами, которые растут через монетки, выдающиеся как за победы, так и за поражения. [...]

Ой, да, тут же ещё и события, и они очень забавно выполнены. [...]

В целом всё это приводит к тому, что The King is Watching сочетает в себе два главных свойства roguelikes:
— каждый отдельный забег оставляет ощущение недосказанности, и хочется тут же запустить следующий;
— разветвлённая метапрогрессия не даёт надолго застрять на одном месте.

Метапрогрессия богатая. Но какая-то она… слишком богатая, что ли. Главная проблема здесь в том, что, в отличие от других roguelikes, здесь один заход длится далеко не 10-15 минут. [...]

Так что сначала я примерно понял, как что работает, дошёл до threat level 2 на первой карте, но там застрял и проиграл несколько заходов подряд. Это, по идее, нормально и ожидаемо в такой игре. Потом вроде бы понял, что делал неправильно, прошёл threat levels 2 и 3, открыл карту с кладбищем и нежитью, там с ходу выиграл пару заходов и застрял опять. Звучит хорошо…

…но в этот момент я оглянулся и заметил, что провёл в игре уже 18 часов. [...] В общем, хотя ощущение “ещё один заход” никуда не делось, я понял, что пора принимать волевое решение и закапывать стю откладывать игру.

Заключение

Лично я люблю проходить игры. Мне в какой-то момент даже пришлось осознанно задушить в себе перфекциониста и перестать пытаться добывать ачивки (слишком уж часто это не какой-то интересный контент, а очень сложная и совершенно бессмысленная деятельность). Поэтому The King is Watching меня победила: кажется, что для того чтобы увидеть здесь всё (или хотя бы всё содержательное), нужно гораздо больше времени, чем я готов потратить.

Но если вы, наоборот, хотите найти игру, которая может не надоесть за десятки часов, это как раз то, что нужно. Так что в целом — безусловно рекомендую: всё то, что игра делает (roguelike-стратегия), она делает очень хорошо. Базовая идея свежа и интересна, игра совершенно не надоедает (как часто бывает со стратегиями!), “ещё один забег” всегда очень хочется.

Создателям игры безусловный респект и пожелания дальнейших успехов!

#tgif #games

А вот и последний доклад на семинаре лаборатории Маркова:

Семинар Markov Lab — 2026.05.22 — Объединяя модели клиентов
(слайды на странице семинара)

Гарри Прошян (ПОМИ РАН)

Это на самом деле доклад о нашей с Гарри совместной статье "Beyond Isolated Clients: Integrating Graph-Based Embeddings into Event Sequence Models" (WWW'26). Постановка такая: большие цифровые платформы — банки, маркетплейсы, соцсети — порождают миллиарды событий вида "клиент-объект-timestamp", и по этим последовательностям хочется делать много разного, например предсказывать атрибуты клиента (пол, возраст, кредитный риск, склонность к мошенничеству).

Современные self-supervised методы для событийных последовательностей (например, CoLES и Barlow Twins) хорошо понимают временной порядок внутри истории одного клиента, но смотрят на каждого клиента изолированно и полностью игнорируют глобальную структуру. Но если посмотреть, как все взаимодействия вместе образуют двудольный граф "клиенты — объекты", то можно из него много чего интересного вытащить.

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

#spsu #markovlab #seminar

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

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

2026-06-04 — Ученый совет ФКН ВШЭ — Образование в эпоху больших языковых моделей
(слайды на странице "Выступления")

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

Сегодня очень острая для образования тема: что меняется в эпоху LLM и других AI-моделей, как нам строить образовательный процесс, что меняется в последнее время, что люди реально делают и так далее. Меня пригласили выступить, и я сделал очень общий доклад, с высоты птичьего полёта о том, что самое главное в этой трансформации.

Доклады там супер-короткие, меньше 15 минут, но я вроде бы смог провести два своих основных тезиса, которые не раз уже высказывал.

Во-первых, главная задача системы образования уже давно не в том, чтобы передать знания, а с появлением общедоступных индивидуальных тьюторов в лице LLM и не в том, чтобы педагогически верно их преподать. Главная задача в том, чтобы дать обучающимся мотивацию всем этим заниматься. Если есть мотивация, вас LLM уже прямо сегодня могут прекрасно обучить большинству областей университетской математики и computer science. Но без системы образования мотивация будет мало у кого.

Во-вторых, мы теперь уже точно теряем возможность предсказать, какие конкретные навыки будут нужны людям через годы. Вот сейчас, например, на наших глазах умирает человеческое программирование как написание кода, но пока ещё не как разработка программного продукта целиком. Но останется ли такая разработка человеческой деятельностью через 5-10 лет, мы уже никак не можем предсказать. Но это тоже не беда для системы образования! Мы учим детей делить в столбик не для того, чтобы они могли справиться без калькулятора при необходимости; такой необходимости, разумеется, никогда не возникнет. Мы это делаем для развития мета-навыков, в данном случае для понимания того, что такое алгоритм. Вот такие мета-навыки останутся нужными всегда (если человечество не вымрет, конечно, но это другая история).

Ну и традиционно отмечу, что GPT Images стал, кажется, ещё лучше. Выкладываю несколько слайдов — посмотрите, как он нарисовал пример деления в столбик, кажется, там буквально всё правильно, хотя я не просил ничего конкретного! Такая семантическая детализация раньше редко получалась.

#talks #ai #events