Todd-Coxeter algoritmus

A csoportelméletben a Todd-Coxeter algoritmus , amelyet J. A. Todd és G. Coxeter talált meg 1936-ban, egy algoritmus a coset felsorolási probléma megoldására . Egy adott csoporthoz és alcsoporthoz a -ban az algoritmus felsorolja a koszeteket , és leírja a permutációkkal történő reprezentációt a kosettek terén. $G$ $H$ $G$ $G$ $H$ $G$

Ha a csoport sorrendje viszonylag kicsi, és az alcsoport nem bonyolult (pl. ciklikus csoport ), akkor az algoritmus kézzel is elvégezhető, és kényelmes leírást ad a csoportról . Coxeter és Todd algoritmusukkal kimutatták, hogy egyes ismert csoportok generáló elemei között meghatározott relációrendszerek teljesek, azaz relációmeghatározó rendszert alkotnak . $G$ $H$ $G$

A Todd-Coxeter algoritmus végtelen csoportokra alkalmazható, és véges számú lépés után véget ér, feltéve, hogy az in index véges. Másrészt általános esetben egy csoport és egy alcsoport meghatározásából álló pár esetében lépéseinek számát nem korlátozza az alcsoport indexének és adatméretének semmilyen kiszámítható függvénye . $H$ $G$

Az algoritmus leírása

Az algoritmus a következőképpen hajtódik végre. Tegyük fel, hogy ahol a generátorok halmaza , ott a relációk halmaza . A generátorok halmazát és azok inverzióit jelöljük . Legyenek hol elemei . Háromféle mátrix használható: coset mátrixok, aránymátrixok minden egyes arányhoz a -ban , és alcsoportmátrixok minden generátorkészlethez -ból . Az információ fokozatosan hozzáadódik ezekhez a mátrixokhoz, és miután kitöltöttük, az összes koset megjelenik, és az algoritmus véget ér. A coset mátrix az ismert kosetták közötti kapcsolatok tárolására szolgál, ha generátorkészlettel megszorozzuk. Ebben minden elemhez sorok és oszlopok tartoznak . Jelölje a mátrixok kosetei sorának cosetjeit, és jelölje az i-edik oszlop generátorainak halmazát . A mátrixok cosetjeinek bemenete szekvenciális, és úgy van meghatározva, hogy (ha ismert) , ahol olyan, hogy . A mátrixarányokat arra használjuk, hogy kimutassuk, hogy az általunk talált kosetták némelyike valójában egyenértékű-e. Futtatás: minden relációhoz egy mátrix reláció -ban . Legyen egy reláció -ben , ahol gni ОX' . A relációs mátrixokban vannak sorok, amelyek H koszetumait reprezentálják, mint a mátrixok koszetumaiban. Oszlopai vannak , és a -edik sor és -edik oszlop bemenete (ha ismert) ahol Ck=Cig1g2…gj. Különösen az i-edik bemenet kezdetben i -ig . Végül az alcsoportmátrixok hasonlóak a relációs mátrixokhoz, azzal a különbséggel, hogy nyomon követik a H generátorhalmaz lehetséges relációit. Minden egyes hn=gn1gn2…gnt generátorhalmazhoz H-ból, gniOH'-val, létrehozunk egy alcsoportmátrixot. Csak egy sora van, amely magának a H-nak felel meg. t oszlopa van, és a j - edik oszlop bejegyzése (ha ismert) k, ahol . Amikor egy arány- vagy alcsoportmátrix sorozat elkészül, új információ található. Ezt kivonásnak nevezik. A kivonásból esetleg további arányokat és részcsoportmátrixokat is kitölthetünk, ami további kivonást eredményezhet. A és az egyenleteknek megfelelő mátrixok cosetjeinek rekordjait kitölthetjük . A szomszédos mátrixosztályok kitöltésekor azonban előfordulhat, hogy egy egyenlethez már van bemenetünk, de a bemenetnek más az értéke. Ebben az esetben azt találtuk, hogy két kosettánk valójában egyforma, egyezésként ismert. Tegyük fel , hogy . A mátrixokban szereplő j minden előfordulását i-re cseréljük. Ezután kitöltjük a mátrixok összes lehetséges bejegyzését, ami esetleg több kivonást és egyezést eredményezhet. Ha az összes kivonás után üres bejegyzések vannak a mátrixban, és az egyezések megtörténtek, adjon hozzá egy új coset-et a mátrixhoz, és ismételje meg a folyamatot. Gondoskodunk arról, hogy egy coset hozzáadásával, ha Hx egy ismert coset, akkor a Hxg egy bizonyos ponton az összeshez hozzáadásra kerüljön . (Erre azért van szükség, hogy az algoritmus véget érjen, feltéve, hogy véges.) Amikor az összes mátrix megtelt, az algoritmus véget ér. Megszereztünk minden információt G hatásáról a H kosetjein. $G = \langle X \mid R \rangle$ $x$ $R$ $x$ $X^\prime$ $H= \langle h_1,h_2,h_3,...,h_s \rangle$ $Szia}$ $X^\prime$ $R$ $Szia}$ $H$ $H$ $X^\prime$ $C_{i}$ $én$ $g_i OX^\prime$ $j$ $én$ $j$ $k$ $k$ $C_k = C_i g_j$ $R$ $1=gn1,gn2,...,gnt$ $R$ $t$ $én$ $j$ $k$ $gn1 gn2...gnt=1$ $Ck=HCig1g2...gj$ $Ci = Cjg, gOH^\prím$ $Ci = Cjg$ $Cj = Cig-1$ $Ci = Cj$ $i<j$ $g \in H^\prím$ $|G:H|$

Irodalom

JA Todd, HSM Coxeter, Gyakorlati módszer véges absztrakt csoport koseteinek számbavételére. Proc. Edinb. Math. Szoc., II. Ser. 5, 26-34 (1936). Zbl 0015.10103, JFM 62.1094.02
HSM Coxeter, WOJ Moser, Generátorok és kapcsolatok diszkrét csoportokhoz. Negyedik kiadás. 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
GS M. Coxeter, W. O. J. Moser Diszkrét csoportok elemeinek generálása és relációinak meghatározása. - M., Nauka, 1980, - 240 p.
Seress, A. "Bevezetés a számítási csoportelméletbe" Az AMS közleményei, 1997. június/július.

Csoportelmélet
Alapfogalmak	Alcsoport Normál alcsoport Tényezőcsoport Munka közvetlen félig közvetlen ingyenes
Algebrai tulajdonságok	kommutatív csoport Ciklikus csoport rendelt csoport Transform Group Megoldható csoport Schreier Lemmája Lagrange-tétel Sylow tételei Egyszerű véges csoportok osztályozása
véges csoportok	Véges ciklikus csoport C n Szimmetrikus csoport S n Diéder csoport D n Váltakozó csoport A n Klein négyes csoport Mathieu csoportok M11_ _ M12_ _ M22 _ M23_ _ M24 _ Conway csoportok Co 1 Co2_ _ Co3_ _ Jankó csoportok J1_ _ J2_ _ J3_ _ J4_ _ Fisher csoportok F22_ _ F 23 F24 _ Szörny (M)
Topológiai csoportok	Hazugságcsoportok O(n) ortogonális csoport Speciális ortogonális csoport SO(n) U(n) egységes csoport Különleges egységes csoport SU(n) Szimlektikus csoport Sp(n) Kivételes Egyszerű Lorentz csoport Poincaré csoport
Algoritmusok csoportokon	Schreier – Sims Todd – Coxeter Fourier transzformáció