Марк Лакенби: Человек, который распутал узел

«На данный момент не известно никакого систематического способа определить, являются ли два узла одинаковыми». Так Алан Тьюринг (Alan Turing) в 1954 году обозначил одну из самых упорно конкретных нерешенных задач в математике: дано переплетение веревки с соединенными концами, нужно решить, является ли это действительно узлом. Макс Ден (Max Dehn) поставил эту задачу в 1910 году. Вольфганг Хакен (Wolfgang Haken) разработал первый алгоритм в 1961 году, но он был безнадежно медленным при решении сложных задач. 2 февраля 2021 года в Калифорнийском университете в Дэвисе Марк Лакенби объявил, что вопрос можно решить за количество шагов порядка n в степени c log n — квазиполиномиальное время, что лишь на шаг опережает эффективность, которую компьютерные ученые считают признаком действительно решаемой задачи. Математики Оксфорда назвали это достижением в стиле Гордиева узла.

Кембридж и школа Ликориша

Лакенби поступил в Кембридж изучать математику в 1990 году и остался там для получения докторской степени, которую завершил в 1997 году под руководством У. Б. Р. Ликориша (W. B. R. Lickorish) с диссертацией под названием «Хирургия Дена и операции распутывания». Ликориш является одной из центральных фигур в теории узлов двадцатого века, и темы диссертации — хирургия Дена и распутывание — оставались темами Лакенби и четверть века спустя. Мало кто из математиков так рано выбирает свою область и продолжает находить в ней что-то новое.

Он был научным сотрудником Миллера в Калифорнийском университете в Беркли и научным сотрудником в Кембридже, прежде чем переехать в Оксфорд в 1999 году в качестве лектора и члена колледжа Святой Екатерины. В 2006 году последовало повышение до профессора. Его работа охватывает теорию узлов, низкоразмерную топологию и теорию групп — три предмета, которые в трех измерениях оказываются более или менее одним и тем же предметом, увиденным с разных сторон.

Заполнение дыр

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

Важный вопрос заключается в том, когда результат остается гиперболическим — гиперболическая геометрия — это структура, которая делает трехмерное многообразие жестким и анализируемым, а ее отсутствие — это то, где начинается дикая природа. Теорема 2π дает геометрический критерий, гарантирующий, что хирургия сохраняет гиперболичность. Лакенби доказал усиленную версию этой теоремы. Это типичный результат для него: не открытие нового ландшафта, а уточнение существующей границы, сделанное настолько хорошо, что гораздо большая территория попадает на полезную сторону.

Альтернированные узлы и объем

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

Лакенби установил границы гиперболического объема дополнений к альтернированным узлам (классу, в котором при прохождении по узлу пересечения чередуются над, под, над, под), связав геометрический инвариант с тем, что можно буквально подсчитать на чертеже. Результаты такого рода делают геометрию узлов вычислимой, а не просто умозрительной.

Считая движения Рейдемейстера

Любая диаграмма узла может быть превращена в любую другую диаграмму того же узла с помощью последовательности из трех элементарных манипуляций — движений Рейдемейстера. Это было известно с 1920-х годов, и само по себе это бесполезно: ничто не говорит вам, сколько движений требуется, и последовательность может проходить через диаграммы, гораздо более запутанные, чем любая из конечных точек, прежде чем упроститься. Именно поэтому распутывание узлов — сложная задача: часто приходится делать узел еще хуже, прежде чем он станет лучше.

Лакенби показал, что диаграмму тривиального узла можно распутать за количество движений Рейдемейстера, полиномиально зависящее от количества пересечений. Пессимизм был неуместен. Всегда есть достаточно короткий путь к тривиальному кругу, даже если найти его — отдельный вопрос.

Квазиполиномиальное время

Что возвращает нас к 2021 году. Проблема распознавания тривиального узла накопила много алгоритмов после Хакена, опирающихся на топологию и геометрию, и почти все они работали катастрофически медленно, как только узлы усложнялись. Существование полиномиального алгоритма стало одним из знаменитых открытых вопросов на стыке топологии и компьютерных наук. Уильям Терстон (William Thurston) в 2011 году сказал прямо: «Многие люди думали над этим вопросом... но это была очень трудная задача для решения».

Граница Лакенби n^(c log n) не совсем решает проблему. Квазиполиномиальное время медленнее полиномиального. Но разрыв между квазиполиномиальным временем и всем, что было до него, огромен, а разрыв между квазиполиномиальным и полиномиальным временем, с практической и концептуальной точек зрения, мал. Задача, которую Тьюринг включил в список неукротимых, теперь, по сути, укрощена.

Почему Марка называют гением

Демонстрируемое качество — это не скорость и не широта охвата. Это своего рода терпеливая глубина: оставаться с одним и тем же кругом вопросов — хирургия Дена, распутывание узлов, геометрия дополнений к узлам — в течение двадцати пяти лет, накапливая технику до тех пор, пока проблемы, сопротивлявшиеся поколениям, не стали доступными. Результат по распутыванию узлов — самое ясное доказательство, потому что он был достигнут не хитрым трюком. Он пришел к человеку, который посвятил карьеру созданию конкретного инструментария и мог видеть там, где другие не могли, какая комбинация топологических и геометрических инструментов сработает.

Признание со стороны коллег было последовательным, а не сенсационным: премия Уайтхеда Лондонского математического общества в 2003 году, премия Филипа Леверхульма в области математики и статистики в 2006 году, приглашение выступить на Международном конгрессе математиков в 2010 году — самый надежный сигнал дисциплины о том, что работа важна. Объявление 2021 года вызвало самые сильные формулировки, при этом Оксфорд назвал это «достижением» (tour-de-force).

Следует привести и контраргументы. Ни один источник не записывает, что кто-либо называл Лакенби гением, и математическая культура, к которой он принадлежит, удивительно скупа на это слово. Его работа напрямую опирается на Хакена, Терстона, Ликориша и всю традицию нормальных поверхностей; квазиполиномиальный алгоритм — это впечатляющее улучшение в рамках сложившейся структуры, а не новая структура. К тому же он не полиномиальный, что означает, что главный вопрос технически все еще открыт. А низкоразмерная топология, при всей своей красоте, — специализированная область: его результаты известны среди топологов и по большей части неизвестны за пределами.

Наследие

Что сделал Лакенби во всех четырех направлениях своей работы, так это сделал теорию узлов эффективной. Ограничение объемов подсчетом пересечений, ограничение распутывания подсчетом движений, ограничение распознавания подсчетом шагов — в каждом случае объект, который можно было только созерцать, стал объектом, который можно вычислить. Этот сдвиг превращает красивую теорию в полезную, и именно поэтому результат 2021 года вышел далеко за пределы топологии в теоретическую компьютерную науку. Ден задал вопрос в 1910 году. Потребовалось 111 лет и профессор в Оксфорде, который отказался заниматься чем-либо другим.