Введение

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

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

Одна из реализаций алгоритма происходит следующим образом. Предположим, что , где – множество генераторов и – множество отношений, и обозначим множеством генераторов и их обратных элементов. Пусть , где – слова, составленные из элементов . Существуют три типа таблиц, которые будут использоваться: таблица косетов, таблица отношений для каждой связи в и таблица подгрупп для каждого генератора . Информация постепенно добавляется в эти таблицы, и как только они заполнены, все косеты перенумерованы и алгоритм завершается. Таблица косетов используется для хранения соотношений между известными косетами при умножении на генератор. Она имеет строки, представляющие косеты из , и столбец для каждого элемента из . Пусть обозначает косет i-й строки таблицы косетов, а – генератор j-го столбца. Элемент таблицы косетов в строке i, столбце j определяется как (если известно) k, где k такое, что . Таблицы отношений используются для определения, когда некоторые из найденных нами косетов на самом деле эквивалентны. Для каждой связи в поддерживается одна таблица отношений. Пусть – отношение в , где . Таблица отношений имеет строки, представляющие косеты , как и в таблице косетов. В ней t столбцов, и элемент в i-й строке и j-м столбце определяется как (если известно) k, где . В частности, элемент в j-м столбце изначально равен i, поскольку . Наконец, таблицы подгрупп аналогичны таблицам отношений, за исключением того, что они отслеживают возможные соотношения генераторов . Для каждого генератора из , где , мы создаем таблицу подгрупп. У нее только одна строка, соответствующая косету самого себя. Она имеет t столбцов, и элемент в j-м столбце определяется (если известно) как k, где . Когда строка таблицы отношений или подгрупп заполнена, найдена новая информация , , что называется выводом. На основе вывода мы можем заполнить дополнительные элементы таблиц отношений и подгрупп, что может привести к дополнительным выводам. Мы можем заполнить элементы таблицы косетов, соответствующие уравнениям и . Однако при заполнении таблицы косетов возможно, что запись для уравнения уже существует, но имеет другое значение. В этом случае мы обнаружили, что два наших косета на самом деле одинаковы, что называется совпадением. Предположим, что , тогда мы заменяем все экземпляры j в таблицах на i. Затем мы заполняем все возможные элементы таблиц, что может привести к дополнительным выводам и совпадениям. Если после всех выводов и совпадений в таблице остаются пустые элементы, добавляем новый косет в таблицы и повторяем процесс. Мы гарантируем, что при добавлении косетов, если Hx – известный косет, то Hxg будет добавлен в какой-то момент для всех (это необходимо для гарантии завершения алгоритма, если конечно). Когда все таблицы заполнены, алгоритм завершается. Тогда у нас есть вся необходимая информация о действии на косетах .