Normalisers of primitive permutation groups in quasipolynomial time

Colva Roney-Dougal, Sergio Siccha

Published 2020-02-04Version 1

We show that given generators for subgroups $G$ and $H$ of $\mathrm{S}_n$, if $G$ is primitive then generators for $\mathrm{N}_H(G)$ may be computed in quasipolynomial time, namely $2^{O(\log^3 n)}$. The previous best known bound was simply exponential.