В математике , особенно в области абстрактной алгебры , известной как комбинаторная теория групп , Нильсно преобразование , названное в честь Якоба Нильсена , некоторые автоморфизмы из более свободной группы , которые являются некоммутативным аналогом сокращения ряда и один из основных инструментов , используемый при изучении свободные группы ( Fine, Rosenberger & Stille, 1995 ). Они были введены в ( Nielsen 1921 ), чтобы доказать, что каждая подгруппа свободной группы свободна ( теорема Нильсена – Шрайера ), но теперь используются во множестве математических задач, включаявычислительная теория групп , k-теория и теория узлов . В учебнике ( Магнус, Каррасс и Солитар, 2004 ) вся глава 3 посвящена преобразованиям Нильсена.
Определения
Одно из простейших определений преобразования Нильсена - это автоморфизм свободной группы, но это не было их первоначальным определением. Следующее дает более конструктивное определение.
Преобразование Нильсена на конечно порожденной свободной группе с упорядоченным базисом [ x 1 , ..., x n ] может быть разложено на элементарные преобразования Нильсена следующих видов:
- Переключатель x 1 и x 2
- Циклически переставлять x 1 , x 2 , ..., x n , на x 2 , ..., x n , x 1 .
- Заменим x 1 на x 1 −1
- Заменить x 1 на x 1 · x 2
Эти преобразования являются аналогами элементарных операций со строками . Преобразования первых двух типов аналогичны перестановкам строк и циклическим перестановкам строк. Преобразования третьего типа соответствуют масштабированию строки обратимым скаляром. Преобразования четвертого типа соответствуют сложениям строк.
Преобразований первых двух типов достаточно для перестановки генераторов в любом порядке, поэтому третий тип может быть применен к любому из генераторов, а четвертый тип - к любой паре генераторов.
Имея дело с несвободными группами, вместо этого применяют эти преобразования к конечным упорядоченным подмножествам группы. В этой ситуации композиции элементарных преобразований называются регулярными . Если разрешено удалять элементы подмножества, которые являются элементами идентичности, то преобразование называется сингулярным .
Изображения при преобразовании Nielsen (элементарные или нет, регулярных или нет) порождающего множества группы G также порождающее множество G . Два порождающих набора называются эквивалентом Нильсена, если существует преобразование Нильсена, переводящее одно в другое. Если порождающие множества имеют одинаковый размер, то достаточно рассмотреть композиции регулярных преобразований Нильсена.
Примеры
Группа диэдра порядка 10 имеет два класса эквивалентности по Нильсену порождающих множеств размера 2. Пусть x будет элементом порядка 2, а y - элементом порядка 5, два класса порождающих множеств представлены как [ x , y ] и [ x , yy ], и каждый класс состоит из 15 различных элементов. Очень важным порождающим множеством диэдральной группы является порождающее множество из его представления в виде группы Кокстера . Такой порождающий набор для группы диэдра порядка 10 состоит из любой пары элементов порядка 2, например [ x , xy ]. Этот генераторный агрегат эквивалентен [ x , y ] через:
- [ x −1 , y ], тип 3
- [ y , x −1 ], тип 1
- [ y −1 , x −1 ], тип 3
- [ y −1 x −1 , x −1 ], тип 4
- [ xy , x −1 ], тип 3
- [ x −1 , xy ], тип 1
- [ x , xy ], тип 3
В отличие от [ x , y ] и [ x , yy ], порождающие множества [ x , y , 1] и [ x , yy , 1] эквивалентны. [1] Последовательность преобразования с использованием более удобных элементарных преобразований (все свопы, все обратные, все продукты):
- [ x , y , 1]
- [ x , y , y ], умножить второй генератор на третий
- [ x , yy , y ], умножить третий генератор на второй
- [ x , yy , yyy ], умножить второй генератор на третий
- [ x , yy , 1], умножить второй генератор на третий
Приложения
Теорема Нильсена – Шрайера
В ( Nielsen 1921 ) дано прямое комбинаторное доказательство того, что конечно порожденные подгруппы свободных групп свободны. Генераторная установка называется сокращенной по Нильсену, если в продуктах не слишком много отмен. В статье показано, что каждое конечное порождающее множество подгруппы свободной группы является (сингулярно) эквивалентным по Нильсену редуцированным порождающим множеством Нильсена, и что редуцированное порождающее множество Нильсена является свободным базисом для подгруппы, поэтому подгруппа свободна. Это доказательство подробно изложено в ( Magnus, Karrass & Solitar 2004 , Ch 3.2). .
Группы автоморфизмов
В ( Nielsen 1924 ) показано, что автоморфизм, определяемый элементарными преобразованиями Нильсена, порождает полную группу автоморфизмов конечно порожденной свободной группы . Нильсен, а затем Бернхард Neumann использовал эти идеи , чтобы дать конечные презентации из групп автоморфизмов свободных групп. Это также описано в учебнике ( Magnus, Karrass & Solitar 2004 , p. 131, Th 3.2). .
Для данного порождающего множества данной конечно порожденной группы не обязательно верно, что каждый автоморфизм задается преобразованием Нильсена, но для каждого автоморфизма существует порождающее множество, в котором автоморфизм задается преобразованием Нильсена ( Rapaport 1959 ).
Проблема со словом
Особенно простой случай проблемы тождества для групп и проблемы изоморфизма для групп спрашивает , если конечно определенная группа является единичной группой . Это, как известно, в общем случае трудноразрешимо, даже несмотря на то, что существует конечная последовательность элементарных преобразований Титце, приводящих представление к тривиальному представлению тогда и только тогда, когда группа тривиальна. Особым случаем являются «сбалансированные представления», те конечные представления с равным числом генераторов и соотносителей. Для этих групп существует предположение, что требуемые преобразования немного проще (в частности, не включают добавление или удаление отношений отношения). Если один позволяет взять набор отношений отношения к любому эквивалентному множеству Нильсена и один позволяет сопрягать отношения отношения, то получается отношение эквивалентности на упорядоченных подмножествах отношений отношения конечно представленной группы. Гипотеза Эндрюса – Кертиса состоит в том, что соотношения любого сбалансированного представления тривиальной группы эквивалентны набору тривиальных соотношений, утверждающих, что каждый образующий является единичным элементом.
В учебнике ( Magnus, Karrass & Solitar 2004 , стр. 131–132) , приложение преобразований Нильсена дается для решения обобщенной проблемы слов для свободных групп, также известной как проблема принадлежности для подгрупп, заданных конечными порождающими множествами в свободных группах.
Проблема изоморфизма
Особенно важный частный случай проблемы изоморфизма для групп касается фундаментальных групп трехмерных узлов , которые могут быть решены с помощью преобразований Нильсена и метода Дж. В. Александера ( Magnus, Karrass & Solitar 2004 , Ch 3.4) .
Алгоритм замены товара
В вычислительной теории групп важно генерировать случайные элементы конечной группы . Популярные методы для этого используют методы цепей Маркова для генерации случайных генерирующих наборов группы. «Алгоритм замены продукта» просто использует случайно выбранные преобразования Нильсена, чтобы совершить случайное блуждание по графику порождающих наборов группы. Алгоритм хорошо изучен, и обзор дан в ( Pak 1999 ). . Одна из версий алгоритма, называемая «встряхивание»:
- Возьмите любой упорядоченный генерирующий набор и добавьте несколько копий элемента идентичности, чтобы в наборе было n элементов.
- Повторите следующее определенное количество раз (это называется ожогом )
- Выбирайте целые числа i и j равномерно случайным образом от 1 до n и выбирайте e равномерно случайным образом из {1, -1}
- Замените i- й генератор произведением i- го генератора и j- го генератора, увеличенного до e- й мощности.
- Каждый раз, когда требуется новый случайный элемент, повторяйте предыдущие два шага, затем возвращайте один из генерирующих элементов как желаемый случайный элемент.
Можно доказать, что генераторная установка, используемая в ходе этого алгоритма, изменяется равномерно для всех эквивалентных генераторных установок Nielsen. Однако этот алгоритм имеет ряд статистических и теоретических проблем. Например, может быть более одного класса эквивалентности генераторов Нильсена. Кроме того, элементы генераторных установок должны быть равномерно распределены (например, элементы подгруппы Frattini никогда не могут встречаться в генерирующей установке минимального размера, но возникают и более тонкие проблемы).
Большинство из этих проблем быстро решаются с помощью следующей модификации, называемой «погремушка» ( Leedham-Green & Murray 2002 ):
- Помимо генераторной установки, храните дополнительный элемент группы, инициализированный идентификатором
- Каждый раз при замене генератора выбирайте k равномерно случайным образом и заменяйте дополнительный элемент произведением дополнительного элемента на k- й генератор.
K-теория
Чтобы понять эквивалентность по Нильсену неминимальных порождающих множеств, были полезны теоретические исследования модулей , как, например, в ( Evans 1989 ). Продолжая эти строки, K-теоретическая формулировка препятствия эквивалентности Нильсена была описана в ( Lustig 1991 ) и ( Lustig & Moriah 1993 ). Они показывают важную связь между группой Уайтхеда группового кольца и классами эквивалентности генераторов по Нильсену.
Смотрите также
- Преобразование Титце
- Группа автоморфизмов свободной группы
Рекомендации
Заметки
- ^ Действительно, все 840 упорядоченных генерирующих установок третьего размера эквивалентны. Это общая черта эквивалентности конечных групп по Нильсену. Если конечная группа может быть порождена d образующими, то все порождающие множества размера d + 1 эквивалентны. Есть аналогичные результаты для полициклических групп , а также некоторых других конечно порожденных групп .
Учебники и обзоры
- Коэн, Дэниел Э. (1989), Комбинаторная теория групп: топологический подход , Студенческие тексты Лондонского математического общества, 14 , Cambridge University Press , DOI : 10.1017 / CBO9780511565878 , ISBN 978-0-521-34133-2, MR 1020297
- Хорошо, Бенджамин; Розенбергер, Герхард; Стилл, Майкл (1995), «Преобразования Нильсена и приложения: обзор» , в Ким, Энн Чи; Ким, AC; Джонсон, DL (ред.), Группы - Корея '94: Материалы международной конференции, проходившей в Пусанском национальном университете, Пусан, Корея, 18–25 августа 1994 г. , Walter de Gruyter, pp. 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
Основные источники
- Александр, JW (1928), "Топологические инварианты узлов и связей", Труды Американского математического общества , 30 (2): 275-306, DOI : 10,2307 / 1989123 , JFM 54.0603.03 , JSTOR 1989123
- Эванс, Мартин Дж (1989), "Примитивные элементы свободных групп", Труды Американского математического общества , 106 (2): 313-6, DOI : 10,2307 / 2048805 , JSTOR 2048805 , MR 0952315
- Фенчел, Вернер ; Нильсен, Якоб (2003), Шмидт, Асмус Л. (ред.), Разрывные группы изометрий в гиперболической плоскости , Исследования Де Грюйтера по математике, 29 , Берлин: Walter de Gruyter & Co.
- Лидхэм-Грин, CR ; Мюррей, Скотт Х. (2002), «Варианты замены продукта», Вычислительная и статистическая теория групп (Лас-Вегас, Невада / Хобокен, Нью-Джерси, 2001) , Contemp. . Математика, 298 , Providence, RI: Американское математическое общество . С. 97-104, DOI : 10,1090 / conm / 298/05116 , MR 1929718
- Люстиг, Мартин (1991), "Nielsen эквивалентности и простой гомотопический тип", Труды Лондонского математического общества , 3 - й серии, 62 (3): 537-562, DOI : 10,1112 / ПНИЛ / s3-62.3.537 , MR 1095232
- Люстиг, Мартин; Мориа, Йоав (1993), "Генерация систем групп и Райдемайстера-Уайтхеда кручения", Журнал алгебры , 157 (1): 170-198, DOI : 10,1006 / jabr.1993.1096 , МР 1219664
- Нильсен, Якоб (1921), "Om regning med ikke-kommutative faktorer og dens anvendelse i gruppeteorien", Math. Tidsskrift Б (Датский), одна тысяча девятьсот двадцать-оден : 78-94, СУЛ 48.0123.03
- Nielsen, Jakob (1924), "Die Isomorphismengruppe дер Freien Gruppen", Mathematische Annalen (на немецком языке ), 91 (3-4): 169-209, DOI : 10.1007 / BF01556078 , JFM 50.0078.04
- Пак, Игорь (2001), «Что мы знаем об алгоритме замены продукта?», Группы и вычисления, III (Колумбус, Огайо, 1999) , Ohio State Univ. Математика. Res. Inst. Publ., 8 , Walter de Gruyter, pp. 301–347, MR 1829489
- Rapaport, Эльвира Штрассер (1959), "Замечание о преобразованиях Nielsen", Труды Американского математического общества , 10 (2): 228-235, DOI : 10,2307 / 2033582 , JSTOR 2033582 , МР 0104724