Fast permutation-word multiplication and the simultaneous conjugacy problem.
Andrej Brodnik, Aleksander Malnič, Rok Požar · arXiv (Cornell University) · 2019
Given a finite sequence $a_1, a_2,\ldots, a_d$ of $d$ permutations in the symmetric group $S_n$, and a permutation word $k_1k_2\cdots k_{m}$ over the alphabet $\{1,2,\ldots, d\}$, computation of the product $a_{k_1}a_{k_2}\cdots a_{k_{m}}$ in a straightforward manner takes $O(n m)$ time. However, it appears that this multiplication is such an elementary operation that, surprisingly enough, it went on unquestioned. We show that the above product can be computed in time $O(\min{\{ n m, n m \log d / \log m\}})$ using $O(m + n m^{\epsilon})$ space, where $0 < \epsilon < 1$. Consequently, this computation takes $o(n m)$ time whenever $\log d = o(\log m)$, which is a reasonable assumption in practice. The above result is used to solve the transitive simultaneous conjugacy problem in $O(n^2 \log d / \log n + dn\log n)$ time and $O(n^{1+ \epsilon} + dn)$ space, where $0 < \epsilon <1$. This problem asks whether there exists a permutation $\tau \in S_n$ such that $b_j = \tau^{-1} a_j \tau$ holds for all $j = 1,2, \ldots, d$, where $a_1, a_2, \ldots, a_d$ and $b_1, b_2, \ldots, b_d$ are given sequences of $d$ permutations in $S_n$, each of which generates a transitive subgroup of $S_n$. As from mid 70' it has been know that the problem can be solved in $O(dn^2)$ time. An algorithm with running time $O(dn \log(dn))$, proposed in late 80', does not work correctly on all input data.