Algoritmul Todd-Coxeter

În teoria grupurilor , algoritmul Todd-Coxeter , găsit de J. A. Todd și G. Coxeter în 1936, este un algoritm pentru rezolvarea problemei de enumerare a grupelor . Pentru un anumit grup și subgrup în , algoritmul enumerează seturi prin și descrie o reprezentare prin permutări în spațiul claselor. $G$ $H$ $G$ $G$ $H$ $G$

Dacă ordinea grupului este relativ mică și subgrupul este necomplicat (de exemplu, un grup ciclic ), atunci algoritmul poate fi realizat manual și oferă o descriere convenabilă a grupului . Folosind algoritmul lor, Coxeter și Todd au arătat că sistemele de relații specifice dintre elementele generatoare ale unor grupuri cunoscute sunt complete, adică ele constituie un sistem de relații definitorii . $G$ $H$ $G$

Algoritmul Todd-Coxeter poate fi aplicat la grupuri infinite și se termină după un număr finit de pași, cu condiția ca indicele în să fie finit. Pe de altă parte, în cazul general, pentru o pereche constând în specificarea unui grup și a unui subgrup, numărul pașilor acestuia nu este limitat de nicio funcție calculabilă a indicelui subgrupului și a mărimii datelor. $H$ $G$

Descrierea algoritmului

Algoritmul este executat după cum urmează. Să presupunem că , unde este mulțimea generatoarelor , este mulțimea relațiilor . Setul de generatoare și inversiunile acestora vor fi notate cu . Fie unde să fie elemente ale . Există trei tipuri de matrice care pot fi utilizate: matrice de tip sec, matrice de raport pentru fiecare raport în , și matrice de subgrup pentru fiecare set de generatoare din . Informațiile sunt adăugate treptat la aceste matrici și, odată ce acestea sunt completate, toate clasele vor fi listate și algoritmul se va termina. Matricea de seturi este folosită pentru a stoca relații între seturi cunoscute atunci când este înmulțită cu un set de generatoare. Acesta are rânduri reprezentând clase și coloane pentru fiecare element . Să notăm clasele din al treilea rând de clase de matrice și să notăm setul de generatori ai coloanei a I-a. Intrarea claselor de matrice este secvențială și sunt definite astfel încât (dacă se cunoaște) , unde este astfel încât . Rapoartele matriceale sunt folosite pentru a detecta când unele dintre seturile pe care le-am găsit sunt de fapt echivalente. Rulați: o relație matriceală pentru fiecare relație în . Fie o relație în , unde gni ОX' . Matricele de relație au rânduri reprezentând seturi ale lui H, ca în seturile de matrice. Are coloane și intrarea în rândul --lea și --a coloană este definită a fi (dacă se cunoaște) unde Ck=Cig1g2...gj. În special, i-a intrare este inițial i până la . În cele din urmă, matricele de subgrupe sunt similare cu matricele de relații, cu excepția faptului că păstrează o urmă a relațiilor posibile ale setului generator H. Pentru fiecare generator hn=gn1gn2…gnt din H, cu gniOH', creăm o matrice de subgrup. Are un singur rând, corespunzătoare claselor lui H în sine. Are t coloane, iar intrarea din coloana j - a este determinată (dacă este cunoscută) a fi k, unde . Când se completează o serie de matrice de raport sau subgrup, se găsesc informații noi. Aceasta este cunoscută sub denumirea de scădere. Din scădere, este posibil să putem completa intrări suplimentare de rapoarte și matrice de subgrup, rezultând o posibilă scădere suplimentară. Putem completa înregistrările claselor de matrice corespunzătoare ecuațiilor și . Cu toate acestea, la completarea claselor de matrice adiacente, este posibil să avem deja o intrare pentru o ecuație, dar intrarea are o valoare diferită. În acest caz, am descoperit că două dintre seturile noastre sunt de fapt aceleași, cunoscute sub numele de potrivire. Să presupunem cu . Înlocuim toate aparițiile lui j în matrice cu i. Apoi, completăm toate intrările posibile ale matricelor, rezultând, eventual, mai multe scăderi și potriviri. Dacă există intrări goale în matrice după toate scăderile și potrivirile au fost luate în considerare, adăugați o nouă categorie la matrice și repetați procesul. Ne asigurăm că, adăugând o serie, dacă Hx este un set cunoscut, atunci Hxg va fi adăugat la un moment dat pentru toate . (Acest lucru este necesar pentru a ne asigura că algoritmul se termină cu condiția ca acesta să fie finit.) Când toate matricele sunt umplute, algoritmul se termină. Am obținut toate informațiile despre acțiunea lui G asupra claselor lui H. $G = \langle X \mid R \rangle$ $X$ $R$ $X$ $X^\prim$ $H= \langle h_1,h_2,h_3,...,h_s \rangle$ $Bună}$ $X^\prim$ $R$ $Bună}$ $H$ $H$ $X^\prim$ $C_{i}$ $i$ $g_i OX^\prime$ $j$ $i$ $j$ $k$ $k$ $C_k = C_i g_j$ $R$ $1=gn1,gn2,...,gnt$ $R$ $t$ $i$ $j$ $k$ $gn1 gn2...gnt=1$ $Ck=HCig1g2...gj$ $Ci = Cjg, gOH^\prime$ $Ci = Cjg$ $Cj = Cig-1$ $Ci = Cj$ $i<j$ $g \in H^\prim$ $|G:H|$

Literatură

JA Todd, HSM Coxeter, O metodă practică pentru enumerarea claselor unui grup abstract finit. Proc. Edinb. Matematică. Soc., II. Ser. 5, 26-34 (1936). Zbl 0015.10103, JFM 62.1094.02
HSM Coxeter, WOJ Moser, Generatoare și relații pentru grupuri discrete. A patra editie. Ergebnisse der Mathematik und ihrer Grenzgebiete [Rezultate în matematică și domenii conexe], 14. Springer-Verlag, Berlin-New York, 1980. ix+169 p. ISBN 3-540-09212-9 MR0562913
GS M. Coxeter, W. O. J. Moser Elemente generatoare și definirea relațiilor de grupuri discrete. - M., Nauka, 1980, - 240 p.
Seress, A. „An Introduction to Computational Group Theory” Notices of the AMS, iunie/iulie 1997.

Teoria grupurilor
Noțiuni de bază	Subgrup Subgrup normal Grup de factori Muncă direct semidirectă gratuit
Proprietăți algebrice	grup comutativ Grup ciclic grup ordonat Transformați grupul Grup solubil Lema lui Schreier teorema lui Lagrange teoremele lui Sylow Clasificarea grupurilor finite simple
grupuri finite	Grupa ciclică finită C n Grupul simetric S n Grupul diedric D n Grupa alternativă A n Grupul Cvadruplu Klein grupurile Mathieu M11 _ M12 _ M22 _ M23 _ M24 _ grupuri Conway Co 1 Co2 _ Co3 _ grupuri Janko J1 _ J2 _ J3 _ J4 _ Grupuri de pescari F22 _ F 23 F24 _ Monstru (M)
Grupuri topologice	Grupuri de minciuni Grupul ortogonal O(n) Grup ortogonal special SO(n) Grupa unitară U(n) Grup unitar special SU(n) Grupa simplectică Sp(n) Simplu excepțional grupul Lorentz grupul Poincaré
Algoritmi pe grupuri	Schreier - Sims Todd - Coxeter transformata Fourier