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

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

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

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

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

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

Отрывок, характеризующий Алгоритм Тодда — Коксетера

– Повар чей то княжеский…
– Что, мусью, видно, русский соус кисел французу пришелся… оскомину набил, – сказал сморщенный приказный, стоявший подле Пьера, в то время как француз заплакал. Приказный оглянулся вокруг себя, видимо, ожидая оценки своей шутки. Некоторые засмеялись, некоторые испуганно продолжали смотреть на палача, который раздевал другого.
Пьер засопел носом, сморщился и, быстро повернувшись, пошел назад к дрожкам, не переставая что то бормотать про себя в то время, как он шел и садился. В продолжение дороги он несколько раз вздрагивал и вскрикивал так громко, что кучер спрашивал его:
– Что прикажете?
– Куда ж ты едешь? – крикнул Пьер на кучера, выезжавшего на Лубянку.
– К главнокомандующему приказали, – отвечал кучер.
– Дурак! скотина! – закричал Пьер, что редко с ним случалось, ругая своего кучера. – Домой я велел; и скорее ступай, болван. Еще нынче надо выехать, – про себя проговорил Пьер.
Пьер при виде наказанного француза и толпы, окружавшей Лобное место, так окончательно решил, что не может долее оставаться в Москве и едет нынче же в армию, что ему казалось, что он или сказал об этом кучеру, или что кучер сам должен был знать это.
Приехав домой, Пьер отдал приказание своему все знающему, все умеющему, известному всей Москве кучеру Евстафьевичу о том, что он в ночь едет в Можайск к войску и чтобы туда были высланы его верховые лошади. Все это не могло быть сделано в тот же день, и потому, по представлению Евстафьевича, Пьер должен был отложить свой отъезд до другого дня, с тем чтобы дать время подставам выехать на дорогу.
24 го числа прояснело после дурной погоды, и в этот день после обеда Пьер выехал из Москвы. Ночью, переменя лошадей в Перхушкове, Пьер узнал, что в этот вечер было большое сражение. Рассказывали, что здесь, в Перхушкове, земля дрожала от выстрелов. На вопросы Пьера о том, кто победил, никто не мог дать ему ответа. (Это было сражение 24 го числа при Шевардине.) На рассвете Пьер подъезжал к Можайску.
Все дома Можайска были заняты постоем войск, и на постоялом дворе, на котором Пьера встретили его берейтор и кучер, в горницах не было места: все было полно офицерами.
В Можайске и за Можайском везде стояли и шли войска. Казаки, пешие, конные солдаты, фуры, ящики, пушки виднелись со всех сторон. Пьер торопился скорее ехать вперед, и чем дальше он отъезжал от Москвы и чем глубже погружался в это море войск, тем больше им овладевала тревога беспокойства и не испытанное еще им новое радостное чувство. Это было чувство, подобное тому, которое он испытывал и в Слободском дворце во время приезда государя, – чувство необходимости предпринять что то и пожертвовать чем то. Он испытывал теперь приятное чувство сознания того, что все то, что составляет счастье людей, удобства жизни, богатство, даже самая жизнь, есть вздор, который приятно откинуть в сравнении с чем то… С чем, Пьер не мог себе дать отчета, да и ее старался уяснить себе, для кого и для чего он находит особенную прелесть пожертвовать всем. Его не занимало то, для чего он хочет жертвовать, но самое жертвование составляло для него новое радостное чувство.


24 го было сражение при Шевардинском редуте, 25 го не было пущено ни одного выстрела ни с той, ни с другой стороны, 26 го произошло Бородинское сражение.
Для чего и как были даны и приняты сражения при Шевардине и при Бородине? Для чего было дано Бородинское сражение? Ни для французов, ни для русских оно не имело ни малейшего смысла. Результатом ближайшим было и должно было быть – для русских то, что мы приблизились к погибели Москвы (чего мы боялись больше всего в мире), а для французов то, что они приблизились к погибели всей армии (чего они тоже боялись больше всего в мире). Результат этот был тогда же совершении очевиден, а между тем Наполеон дал, а Кутузов принял это сражение.
Ежели бы полководцы руководились разумными причинами, казалось, как ясно должно было быть для Наполеона, что, зайдя за две тысячи верст и принимая сражение с вероятной случайностью потери четверти армии, он шел на верную погибель; и столь же ясно бы должно было казаться Кутузову, что, принимая сражение и тоже рискуя потерять четверть армии, он наверное теряет Москву. Для Кутузова это было математически ясно, как ясно то, что ежели в шашках у меня меньше одной шашкой и я буду меняться, я наверное проиграю и потому не должен меняться.
Когда у противника шестнадцать шашек, а у меня четырнадцать, то я только на одну восьмую слабее его; а когда я поменяюсь тринадцатью шашками, то он будет втрое сильнее меня.
До Бородинского сражения наши силы приблизительно относились к французским как пять к шести, а после сражения как один к двум, то есть до сражения сто тысяч; ста двадцати, а после сражения пятьдесят к ста. А вместе с тем умный и опытный Кутузов принял сражение. Наполеон же, гениальный полководец, как его называют, дал сражение, теряя четверть армии и еще более растягивая свою линию. Ежели скажут, что, заняв Москву, он думал, как занятием Вены, кончить кампанию, то против этого есть много доказательств. Сами историки Наполеона рассказывают, что еще от Смоленска он хотел остановиться, знал опасность своего растянутого положения знал, что занятие Москвы не будет концом кампании, потому что от Смоленска он видел, в каком положении оставлялись ему русские города, и не получал ни одного ответа на свои неоднократные заявления о желании вести переговоры.