14
$\begingroup$

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:

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

  2. This algorithm is needed to speed up an algorithm for the SCP in Artin's braid group $B_N$.

  3. The answers for a related question do not seem to help here.

$\endgroup$
3
  • 1
    $\begingroup$ I like your canonical form and Brendan's answer below. I just wanted to comment that Burnside's lemma says there are \begin{equation} \frac{1}{|S_N|} \sum_{\alpha \in S_N} |\text{centralizer}(\alpha)|^d = \frac{1}{N!} \sum_{\alpha} \left( \sum_{\chi} \chi^2(\alpha) \right)^d \end{equation} different orbits of $G^d$ under simultaneous conjugation. So you can compute the corresponding count of types rather easily (but it involves the character table). $\endgroup$ Apr 4, 2014 at 20:28
  • $\begingroup$ Sorry. I just noticed that my comment about the count of orbits is directly addressed (for $d=2$, anyway) in a "Related" MO problem to the left: mathoverflow.net/questions/41337/… $\endgroup$ Apr 4, 2014 at 22:09
  • $\begingroup$ I posted some related computations in arxiv.org/abs/1407.5284 $\endgroup$ Sep 14, 2015 at 10:53

2 Answers 2

15
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks Brendan. But don't you think there should be a (small degree, in $dN$, say) polynomial time algorithm for this problem? Also, unfortunately, this is supposed to be implemented in Magma, so I cannot use any available software. Perhaps your algorithm could be stated succinctly in this specific case. $\endgroup$ Apr 6, 2014 at 10:15
  • $\begingroup$ @Boaz Tsaban: In Magma you can use the graph isomorphism routines already there. But you are right, there is a polynomial time algorithm for $S_N$. I think $O(N^2d)$. I'll add it to my answer later today. $\endgroup$ Apr 6, 2014 at 11:58
  • $\begingroup$ Looks awesome. Could you explain what is meant by taking the lex-smallest labeled graph? The way I see it, your algorithm returns, for each $v$, a permutation of $1,\dots,N$ that you can move by conjugation to the identity permutation. $\endgroup$ Apr 6, 2014 at 20:54
  • 1
    $\begingroup$ Update: I have implemented this algorithm and it works. $\endgroup$ Apr 10, 2014 at 18:33
  • 2
    $\begingroup$ I worked out the connection of your polynomial time algorithm to isomorphism algorithms for DFAs, see: A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata. Summary: Your algorithm (if slightly generalized) can handle exactly the reversible DFAs, and isomorphism of more general DFAs (without the restriction that any state is reachable from the initial state) is GI complete. $\endgroup$ Nov 16, 2015 at 7:59
3
$\begingroup$

I used the same algorithm in several papers. I was unable to find older references, but given how simple the algorithm is, I'm sure they must exist.

arXiv:1604.08158 (section 4.3, implementation of UniqueRepresentative available at [1] in the references)

http://diginole.lib.fsu.edu/islandora/object/fsu%3A254453 (page 37)

arXiv:1305.7218 (section 4.3)

arXiv:1212.3803 (mentioned on page 12, implementation available at [23] in the references)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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