# Group acting on two different sets, can isomorphisms be computed efficiently?

For the permutation group isomorphism problem, a permutational isomorphism between two permutation groups is sought. A closely related but seemingly easier problem arises, if an isomorphism between the groups is already fixed, and only a compatible (bijective) mapping of the sets where the groups act must be computed. Instead of fixing an isomorphism between the groups, we can also say that we have just a single group acting on two different sets.

This problem seems to be easier (than the permutation group isomorphism problem), because it seems to allow to directly exploit the fact that any group of size $n$ has a generator set of size at most $\log_2 n$. Such a generator set allows a construction similar to a Cayley graph, such that all that remains is to compute an isomorphism of the corresponding graphs. But I haven't found a suitable data structure for representing the automorphisms of such graphs yet, so I'm stuck at that point.

Because the problem doesn't feel too difficult, I wonder whether it has been solved already. An algorithm with run time polynomial in the size of the set and the size of the group (i.e. exponential in the size of a minimal generator set) would qualify as a solution, in the context of this question.

• What do you mean by "an isomorphism between the groups is already fixed"? – Brendan McKay Nov 3 '15 at 9:39
• @BrendanMcKay After computing a permutational isomorphism, I have both an isomorphism between the groups, and a bijection between the sets where the groups act. If I forget the bijection between the sets and only remember the isomorphism, then "an isomorphism between the groups is already fixed". I admit that the wording "already fixed" is a bit misleading, because computing an arbitrary isomorphism between the groups and fixing it can lead to a situation where there is no corresponding bijection between the sets, even if there would have been one for a different isomorphism. – Thomas Klimpel Nov 3 '15 at 10:45

I'm still not sure in what form your input is given. I'll assume you have permutations $\lbrace g_1,\ldots,g_k\rbrace$ generating $G$, and permutations $\lbrace h_1,\ldots,h_k\rbrace$ generating $H$, and you know there is an isomorphism $\phi:G\to H$ defined by $\phi(g_j)=h_j$ for each $j$. Now you want to find a conjugacy in $S_n$ that implements that isomorphism, i.e. an element $\ell\in S_n$ such that $g_j^\ell=h_j$ for all $j$, or to prove that there is none.

If this is the question, then the question seems to be identical to this one. You will see that I gave an algorithm there with time requirements $O(n^2k)$.

If your input doesn't consist of permutations, something else is needed.

• I think your interpretation was the same as mine, but I simplified the problem by identifying $G$ with $H$ and letting it act on two dsitinct sets. But your algorithm is better because it is more directed to this specific problem. – Derek Holt Nov 3 '15 at 12:05

I haven't thought out the details, but I think this should be possible in time polynomial in the size of the sets being permuted and in the number of generators of the group $G$. So it would be a polynomial time algorithm if your input consisted of generators of the group, which is the most common assumption in computational group theory.

Two transitive actions of $G$ on sets $X$ and $Y$ are equivalent, if and only if their point stabilizers are conjugate in $G$, and there is a equivalence $\alpha$ mapping $x \in X$ to $y \in Y$, where $x$ and $y$ have the same stabilizers. Once you have identified $x$ and $y$, you can easily calculate the action of $\alpha$ on the remaining points of $X$, using $\alpha(x^g) = \alpha(x)^g$. (I am using right actions here.)

Of course your actions will not in general be transitive. But you can start by calculating the stabilizers of all points in the two sets $X$ and $Y$. That can certainly be done in polynomial time, using base and strong generating set methods, and can be done efficiently in practice in GAP or Magma.

Having done that, choose a point $x \in X$ and search for $y \in Y$ with the same stabilizer in $G$ as $x$. If you don't find one, then the actions are not equivalent. If you do, then define $\alpha(x)=y$ and calculate the action of $\alpha$ on the rest of the orbit of $\alpha$ under $G$, which will be mapped by $\alpha$ to the orbit of $y$. Now if $\alpha$ is not defined on all of $X$, choose a point $x$ on which it is not defined, and search for a point $y \in Y$ that is not in the current image of $\alpha$ having the same stabilizer as $x$. Just repeat this process. I think the whole procedure could be programmed easily in GAP or Magma and would run fast in practice.