ГИПОТЕЗА О ПОДСОЛНУХАХ ДОКАЗАНА

Возьмите числа от 1 до n и рассмотрите все способы выбрать некоторые из них: таких подмножеств 2ⁿ. Теперь выберите несколько подмножеств, у которых ровно одна и та же общая часть и больше ничего общего. Математики называют это подсолнухом (sunflower): общая часть — это ядро, а то, что остаётся от каждого множества, — лепесток, не касающийся ни одного другого лепестка.

Подсолнухи — базовый инструмент комбинаторики. В статье перечислены связи с ограничениями некоторых логических схем, с задачей о «cap set», с быстрым умножением матриц и с теорией информации.

Вопрос из 1970 года

Самый естественный вопрос о них, по словам авторов, восходит к статье Пала Эрдёша 1970 года. Насколько большим может быть набор подмножеств {1, …, n}, если никакие k его множеств не образуют подсолнух?

В 1970-х Эрдёш и Эндре Семереди предположили, что такой набор должен быть экспоненциально меньше 2ⁿ возможных подмножеств: не больше cⁿ для некоторого числа c, строго меньшего 2.

Десятилетиями лучшие оценки отщипывали совсем немного и ни разу не опускали основание ниже 2. Решён был лишь случай трёх лепестков (k = 3) — в 2016 году, благодаря прорыву в задаче о cap set и редукции Алона, Шпилки и Уманса.

Оценка

Матия Бучич и Фанкан Хэ (Венский университет) и Хёну Ли (KAIST и Институт фундаментальных наук, Южная Корея) доказывают гипотезу для всех k ≥ 3. Их основная теорема: набор без подсолнуха из k лепестков содержит не более

3 · (2 − 1/(16k³))ⁿ

элементов. Основание лишь чуть меньше 2, но это фиксированное число меньше 2 — именно этого и требовали Эрдёш и Семереди. Конструкция 1997 года показывает, что при больших k истинное значение не может быть намного ниже.

От множеств к векторам

Доказательство проходит через версию задачи с векторами. Разбейте числа на n блоков по D элементов и выберите по одному элементу в каждом блоке: каждый такой выбор — вектор. Несколько векторов образуют подсолнух, если в каждой позиции их компоненты либо все равны, либо все различны.

Затем авторы строят «тестер подсолнухов»: функцию, которая на наборе без подсолнухов отлична от нуля, только когда все её аргументы — один и тот же вектор. Новый ингредиент — записать эту функцию шаг за шагом с помощью интерполяционных многочленов малой степени. Подсчёт этих многочленов ограничивает размер набора (их теорема 2). Вероятностное рассуждение — случайные блоки с усреднением по всем размерам множеств — переносит оценку обратно на обычные множества.

Найдено одной машиной, проверено другой

Заявление статьи об ИИ необычайно прямое. Доказательство теоремы 2 нашёл ChatGPT 6 Astra Pro после короткого обсуждения, которое началось с просьбы обобщить известное рассуждение для трёх лепестков. Авторам этот шаг был нужен для другой цели: индуцированной версии задачи о графах, поставленной Семереди, которую они анонсируют в следующей заметке.

Модель записала доказательство на языке «slice rank» (срезового ранга). Авторы переписали его на языке полиномиального метода, который считают более доступным для читателей. Они заявляют, что проверили каждый результат и несут за него полную ответственность, а доказательство проверено в Lean 4.35 — программе для проверки доказательств; проверка будет выложена в репозиторий Palomar.

Что остаётся нерешённым

Авторы не пытались оптимизировать основание. Для трёх лепестков оно не превосходит оценку Наслунда и Сойина 2017 года, около 1,89. А более сильная родственная задача, гипотеза Эрдёша — Радо о подсолнухах, остаётся открытой: их оценки всё ещё сильно зависят от размера блока D, а именно это та задача и запрещает.