Group Membership Test for Permutations

Suppose there are $$2$$ permutations given by $$p$$ and $$q$$.
I need to check whether $$p$$ belongs to the group generated by $$q$$, and if so, it's representation in a power of $$q$$.

In other words, I've been given $$p$$ and $$q$$, I need to check whether $$\exists i \in \{ 0,...,|q|-1 \} \text{ such that } p = q^i$$

I know that if $$m = \gcd(i, |q|)$$, then $$|q^i| = \frac{|q|}{m}$$.
Now, say that such an $$i$$ exists. Then, $$|p| = \frac{|q|}{\gcd(i, |q|)} \Rightarrow \gcd(i, |q|) = \frac{|q|}{|p|}$$ Thus, a necessary condition for such an $$i$$ to exist is: $$|p|$$ divides $$|q|$$
Say that this holds, and $$\frac{|q|}{|p|} = r$$, where r is an integer.
Then we just have to solve $$\gcd(i, |q|) = r$$ for $$i \in \{ 0,...,|q|-1 \}$$.
Can this be done? If not manually, then by some efficient algorithm?
(Note: Just looping over all values of $$i$$ is not efficient as $$i$$ may be very large)

Edit:
Another way I can think of solving this is by writing both $$p$$ and $$q$$ as product of disjoint cycles:
$$p = c_1c_2\ldots c_k \text{ and } q = d_1d_2\ldots d_l$$ And thus, as disjoint cycles commute: $$p^i = c_1^ic_2^i\ldots c_k^i$$ How to proceed after this?

As you suggest, start by decomposing the permutations into cycles $$p=c_1\ldots c_k$$, $$q=d_1\ldots d_l$$.

If $$p$$ is a power of $$q$$, then the points in each cycle $$c_i$$ must be unions of points in a subset of the cycles of $$q$$, all of the same length. You can check that in time $$O(n)$$, and also make a record of which cycles of $$p$$ are involved in each $$d_i$$.

So now we have $$p = e_1 \ldots e_l$$, where each $$e_i$$ is a union of some of the cycles of $$p$$ of the same length, and the points in $$e_i$$ are the same as those in $$d_i$$.

Now, for each $$d_i$$ in turn, check whether $$e_i$$ is a power $$d_i^{m_i}$$ of $$d_i$$, where we can take $$0 \le m_i < |d_i|$$. You can quickly identify $$m_i$$ (assuming it exists) by looking at the image under $$e_i$$ of any point in $$d_i$$ and then locating the corresponding point in $$d_i$$.

For example, if $$d_i = (3,5,11,4,9,8,12,6)$$ and $$e_i$$ maps $$3$$ to $$8$$, then $$m_i = 5$$. Now check whether we really do have $$e_i = d_i^{m_1}$$. In the example, we check that $$e_i$$ maps 5 to 12, 11 to 6, 4 to 3, etc.

All of this for all of the cycles can be done in time $$O(n)$$.

If any of the tests so far have failed then $$p$$ is not a power of $$q$$. Otherwise, we have found $$m_i$$ with $$0 \le m_i < |d_i|$$ such that $$e_i = d_i^{m_1}$$ for each $$i$$.

Now, finally we have to solve the system of congruences $$m \equiv m_i \bmod |d_i|$$ for $$1 \le i \le l$$. If there is a solution $$m$$, then $$q^m = p$$, and otherwise $$p$$ is not a power of $$q$$. This can be done using the Chinese Remainder Theorem.

I should know the complexity of solving congruence equations, but I cannot remember it. I think it is low degree polynomial in $$\log {\rm lcm}(|d_1|,\ldots,|d_k|)$$ and, as was mentioned earler, this least common multiple is $$O(e^{\sqrt{n}})$$. So it will be low degree polynomial in $$n$$.

• "Now, for each pi in turn, check whether ei is a power" what is $p^i$ here? Also, do we assume $k > l$? And what is meant by "union" of 2 cycles? – Bingwen Sep 1 '20 at 13:36
• Sorry, typo, $p_i$ should $d_i$. I've corrected it. We must have $k \ge l$. By the union of two cycles I just mean all of the points in them. For example, the union of the cycles $(2,3,5)$, $(6,7,9,10)$ is $\{2,3,5,6,7,9,10\}$. – Derek Holt Sep 1 '20 at 14:01
• Shouldn't be $n ≡ m_i mod|d_i|$ in the last line be $m ≡ m_i mod|d_i|$? – Bingwen Sep 1 '20 at 16:31
• @n3d Yes maybe! I was thinking that $n$ was the variable and $m$ was the solution, but I'll change it to make it clearer. – Derek Holt Sep 1 '20 at 16:41
• Thanks! I think I understand all but the final step where we are applying the Chinese Remainder Theorem (CRT), (which is not quite related to the original question). What if $|d_i|$s aren't co-prime? Won't the CRT say that the solution doesn't exist? There could be multiple cycles with the same $|d_i|$ and $m_i$ right? Should we remove the duplicates before applying CRT? – Bingwen Sep 1 '20 at 16:52

$$|p| = \frac{|q|}{\gcd(i, |q|)} \iff 1= \frac{|q|}{|p|\cdot\gcd(i, |q|)} \iff \gcd(i, |q|) = \frac{|q|}{|p|}$$

Note that the group generated by a single permutation is cyclic. Take for example, $$q = (1234).$$

• $$q^2= (13)(24).$$ Let's call this $$p$$.
• $$q^3 = (1432).$$
• $$q^4 = p^2 = id_{S_4}$$

So the order of $$q = |q| = 4$$, whereas the order of $$p=|p| = 2$$. So as my algebra reveals, $$\gcd(2, 4) = \frac{|q|}{|p|} = \frac 42 = 2$$.

• Thanks for pointing out the mistake, I've corrected it – Bingwen Sep 1 '20 at 2:53

You probably want to work with cycle representations of $$p$$ and $$q$$. Converting a permutation from a table to a cycle representation takes $$O(n)$$ time (where $$n$$ is the order of the permutation group; i.e., the number of things being permuted). Then a necessary condition is that every 'cycle set' of $$p$$ is a subset of a 'cycle set' of $$q$$ (which can easily be checked in $$O(n^2)$$ time and should be checkable in $$O(n)$$ with slightly smarter algorithms); given that, you just have to check that the possible orders given by the cycle set decomposition are consistent. I believe that should also be doable in time $$O(n^2)$$ and maybe faster, though it's a somewhat trickier thing and I haven't looked in close detail.

Note that all of these are faster than anything that takes time comparable to the order of the permutation, since the maximal order of a permutation in $$S_n$$ can be larger than $$e^{\sqrt{n}}$$.

• What do you mean by "cycle sets"? – Bingwen Sep 1 '20 at 2:51
• @n3rd e.g. if $q\in S_6$ is written in cycle representation as $(1\ 4\ 5) (2\ 3) (6)$, then the 'cycle sets' are $\{1,4,5\}$, $\{2, 3\}$, and $\{6\}$. Note that we can't say that the cycle sets of $p$ must be equal to the cycle sets of $q$, because for this $q$, $p\in S_6=(1\ 5\ 4) (2) (3) (6)$ is a power of $q$ (specifically, $q^2$). – Steven Stadnicki Sep 1 '20 at 4:23
• So basically, I need to compute the cycle sets for both the permutations and check whether all members of cycle set of p are subsets of some member of a cycle set of q? But then how do I actually compute the power $i$ ($p = q^i$)? – Bingwen Sep 1 '20 at 5:21