Group Membership Test for Permutations

Question

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?

Answer 1

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$.

Answer 2

As I commented, you simply made a mistake in your algebra:

$$|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$.

Answer 3

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}}$.