Новый подход к классификации зацеплений и алгоритмическому распознаванию тривиального узла тема диссертации и автореферата по ВАК РФ 01.01.04, доктор физико-математических наук Дынников, Иван Алексеевич

• Дынников, Иван Алексеевич
• доктор физико-математических наук
• 2006

Оглавление диссертации доктор физико-математических наук Дынников, Иван Алексеевич

Введение

Глава 1. Классификация неориентированных зацеплений с помощью полугруппы

§1.1. Неориентированные n-страничные зацепления

§1.2. Кодирование специальных n-страничных зацеплений

§1.3. Конструкция конечно определенных полугрупп с центром, классифицирующим зацепления

§1.4. Категория плетений и полугруппа плетений

§1.5. Полугруппа n-страничных плетений

§1.6. Построение гомоморфизма Т —>Yn

§1.7. Вывод «коротких» соотношений в Yn

§1.8. Вывод «длинных» соотношений в полугруппе Yn

§1.9. Завершение доказательства изоморфности Уп и

§1.10. Центр полугруппы Yn

Глава 2. Классификация ориентированных зацеплений с помощью полугруппы

§2.1. Ориентированные 2п-страничные плетения

§2.2. Ориентированные плетения

§2.3. Проверка соотношений в Zn

§2.4. Завершение доказательства предложения 2.2 и теоремы

Глава 3. Распознавание тривиального узла и факторизация зацеплений с помощью монотонного упрощения

§3.1. Теорема о монотонном упрощении

§3.2. Книжные зацепления и прямоугольные диаграммы

§3.3. Элементарные движения книжных зацеплений

§3.4. Обобщенные движения

§3.5. Схема доказательства теоремы

§3.6. Характеристические поверхности

§3.7. Преобразования характеристической поверхности

§3.8. Всегда присутствующие фрагменты слоения Т

§3.9. Упрощение характеристической поверхности

§3.10. Полное разложение на простые

§3.11. Алгоритм для распознавания тривиального узла и факторизации зацеплений

§3.12. Оценка сверху для числа дополнительных пересечений, достаточных для распутывания плоской диаграммы тривиального узла

Введение диссертации (часть автореферата) на тему «Новый подход к классификации зацеплений и алгоритмическому распознаванию тривиального узла»

Теория узлов является классическим разделом топологии, активно развивающимся с конца XIX века. Центральное место в этой теории занимает проблема классификации узлов и зацеплений в трехмерном пространстве. На обычном языке это означает описать все способы, которыми можно завязать веревку (в случае зацеплений — несколько веревок).

Под узлом или зацеплением в настоящей работе всегда подразумеваются так называемые ручные узлы и зацепления. Это понятие в точности отвечает нашему представлению о «физических» узлах. Поэтому мы сразу дадим определение таким образом, чтобы исключить так называемые дикие узлы (в которые можно завязывать только бесконечно тонкие веревки).

Итак, зацеплением мы будем называть объединение конечного числа попарно непересекающихся простых кусочно гладких замкнутых кривых в трехмерном пространстве R3 или трехмерной сфере S3. Эти кривые могут быть наделены ориентацией, в этом случае мы будем говорить об ориентированном зацеплении. Зацепление из одной связной компоненты называется также узлом. Зацепление (или узел) называется тривиальным, если оно эквивалентно зацеплению, целиком содержащемуся в некоторой плоскости.

Под простой кусочно гладкой кривой понимается одномерное PL-подмногообразие в R3 (или S3) для PL-структуры, заданной некоторой гладкой триангуляцией.

Два зацепления L и L' называются эквивалентными или объемлемо изотопными в R3 (или S3), если существует кусочно-гладкий гомеоморфизм h : М3 —► R3 (или, соответственно, h : S3 —> S3), изотопный тождественному и переводящий L в L' (с учетом ориентации, если речь идет об ориентированных зацеплениях).

Хорошо известно [54, 55], что в определениях зацепления и объемлемой изотопности условие кусочной гладкости можно заменить на кусочную линейность или гладкость, и получится эквивалентная теория. Известны также другие способы определить эквивалентность зацеплений, дающие те же классы эквивалентности. Например, для гомеоморфизма h достаточно требовать сохранение ориентации пространства R3 (то есть, чтобы его степень равнялась единице). Мы не останавливаемся подробно на этих вопросах, считая их общеизвестными.

Хорошо известно также, что для классификации не имеет значения, рассматривать ли узлы и зацепления в R3 или в S3. При одноточечной ком-пактификации пространства R3 получается сфера, что дает сопоставление каждому зацеплению в R3 зацепление в53и при этом: 1) отношение эквивалентности сохраняется; 2) каждый класс эквивалентности зацеплений в S3 содержит представителя, не проходящего через добавленную точку.

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

На множестве С (иди Сот) определена коммутативная и ассоциативная операция несвязной суммы, если X, X' — два класса эквивалентности (ориентированных) зацеплений, то в них найдутся представители L £ X, U G X', лежащие но разные стороны от некоторой плоскости (или сферы S2 С S3). Тогда класс эквивалентности объединения L U 11 является но определению несвязной суммой классов X и X' и обозначается через X U X'. Легко показать, что это определение корректно, и что в полугруппах С и £ог имеется однозначное разложение на неприводимые слагаемые, называемые неразводимыми зацеплениями. Нетрудно также указать бесконечный набор попарно неэквивалентных (ориентированных) неразводи-мых зацеплений и показать, что множества £ и £ог счетны. Таким образом, С и Сог представляют собой счетно порожденные свободные абелевы полугруппы с единицей, роль которой играет пустое зацепление.

На множестве классов эквивалентности ориентированных узлов определена также операция связного суммирования. А именно, если К\ и К2 — два ориентированных узла в R3, расположенные по разные стороны от некоторой плоскости, то их связной суммой, обозначаемой К1ФК2, называется любой узел, полученный из К\ U К? вырезанием дуг а С К\ и

3 С К2 и заменой их на пару других дуг 7, S при условии, что объединение a U р U 7 U tf является краем вложенного двумерного диска D С Е3, внутренность которого не пересекает узлов К\ и При этом требуется также, чтобы ориентации дуг а., (5 в крае 0D совпадали. Связная сумма наследует ориентацию со своих слагаемых.

Легко убедиться, что связная сумма определена для любой пары ориентированных узлов, при этом однозначно с точностью до эквивалентности, и что она коммутативна и ассоциативна как операция на классах эквивалентности. Таким образом, множество классов эквивалентности ориентированных узлов является коммутативной полугруппой. Тривиальный узел играет роль единицы в этой полугруппе. Как показал X. Шуберт [61], в этой полугруппе также имеет место однозначное разложение на простые слагаемые. Узлы, не представимые в виде связной суммы двух нетривиальных узлов, называются простыми или неприводимыми, а представимые — составными.

Связное суммирование определяется также для ориентированных непустых зацеплений, но теперь эта операция является неоднозначной, если хотя бы одно из зацеплений имеет более одной компоненты. Если зафиксировать, из каких компонент вырезаются упомянутые выше дуги а и (5, результат снова определен однозначно с точностью до эквивалентности. Для неразводимых зацеплений имеет место аналог утверждения об однозначном разложении на простые слагаемые [34], в котором нужно лишь сделать необходимые поправки, связанные с неоднозначностью операции. Таким образом, для классификации всех зацеплений достаточно классифицировать неприводимые зацепления.

Интерес к классификации узлов и зацеплений появился еще до того, как были заложены основы математически формализованной теории. Таблицы простых узлов малой сложности составлялись уже в XIX веке [64, 45, 49], в то время как первые доказательства нетривиальности некоторых узлов появились лишь в начале XX века (по-видимому, первый результат такого рода принадлежит Виртингеру, который в 1905 г. доказал нетривиальность трилистника — простейшего из нетривиальных узлов — с помощью фундаментальной группы). В дальнейшем эти таблицы подвергались исправлениям и дополнениям [15, 14, 12, 58], значительное расширение таблиц произошло в последние годы благодаря использованию компьютеров и развитию численных методов [18, 38, 47].

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

Возможны различные точки зрения на то, что следует считать решением проблемы классификации зацеплений. Наиболее формализованный подход к классификации, называемый алгоритмической классификацией, состоит в построении вычислимого взаимно однозначного соответствия между элементами множества С (или £ог) и натуральными числами. Не составляет труда построить алгоритм для перечисления элементов множества С (£ог) с неконтролируемым числом повторений каждого элемента, поэтому задача алгоритмической классификации по сути равносильна задаче алгоритмического сравнения зацеплений.

Первым достижением в этой области была работа В.Хакена [31], который, используя теорию нормальных поверхностей [46], предложил алгоритм для распознавания тривиального узла. X. Шуберт [62] обобщил его метод, построив алгоритм для полного разложения зацепления на неприводимые слагаемые. Отметим, что эти алгоритмы требуют достаточно большого перебора, который превышает возможности современных компьютеров даже для узлов с небольшим числом пересечений на диаграмме (10 — уже, как правило, слишком много). Поэтому для составления таблиц и сравнения узлов на компьютере обычно используются другие методы — вычисление инвариантов, нахождение геометрической структуры дополнения, эвристические методы.

Полное решение задачи алгоритмической классификации зацеплений потребовало развития сложной теории и усилий целого ряда математиков

32, 33, 39, 40, 36, 37, 65, 9] и было завершено лишь недавно С. В. Матвеевым [51].

Построенный в [51] алгоритм дает формальное решение задачи алгоритмической классификации, но неприменим на практике из-за очень большой сложности, а биекция N «-> которую он вычисляет, не обладает какими-либо интересными свойствами, помимо вычислимости.

Имеются и другие достижения, относящиеся к классификации узлов и зацеплений. К одному из первых продвижений в этой области следует отнести классическую теорему К. Райдемайстера [59], которая описывает классы эквивалентности зацеплений в чисто комбинаторных терминах. А именно, он показал, что две диаграммы задают эквивалентные зацепления тогда и только тогда, когда их можно получить друг из друга конечной последовательностью преобразований, называемых теперь движениями Райдемайстера, см. рис. 1. Под диаграммой при этом понимается D О

Рис. 1. Движения Райдемайстера рассматриваемая с точностью до изотопии плоская проекция зацепления, удовлетворяющая условию общего положения (допускаются только двойные трансверсальные самопересечения), причем для каждого самопересечения дополнительно указано, какая из двух ветвей проходит сверху, а какая — снизу [3].

Другой классический подход, основанный на теоремах Дж. Александе-ра [1] и А.Маркова [50], дает описание классов эквивалентности ориентированных зацеплений в комбинаторно-алгебраических терминах. В качестве множества диаграмм берется дизъюнктное объединение .B1U.B2U.B3LJ U . групп кос:

Вп = (сть . ,а„! | UiGj = o-j<7i, 1 ^ i, j ^ п - 1, \i - j\ > 1;

TjCr;+i<Ti = (7i+i(7i<7i+i, 1 < г < П — 2).

Элементы группы Вп называются косами на п нитях, поскольку они имеют соответствующую топологическую интерпретацию [4, 5]. Каждой паре (■n,w), где п ^ 1 — натуральное число, aw — слово в образующих afl, 1 ^ г ^ п — 1, сопоставляется ориентированное зацепление, называемое замыканием соответствующей косы. Идея проиллюстрирована на рис. 2,

Рис. 2. Коса (4,02(7! 2о'з0'20'з г) и ее замыкание подробности мы опускаем. Александер доказал (используя другую терминологию — группы кос были определены позднее), что каждое зацепление можно представить в виде замкнутой косы, а Марков указал набор сохраняющих класс эквивалентности зацепления преобразований, достаточных для того, чтобы перевести друг в друга любые две косы, задающие эквивалентные зацепления. Эти преобразования, называемые теперь двиэюе-ииями Маркова, таковы:

1) (n,w) (n,w'), если в группе Вп выполнено равенство w = w';

2) (n,w) «-» (n,uwu~l) — сопряжение с помощью произвольной косы на таком же количестве нитей;

3) (п, w) (п+1, wa^1), если в слове w встречаются лишь образующие af \ l^i^n-1.

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

Использование замкнутых кос для представления зацеплений имеет также один серьезный недостаток, редко упоминаемый в литературе: таким способом можно описывать только ориентированные зацепления. Набор дополнительных преобразований, позволяющий «забыть» ориентацию, по-видимому, не имеет описания в разумных алгебраических терминах и в литературе не исследован.

Стоит отметить несколько случаев, когда удается удовлетворительным образом классифицировать некоторый класс зацеплений, выделяемый из множества всех зацеплений каким-либо интересным свойством.

Например, торические узлы и зацепления, определяемые тем, что содержатся в некотором незаузленном вложенном двумерном торе Т2 С S3, естественным образом нумеруются неупорядоченными парами (р, q) целых чисел с условием p,q £ {—1,0,1}, рассматриваемых с точностью до общего знака, (p,q) ~ (— р, — q) ~ (q,p). А именно, паре (р, q), где р > 0, сопоставляется замыкание косы (р, (cri. ap-i)q). Торические зацепления замечательны также тем, что только для них и тривиального узла дополнение до S3 является так называемым зейфертовым многообразием (грубо говоря, расслоением над орбиобразием со слоем окружность).

Классифицированы двумостиые узлы и зацепления [63]. Это зацепления (отличные от тривиального узла), на которых некоторая функция высоты имеет ровно две точки локального максимума, или эквивалентные таким. Кроме этого свойства, они замечательны тем, что двулистное накрытие над сферой S3 с ветвлением вдоль двумостного зацепления имеет род Хегора один, то есть является линзовым пространством или S2 х S1, причем неэквивалентным двумостным зацеплениям соответствуют негомеоморфные (с учетом ориентации) линзовые пространства. Двумостные зацепления естественно нумеруются несократимыми дробями p/q, рассматриваемыми с точностью до следующей эквивалентности: (Р><7) ~ (PiQ')> если Я = Q1 (mod р) или qq' = 1 (mod р). Построить по дроби p/q соответствующее двумостное зацепление Lp/q можно, например, с помощью произвольного ее разложения в цепную дробь четной длины: p/q = к\+1/(к2+1/(кз+. .+1/к2т) • • •) (h не обязательно положительные). Зацепление Lp/q получается из косы (4,a2kiа*2а2кзof4.а2к2,"-1ак2т) операцией, похожей на замыкание, см. рис. 3.

Интересным классом зацеплений являются также неразводимые альтернированные зацепления, которые, по определению, представимы альтернированными плоскими диаграммами — такими, что прохождения сверху и снизу пересечений чередуются, если идти вдоль проекции зацепления (например, диаграмма на рис. 3 слева альтернированная). В частности, все двумостные узлы являются альтернированными. Известно [56], что наименьшее число самопересечений на диаграмме альтернированного зацепления достигается именно на его альтернированной диаграмме, при этом на различных альтернированных диаграммах это число одно и то же, при выполнении некоторого условия неприводимости, а именно, при

5/3 - 1 + 1/(1 + 1/(1 + 1/1)))

2-1/3

Рис. 3. Двумостный узел L5/3 отсутствии так называемых разбивающих пересечений на диаграмме. Доказано также [52, 53], что две неприводимые альтернированные диаграммы задают эквивалентные зацепления тогда и только тогда, когда они получаются друг из друга последовательностью операций (называемых Ауре), показанных на рис. 4. Эти два утверждения, сформулированных в

Рис. 4. Операция Ауре виде гипотезы Тейтом в конце XIX века, можно рассматривать как решение задачи классификации альтернированных зацеплений.

Имеется обширнейшая литература по построению и изучению свойств всевозможных топологических инвариантов узлов и зацеплений, что также можно рассматривать как подход к решению задачи классификации. Укажем лишь несколько ключевых работ: [2, 15, 41, 30, 42, 43, 68, 6, 44]. Однако, для построенных инвариантов, несмотря на их замечательные свойства, как правило, не удается ответить на самые естественные вопросы, а именно: сформулировать в топологических терминах, какие узлы различаются данным инвариантом, а какие — нет; указать область значения инварианта.

В настоящей работе развивается подход к теории узлов, основанный на нетрадиционном комбинаторном способе представления узлов и зацеплений. Вместо проецирования на плоскость или рассмотрения дополнительного пространства, мы будем изучать зацепления, имеющие специальный вид, а именно, целиком содержащиеся в «книге» — объединении нескольких полуплоскостей, имеющих общий край. Тот факт, что любой узел можно продеформировать так, чтобы он имел указанный вид, где число «страниц» неограничено, отмечался еще в конце XIX века [13], а в более современной литературе вскользь отмечается и то, что для представления зацепления в таком «книжном» виде достаточно всего трех страниц.

Однако, вплоть до недавнего времени (до работ [16, 19]) комбинаторные и алгебраические свойства этой простой и естественной конструкции не изучались.

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

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

Заметим, что одним из наиболее предпочтительных вариантов решений задачи классификации каких-либо объектов является указание процедуры приведения их к каноническому виду, которая имеет вид «монотонного упрощения». Известно, что для плоских диаграмм узлов и движений Райдемайстера эта идея не работает. На рис. 5 показан пример плоской диаграммы тривиального узла, к которой нельзя применить ни одного движеиия Райдемайстера, сохраняющего или уменьшающего число пересечений. Этот пример принадлежит Гёрицу [67].

Рис. 5. Пример не упрощаемой монотонно плоской диаграммы тривиального узла

Отчасти желанием найти способ приведения узлов к каноническому виду мотивированы исследования различных функционалов, обычно называемых энергией узла [29, 48].

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

Если данное зацепление разводимое или составное, это может быть совершенно не очевидно из его комбинаторного представления. Однако, если зацепление задано в книжном виде, то, применив к его диаграмме конечное число элементарных операций, не увеличивающих сложность, всегда можно получить диаграмму, из которой будет «явно видно» разложение данного зацепления на простые (в главе 3 этому будет придан точный смысл). Здесь важно, что, в силу предыдущего результата, все тривиальные слагаемые при монотонном упрощении исчезают.

Основной результат третьей главы немедленно дает новые алгоритмы для распознавания тривиального узла и разложения зацеплений на простые слагаемые. Эти алгоритмы кардинально проще построенных ранее, хотя, к сожалению, известные (очевидные из конструкции) оценки на сложность этих алгоритмов также достаточно плохие и принципиально не отличаются от сложности алгоритма Хакена и других. Неоспоримое преимущество алгоритмов с использованием монотонного упрощения состоит в том, что в качестве ответа они выдают не только информацию о возможности разложении на простые или о тривиальности исходного зацепления, но и последовательность преобразований, которая превращает исходное зацепление в то, которое имеет очевидную факторизацию.

Для доказательства результатов третьей главы используется техника, развитая в работах [8, 10, 11, 16]. Основная теорема третьей главы имеет схожую формулировку с результатами работ [10, 11]. А именно, в [10, 11] доказано аналогичное утверждение, в котором вместо книжных зацеплений используются замкнутые косы, а в качестве функции сложности — число нитей косы. Принципиальное преимущество нашего подхода в том, что количество книжных зацеплений данной сложности конечно, а количество кос на данном числе нитей — нет. Поэтому результаты [10, 11] не дают алгоритма монотонного упрощения, подобного тому, что указан в настоящей работе.

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

Я признателен А. Сикора и У. Менаско, обратившим мое внимание на пробел, содержащийся в первоначальном варианте доказательства теоремы о монотонном упрощении тривиального узла.

Список литературы диссертационного исследования доктор физико-математических наук Дынников, Иван Алексеевич, 2006 год

1. A. Dynnikov, A new way to represent links. One-dimensional formalism and untangling technology, Acta Appl. Math. 69 (2001), 243-283.И. А. Дынников, Алгоритмы распознавания в теории узлов. Успехи математических наук 58 (2003), 6(354), 45-92.

2. A. Dynnikov, Finitely presented semigroups in knot theory. Oriented case. Geometry, topology, and mathematical physics, 133-144, Amer. Math. Soc. Transl. Ser. 2, 212, Amer. Math. Soc., Providence, RI, 2004.

3. A. Dynnikov, Arc-presentations of links. Monotonic simplification, Fund. Math. 190 (2006), 29-76.

4. H.Kauffman, State models and the Jones polynomial. Topology 26 (1987), no. 3, 395-407.

5. К. A. Perko. On the Classification of Knots. Proc. Amer. Math. Soc. 45, 262-266, 1974.

6. K. Reidemeister, Knotentheorie. Ergebn. Math. Grenzgeb., Bd. 1; Berlin: Springer-Verlag, 1932.

7. D.Rolfsen, Table of Knots and Links. Appendix С in Knots and Links. Wilmington, DE: Publish or Perish Press, pp. 280-287, 1976.

8. H.Schubert: Die eindeutige Zerlegbarkeit eines Knotens in Primknoten, Sitzungsber, S.-B. Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (1949). no. 3, 57-104.

9. H.Schubert, Bestimmung der Primfactorzerlegung von Verkettungen, Math. Z. 76 (1961), 116-148; русский перевод: Х.Шуберт, Алгоритм для разложения зацеплений на простые слагаемые, Математика 10:4, 45-78.

10. H.Schubert. Knoten mit zwei Brucken. Math. Z. 65 (1956), 133-170.

11. P.G.Tait, On knots, Trans. Roy. Soc. Edinburgh 28 (1877), 145-190.

12. W. Thurston, On the geometry and dynamics of diffeomorphisms of surfaces, Dull. Amer. Math. Soc. 19 (1988), no. 2, 417-431.

13. В. Г.Тураев, Операторные инварианты связок и Л-матрицы. Изв. Акад. Наук СССР Сер. Мат. 53 (1989), 5, 1073-1107.

14. L. Goeritz, Bemerkungen zur knotenthoerie, Abh. Math. Sem. Univ. Hamburg 10 (1934), 201-210.

15. V. A. Vassiliev, Cohomology of knot spaces. Theory of singularities and its applications, 23-69, Adv. Soviet Math., 1, Amer. Math. Soc., Providence, RI, 1990.