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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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