СКОЛЬКО КРАСОК НУЖНО, ЧТОБЫ РАСКРАСИТЬ ПРОСТРАНСТВО? ДЛЯ ТИПИЧНОЙ ЛИНЕЙКИ — НЕ БОЛЬШЕ 2d

Возьмите каждую точку плоскости и присвойте ей цвет. Правило одно: две точки на расстоянии ровно одна единица никогда не должны быть одного цвета. Какое наименьшее число цветов для этого достаточно?

Это задача Хадвигера — Нелсона, восходящая к 1950 году и, по словам авторов, одна из самых известных открытых задач дискретной геометрии. Долгое время было известно лишь, что ответ лежит между 4 и 7. Недавний прорыв поднял нижнюю границу до 5. Точный ответ по-прежнему неизвестен.

Смена линейки

Расстояние не обязательно мерить обычной линейкой. Математики определяют множество других норм — способов измерять длину, — каждая из которых описывается своим «единичным шаром», то есть множеством точек на расстоянии не более 1 от центра. Для обычного расстояния это круглый шар; для других норм — любая выпуклая фигура, симметричная относительно центра.

Для любой нормы на плоскости ответ на задачу о раскраске лежит между 4 и 7. В d измерениях он не более чем экспоненциален по d для любой нормы, а для многих естественных норм — включая обычную евклидову — ещё и не менее чем экспоненциален: число цветов взрывообразно растёт с размерностью.

Является ли этот взрыв правилом? Нога Алон (Принстонский и Тель-Авивский университеты), Матия Бучич (Венский университет) и Джеймс Дэвис (Лейпцигский университет) рассмотрели типичную норму. Естественного способа выбрать норму «наугад» нет, поэтому они используют топологическое понятие: свойство выполнено для типичной нормы, если исключения образуют пренебрежимое («тощее») множество. Ранее Алон, Бучич и Лиза Зауэрман показали, что типичной норме нужно не более 2ᵈ цветов, и спросили, насколько это близко к истине.

Линейно, а не экспоненциально

Ответ: очень далеко. Новая статья доказывает, что

• для типичной нормы в d-мерном пространстве всегда достаточно 2d цветов;
• это наилучший возможный результат: открытому множеству норм требуется не менее 2d цветов. Значит, некоторым нормам нужно ровно 2d.

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

Нижняя оценка использует изящную ловушку. Найдите 2d точек, попарно отстоящих друг от друга ровно на единицу, кроме двух, a и b, расстояние между которыми — половина единицы. Добавьте зеркальное отражение всей конфигурации относительно a. Если цветов меньше 2d, то и b, и её зеркальный образ вынуждены получить цвет a — но они находятся ровно на расстоянии единицы друг от друга. Противоречие. Лемма об устойчивости показывает, что эта конфигурация переживает любое малое изменение нормы.

Одинокий бегун в высоких размерностях

Верхняя оценка раскрашивает каждую точку в зависимости от того, куда попадает её удачно выбранная проекция, по полосам шириной 1/(2d). Чтобы это сработало, нужен ключевой ингредиент, который авторы описывают как многомерную матричную версию знаменитой гипотезы об одиноком бегуне (lonely runner conjecture):

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

где ‖t‖ — расстояние от t до ближайшего целого, для любых n векторов aᵢ в k измерениях, любые k из которых независимы. Это утверждение также доказывает гипотезу И. Дж. Шёнберга 1978 года о «препятствии обзору» (view obstruction) — вопрос о том, насколько толстыми должны быть периодические пластины, чтобы перекрыть любой взгляд на бесконечность, — которую авторы называют одной из самых классических открытых задач в этой области, а также родственную гипотезу Хенце и Маликиосиса.

Машина в благодарностях

Авторы говорят прямо: «ChatGPT 6 Pro предоставил нам доказательство последнего ингредиента, необходимого для доказательства теоремы 1, а именно леммы 7, после продолжительного обсуждения», в ходе которого они поделились собственными наблюдениями — включая идею индукции и общую стратегию. «Аргумент для нижней оценки также был найден с помощью ChatGPT 6 Pro».

Вопросы остаются. Точное значение 2d доказано на открытом множестве норм, а не для всех типичных. А для обычного евклидова расстояния авторы ожидают строго больше 2d цветов в каждой размерности — это уже известно в размерностях 2, 4, 7, 8 и начиная с 9, но всё ещё открыто в размерностях 3, 5 и 6.