Содержание раздела:

Мы обсудим первостепенную алгоритмическую задачу, связанную с косами, а именно, вопрос их распознавания.

Определение. Задачей распознавания кос называется алгоритмическая задача разрешимости, заключающаяся в определении того, представляют ли два артиновских слова одинаковые косы.

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

<aside> ✅ Задача распознавания кос алгоритмически разрешима, и известно несколько существенно различных алгоритмов распознавания. Каждый из них позволяет взглянуть на косы с совершенно новой точки зрения.

</aside>

Карл Фридрих Гаусс (1777-1855) — немецкий математик

Макс Ден (1878-1952) — германо-американский математик

Распознаванием кос впервые занимался К. Ф. Гаусс в 1815 году:

Черновик Гаусса, в котором он описал обобщения коэффициентов зацепления нитей косы

Основным методом решения задачи распознавания является привлечение инвариантов кос. Инварианты возникают в совершенно разных обличиях, и для облегчения восприятия мы сконцентрируемся на двух основных подходах к решению задачи распознавания:

• алгебраические (нормальные формы);
• геометрические (действия групп кос).

Прежде чем переходить к обзору этих подходов, сделаем важное наблюдение.

<aside> 💡 Структура группы позволяет свести задачу распознавания к своему частному случаю.

</aside>

Лемма. Задача распознавания кос равносильна задаче определения того, представляет ли заданное артиновское слово тривиальную косу.

Доказательство. Имеем $x = y \ \Longleftrightarrow \ xy^{-1}=1.$

Запутанное изображение тривиальной косы

Чаще всего мы будем концентрироваться именно на задаче распознавания нетривиальности.

Алгебраические решения задачи распознавания

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

<aside> 💡 Задумка в том, что сравнивать геометрические косы, представленные в таком специальном виде, должно быть куда проще, чем сравнивать произвольные.

</aside>

Часто мы будем концентрироваться на специальных видах, обладающих свойством единственности. Такие специальные виды называются нормальными формами.

<aside> ❓ Как использовать нормальные формы на практике?

</aside>

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

Более того, как мы обсудили выше, достаточно научиться отличать косу от тривиальной, поэтому алгебраические решения задачи распознавания обычно предоставляют способ привести каждую косу либо к виду тривиальной геометрической косы, либо к тому, по которому нетривиальность ясна.