1
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ "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? $\endgroup$ – Bingwen Sep 1 '20 at 13:36
  • $\begingroup$ 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\}$. $\endgroup$ – Derek Holt Sep 1 '20 at 14:01
  • $\begingroup$ Shouldn't be $n ≡ m_i mod|d_i| $ in the last line be $m ≡ m_i mod|d_i|$? $\endgroup$ – Bingwen Sep 1 '20 at 16:31
  • $\begingroup$ @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. $\endgroup$ – Derek Holt Sep 1 '20 at 16:41
  • $\begingroup$ 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? $\endgroup$ – Bingwen Sep 1 '20 at 16:52
2
$\begingroup$

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

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

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

$\endgroup$
3
  • $\begingroup$ What do you mean by "cycle sets"? $\endgroup$ – Bingwen Sep 1 '20 at 2:51
  • $\begingroup$ @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$). $\endgroup$ – Steven Stadnicki Sep 1 '20 at 4:23
  • $\begingroup$ 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$)? $\endgroup$ – Bingwen Sep 1 '20 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.