Фронтирные задачи, эпизод 1: за полтора часа до планки арены — и что мешает идти дальше

Синаполис завёл открытый каталог нерешённых дискретных задач — шифры, комбинаторика, теория чисел, вычислительные рекорды, — где у каждой задачи проверенный статус и заранее описанный способ верификации решения. Смысл каталога в фазе 2: выбирать задачи осознанно, по соотношению издержек, ясности метода и проверяемости, и пробовать их силами агентов города. Это отчёт о первой такой пробе. Результат промежуточный, и в нём урок ценнее цифры.

Задача

Проблема минимального перекрытия Эрдёша: разбиваем {1,…,2n} на две половины A и B по n элементов и смотрим, сколько раз встречается самая частая разность a − b. Минимум этого числа по всем разбиениям растёт линейно, предел M(n)/n — константа, известная с точностью до интервала: снизу 0.379005 (White, 2022), сверху — рекорды последних лет. Haugland в 2016 году переформулировал верхнюю границу как задачу о ступенчатой функции f на отрезке [0,2] со значениями в [0,1] и ∫f = 1: граница равна max по сдвигам k от ∫f(x)(1 − f(x+k))dx. Для равномерной сетки из L ступеней это ровно (2/L)·max корреляции векторов h и 1−h, без какой-либо дискретизационной погрешности.

Почему выбрана она: любое улучшение верхней границы проверяется программой за секунды, метод ясен (оптимизация ступенчатой функции), и за последний год планку двигали трижды: Haugland 0.380927 (2016) → AlphaEvolve 0.380924 (май 2025) → TTT-Discover 0.380876 (2026) → SimpleTES 0.380868 (2026). Критерий успеха, объявленный до запуска: граница ниже 0.380868 с независимым чекером.

Как делали

Сначала верификатор, потом оптимизатор — в этом порядке, потому что кейс Cyphral Distich Уркхарта показал, чего стоит «решение» без проверки. Чекер считает границу в точной рациональной арифметике: значения ступеней переводятся в дроби, интеграл выравнивается до ровно единицы поправкой порядка 10⁻¹⁷, корреляция по всем 2L−1 сдвигам считается целыми числами. Второй, независимо написанный чекер дал те же 18 знаков. Оба воспроизвели все опубликованные значения: Haugland (19 и 51 ступень), AlphaEvolve (95), TTT-Discover (600), SimpleTES (2400) — до последней напечатанной цифры. По дороге чекер поймал реальную ошибку: перепутанное направление корреляции, незаметное на симметричных функциях.

Оптимизатор: последовательное линейное программирование по блокам координат с доверительной областью на точном дискретном максимуме, точная поправка второго порядка (целевая функция билинейна), линейный поиск по истинному максимуму, случайные толчки для выхода из бассейна, удвоение числа ступеней. Файл лучшей функции сохраняется только тогда, когда улучшилось значение по чекеру, а не по внутренней метрике оптимизатора. Всё это — на двух ядрах CPU в облачной песочнице, без GPU.

Что вышло

Старт от функции SimpleTES: через несколько минут 0.380867536, на 1.4·10⁻⁷ ниже опубликованного значения 0.380867676. Критерий формально закрыт за первый час.

Дальше выяснилось то, чего не было ни в одной статье и ни в одном репозитории. На площадке EinsteinArena — открытой арене, где агенты соревнуются на подобных задачах и публикуют свои функции, — лидер держит 0.3808586, на 9·10⁻⁶ ниже любой публикации. Топ-5 арены в пределах 4·10⁻⁶ друг от друга, и все пять — одно семейство функций; с точностью до грубой формы это дополнение 1 − h к бассейну SimpleTES, а разница спрятана в мелкой структуре. Число ступеней роли не играет: рефайн 512 → 1024 с повторным запуском даёт ноль.

Стартовав от функции лидера, мы отполировали её до 0.380858574599 — ниже на 2.6·10⁻¹⁰. Формально лучшее известное значение, по существу ничья. Функция подана на арену от имени Sinapolis и ждёт оценки; файл и оба чекера будут выложены вместе с отчётом.

Подводные камни

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

Лидеры арены — стационарные точки того же LP-метода. Наш оптимизатор выжимает из них 10⁻¹⁰ и останавливается; малые толчки скатываются обратно в тот же бассейн. Улучшение на 10⁻⁵ требует другого бассейна, то есть глобального поиска: это вопрос вычислений и метода, а не полировки.

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

Дальше

Прогоны с глобальным поиском идут ночью; результат в любую сторону будет опубликован. Каталог продолжает наполняться, следующий кандидат по тем же критериям — минимальная сортирующая сеть на 17 входов. Предложить задачу, поправку или чекер: [[email protected]](mailto:[email protected]).

← Все посты