Преобразование Нильсена - Nielsen transformation

В математика, особенно в районе абстрактная алгебра известный как комбинаторная теория групп, Преобразования Нильсена, названный в честь Якоб Нильсен, уверены автоморфизмы из свободная группа которые являются некоммутативным аналогом сокращение ряда и один из основных инструментов, используемых при изучении свободных групп, (Fine, Rosenberger & Stille, 1995 г. ). Они были введены в (Нильсен 1921 ), чтобы доказать, что каждое подгруппа свободной группы бесплатно ( Теорема Нильсена – Шрайера ), но в настоящее время используются в различных областях математики, включая вычислительная теория групп, k-теория, и теория узлов. Учебник (Магнус, Каррасс и Солитэр 2004 ) посвящает всю главу 3 преобразованиям Нильсена.

Определения

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

Преобразование Нильсена на конечно порожденный свободная группа с упорядоченной базой [ Икс1, …, Иксп ] можно учесть элементарные преобразования Нильсена следующих видов:

  • Выключатель Икс1 и Икс2
  • Циклически переставлять Икс1, Икс2, …, Иксп, к Икс2, …, Иксп, Икс1.
  • Заменять Икс1 с Икс1−1
  • Заменять Икс1 с Икс1·Икс2

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

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

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

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

Примеры

Группа диэдра порядка 10 имеет два класса эквивалентности по Нильсену порождающих множеств размера 2. Пусть Икс элемент порядка 2 и у будучи элементом порядка 5, два класса генераторных установок представлены [ Икс, у ] и [ Икс, гг ], и каждый класс состоит из 15 различных элементов. Очень важным порождающим множеством диэдральной группы является порождающее множество из его представления в виде Группа Коксетера. Такой порождающий набор для группы диэдра порядка 10 состоит из любой пары элементов порядка 2, например [ Икс, ху ]. Этот генераторный агрегат эквивалентен [ Икс, у ] через:

  • [ Икс−1, у ], тип 3
  • [ у, Икс−1 ], Тип 1
  • [ у−1, Икс−1 ], тип 3
  • [ у−1Икс−1, Икс−1 ], тип 4
  • [ ху, Икс−1 ], тип 3
  • [ Икс−1, ху ], Тип 1
  • [ Икс, ху ], тип 3

В отличие от [ Икс, у ] и [ Икс, гг ], порождающие установки [ Икс, у, 1] и [ Икс, гг, 1] эквивалентны.[1] Последовательность преобразований с использованием более удобных элементарных преобразований (все свопы, все обратные, все продукты):

  • [ Икс, у, 1 ]
  • [ Икс, у, у ], умножьте 2-й генератор на 3-й
  • [ Икс, гг, у ], умножьте третий генератор на второй
  • [ Икс, гг, ггг ], умножьте 2-й генератор на 3-й
  • [ Икс, гг, 1], умножить 2-й генератор на 3-й

Приложения

Теорема Нильсена – Шрайера

Основная статья: Теорема Нильсена – Шрайера

В (Нильсен 1921 ) дается прямое комбинаторное доказательство того, что конечно порожденные подгруппы свободных групп свободны. Генераторная установка называется сокращенной по Нильсену, если в продуктах не слишком много отмен. В статье показано, что каждое конечное порождающее множество подгруппы свободной группы является (сингулярно) эквивалентным по Нильсену редуцированным порождающим множеством Нильсена, и что редуцированное порождающее множество Нильсена является свободным базисом для подгруппы, поэтому подгруппа свободна. Это доказательство подробно изложено в (Магнус, Каррасс и Солитэр 2004, Гл. 3.2).

Группы автоморфизмов

В (Нильсен 1924 ), показано, что автоморфизм, определяемый элементарными преобразованиями Нильсена, порождает полный группа автоморфизмов конечно порожденной свободной группы. Нильсен, а затем Бернхард Нойманн использовал эти идеи, чтобы дать конечные презентации из группы автоморфизмов бесплатных групп. Это тоже описано в учебнике (Магнус, Каррасс и Солитэр 2004, п. 131, чт 3.2).

Для данного порождающего множества данной конечно порожденной группы не обязательно верно, что каждый автоморфизм задается преобразованием Нильсена, но для каждого автоморфизма существует порождающее множество, в котором автоморфизм задается преобразованием Нильсена, (Рапапорт 1959 г. ).

Проблема со словом

Основная статья: Гипотеза Эндрюса – Кертиса

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

В учебнике (Магнус, Каррасс и Солитэр 2004, стр. 131–132)., приложение преобразований Нильсена дается для решения обобщенной проблемы слов для свободных групп, также известной как проблема принадлежности для подгрупп, заданных конечными порождающими множествами в свободных группах.

Проблема изоморфизма

Основная статья: Полином александра

Особенно важный частный случай проблема изоморфизма групп касается фундаментальных групп трехмерных узлы, которое можно решить с помощью преобразований Нильсена и метода Дж. В. Александер (Магнус, Каррасс и Солитэр 2004, Гл. 3.4).

Алгоритм замены товара

Основная статья: алгоритм замены товара

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

  • Возьмите любой упорядоченный генераторный агрегат и добавьте несколько копий элемента идентичности, чтобы было п элементы в наборе
  • Повторите следующее определенное количество раз (это называется записать в )
    • Выбрать целые числа я и j равномерно случайно от 1 до п, и выберите е равномерно случайным образом из {1, -1}
    • Заменить я-го генератора с произведением яth генератор и j-й генератор поднят на ея сила
  • Каждый раз, когда требуется новый случайный элемент, повторяйте предыдущие два шага, затем возвращайте один из генерирующих элементов как желаемый случайный элемент.

Можно доказать, что генераторная установка, используемая в ходе этого алгоритма, изменяется равномерно для всех эквивалентных генераторных установок Nielsen. Однако этот алгоритм имеет ряд статистических и теоретических проблем. Например, может быть более одного класса эквивалентности генераторов Нильсена. Также необходимо равномерно распределить элементы генераторных установок (например, элементы Подгруппа Фраттини никогда не может возникнуть в генераторной установке минимального размера, но возникают и более тонкие проблемы).

Большинство этих проблем быстро решаются с помощью следующей модификации, называемой "трещотка", (Лидхэм-Грин и Мюррей 2002 ):

  • Помимо генераторной установки, храните дополнительный элемент группы, инициализированный идентификатором
  • Каждый раз при замене генератора выбирайте k равномерно наугад и заменить дополнительный элемент произведением дополнительного элемента на k-й генератор.

K-теория

Чтобы понять эквивалентность по Нильсену неминимальных порождающих множеств, теоретический модуль исследования были полезны, как в (Эванс 1989 ). Продолжая эти строки, K-теоретическая формулировка препятствия к эквивалентности по Нильсену была описана в (Люстиг 1991 ) и (Люстиг и Мориа 1993 ). Они показывают важную связь между Группа Уайтхеда группового кольца и классов эквивалентности по Нильсену образующих.

Смотрите также

Рекомендации

Примечания

  1. ^ Действительно, все 840 упорядоченных генераторных установок третьего размера эквивалентны. Это общая черта эквивалентности Нильсена конечные группы. Если конечная группа может быть порождена d генераторы, то все генераторы размера d + 1 эквивалентны. Есть аналогичные результаты для полициклические группы, и некоторые другие конечно порожденные группы также.

Учебники и обзоры

  • Коэн, Дэниел Э. (1989), Комбинаторная теория групп: топологический подход, Студенческие тексты Лондонского математического общества, 14, Издательство Кембриджского университета, Дои:10.1017 / CBO9780511565878, ISBN  978-0-521-34133-2, МИСТЕР  1020297
  • Хорошо, Бенджамин; Розенбергер, Герхард; Стилл, Майкл (1995), «Преобразования Нильсена и приложения: обзор» в Ким, Энн Чи; Kim, A.C .; Джонсон, Д. (ред.), Группы - Корея '94: Материалы международной конференции, проходившей в Пусанском национальном университете, Пусан, Корея, 18–25 августа 1994 г., Вальтер де Грюйтер, стр. 69–105, ISBN  978-3-11-014793-3, МИСТЕР  1476950
  • Шупп, Пол Э.; Линдон, Роджер С. (2001), Комбинаторная теория групп, Springer-Verlag, ISBN  978-3-540-41158-1, МИСТЕР  0577064
  • Магнус, Вильгельм; Авраам Каррасс, Дональд Солитэр (2004), Комбинаторная теория групп, Dover Publications, ISBN  978-0-486-43830-6, МИСТЕР  0207802

Основные источники