We are interested in the following notions in the case $G=S_N$, the symmetric group on
$\{1,\dots,N\}$.
Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
$$(g_1,\dots,g_d)^x := (g_1^x,\dots,g_d^x).$$
(Throughout, $g^x:=x^{-1}gx$.)
$d$-tuples $g=(g_1,\dots,g_d)$ and $h=(h_1,\dots,h_d)$ in $G^d$ are conjugate if there is $x\in G$ such that (in the above notation) $g^x=h$.
The ($d$-dimensional) Simultaneous Conjugacy Problem (SCP) is $G$ is that of deciding whether
given $d$-tuples $g,h\in G^d$ are conjugate.
We need an efficient solution of the SCP in the symmetric group $S_N$. (In fact, for our specific use we are more interested in the search version of this problem (given conjugate $g,h\in G^d$, find $x\in G$ such that $g^x=h$), if that matters.)
One very nice way to solve the SCP is to come up with efficiently computable representatives of conjugacy classes. For ordinary (1-dimensional) conjugacy this is trivial: E.g., the representative of the conjugacy class of the permutation $(7, 9, 5, 3)(1, 2, 4)(6,8)\in S_9$ would be $(1,2,3,4)(5,6,7)(8,9)$.
For larger dimension $d$, one can define the representative as follows:
Define a linear order on $S_N$ as follows: Given $g$, order its cycles from longest to shortest. Make each cycle begin with its minimal element, and order every set of cycles of equal length by their first element. This results in a sequence of $N$ natural numbers.
Compare two permutations by comparing their corresponding sequences, lexicographically.
Given $(g_1,\dots,g_d)\in S_N^d$, bring $g_1$ by conjugation to the above canonical form
$\tilde g_1$.
Then minimize $g_2$ by conjugation with elements of the centeralizer of $\tilde g_1$ to obtain $\tilde g_2$, then minimize $g_3$ by conjugation with elements of the centeralizer of $\{\tilde g_1,\tilde g_2\}$ to obtain $\tilde g_3$, etc. The canonical representative is
$(\tilde g_1,\dots,\tilde g_d)$ (and we can also keep track how to conjugate there).
Question: In the above notation, can we find $(\tilde g_1,\dots,\tilde g_d)$ in polynomial time?
Of course, I would appreciate any efficient solution of the SCP.
Comments:
-
In each stage, one can take generators of the centralizers, compute the orbits using them, and choose the minimal elements. This is better than conjugating by the whole centralizer, but seems inefficient in the worst case.
-
This algorithm is needed to speed up an algorithm for the SCP in Artin's braid group $B_N$.
-
The answers for a related question do not seem to help here.
Best Answer
I'll only consider the case of $S_N$ to start with.
Given $(g_1,\ldots,g_d)\in S_N^d$, define a directed graph $G$ on vertices $\lbrace 1,\ldots,N\rbrace$ whose edges are coloured with elements of $Z_2^d$. Edge $i{\to}j$ is coloured $(\epsilon_1,\ldots,\epsilon_d)$, where $\epsilon_t=1$ iff $g_t$ maps $i$ onto $j$. You can remove loops and edges of colour 0 if you like.
The isomorphism type of the graph $G$ exactly corresponds to the conjugacy class of $(g_1,\ldots,g_d)$, so you can use graph isomorphism software to find a canonical form together with the conjugacy that produces it. Generators for the centraliser too, if you want it.
This will be possible in practice for very large examples (say $dN$ up to several million), but whether it is competitive with other methods will depend on the size of your typical example. If $N$ is small it will take milliseconds. What typical values of $N$ and $d$ are you interested in?
Instead of $S_N$, any permutation group which is the full automorphism group of some graph (in its action on vertices) can be handled too, by adding that graph as an extra layer. More general permutation groups are harder.
ADDED: Going back to $S_N$, I'll give a polynomial time algorithm, confusingly using both group and graph terminology all mixed up. First, if $\langle g_1,\ldots,g_d \rangle$ is intransitive (the graph is disconnected), canonically label each component separately and list them in lexicographic order. So now assume connectivity.
For each vertex $v$, we can make a unique labelling $\ell(v)$ of the graph by starting at $v$ and scanning the graph in a deterministic way. There are many possibilities; I'll describe a version of breadth-first search. You have a queue (first-in, first-out store) $Q$, initially containing only $v$. Repeatedly do this: remove the vertex at the head of the queue, say $x$, then push into $Q$ (at the tail) those of $x^{g_1},\ldots,x^{g_d}$ (in that order) which have never previously been put into $Q$. Since the graph is strongly connected (being a union of directed cycles), every vertex is put into $Q$ eventually. Stop when that has happened and define $\ell(v)$ to be the order in which vertices were put into $Q$. Relabelling the vertices in the order they are listed in $\ell(v)$ to get a labelled graph $G(v)$. (This corresponds to $(g_1^\gamma,\ldots,g_d^\gamma)$ where $\gamma$ is the permutation mapping the old labels to the new labels.)
Now you have $G(v)$ for each $v$. Choose the lexicographically smallest and that is your canonical labelling of the graph. Each scan takes $O(Nd)$ time and there are $N$ scans, so the total time is $O(N^2d)$.
Several observations will speed it in practice. (1) You can restrict the starting points of scans to vertices minimising some combinatorial invariant (for example the list of cycle lengths of $g_1,\ldots,g_d$ that involve the vertex). This might greatly reduce the typical number of scans. (2) As all scans except the first are being made, compare the graphs as you go. It might allow some scans to stop early. (3) If $G(v)$ and $G(w)$ are identical (not just isomorphic) you have found an element of the centraliser. You can use such elements to avoid some scans by proving their starting vertices are equivalent to those you already used. (4) Even though I talked about the graph, I wouldn't actually construct it but would work directly with lists of permutations.
The graph is actually a deterministic finite automaton (at most one edge of each colour leaves each vertex). There could be faster isomorphism algorithms out there for DFAs, though I'm dubious that anything would work faster in practice than a well-tuned implementation of the method I described.