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

В теории групп алгоритм Тодда–Коксетера , созданный JA Todd и HSM Coxeter в 1936 году, является алгоритмом для решения задачи перечисления смежных классов . При заданном представлении группы G образующими и соотношениями и подгруппой H группы G алгоритм перечисляет смежные классы H на G и описывает перестановочное представление G на пространстве смежных классов (задаваемое левым умножением). Если порядок группы G относительно мал и известно, что подгруппа H несложная (например, циклическая группа ), то алгоритм может быть выполнен вручную и дает разумное описание группы G. Используя свой алгоритм, Коксетер и Тодд показали , что некоторые системы соотношений между образующими известных групп являются полными, т. е. составляют системы определяющих соотношений.

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

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

Одна из реализаций алгоритма выполняется следующим образом. Предположим, что , где — набор генераторов , а — набор отношений , и обозначим через набор генераторов и их обратных. Пусть где — слова элементов из . Будут использоваться три типа таблиц: таблица смежных классов, таблица отношений для каждого отношения в и таблица подгрупп для каждого генератора из . Информация постепенно добавляется в эти таблицы, и как только они заполняются, все смежные классы перечисляются, и алгоритм завершается. ${\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}$

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

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

Наконец, таблицы подгрупп похожи на таблицы отношений, за исключением того, что они отслеживают возможные отношения генераторов . Для каждого генератора , с , мы создаем таблицу подгрупп. Она имеет только одну строку, соответствующую смежному классу самой себя. Она имеет t столбцов, а запись в j -м столбце определяется (если известна) как k , где . ${\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}$ ${\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}}$

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

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

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

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

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

Ссылки

• Тодд, JA ; Коксетер, HSM (1936). «Практический метод перечисления смежных классов конечной абстрактной группы». Труды Эдинбургского математического общества . Серия II. 5 : 26–34. doi : 10.1017/S0013091500008221 . JFM  62.1094.02. Zbl  0015.10103.
• Коксетер, HSM ; Мозер, WOJ (1980). Генераторы и соотношения для дискретных групп . Ergebnisse der Mathematik und ihrer Grenzgebiete . Том. 14 (4-е изд.). Springer-Verlag 1980. ISBN. 3-540-09212-9. МР  0562913.
• Сересс, Акош (1997). "Введение в вычислительную теорию групп" (PDF) . Notices of the American Mathematical Society . 44 (6): 671–679. MR  1452069.