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

В теории групп, алгоритм Тодда — Коксетера, найденный Дж. А. Тоддом и Г. Коксетером в 1936 году, является алгоритмом для решения проблемы перечисления смежных классов. Для конкретных задания группы [math]\displaystyle{ G }[/math] и подгруппы [math]\displaystyle{ H }[/math] в [math]\displaystyle{ G }[/math], алгоритм перечисляет смежные классы [math]\displaystyle{ G }[/math] по [math]\displaystyle{ H }[/math] и описывает представление перестановками [math]\displaystyle{ G }[/math] на пространстве смежных классов.

Если порядок группы [math]\displaystyle{ G }[/math] является относительно небольшим, и подгруппа [math]\displaystyle{ H }[/math] является несложной (например, циклическая группа), то алгоритм может быть выполнен вручную и дает удобное описание группы [math]\displaystyle{ G }[/math]. Используя свой алгоритм, Коксетер и Тодд показали, что конкретные системы соотношений между порождающими элементами некоторых известных групп полны, то есть составляют систему определяющих соотношений.

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

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

Выполнение алгоритма проходит следующим образом. Предположим это [math]\displaystyle{ G = \langle X \mid R \rangle }[/math], где [math]\displaystyle{ X }[/math] — множество образующих, [math]\displaystyle{ R }[/math] — множество соотношений. Множество образующих [math]\displaystyle{ X }[/math] и их инверсий обозначим [math]\displaystyle{ X^\prime }[/math]. Пусть [math]\displaystyle{ H= \langle h_1,h_2,h_3,...,h_s \rangle }[/math] где [math]\displaystyle{ h_i }[/math] — элементы [math]\displaystyle{ X^\prime }[/math]. Есть три типа матриц, которые будут использоваться: смежный класс матриц, матрицы соотношения для каждого соотношения в [math]\displaystyle{ R }[/math], и матрицы подгруппы для каждого множества образующих [math]\displaystyle{ h_i }[/math] от [math]\displaystyle{ H }[/math]. Информация постепенно добавляется к этим матрицам, и как только они будут заполнены, все смежные классы будут перечислены, и алгоритм закончится. Смежный класс матриц используется, чтобы хранить соотношения между известными смежными классами при умножении множеством образующих. Это имеет ряды, представляющие смежные классы [math]\displaystyle{ H }[/math] и колонки для каждого элемента [math]\displaystyle{ X^\prime }[/math]. Пусть [math]\displaystyle{ C_i }[/math] обозначает смежные классы [math]\displaystyle{ i }[/math]-го ряда смежных классов матриц, и пусть [math]\displaystyle{ g_i O X^\prime }[/math] обозначает множество образующих [math]\displaystyle{ j }[/math]-й колонки. Ввод смежных классов матриц последователен, [math]\displaystyle{ i }[/math] и [math]\displaystyle{ j }[/math] определены так, чтобы было (если известно) [math]\displaystyle{ k }[/math], где [math]\displaystyle{ k }[/math] — такое, что [math]\displaystyle{ C_k = C_i g_j }[/math]. Соотношения матриц используются, чтобы обнаружить, когда некоторые из смежных классов, которые мы нашли, фактически эквивалентны. Выполняется: одно соотношение матриц для каждого соотношения в [math]\displaystyle{ R }[/math]. Пусть [math]\displaystyle{ 1=gn1,gn2,..., gnt }[/math] — соотношение в [math]\displaystyle{ R }[/math], где gni ОX' . матриц соотношения имеет ряды, представляющие смежных классов H, как в смежных классов матриц. Это имеет [math]\displaystyle{ t }[/math] колонки, и ввод в [math]\displaystyle{ i }[/math]-м ряду и [math]\displaystyle{ j }[/math]-й колонке определен, чтобы быть (если известно) [math]\displaystyle{ k }[/math], где Ck=Cig1g2…gj. В частности i-й вход — первоначально i, пока [math]\displaystyle{ gn1 gn2...gnt=1 }[/math]. Наконец, матрицы подгруппы подобны матрицам соотношения, за исключением того, что они держат след возможных соотношений множества образующих H. Для каждого множества образующих hn=gn1gn2…gnt из H, с gniOH', мы создаем матрицу подгруппы. Это имеет только один ряд, соответствуя смежным классам H непосредственно. Это имеет t колонки, и вход в j-й колонке определен (если известно), чтобы быть k, где [math]\displaystyle{ Ck=HCig1g2...gj }[/math] . Когда ряд соотношения или матриц подгруппы закончен, новая информация [math]\displaystyle{ Ci = Cjg, gOH^\prime }[/math] найдена. Это известно как вычитание. От вычитания, мы можем быть в состоянии заполнить в дополнительных записях соотношения и матриц подгруппы, приводя к возможному дополнительному вычитанию. Мы можем заполниться в записях смежных классах матриц, соответствующего уравнениям [math]\displaystyle{ Ci = Cjg }[/math] и [math]\displaystyle{ Cj = Cig-1 }[/math]. Однако, заполняясь в смежных классах матриц, возможно, что мы можем уже иметь ввод для уравнения, но ввод имеет различную ценность. В этом случае, мы обнаружили, что два из наших смежных классов — фактически то же самое, известные как совпадение. Предположим [math]\displaystyle{ Ci = Cj }[/math], с [math]\displaystyle{ i\lt j }[/math] . Мы заменяем все случаи j в матриц с i. Тогда, мы заполняем во всех возможных записях матриц, возможно приводя к большему количеству вычитания и совпадений. Если есть пустые записи в матрице после всего вычитания, и о совпадениях заботились, добавляем новый смежный класс к матрице и повторяем процесс. Мы удостоверяемся, что, добавляя смежный класс, если Hx — известный смежный класс, то Hxg будет добавлен в некоторый момент для всех [math]\displaystyle{ g \in H^\prime }[/math] . (Это необходимо, чтобы гарантировать, что алгоритм закончится обеспеченный [math]\displaystyle{ |G:H| }[/math] конечен.) Когда все матрицы заполнены, алгоритм заканчивается. Мы получили всю информацию о действии G на смежные классы H.

Литература

• J.A. Todd, H.S.M. Coxeter, A practical method for enumerating cosets of a finite abstract group. Proc. Edinb. Math. Soc., II. Ser. 5, 26-34 (1936). Zbl 0015.10103, JFM 62.1094.02
• H.S.M. Coxeter, W.O.J. Moser, Generators and relations for discrete groups. Fourth edition. Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], 14. Springer-Verlag, Berlin-New York, 1980. ix+169 pp. ISBN 3-540-09212-9 MR0562913
• Г. С. М. Коксетер, У. О. Дж. Мозер Порождающие элементы и определяющие соотношения дискретных групп. — М., Наука, 1980, — 240 с.
• Seress, A. «An Introduction to Computational Group Theory» Notices of the AMS, June/July 1997.