Jüngste Fortschritte bei Algorithmen für Permutationsgruppen?

10

Ich interessiere mich für Algorithmen für endliche Gruppen, wie sie im GAP-Paket implementiert sind. Es scheint, dass alle bekannten Algorithmen in diesem Bereich Permutationsgruppen / Matrixgruppen behandeln; zwei grundlegende sind Schreier-Sims [1970] und Butler [1979], siehe zB 'Algorithmen für Permutationsgruppen' von Alice Niemeyer als mögliche Referenz (?)

Daher habe ich mich gefragt, ob in den letzten 50 Jahren auf diesem Gebiet erhebliche Fortschritte erzielt wurden. Ich habe gesehen, dass Benutzer NisaiVloot einige Fragen zu Geflechtgruppen gestellt hat, die eine interessante Erweiterung bekannter Ergebnisse zu Permutationsgruppen darstellen könnten, obwohl mir unklar ist, wie der aktuelle Forschungsstand auf diesem Gebiet ist, da die Mathematik- / Algorithmus-Communitys etwas uneinheitlich zu sein scheinen -von-synchron heutzutage.

Charles Mosley
quelle
Ein guter Anfang wäre wahrscheinlich zu sehen, ob Mitglieder der rechnergestützten Gruppentheorie unter cmsc.uwa.edu.au/research/cgt (Cheryl Praeger, Alice Niemeyer oder Ákos Seress) kürzlich eine Umfrage veröffentlicht oder einen Vortrag darüber gehalten haben.
Anthony Labarre

Antworten:

8

Sicherlich hat es Unmengen von Fortschritten gegeben! (Und wenn Sie wirklich nach den letzten 50 Jahren fragen wollten , dann gehören dazu die Algorithmen von Schreier-Sims und Butler, die Sie bereits erwähnt haben ...)

NCnO(2n|G|)n!poly(n)

[1] Seress, Ákos Permutationsgruppenalgorithmen . Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003

[2] Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos Black-Box-Erkennung endlicher einfacher Gruppen vom Lie-Typ durch Statistik der Elementreihenfolgen . J. Group Theory 5 (2002), No. 4, 383–401.

[3] László Babai, Paolo Codenotti, Youming Qiao: Polynom-Zeit-Isomorphismus-Test für Gruppen ohne abelsche normale Untergruppen (Extended Abstract) . In: Proc. 39. Internat. Colloq. zu Automaten, Sprachen und Programmierung (ICALP'12), Springer LNCS 7391, 2012, S. 51-62.

Joshua Grochow
quelle