Разделить 12 участников викторины на две команды легко, пока не приходится учитывать знания каждого. Один хорошо разбирается в географии, но плохо знает музыку, другой помнит биологию, но почти не смотрит фильмы, третий силен в кино и слаб в литературе. Если нужно одновременно уравнять команды по истории, книгам, спорту, мифологии и десяткам других тем, задача быстро усложняется. Математики изучают подобные задачи в теории расхождений, где ищут способы распределить объекты между группами с минимально возможной разницей по заданным признакам.
В начале 1980-х математик Янош Комлош сформулировал гипотезу с неожиданно сильным условием. Сколько бы объектов и характеристик ни содержала система, объекты всегда можно разделить на две группы так, чтобы максимальное расхождение не превышало некоторую универсальную постоянную величину. Размер системы при этом может расти сколько угодно. Число учитываемых параметров тоже не должно влиять на предел расхождения.
За десятилетия никто не нашел контрпример, который опроверг бы гипотезу Комлоша. Доказательства тоже нет. Долгое время математики получали оценки, которые увеличивались вместе с размером задачи, поэтому постоянная граница казалась очень далекой. В 2025 году исследователям впервые почти за 30 лет удалось заметно улучшить лучший известный результат и приблизить верхнюю границу к константе.
Математическую постановку удобно разобрать на примере тех же участников викторины. Каждому человеку сопоставляют единичный вектор, то есть набор чисел, геометрически соответствующий стрелке длиной один. Каждая координата показывает вклад человека в определенную характеристику. Если учитывать только знания литературы и кино, понадобятся две координаты. Для десятков или сотен признаков используют векторы соответствующей размерности.
При распределении между двумя командами каждому вектору присваивают знак плюс или минус. Вектор первой команды сохраняют без изменений, а координаты вектора второй умножают на минус один. Затем все векторы складывают. Если сумма равна нулю, команды полностью уравновешивают друг друга по всем учитываемым характеристикам. На практике добиться нулевой суммы удается далеко не всегда, поэтому математики ищут распределение, при котором отклонение от нуля минимально.
Для нескольких объектов варианты еще можно перебрать вручную. С четырьмя участниками легко проверить все сочетания и выбрать распределение с минимальным расхождением. Равное количество людей в командах при этом необязательно. Значение имеет баланс характеристик, а не численность групп. С ростом числа векторов и координат количество возможных комбинаций увеличивается настолько быстро, что полный перебор перестает помогать. Гипотеза Комлоша утверждает: среди всех распределений все равно найдется вариант, где расхождение останется ниже одной и той же постоянной величины независимо от размерности задачи.
Простое случайное распределение дает намного худший результат. Расхождение растет вместе с количеством векторов (N). В 1985 году Джоэл Спенсер доказал, что верхнюю границу можно опустить до величины порядка (\log N). В 1998 году Войцех Банашчик улучшил оценку до (\sqrt{\log N}). Прогресс был значительным, но обе функции продолжают увеличиваться при росте (N), тогда как гипотеза Комлоша требует постоянной границы.
Оценка (\sqrt{\log N}) удерживала рекорд почти три десятилетия. Новое направление появилось благодаря алгоритмическому подходу. Вместо попытки сразу определить окончательную группу для каждого вектора исследователи начали использовать промежуточное дробное распределение.
В алгоритме 2010 года каждый вектор сначала условно делили между двумя группами. Например, вектор (\langle1,0\rangle) временно превращался в две части (\langle1/2,0\rangle). Затем случайная процедура постепенно меняла дробные значения, пока одна группа не получала исходный вектор целиком, а доля второй не обращалась в ноль. Алгоритм на каждом шаге ограничивал рост расхождения.
Первая версия позволяла получить границу порядка (\log N), уже известную из более раннего математического доказательства. В 2016 году алгоритм усовершенствовали и достигли оценки (\sqrt{\log N}), сравнявшись с рекордом 1998 года. Практический смысл алгоритмического подхода заключался в другом: доказательство теперь давало последовательность вычислений, с помощью которой можно находить распределение с гарантированно небольшим расхождением.
В 2022 году гипотезу Комлоша удалось доказать для систем с дополнительными ограничениями. Общая задача осталась открытой. В феврале 2025 года исследователи вернулись к полной версии и попробовали изменить сам способ контроля ошибок, возникающих во время распределения векторов.
Главная трудность связана с зависимостью между координатами. Улучшение баланса по одному признаку способно ухудшить другой. Представим две площадки, которые делят партию автомобилей. Машины можно распределить так, чтобы обе получили одинаковое количество автомобилей каждого цвета. После проверки типов кузова выяснится, например, что на одной площадке оказалось больше кабриолетов. Перемещение машин ради выравнивания числа кабриолетов нарушит уже достигнутый баланс по цветам.
Новый алгоритм учитывает не только текущее расхождение, но и зависимость между разными координатами. При каждом случайном изменении алгоритм оценивает, насколько корректировка одного параметра повлияет на остальные. Векторы по-прежнему сначала распределяют дробно, а затем постепенно переводят в окончательное состояние. Направления изменений выбирают так, чтобы разные координаты как можно меньше мешали друг другу.
Дополнительный контроль снизил верхнюю границу расхождения с (\sqrt{\log N}) до ((\log N)^{1/4}), четвертого корня из логарифма числа векторов. Улучшение стало первым для общей задачи Комлоша с 1998 года.
Разница между двумя формулами особенно заметна при больших значениях (N). Если (N=10), величина ((\log N)^{1/4}) составляет примерно один. Даже при (N=10^{81}), приблизительно соответствующем оценке числа атомов в наблюдаемой Вселенной, значение достигает лишь примерно трех. Поэтому новая граница растет настолько медленно, что для любых практически достижимых размеров системы ведет себя почти как постоянная величина.
Алгоритм при этом остается достаточно эффективным для вычислений. Методы теории расхождений применимы к задачам оптимизации, физики и финансов, где нужно распределять большое количество объектов при множестве одновременно действующих ограничений. Отдельные исследования связывают теорию расхождений с машинным обучением, включая методы улучшения больших языковых моделей.
Гипотеза Комлоша пока не доказана. Авторы нового результата считают, что алгоритмический подход, который развивают с 2010 года, уперся в границу ((\log N)^{1/4}). Продвинуться ниже четвертого корня прежними методами пока не получается, поэтому для доказательства постоянной границы потребуется другая идея. Математики при этом считают степень (1/4) вряд ли окончательным ответом: квадратный корень из логарифма регулярно возникает в разных задачах, а четвертый корень гораздо реже появляется как естественная предельная оценка. Следующая цель остается прежней - доказать, что расхождение действительно можно ограничить универсальной константой, которую предсказал Комлош больше сорока лет назад.