Алгоритм Тодда-Кокстера - Todd–Coxeter algorithm

В теория групп, то Алгоритм Тодда-Кокстера, сделано Дж. А. Тодд и Х. С. М. Коксетер в 1936 г. алгоритм для решения перечисление смежных классов проблема. Учитывая презентация группы грамм генераторами и отношениями и подгруппа ЧАС из грамм, алгоритм перечисляет смежные классы из ЧАС на грамм и описывает перестановочное представление из грамм на пространстве смежных классов (заданном действием левого умножения). Если порядок группы грамм относительно невелика, и подгруппа ЧАС заведомо несложный (например, циклическая группа ), то алгоритм может быть выполнен вручную и дает разумное описание группы грамм. Используя свой алгоритм, Кокстер и Тодд показали, что некоторые системы отношений между генераторами известных групп являются полными, т.е. представляют собой системы определяющих отношений.

Алгоритм Тодда – Кокстера может применяться к бесконечным группам и, как известно, завершается за конечное число шагов при условии, что индекс из ЧАС в грамм конечно. С другой стороны, для общей пары, состоящей из представления группы и подгруппы, время ее работы не ограничено никакими вычислимая функция индекса подгруппы и размера входных данных.

Описание алгоритма

Одна реализация алгоритма работает следующим образом. Предположим, что ${\displaystyle G=\langle X\mid R\rangle }$, куда ${\displaystyle X}$ это набор генераторы и ${\displaystyle R}$ это набор связи и обозначим через ${\displaystyle X'}$ набор генераторов ${\displaystyle X}$ и их обратные. Позволять ${\displaystyle H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle }$ где ${\displaystyle h_{i}}$ слова элементов ${\displaystyle X'}$. Будет использоваться три типа таблиц: таблица смежных классов, таблица отношений для каждого отношения в ${\displaystyle R}$, и таблица подгрупп для каждого генератора ${\displaystyle h_{i}}$ из ${\displaystyle H}$. Информация постепенно добавляется в эти таблицы, и как только они заполняются, все смежные классы пронумерованы, и алгоритм завершается.

Таблица смежных классов используется для хранения отношений между известными смежными классами при умножении на генератор. В нем есть строки, представляющие смежные классы ${\displaystyle H}$ и столбец для каждого элемента ${\displaystyle X'}$. Позволять ${\displaystyle C_{i}}$ обозначим смежный класс я-я строка таблицы смежных классов, и пусть ${\displaystyle g_{j}\in X'}$ обозначают генератор j-й столбец. Запись таблицы смежных классов в строке я, столбец j определяется как (если известно) k, куда k таково, что ${\displaystyle C_{k}=C_{i}g_{j}}$.

Таблицы отношений используются для определения того, когда некоторые из найденных нами смежных классов фактически эквивалентны. Одна таблица отношений для каждого отношения в ${\displaystyle R}$ поддерживается. Позволять ${\displaystyle 1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$ быть родственником в ${\displaystyle R}$, куда ${\displaystyle g_{n_{i}}\in X'}$. В таблице отношений есть строки, представляющие смежные классы ${\displaystyle H}$, как в таблице смежных классов. Она имеет т столбцы, а запись в яй ряд и j-й столбец определяется как (если известен) k, куда ${\displaystyle C_{k}=C_{i}g_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$. В частности, ${\displaystyle (i,t)}$ая запись изначально я, поскольку ${\displaystyle g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1}$.

Наконец, таблицы подгрупп похожи на таблицы отношений, за исключением того, что они отслеживают возможные отношения генераторов ${\displaystyle H}$. Для каждого генератора ${\displaystyle h_{n}=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$ из ${\displaystyle H}$, с ${\displaystyle g_{n_{i}}\in X'}$, мы создаем таблицу подгрупп. В нем всего одна строка, соответствующая смежному классу ${\displaystyle H}$ сам. Она имеет т столбцы, а запись в j-й столбец определен (если известен) как k, куда ${\displaystyle C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$.

Когда строка в таблице отношения или подгруппы завершена, появляется новый фрагмент информации. ${\displaystyle C_{i}=C_{j}g}$, ${\displaystyle g\in X'}$, находится. Это известно как вычет. Исходя из этого вывода, мы можем заполнить дополнительные записи в таблицах отношений и подгрупп, что приведет к возможным дополнительным вычетам. Мы можем заполнить записи таблицы смежных классов, соответствующие уравнениям ${\displaystyle C_{i}=C_{j}g}$ и ${\displaystyle C_{j}=C_{i}g^{-1}}$.

Однако при заполнении таблицы смежных классов возможно, что у нас уже есть запись для уравнения, но она имеет другое значение. В этом случае мы обнаружили, что два из наших смежных классов на самом деле одинаковые, известные как совпадение. Предполагать ${\displaystyle C_{i}=C_{j}}$, с ${\displaystyle i<j}$. Мы заменяем все экземпляры j в таблицах с я. Затем мы заполняем все возможные записи таблиц, что может привести к большему количеству выводов и совпадений.

Если после учёта всех выводов и совпадений в таблице остались пустые записи, добавьте в таблицы новый смежный класс и повторите процесс. Мы следим за тем, чтобы при добавлении смежных классов, если Hx - известный смежный класс, то Hxg будет добавлен в какой-то момент для всех ${\displaystyle g\in X'}$. (Это необходимо, чтобы гарантировать, что алгоритм завершится, если ${\displaystyle |G:H|}$ конечно.)

Когда все таблицы заполнены, алгоритм завершается. Затем у нас есть вся необходимая информация о действии ${\displaystyle G}$ на смежных классах ${\displaystyle H}$.

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

• Группа Кокстера

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

• Тодд, Дж. А.; Кокстер, Х. С. М. (1936). «Практический метод перечисления смежных классов конечной абстрактной группы». Труды Эдинбургского математического общества. Серия II. 5: 26–34. Дои:10.1017 / S0013091500008221. JFM  62.1094.02. Zbl  0015.10103.
• Кокстер, Х. С. М.; Мозер, В. О. Дж. (1980). Генераторы и соотношения для дискретных групп. Ergebnisse der Mathematik и ихрер Гренцгебиете. 14 (4-е изд.). Springer-Verlag 1980. ISBN  3-540-09212-9. МИСТЕР  0562913.
• Seress, Ákos (1997). «Введение в вычислительную теорию групп» (PDF). Уведомления Американского математического общества. 44 (6): 671–679. МИСТЕР  1452069.