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

В математике , особенно в области абстрактной алгебры, известной как комбинаторная теория групп , преобразования Нильсена , названные в честь Якоба Нильсена , представляют собой определенные автоморфизмы свободной группы , которые являются некоммутативным аналогом редукции строк и одним из основных инструментов, используемых при изучении. свободные группы ( Fine, Rosenberger & Stille 1995 ). Они были введены в ( Нильсен 1921 ), чтобы доказать, что каждая подгруппа свободной группы свободна ( теорема Нильсена-Шрайера ), но теперь используются в разнообразной математике, включая вычислительную теорию групп , k-теорию и теорию узлов . В учебнике «Комбинаторная теория групп» ( Magnus, Karrass & Solitar 2004 ) вся глава 3 посвящена преобразованиям Нильсена.

Определения

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

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

Переключатель х ₁ и х ₂
Циклически переставляйте x ₁ , x ₂ , ..., x _n , в x ₂ , ..., x _n , x ₁ .
Заменить х ₁ на х ₁⁻¹
Замените x ₁ на x ₁ · x ₂

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

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

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

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

Примеры

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

[ х ⁻¹, y ], тип 3
[ у , х ⁻¹ ], тип 1
[ и ⁻¹, х ⁻¹ ], тип 3
[ и ⁻¹х ⁻¹, х ⁻¹ ], тип 4
[ ху , х ⁻¹ ], тип 3
[ х ⁻¹, xy ], тип 1
[ x , xy ], тип 3

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

[ х , у , 1]
[ x , y , y ], умножить 2-й генератор на 3-й
[ x , yy , y ], умножьте 3-й генератор на 2-й
[ x , yy , yyy ], умножьте 2-й генератор на 3-й
[ x , yy , 1 ], умножьте 2-й генератор на 3-й

Приложения

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

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

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

В ( Нильсен, 1924 ) показано, что автоморфизм, определяемый элементарными преобразованиями Нильсена, порождает полную группу автоморфизмов конечно порожденной свободной группы . Нильсен, а позже Бернхард Нейман использовали эти идеи, чтобы дать конечные представления групп автоморфизмов свободных групп. Это также описано в учебнике ( Magnus, Karrass & Solitar 2004 , стр. 131, Th 3.2).

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

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

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

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

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

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

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

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

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

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

Большинство этих проблем быстро устраняются с помощью следующей модификации под названием «погремушка» ( Leedham-Green & Murray 2002 ):

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

К-теория

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

См. также

Ссылки

Примечания

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

Учебники и опросы

Коэн, Дэниел Э. (1989), Комбинаторная теория групп: топологический подход , Студенческие тексты Лондонского математического общества, том. 14, Издательство Кембриджского университета , номер документа : 10.1017/CBO9780511565878 , ISBN. 978-0-521-34133-2 , МР 1020297
Хорошо, Бенджамин; Розенбергер, Герхард; Стилле, Майкл (1995), «Преобразования и приложения Нильсена: обзор» , Ким, Энн Чи; Ким, AC; Джонсон, Д.Л. (ред.), Группы — Корея '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

Первоисточники

Александр, 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, Берлин: Вальтер де Грюйтер и компания.
Лидхэм-Грин, Чехия ; Мюррей, Скотт Х. (2002), «Варианты замены продукта», Вычислительная и статистическая теория групп (Лас-Вегас, Невада / Хобокен, Нью-Джерси, 2001) , Contemp. Матем., вып. 298, Провиденс, Род-Айленд: Американское математическое общество , стр. 97–104, doi : 10.1090/conm/298/05116 , MR 1929718.
Люстиг, Мартин (1991), «Эквивалентность Нильсена и простой гомотопический тип», Труды Лондонского математического общества , 3-я серия, 62 (3): 537–562, doi : 10.1112/plms/s3-62.3.537 , MR 1095232
Люстиг, Мартин; Мориа, Йоав (1993), «Порождающие системы групп и кручение Райдемайстера-Уайтхеда», Journal of Algebra , 157 (1): 170–198, doi : 10.1006/jabr.1993.1096 , MR 1219664
Нильсен, Якоб (1921), «Об исчислении с некоммутативными факторами и его применении к теории групп», Math. Журнал B (на датском языке), 1921 : 78–94, JFM 48.0123.03.
Нильсен, Якоб (1924), «Группа изоморфизма свободных групп», Mathematical Annals (на немецком языке), 91 (3–4): 169–209, doi : 10.1007/BF01556078 , JFM 50.0078.04
Пак, Игорь (2001), «Что мы знаем об алгоритме замены продуктов?», Группы и вычисления, III (Колумбус, Огайо, 1999) , Университет штата Огайо. Математика. Рез. Инст. Опубл., т. 1, с. 8, Вальтер де Грюйтер, стр. 301–347, MR 1829489.
Рапапорт, Эльвира Штрассер (1959), «Заметки о преобразованиях Нильсена», Труды Американского математического общества , 10 (2): 228–235, doi : 10.2307/2033582 , JSTOR 2033582 , MR 0104724

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

[1]