Алгоритм Тодда-Кокстера - 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 (я, т)}$ая запись изначально я, поскольку ${ 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 в таблицах с я. Затем мы заполняем все возможные записи таблиц, что может привести к большему количеству выводов и совпадений.

Если после учёта всех выводов и совпадений в таблице остались пустые записи, добавьте в таблицы новый смежный класс и повторите процесс. Мы следим за тем, чтобы при добавлении смежных классов, если 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.