Primitive normalisers in quasipolynomial time (Q2071768)

The \textit{normaliser problem} asks for generators of \(N_K(H)\) given generating sets of subgroups \(H\) and \(K\) of the symmetric group \(S_n\). The best known algorithm is due to [\textit{D. Wiebking}, Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 230--238 (2020; Zbl 07304037)] and runs in simply exponential time \(2^{O(n)}\). It was shown in [\textit{C. M. Roney-Dougal} and \textit{S. Siccha}, Bull. Lond. Math. So. 52, 358--366 (2020; Zbl 07206657) that the normaliser problem may be solved in quasipolynomial time \(2^{O(\log^3(n))}\) when \(H\) is primitive. The paper under review shows that whether \(N_{S_n}(H)\) is primitive or not may be determined in quasipolynomial time \(2^{O(\log^3(n))}\), and the normaliser problem may be solved in quasipolynomial time \(2^{O(\log^3(n))}\) when \(N_{S_n}(H)\) is primitive.