Quasi-polynomial time algorithm for permutation group isomorphism

Question

Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism.

My hope for such an algorithm comes from reading a blog post on the group isomorphism problem and its comments. Because any group of size $n$ has a generator set of size at most $\log_2 n$, maybe a permutation group will even have a strong generator set of size at most $\log_2 n$ (and hopefully that would already be sufficient for a quasi-polynomial algorithm). The comments mention two papers that relate the complexity of the problem of permutational isomorphism of permutation groups to the complexity of the problem of isomorphism of semisimple groups, and also mention earlier work on the permutational isomorphism problem.

---

A comment by Ben Barber on a related question indicates that permutation group isomorphism can be reduced to graph isomorphism, which is not really surprising, but nice to know nevertheless.

Answer 1

The answer is basically yes, if we take into account the hidden assumption that the degree of the group is at most $n$. More precisely, let $G_1, G_2$ with $|G_1|=| G_2|=n$ be finite permutation groups acting on a set $\Omega$. Then existence of a permutational isomorphism between $G_1$ and $G_2$ can be checked in time $n^{\log_2 n} \cdot {\max(|\Omega|,n)}^{O(1)}$.

As suggested in the question, a permutation group has a base and corresponding strong generating set (SGS) of size at most $\log_2 n$, and both can be computed in time polynomial in $n$. But this isn't even needed, any generating set of size at most $\log_2 n$ is enough.

After computing such a generating set for $G_1$, the algorithm simply maps successively each element of the generating set to an element of $G_2$, and checks for each such mapping whether it leads to an isomorphism of $G_1$ and $G_2$. For those who do, the algorithm then checks whether there is a permutation of $\Omega$ inducing that isomorphism (for example by a canonical labeling technique, which is closely related to a similar technique for deterministic finite automata, but more group theoretic methods also work). Those checks can be done in time ${\max(|\Omega|,n)}^{O(1)}$, and because there are at most $n^{\log_2 n}$ such mappings, and every isomorphism between $G_1$ and $G_2$ is determined by such a mapping, the above time bound follows.