Как распутать нераспутываемое? Уникальный «QR-код» за доли секунды распознает любые запутанные узлы

Узлы встречаются повсюду — от спутанных проводов до спиралей ДНК, но математики до сих пор не умеют надежно отличать один сложный узел от другого. Смысл здесь простой: можно ли превратить один узел в другой, если просто тянуть, сгибать и перекладывать нить, не разрезая ее и не склеивая заново. Если преобразование возможно, математика считает оба узла одним и тем же, даже если на рисунке они выглядят по-разному. Если не получается, узлы действительно разные. Новая работа международной группы предлагает инструмент, который одновременно точный и быстрый в расчетах, и тем самым открывает доступ к задачам, которые раньше считались практически недостижимыми.

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

За сто лет накопилось множество инвариантов, но почти все они подчиняются одному и тому же ограничению. Сильные инварианты хорошо различают узлы, но их трудно вычислять. Простые считаются быстро, но почти не помогают. Уже на уровне 15-20 пересечений многие методы либо перестают различать узлы, либо требуют неподъемных вычислений. При сотнях пересечений задача вообще выходит за пределы практических расчетов.

Дрор Бар-Натан из Университета Торонто и Роланд ван дер Веен из Университета Гронингена предложили новый инвариант, который снимает этот компромисс. Метод одновременно остается вычислимо простым и при этом сохраняет высокую различающую способность. Для узлов с сотнями пересечений вычисления выполняются без особых проблем, а отдельные параметры удалось получить даже для узлов с более чем 600 пересечениями.

С практической точки зрения разница огромная. Если раньше исследователи работали с относительно небольшими наборами узлов, теперь появляется возможность анализировать гораздо более сложные структуры. По оценкам, новый инвариант способен однозначно различать более 97% узлов с 18 пересечениями. Для сравнения: один из самых популярных инструментов, полином Джонса, справляется примерно с 42%, а полином Александера — примерно с 11%.

Сам результат оформляется в неожиданной форме. Для каждого узла метод выдает сложный многочлен от переменных, а визуализация коэффициентов превращает его в шестиугольный узор, напоминающий QR-код (на картинке ниже). У разных узлов рисунки не совпадают. Если узоры различаются, различаются и сами узлы.

Идея выросла из попыток упростить более мощный, но практически невычислимый инструмент — интеграл Концевича. Математики давно предполагают, что он способен различать любые узлы, но использовать его напрямую невозможно. Бар-Натан попытался построить приближения, которые сохраняют часть информации, но поддаются вычислению. Последовательность таких приближений известна, однако вычислять удавалось только самый простой уровень.

Отправной точкой стал полином Александера, известный с 1923 года. Его можно интерпретировать через наглядную модель. Узел представляют как одностороннюю дорогу, разрезанную в одной точке. Между каждым пересечением располагаются города, а машина, стартовавшая в начале, проезжает через них и уходит в конец. В местах пересечений вводятся развилки: с некоторой вероятностью машина меняет маршрут. Подсчет ожидаемого трафика через каждый город дает функции, из которых складывается полином.

Исследователи попытались усложнить модель. Вместо одного типа машин ввели несколько, с разными вероятностями поведения. Сначала подход не работал. Решение появилось после аналогии с физикой частиц: разные машины могут объединяться в новый тип, двигаться вместе, а затем снова разделяться. Такая схема позволила описать более сложные взаимодействия и сохранить вычислимость.

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

Несмотря на громоздкий вид формулы, компьютер справляется с расчетами быстро. При этом инвариант сохраняет глубокую топологическую информацию. Многие исследователи считают, что новый метод эквивалентен так называемому двухпетлевому полиному — второму приближению интеграла Концевича, которое изучают уже десятилетиями, но раньше не умели эффективно вычислять.

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

Работа оставляет открытым следующий шаг. Текущая формула работает, но пока не имеет простого объяснения. Исследователи считают, что за ней стоит более элементарная конструкция, которую еще предстоит найти. Параллельно можно развивать идею дальше — добавлять новые типы «машин» и переменные, чтобы извлекать все больше информации из интеграла Концевича.