Todd-Coxeterin algoritmi

Ryhmäteoriassa Todd- Coxeterin algoritmi , jonka J. A. Todd ja G. Coxeter löysivät vuonna 1936, on algoritmi kosetin numerointiongelman ratkaisemiseksi . Tietylle ryhmälle ja aliryhmälle kohdassa , algoritmi luettelee kosetit ja kuvaa esityksen permutaatioilla kosettien avaruudessa.

Jos ryhmän järjestys on suhteellisen pieni ja alaryhmä on mutkaton (esim. syklinen ryhmä ), niin algoritmi voidaan tehdä käsin ja se antaa sopivan kuvauksen ryhmästä . Coxeter ja Todd osoittivat algoritmiaan käyttäen, että tietyt relaatiojärjestelmät joidenkin tunnettujen ryhmien generoivien elementtien välillä ovat täydellisiä, eli ne muodostavat relaatioiden määrittelyjärjestelmän .

Todd-Coxeter-algoritmia voidaan soveltaa äärettömiin ryhmiin ja se päättyy äärellisen määrän vaiheiden jälkeen, edellyttäen, että indeksi in on äärellinen. Toisaalta yleisessä tapauksessa ryhmän ja aliryhmän määrittämisestä koostuvan parin vaiheiden lukumäärää ei rajoita mikään aliryhmän indeksin ja datakoon laskettava funktio .

Algoritmin kuvaus

Algoritmi suoritetaan seuraavasti. Oletetaan, että missä  on generaattoreiden joukko , on suhteiden  joukko . Generaattorijoukko ja niiden inversiot merkitään . Olkoon missä  elementtejä . Käytettävissä on kolmen tyyppisiä matriiseja : coset-matriisit, suhdematriisit jokaiselle suhteelle kohteessa , ja alaryhmämatriisit jokaiselle generaattorijoukolle alkaen . Näihin matriiseihin lisätään tietoja asteittain, ja kun ne on täytetty, kaikki kosetit luetellaan ja algoritmi päättyy. Coset-matriisia käytetään suhteiden tallentamiseen tunnettujen kosettien välillä, kun ne kerrotaan generaattorijoukolla. Tässä on rivit, jotka edustavat kunkin elementin kosetteja ja sarakkeita . Merkitään matriisien :nnen rivin kosetit ja i :nnen sarakkeen generaattorien joukkoa . Syöte cosets matriisien on peräkkäinen, ja ne määritellään siten, että (jos tiedossa) , jossa  on sellainen, että . Matriisisuhteita käytetään havaitsemaan, milloin jotkin löytämämme kosetit ovat todella vastaavia. Suorita: yksi matriisirelaatio jokaiselle relaatiolle . Antaa olla  suhde , jossa gni ОX' . Relaatiomatriiseissa on rivejä, jotka edustavat H:n kosetteja, kuten matriisien koseteissa. Siinä on sarakkeita ja -:nnen rivin ja -:nnen sarakkeen syöte on määritelty (jos tiedossa) jossa Ck=Cig1g2…gj. Erityisesti i:s syöte on aluksi i asti . Lopuksi alaryhmämatriisit ovat samanlaisia ​​kuin relaatiomatriisit, paitsi että ne pitävät jäljen generaattorijoukon H mahdollisista suhteista. Jokaiselle generaattorijoukolle hn=gn1gn2…gnt H:sta, jossa gniOH', luodaan aliryhmämatriisi. Siinä on vain yksi rivi, joka vastaa itse H:n kosetteja. Siinä on t saraketta, ja j :nnen sarakkeen merkinnäksi määritetään (jos tiedossa) on k, jossa . Kun suhde- tai alaryhmämatriisisarja on valmis, löydetään uutta tietoa. Tätä kutsutaan vähennykseksi. Vähennyksellä voimme ehkä täyttää lisää suhdelukuja ja aliryhmämatriiseja, mikä johtaa mahdolliseen lisävähennykseen. Voimme täyttää matriisien cosettien tietueet, jotka vastaavat yhtälöitä ja . Vierekkäisiä matriisiluokkia täytettäessä on kuitenkin mahdollista, että meillä voi olla jo syöte yhtälöön, mutta syötteellä on eri arvo. Tässä tapauksessa havaitsimme, että kaksi asustamme ovat itse asiassa samat, eli ottelut. Oletetaan kanssa . Korvataan kaikki j:n esiintymät matriiseissa i:llä. Sitten täytämme kaikki mahdolliset matriisien merkinnät, mikä mahdollisesti johtaa enemmän vähennyksiin ja osuuksiin. Jos matriisissa on tyhjiä merkintöjä kaikkien vähennysten jälkeen ja osumat on hoidettu, lisää matriisiin uusi kosetti ja toista prosessi. Varmistamme, että lisäämällä kosetin, jos Hx on tunnettu kosetti, Hxg lisätään jossain vaiheessa kaikille . (Tämä on tarpeen sen varmistamiseksi, että algoritmi päättyy, jos se on äärellinen.) Kun kaikki matriisit on täytetty, algoritmi päättyy. Olemme saaneet kaikki tiedot G:n vaikutuksesta H:n koseteihin.

Kirjallisuus

• JA Todd, HSM Coxeter, Käytännön menetelmä äärellisen abstraktin ryhmän kosettien laskemiseen. Proc. Edinb. Matematiikka. Soc., II. Ser. 5, 26-34 (1936). Zbl 0015.10103, JFM 62.1094.02
• HSM Coxeter, WOJ Moser, Generaattorit ja relaatiot erillisryhmille. Neljäs painos. Ergebnisse der Mathematik und ihrer Grenzgebiete [Tulokset matematiikassa ja siihen liittyvissä kysymyksissä], 14. Springer-Verlag, Berliini-New York, 1980. ix+169 s. ISBN 3-540-09212-9 MR0562913
• GS M. Coxeter, W. O. J. Moser Diskreettien ryhmien elementtien generointi ja suhteiden määrittely. - M., Nauka, 1980, - 240 s.
• Seress, A. "Johdatus laskennalliseen ryhmäteoriaan" AMS:n ilmoitukset, kesä/heinäkuu 1997.