СОЕДИНИТЕ КАЖДУЮ ТОЧКУ С КАЖДОЙ: НАИМЕНЬШЕЕ ЧИСЛО ПЕРЕСЕЧЕНИЙ ДОКАЗАНО

Поставьте на листе бумаги пять точек и соедините каждую пару кривой — всего десять кривых. Они могут изгибаться как угодно, но ни одна не должна проходить через третью точку. Попробуйте избежать всех пересечений — и у вас не выйдет. При пяти точках неизбежно хотя бы 1 пересечение; при шести — не менее 3; при десяти — не менее 60.

Математики называют такую картинку рисунком полного графа Kₙ — n точек, каждая пара соединена, — а наименьшее число пересечений, которого может достичь какой-либо рисунок, — его числом пересечений. Мартин Балко (Martin Balko) из Карлова университета в Чехии называет этот вопрос «одной из самых известных задач топологической теории графов».

Подсчёт художника

В конце 1950-х британский художник Энтони Хилл (Anthony Hill) построил рисунки Kₙ ровно с

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

пересечениями, где ⌊ ⌋ означает округление вниз. Предположение, что ни один рисунок не может быть лучше, впервые опубликовал Гай (Guy), позднее его обсуждали Харари (Harary) и Хилл, а популяризировали Эрдёш (Erdős) и Гай. Оно известно как гипотеза Харари — Хилла, или гипотеза Гая.

Формула быстро растёт:

4 точки или меньше: 0 пересечений
5 точек: 1
7 точек: 9
10 точек: 60
14 точек: 315

Шесть десятилетий частичных ответов

Рисунки ровно с Z(n) пересечениями существовали для любого числа точек; трудность состояла в том, чтобы показать, что ни один рисунок не даёт меньше.

Более шестидесяти лет это удавалось доказать лишь для особых видов рисунков — например, когда все точки лежат на одной прямой, а каждая кривая остаётся по одну сторону от неё, или когда точки лежат на сфере, а каждая кривая идёт по кратчайшему пути. Сам Балко вместе с Фулеком (Fulek) и Кинчлом (Kynčl) решил задачу для одного такого класса. К 2021 году компьютеры подтвердили формулу вплоть до 14 точек. Для очень больших чисел точек лучшие общие результаты гарантировали не менее 98,5%, а затем 98,99% от Z(n).

Доказательство, а затем более ясное

В 2026 году OpenAI объявила о доказательстве для любого числа точек; в статье Балко оно значится как «OpenAI Math Release preprint», и именно ему приписана теорема. Статья не сообщает, как было найдено это доказательство. По словам Балко, оригинал «относительно короткий», но «довольно трудный для понимания». Его препринт излагает упрощённый вариант, который, как он пишет, «требует лишь элементарных знаний линейной алгебры и теории графов». Другой математик, Хеласио Салазар (Gelasio Salazar), готовит отдельное подробное изложение.

Считать коэффициенты вместо пересечений

Поскольку известные рисунки уже достигают Z(n), доказывать нужно лишь нижнюю оценку. Для этого требуется четыре хода.

Достаточно нечётных чисел. Наилучший рисунок можно перерисовать так, чтобы кривые с общей точкой никогда не пересекались; тогда в каждом пересечении участвуют 4 разные точки. Удалите по очереди каждую из 6 точек: каждая оставшаяся картинка из 5 точек имеет хотя бы 1 пересечение, а каждое пересечение переживает ровно 2 из 6 удалений (оно исчезает всякий раз, когда удаляется одна из его собственных 4 точек, и переживает остальные 2). Значит, удвоенное число пересечений не меньше 6: пересечений не меньше 3, а это и есть Z(6). Тот же подсчёт работает для любого чётного числа.
Семейство многочленов. Дайте каждой точке собственное число. В пересечении участвуют две кривые, значит, четыре точки, значит, четыре числа. Балко использует многочлены от четырёх переменных, подобранные так, чтобы при нечётном n у семейства было ровно Z(n) независимых коэффициентов — для 7 точек 3 × 3 = 9.
Слишком мало пересечений оставляет свободу. Потребовать, чтобы многочлен обращался в нуль в пересечении, — это одно уравнение. Когда уравнений меньше, чем свободных коэффициентов, линейная алгебра всегда оставляет ненулевое решение. Поэтому рисунку с менее чем Z(n) пересечениями соответствовал бы ненулевой многочлен, обращающийся в нуль во всех его пересечениях; возьмём такой многочлен наименьшей степени.
Плоскость сопротивляется. Геометрия входит через один классический факт: замкнутая петля на плоскости пересекает другую справа налево ровно столько же раз, сколько слева направо. При удачно выбранных весах это даёт сумму квадратов значений многочлена — одни считаются со знаком плюс, другие со знаком минус, — равную нулю. Все положительные слагаемые приходятся на пересечения, где многочлен равен нулю, значит, и отрицательные тоже должны обратиться в нуль. Повторное применение факта о петлях делает его делимым на фиксированный множитель; деление даёт ненулевой многочлен меньшей степени с тем же свойством, что невозможно: ведь мы взяли многочлен наименьшей степени.

Этот довод о знаках — главное изменение Балко: он заменяет исходное рассуждение, «использующее невырожденную билинейную форму и ортогональные дополнения». Он также иначе доказывает факт о петлях и более непосредственно выделяет каждую точку.

Другие сети — заодно

Ответ остаётся равным Z(n), если считать не пересечения, а пары кривых, которые вообще пересекаются или пересекаются нечётное число раз, — при условии, что кривые с общей точкой больше нигде не встречаются. В сочетании с более ранними сведениями одних задач к другим теорема также даёт точные числа пересечений для полных графов с несколькими удалёнными рёбрами, для копий полного графа, сцепленных вдоль пути или по чётному циклу, и для семейства фракталоподобных сетей, называемых расширенными графами Серпинского.

Уберите из полного графа на 6 точках одну-единственную кривую — и его минимум упадёт с 3 пересечений до 2; на 8 точках — с 18 до 15.