Quasi-polynomial time algorithm for permutation group isomorphism

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.

• Theorem 2 will do the job when the number of symbols is $\: O\hspace{-0.03 in}\left(\hspace{-0.03 in}(\hspace{.02 in}\log(n))^{\hspace{.02 in}2}\hspace{-0.04 in}\right) \;$. $\;\;\;\;$
– user6973
Oct 11 '15 at 14:57

1 Answer

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.

• Obviously you know what you were asking about, but it's worth pointing out that most people, when talking about algorithms on permutation groups, want the running time expressed in terms of the size of the input, which is typically a list of permutations. That is, typically in permutation groups, n is used to denote the degree of the groups, which can be exponentially smaller than their order. As you'll see in the final section of Babai's recent paper, it remains open whether there is a quasi-poly (in the degree) algorithm for perm iso of perm groups. Feb 11 '16 at 21:23
• @JoshuaGrochow I wondered whether permutation group isomorphism is more difficult than group isomorphism, so I tried to come up with an answerable question by staying close to the group isomorphism setup. And I wanted a problem that is many-one reducible to GI, because the ultimate goal was/is to find sources of hard GI instances. Knowing possible sizes of (strong) generating sets was also important. After learning this from Lecture 2, Algebra and Computation by V. Arvind, I started to write this answer, which turned out to be nearly trivial. Feb 12 '16 at 8:35
• Seems reasonable. (Just wanted to point out that "finding a quasi-polynomial-time algorithm for permutational isomorphism of permutation groups," in the usual terminology, is still an interesting open question.) Feb 12 '16 at 20:51