Два математика доказали, что на простой вопрос — насколько сложно развязать узел? — существует сложный ответ. Комментарий Сохранить статью Прочитать позже
Введение
В 1876 году Питер Гатри Тейт решил измерить то, что он назвал «узловатостью» узлов.
Шотландский математик, чьи исследования заложили основу современной теории узлов, пытался найти способ различать узлы — задача, известная своей сложностью. В математике узел — это спутанная нить со склеенными концами. Два узла считаются одинаковыми, если их можно скрутить и растянуть, не разрезая нить. Но сложно сказать, возможно ли это, основываясь только на внешнем виде узлов. Например, узел, который кажется очень сложным и запутанным, на самом деле может быть эквивалентом простой петли.
Тейту пришла в голову идея, как определить, различаются ли два узла. Сначала положите узел на стол и найдите место, где нить перекрещивается. Разрежьте нить, поменяйте местами нити и склейте всё обратно. Это называется перекрещиванием. Если вы проделаете это достаточное количество раз, у вас останется незавязанный круг. Завязанность Тейта — это минимальное количество перекрещиваний, необходимое для этого процесса. Сегодня это называется «числом распутывания» узла.
Если два узла имеют разные числа развязывания, то они должны быть разными. Но Тейт обнаружил, что его числа развязывания породили больше вопросов, чем дали ответов.
«Я настолько глубоко усвоил одно и то же, — писал он в письме другу, ученому Джеймсу Клерку Максвеллу, — что опасаюсь, что упускаю или чрезмерно преувеличиваю что-то, что покажется чрезмерно простым всем, кроме меня».
Если Тейт что-то упустил, то же самое сделали и все математики, последовавшие за ним. За последние 150 лет многие специалисты по теории узлов были озадачены числом развязывания. Они знают, что оно может дать мощное описание узла. «Это, пожалуй, самая фундаментальная [мера] из всех», — сказала Сьюзен Хермиллер из Университета Небраски. Но часто вычислить число развязывания узла невероятно сложно, и не всегда ясно, как это число соотносится со сложностью узла.
Чтобы разгадать эту загадку, математики в начале XX века выдвинули простую гипотезу о том, как изменяется число развязывания при объединении узлов. Если бы им удалось это доказать, они бы получили способ вычислить число развязывания для любого узла, что дало бы математикам простой и конкретный способ измерения сложности узлов.
Исследователи искали почти столетие, но не нашли практически никаких доказательств ни в пользу, ни против этой гипотезы.
Затем, в статье, опубликованной в июне, Хермиллер и её давний коллега Марк Бриттенхэм обнаружили пару узлов, которые в сочетании образуют узел, развязать который легче, чем предсказывает гипотеза. Тем самым они опровергли гипотезу и, используя свой контрпример, нашли бесконечное множество других пар узлов, также её опровергающих.
«Когда статья была опубликована, я ахнула вслух», — сказала Эллисон Мур из Университета Содружества Вирджинии.
Результат показывает, что «распутывающее число хаотично и непредсказуемо, и его изучение действительно увлекательно», — добавила она. Эта работа — «как размахивание флагом, которое говорит: мы этого не понимаем».
Распутывание и Великое Неизвестное
Гипотеза появилась как минимум в 1937 году, когда немецкий математик Хильмар Вендт решил понять, что происходит, когда узлы складываются, то есть когда оба узла связываются одной и той же нитью, а концы склеиваются. (Математики называют этот объединённый узел «соединительной суммой».) Вендт считал, что число развязываний получившегося узла всегда должно быть суммой чисел развязываний двух исходных узлов.
Его предсказание, теперь известное как гипотеза аддитивности, имеет смысл. Допустим, вы складываете два узла, описанных выше, числа развязывания которых, как известно, равны 2 и 3. Это означает, что существует последовательность из двух скрещивающихся изменений, которая развязывает левую часть суммы-соединений, и последовательность из трёх скрещивающихся изменений, которая развязывает правую часть. Используя эти последовательности, вы можете развязать всё за 2 + 3, или 5 скрещивающихся изменений.
Но это говорит лишь о том, что число развязываний суммы соединения не превышает 5. Возможно, вам удастся найти последовательность перекрещивающихся изменений, которая будет эффективнее, чем развязывание каждой стороны по отдельности. То есть, может оказаться, что узел действительно меньше суммы своих частей.
Чтобы доказать гипотезу аддитивности, математикам нужно было либо найти связную сумму с более короткой последовательностью развязывания, либо доказать, что такого примера не существует. В любом случае они понятия не имели, с чего начать.
Отчасти проблема заключалась в том, что способ расположения узла — то, что математики называют «схемой» — определяет, где и как узел пересекает сам себя. Существует множество схем, которые могут представлять один и тот же узел. Чтобы найти кратчайшую последовательность изменений в пересечении, вам, возможно, придётся выбрать подходящую схему. Зачастую это не та, которую вы обычно ассоциируете с узлом.
«Существует невообразимое количество способов попытаться представить себе изменение вашей диаграммы, прежде чем вы решите ввести изменение с помощью пересечения», — сказал Бриттенхэм. «Мы не можем, по крайней мере на начальном этапе, контролировать, насколько сложной должна быть картинка».
В 1985 году математик Мартин Шарлеманн наконец добился некоторого прогресса, когда доказал, что для любых двух узлов, число развязывания которых равно 1, сумма связей всегда будет иметь число развязывания, равное 2. «Это сделало [всю гипотезу] гораздо более правдоподобной», — сказал Чарльз Ливингстон из Университета Индианы.
Сьюзен Хермиллер (слева) и Марк Бриттенхэм опровергли давнюю гипотезу об узлах, усложнив понимание математиками этих, казалось бы, простых объектов.
Результат предоставил заманчивое доказательство того, что вселенная узлов может быть чётко организована. Это связано с тем, что все узлы можно построить из более узкого класса «простых» узлов. Гипотеза аддитивности подразумевала, что, зная числа развязывания этих простых узлов, вы узнаете их для всех узлов. Любая информация, которая может вам понадобиться о данном узле, естественным образом вытекает из этого гораздо более простого набора.
Математики хотели, чтобы эта гипотеза оказалась верной, говорит Арунима Рэй из Мельбурнского университета, «потому что это означало бы, что в мире есть порядок».
Результат Шарлемана был позднее распространён на другие классы узлов. Однако было неясно, применим ли он ко всем узлам.
Затем Бриттенхэм и Хермиллер объединили усилия с группой компьютеров, чтобы оказать помощь.
Sneakernet
Пара начала свой проект десять лет назад с более широкой целью: с помощью компьютеров узнать как можно больше о числе, распутывающем узел.
Они обратились к программному обеспечению SnapPy, которое использует сложные геометрические методы для проверки того, изображает ли два изображения один и тот же узел. Всего несколько лет назад SnapPy значительно расширил свою базу данных, что позволило ему идентифицировать почти 60 000 уникальных узлов.
Он идеально подходил для замысла Бриттенхэма и Хермиллера. Они взяли за основу один сложный узел и применили к нему все мыслимые способы перекрещивания, получив множество новых узлов. Затем они воспользовались SnapPy для идентификации этих узлов и повторили процесс.
Они проделали это для миллионов диаграмм узлов, соответствующих сотням тысяч узлов. В конечном итоге они собрали огромную библиотеку информации о последовательностях развязывания узлов и вычислили верхние границы количества развязываний для тысяч узлов. Работа требовала огромных вычислительных мощностей: пара зарегистрировалась на суперкомпьютерном рабочем месте в вычислительном центре Университета Небраски, одновременно запуская свою программу на старых ноутбуках, купленных на аукционе. В общей сложности им приходилось управлять десятками компьютеров. «У нас был своего рода сникернет, — сказал Бриттенхэм, — где информация передавалась с компьютера на компьютер, просто переходя между ними».
Тейт составил таблицу десятков узлов и описал их свойства. Эта страница взята из статьи 1885 года.
Дуэт поддерживал свою программу в фоновом режиме более десяти лет. За это время пара компьютеров из их разношёрстной коллекции перегрелась и даже загорелась. «Один компьютер буквально высек искры», — сказал Бриттенхэм. «Было довольно забавно». (Он добавил, что эти машины «с почётом были отправлены на пенсию»).
Затем, осенью 2024 года, внимание Бриттенхэма и Хермиллера привлекла статья о неудачной попытке опровергнуть гипотезу аддитивности с помощью машинного обучения. Возможно, они решили, что машинное обучение — не лучший подход к решению этой конкретной задачи: «Если бы существовал контрпример к гипотезе аддитивности, он был бы «иголкой в стоге сена», — сказал Хермиллер. «Машинное обучение не совсем в этом суть. Оно заключается в поиске закономерностей в явлениях».
Но это усилило подозрения, которые уже были у пары, — что, возможно, их более тщательно отточенная сеть кроссовок сможет найти иголку.
Галстук, который связывает
Бриттенхэм и Хермиллер поняли, что могут использовать обнаруженные ими распутывающие последовательности для поиска потенциальных контрпримеров к гипотезе аддитивности.
Представьте себе, что у вас есть два узла с числами развязывания 2 и 3, и вы пытаетесь развязать их сумму связей. После одного перекрещивания получается новый узел. Если верить гипотезе аддитивности, то число развязывания исходного узла должно быть равно 5, а нового — 4.
Но что, если число развязываний этого нового узла уже известно и равно 3? Это означает, что исходный узел можно развязать всего за четыре шага, что опровергает гипотезу.
«У нас есть эти средние узлы, — сказал Бриттенхэм. — Чему мы можем у них научиться?»
У них с Хермиллером уже имелся идеальный инструмент для такого случая, работающий на их ноутбуках: база данных, на разработку которой они потратили предыдущее десятилетие, с ее верхними пределами развязывания узлов в тысячи узлов.
Математики начали добавлять пары узлов и прорабатывать последовательности распутывания их сумм связей. Они сосредоточились на суммах связей, чьи числа распутывания были оценены лишь в самом грубом смысле, с большим разрывом между их максимальным и минимальным возможными значениями. Но это всё равно оставило им огромный список узлов для анализа — «определённо в десятки миллионов, а возможно, и в сотни миллионов», — сказал Бриттенхэм.
В течение нескольких месяцев их компьютерная программа применяла к этим узлам скрещивание и сравнивала полученные узлы с узлами в базе данных. Однажды поздней весной Бриттенхэм, как и обычно, проверил выходные файлы программы, чтобы посмотреть, не появилось ли чего-нибудь интересного. К его великому удивлению, там была строка текста: «CONNECT SUM BROKEN». Это сообщение они с Хермиллером закодировали в программе, но никак не ожидали увидеть его.
Поначалу они сомневались в результате. «Первое, что пришло нам в голову, — это то, что что-то не так с нашей программой», — сказал Бриттенхэм.
«Мы просто отбросили абсолютно всё остальное», — вспоминал Хермиллер. «Вся жизнь просто исчезла. Еда и сон стали раздражать».
Но их программа сработала. Они даже завязали узел на верёвке, который она определила, а затем вручную развязали его, просто для уверенности.
Их контрпример был реальным.
Запутанные тайны
Контрпример, найденный Бриттенхэмом и Хермиллером, построен на основе двух копий узла, называемого торическим узлом (2, 7). Этот узел получается путём обматывания двух нитей друг вокруг друга три с половиной оборота и последующего склеивания их противоположных концов. Его зеркальное отражение получается путём обматывания в обратном направлении три с половиной оборота.
Число развязывания как торического узла (2, 7), так и его зеркального отражения равно 3. Но программа Бриттенхэма и Хермиллера обнаружила, что если сложить эти узлы, то можно развязать результат всего за пять шагов, а не за шесть, как предсказывала гипотеза аддитивности.
«Это поразительно простой контрпример, — сказал Мур. — Всё дело в непредсказуемости перехода границы».
Результат привел Бриттенхэма и Хермиллера к бесконечному списку других контрпримеров, включая практически любой узел, образованный путем наматывания двух нитей и склеивания.
Теперь, когда гипотеза аддитивности окончательно опровергнута, у сообщества теории узлов появился огромный мир для исследования.
Для некоторых математиков новый результат разочаровал. Он показывает, что в мире узлов меньше структур, чем они надеялись. Число, необходимое для развязывания узла, «ведёт себя не так хорошо, как хотелось бы», — сказал Рэй. «Это немного печально».
Но с другой стороны, это только делает число развязывания узлов ещё более интригующим. «В теории узлов гораздо больше сложностей и неизведанного, чем мы предполагали несколько месяцев назад», — сказал Ливингстон.
Природа этой дополнительной сложности пока не ясна. В ходе тщательного анализа своего контрпримера Бриттенхэм и Хермиллер не смогли интуитивно понять, почему он нарушает гипотезу аддитивности, в то время как другие узлы — нет. Понимание этого может помочь математикам лучше понять, почему одни узлы сложные, а другие — менее.
«Меня всё ещё озадачивает этот самый простой вопрос» о числе, которое нужно развязать, — сказал Мур. — «Это просто разжигает огонь в вашей душе».
Примечание редактора: исследование Бриттенхэма и Хермиллера частично финансировалось Фондом Саймонса, который также финансирует этот независимо в редакционном отношении журнал. Решения Фонда Саймонса о финансировании не влияют на наше освещение событий.
Источник: www.quantamagazine.org
