Вы давеча накидали мне так много реакций, что я не мог не откликнуться на этот запрос. Тем более что в итоге оказалось, что довольно много чего о гипотезе Эрдёша, которую давеча опроверг 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