Алгоритм Тодда

В теории групп, алгоритм Тодда — Коксетера, найденный Дж. А. Тоддом и Коксетером в 1936 году, является алгоритмом для решения проблемы перечисления смежных классов. Для конкретных задания группы $G$ и подгруппы $H$ в $G$, алгоритм перечисляет смежные классы $G$ по $H$ и описывает представление перестановками $G$ на пространстве смежных классов.

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

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

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

Эта статья должна быть полностью переписана. На странице обсуждения могут быть пояснения.

Выполнение алгоритма проходит следующим образом. Предположим это $G = \langle X \mid R \rangle$, где $X$ — множество образующих, $R$ — множество отношений. Множество образующих $X$ и их инверсий обозначим $X^\prime$. Пусть $H= \langle h_1,h_2,h_3,...,h_s \rangle$ где $h_i$ — элементы $X^\prime$. Есть три типа матриц, которые будут использоваться: смежный класс матриц, матрицы отношения для каждого отношения в $R$, и матрицы подгруппы для каждого множества образующих $h_i$ от $H$. Информация постепенно добавляется к этим матрицам, и как только они будут заполнены, все смежные классы будут перечислены, и алгоритм закончится. Смежный класс матриц используется, чтобы хранить отношения между известными смежными классами при умножении множеством образующих. Это имеет ряды, представляющие смежные классы $H$ и колонки для каждого элемента $X^\prime$. Пусть $C_i$ обозначает смежные классы $i$-того ряда смежных классов матриц, и пусть $g_i O X^\prime$ обозначает множество образующих $j$-той колонки. Ввод смежных классов матриц последователен, $i$ и $j$ определены так, чтобы было (если известно) $k$, где $k$ — такое, что $C_k = C_i g_j$. Отношения матриц используются, чтобы обнаружить, когда некоторые из смежных классов, которые мы нашли, фактически эквивалентны. Выполняется: одно отношение матриц для каждого отношения в $R$. Пусть $1=gn1,gn2,..., gnt$ — отношение в $R$, где gni ОX' . матриц отношения имеет ряды, представляющие смежных классов H, как в смежных классов матриц. Это имеет $t$ колонки, и ввод в $i$-том ряду и $j$-том колонке определен, чтобы быть (если известно) $k$, где Ck=Cig1g2...gj. В частности i-тый вход - первоначально i, пока $gn1 gn2...gnt=1$. Наконец, матрицы подгруппы подобны матрицам отношения, за исключением того, что они держат след возможных отношений множества образующих H. Для каждого множества образующих hn=gn1gn2...gnt из H, с gniОH', мы создаем матрицу подгруппы. Это имеет только один ряд, соответствуя смежным классам H непосредственно. Это имеет t колонки, и вход в j-той колонке определен (если известно), чтобы быть k, где $Ck=HCig1g2...gj$ . Когда ряд отношения или матриц подгруппы закончен, новая информация $Ci = Cjg, gOH^\prime$ найдена. Это известно как вычитание. От вычитания, мы можем быть в состоянии заполнить в дополнительных записях отношения и матриц подгруппы, приводя к возможному дополнительному вычитанию. Мы можем заполниться в записях смежных классах матриц, соответствующего уравнениям $Ci = Cjg$ и $Cj = Cig-1$. Однако, заполняясь в смежных классах матриц, возможно, что мы можем уже иметь ввод для уравнения, но ввод имеет различную ценность. В этом случае, мы обнаружили, что два из наших смежных классов - фактически то же самое, известные как совпадение. Предположим $Ci = Cj$, с $i<j$ . Мы заменяем все случаи j в матриц с i. Тогда, мы заполняем во всех возможных записях матриц, возможно приводя к большему количеству вычитания и совпадений. Если есть пустые записи в матрице после всего вычитания, и о совпадениях заботились, добавляем новый смежный класс к матрице и повторяем процесс. Мы удостоверяемся, что, добавляя смежный класс, если Hx - известный смежный класс, то Hxg будет добавлен в некоторый момент для всех $g \in H^\prime$ . (Это необходимо, чтобы гарантировать, что алгоритм закончится обеспеченный $|G:H|$ конечен.) Когда все матрицы заполнены, алгоритм заканчивается. Мы тогда все нуждались в информации относительно действия 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
• Seress, A. "An Introduction to Computational Group Theory" Notices of the AMS, June/July 1997.

У этой статьи нет иллюстраций. Вы можете помочь проекту, добавив их (с соблюдением правил использования изображений). Для поиска иллюстраций можно: попробовать воспользоваться инструментом FIST: нажмите эту ссылку, чтобы начать поиск; попытаться найти изображение на Викискладе; просмотреть иноязычные варианты статьи (если они есть); см. также Википедия:Источники изображений.

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.