Normalizers of primitive groups with non-regular socles in polynomial time

Siccha, Sergio Christian; Niemeyer, Alice Catherine (Thesis advisor); Barakat, Mohamed (Thesis advisor)

Aachen (2020)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

Für zwei Gruppen $G$ und $H$, die in einer gemeinsamen Obergruppe $K$ enthalten sind, heißt der \emph{Normalisator von $G$ in $H$}die Untergruppe von $H$ die aus allen Elementen besteht die $G$ unter Konjugation invariant lassen. Diese Gruppe bezeichnen wir mit $N_H(G)$. Wir sagen, dass ein Problem für Permutationsgruppen in \emph{Polynomialzeit}gelöst werden kann, falls ein Algorithmus existiert der, für gegebene Permutationsgruppen von Grad $n$, das Problem in polynomiell in $n$ beschränkter Zeit lösen kann. Das Hauptresultat dieser Arbeit ist, dass für eine primitive Gruppe $G \leq \sym \Omega$ mit nicht-regulärem Sockel der Normalisator $N_{\sym \Omega}(G)$ in Polynomialzeit berechnet werden kann. Ein essenzielles Werkzeug ist das in dieser Arbeit entwickelte Konzept der Permutationsmorphismen. Diese verallgemeinern Permutationsisomorphismen und ermöglichen es uns eine Kategorie von Permutationsgruppen zu definieren. In dieser Kategorie können wir Produkte von Permutationsgruppen und auf Blocksystemen induzierte Operationen elegant beschreiben. Unser Hauptresultat erreichen wir mithilfe der folgenden Schritte. Wir definieren schwach kanonische Formen für primitive Gruppen: anschaulich gesehen ist eine Gruppe in schwach kanonischer Form, falls ihr Sockel eine einfach zu beschreibende Form annimmt. Mithilfe der Theorie der Permutationsmorphismen zeigen wir, dass wir schwach kanonische Formen primitiver Gruppen effizient berechnen können. Für eine primitive Gruppe in schwach kanonischer Form wiederum zeigen wir, dass wir den Normalisator ihres Sockels in Polynomialzeit berechnen können. Wir nutzen dann den Normalisator des Sockels, eine logarithmische Reduktion und einfach-Exponentialzeit-Algorithmen für das Normalisator und das Gruppen-Schnitt Problem um mit diesen einen Algorithmus zu entwerfen der $N_{\sym \Omega}(G)$ in Polynomialzeit berechnet. Wir untersuchen außerdem weitere mögliche Anwendungen der schwach kanonischen Formen um Konjugiertheit von Permutationsgruppen zu entscheiden und um kleine Permutationsdarstellungen primitiver Gruppen zu berechnen.