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)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2020

Abstract

For two groups $G$ and $H$, which are contained in a common overgroup $K$, we call the \emph{normalizer of $G$ in $H$}the subgroup of $H$ consisting of those elements that leave $G$ invariant under conjugation, and denote it by $N_H(G)$.We say that a problem for permutation groups can be solved in \emph{polynomialtime}, if there exists an algorithm that, given permutation groups of degree $n$, can solve the problem in time bounded polynomially in $n$ and in the sizes of the given generating sets. The main result of this thesis is that for a primitive group $G \leq \sym\Omega$ with non-regular socle the normalizer $N_{\sym \Omega}(G)$ can be computed in polynomial time. An essential tool is the, in this thesis newly developed, concept of permutation morphisms. These generalize permutation isomorphisms and enable us to define a category of permutation groups. In this category we can elegantly describe direct products of permutation groups and actions induced on block systems. Our main result is obtained by the following steps. We define weak canonical forms of primitive groups: essentially a group is in weak canonical form if its socle admits a nice action. By using the theory of permutation morphisms we show that we can compute weak canonical forms for all primitive groups efficiently. For a primitive group in weak canonical form we show that we can compute the normalizer of the socle in polynomial time. We then use the normalizer of the socle, a logarithmic reduction, and simply exponential time algorithms for the normalizer and the group intersection problem to design a polynomial time algorithm to compute$N_{\sym \Omega}(G)$ in polynomial time. We also discuss further possible applications of weak canonical forms in testing conjugacy of permutation groups and finding small permutation representations of primitive groups.