1 Introduction
Let be permutations in the symmetric group on letters , and let be a word over the alphabet . Such a word, often referred to as the permutation word, uniquely determines the product
We define the computation of as the permutationword multiplication problem.
This problem is quite fundamental as it is encountered in many algorithms in computational group theory dealing with permutation groups represented by a set of its generators [5]. In our context, is an element of the permutation group generated by . It is obvious that can be computed in time, which brings us to the following question:
Given a finite sequence of permutations in and a permutation word over , can we compute in time less than the product ?
Note that if all permutations in are pairwise distinct, then the product cannot be evaluated in less than time since each permutation has to be at least scanned. But can we do better if we assume that is relatively small compared to ? This is not an unreasonable assumption since in practice most interesting groups can be generated by a few generators (rarely more than ten, [9]); for instance, all finite simple groups can be generated by just two generators.
In this paper we show that the permutationword multiplication problem can be solved in time as soon as . More precisely, the following holds.
Theorem 1.1.
Given permutations of and a word over , the product can be computed in time and space, where .
At this point we would like to emphasize that multiplication of permutations as far as we can tell went unquestioned so far, which is surprising enough since it appears to be such a basic problem.
A more direct motivation for considering the permutationword multiplication problem stems from the transitive simultaneous conjugacy problem: given two ordered tuples and of elements from that generate transitive subgroups, does there exists an element in such that holds for all indices ?
This problem arises naturally in various fields of mathematics and computer science, for instance in the theory of maps on surfaces, theory of covering graphs, computational group theory, representation theory and interconnection networks – most notably when decideing whether two objects from a given class of objects are isomorphic (which usually means structural equivalence). We refer the reader to relevant literature for more information on these topics [7, 8, 9, 10, 11].
In the context of finding centralizers, Fontet [3] gave, in 1977, an time algorithm for solving the transitive simultaneous conjugacy problem by translating it into a special case of a coloured multidigraph isomorphism problem. His solution works also for the intransitive case. Fontet’s algorithm was independently discovered by Hoffmann [4] in 1982. In studying permutation networks, Sridhar [10] in 1989 presented an time algorithm. In his solution he applied techniques used by the Hopcroft and Tarjan for testing isomorphism of planar 3connected graphs [6]. Unfortunately, as we have recently discovered, Sridhar’s algorithm does not work correctly on all input data. For instance, this happens when all permutations are semiregular but the group they generate is not regular. The question that arises naturally is therefore the following:
Given two ordered tuples and of elements from that generate transitive subgroups, can we find in time less than an element such that holds for all indices ?
Using Theorem 1.1 as the main ingredient we have the following result.
Theorem 1.2.
Let and be ordered tuples of permutations that generate transitive subgroups of the symmetric group , and let . Then we can test whether one tuple is simultaneously conjugate to another in time, using space.
In the rest of paper we present first the necessary notation. The following two sections give the solutions to the problems presented above including proofs of the theorems. We wrap up with a brief conclusion and some open problems.
2 Preliminaries
The aim of this section is to establish some notation and terminology used in this paper. For the concepts not defined here see [2]. The notations are quite graph centred since in our solution to the transitive simultaneous conjugacy problem we use graph based techniques.
Let be a tuple of permutation in the symmetric group . The permutation graph of is a pair , where is the set of vertices, and
is the set of ordered pairs
, , called arcs. The degree of is . An arc has its initial vertex , terminal vertex , and colour . The vertices and are endvertices of .A walk from a vertex to a vertex in a permutation graph is an alternating sequence of vertices and arcs from such that for each , the vertices and are the endvertices of the arc . In particular, if and for each , then is a directed walk. The vertices and are called the initial vertex and the terminal vertex of , respectively. If , then the walk is closed walk, and is open otherwise. A path is a walk whose vertices (and hence arcs) are all pairwise distinct. Note that is strongly connected (in the sense that any vertex is reachable form any other vertex by traversing a directed path) if and only if the tuple generates a transitive subgroup of . A subgraph of consists of a subset and a subset such that every arc in has both endvertices in . A walk in a subgraph of is a walk in consisting only of arcs from . A subgraph of is a tree if for any two vertices and in , there is a unique path from to in . If , then is a spanning tree of .
A colourisomorphism between two permutation graphs and is a pair of bijections, where and such that , and for any arc .
A partition of a set is a set of nonempty pairwise disjoint subsets of whose union is . Each set is called a cell of the partition. A partition is trivial if it has only one cell, .
Let be the set of all strongly connected permutation graphs each of degree with vertices, and let be the set of all rooted graphs from . Given a set of labels, a vertex invariant is a function such that whenever there exists a colourisomorphism mapping onto , then
Since a vertex invariant assigns a label to every vertex of a permutation graph , it induces a partition on the vertices such that for any two vertices , and are in the same cell if and only if they have the same labels . Two partitions and are compatible if , and the cells of can be reenumerated such that for all we have that and for all , . The following results follow directly from definitions.
Lemma 2.1.
Let be a vertex invariant, and let , then:

If and are colourisomorphic, then the partitions and are compatible.

Let and be compatible partitions, and let . Then and are not colourisomorphic if and only if there is no colourisomorphism of onto mapping to some vertex in .
An alphabet is a finite set of characters. A word (or a string) over the alphabet is a finite sequence of characters from . The length of a word is the number of characters in . The unique word of length 0 is the empty word. We denote the set of all words of length over the alphabet by . We write for the concatenation of words and . For a word and a nonnegative integer we define for , and otherwise .
Let be a permutation graph of degree and let be an alphabet. A walk in defines the word over , where: (i) ; and (ii) if and , then , and otherwise.
Conversely, a word over and a vertex together define the walk in starting with such that . Finally, for a word over we define the permutation .
Let be a set of labels and let be a word over . The function defined by
is vertex invariant. In grouptheoretical terms, vertices labelled by C represent the set of fixed points of the permutation , while vertices labelled by O represent its support set. For a set , we let
For , we have for all , and therefore and .
Let and be two permutation graphs, and let and be walks in and , respectively. We say that is the walk corresponding to walk if . In particular, an arc corresponds to an arc if . Further, a word over is a distinguishing word for vertices and if . In this case, and are said to be distinguishable.
3 Permutationword multiplication
Our approach for solving the permutationword multiplication problem is similar to fast computation of large positive integer powers by repeated squaring. For technical reason we describe a procedure how to make always of even length. Namely, if
is odd we expand it by a single character
making its length even. Moreover, defining to be the identity permutation of , the new word defines the same product .Let , , , , and . In case is odd, we use the above technical procedure making its length even. In the next step we scan through the word , replacing a pair by , . The obtained word is actually built over , where . Clearly, and . So assuming that the set of all products of pairs of permutations in is precomputed and the permutation is known, the time of straightforward evaluation of is reduced to half.
The above reduction step can be repeated. If before the th iteration the length is odd, we apply the above technical procedure making even. Then, after the th iteration we have the set and the word
where for , and is over the alphabet . We leave to the reader to check that . Again, with and the permutation being precomputed, a straightforward evaluation of the product takes .
At this point we truncate the iteration similarly as it is truncated recursion in [1]. Namely, since , the construction of from takes . Consequently, we iterate the described process for times until
(1) 
Observe that inequality (1) has no closed form solution for . However, by rewriting it as , we see that . Let us thus take an arbitrary constant , and define to be the integer satisfying
(2) 
Therefore, after iterations the length of the word becomes bounded from above by
Based on this analysis, we give a formal description of this reduction in the algorithm WordReduction, which guarantees the size of the word to be and simultaneously increases the set of permutations.
Lemma 3.1.
Given a set of permutations of , a word over , and a constant , the algorithm WordReduction, , takes time and space.
Proof.
We may assume that as otherwise we are done. After taking another logarithm in (2) we get that the for loop is executed times. Lines 68 take time. Since , lines 8 and 9 take time. Obviously, the construction of from in line 10 takes time, while line 11 takes time. So, we can express the total time of the algorithm as being bounded from above by
The last summation can be estimated as
Thus, the algorithm takes time. Moreover, the space complexity is proportional to the sum of the length of the input word and the size of the set . However, has permutations of length , and the result follows. ∎
Once the length of the word is guaranteed to be , we evaluate its corresponding product on points in a straightforward manner.
Lemma 3.2.
Let be permutations of , let be a word over , and let . Then we can evaluate the product on points in time.
Proof.
The evaluation is done in two phases. First, by Lemma 3.1 we can guarantee in time that the length of the word is . In the second phase we evaluate the obtained word in time . ∎
4 Simultaneous conjugation
Let and be strongly connected permutation graphs on vertices, each of degree . In this section, we show that we can decide whether and are colourisomorphic by an algorithm running in time and space, where . We first prove the following theorem.
Theorem 4.1.
Let and be strongly connected permutation graphs on vertices and of degree , and let and . Then there exists a colourisomorphism of onto mapping onto if and only if and are indistinguishable.
Proof.
If there exists a colourisomorphism of onto mapping onto , then any closed walk is mapped to a closed walk and hence and are indistinguishable.
Let and be indistinguishable vertices of and , respectively. Construct an isomorphism as follows. Take a spanning tree of rooted at . For a vertex , let be a unique path in from to , and let be the corresponding path in starting with . For each vertex , map the arc to , the vertex to , and the vertex to . The subgraph of with the set of vertices and with the set of arcs must be a spanning tree of rooted at , for otherwise there exists an open walk starting with such that the corresponding walk starting with is closed. But this is not possible, since and are indistinguishable. It remains to define the mapping on the cotree arcs. Let be a fixed cotree arc of , and suppose that is mapped to . Then, map to the corresponding arc in . If has already been mapped to some vertex different than , then there exists a closed walk starting with such that the corresponding walk starting with is open. But this is not possible. Repeating the process at the remaining cotree arcs yields the desired isomorphism. ∎
From Theorem 4.1 we derive necessary and sufficient condition for and to be colourisomorphic. Since for an arbitrary vertex there are possible candidates in that might be indistinguishable from , we need to check, for each vertex , whether and are indistinguishable. Algorithm Indistinguishable, based on Theorem 4.1 and breadthfirst search, does precisely that – with an addition of returning the empty word whenever and are indistinguishable, and a distinguishing word for and otherwise.
Proposition 4.2.
Given strongly connected permutation graphs and each of degree on vertices and , , the algorithm Indistinguishable correctly test whether and are indistinguishable in time and space.
Proof.
The correctness of the algorithm follows directly from remarks above and Theorem 4.1.
The closed walk in lines 13 or 18 is constructed at most once, and this can be done in time using space. Finally, since the algorithm is based on breadthfirst search its total time is , and the space used is also . ∎
If are indistinguishable we have found a colourisomorphism. Otherwise, we get a distinguishable word such that the vertex invariant induces nontrivial partitions
If , then the partitions and are not compatible. Hence and are not colourisomorphic by (i) of Lemma 2.1. Consequently, no indistinguishable vertices exist.
Otherwise, by (ii) of Lemma 2.1 we can search for indistinguishable vertices either between and or between and . We reapply algorithm Indistinguishable on the smaller sets. This reduces the number of possible candidates from to at most .
Algorithm ColourIsomorphic formally describes this process. In the th iteration it uses the function Partition to split the sets and with respect to the word . This is done by evaluating the product on and as described in Section 3.
Theorem 4.3.
Given strongly connected permutation graphs and each of degree on vertices, the algorithm ColourIsomorphic correctly test whether and are colourisomorphic in time and space, were .
Proof.
We first show the following loop invariant.
At the start of each iteration of the repeat loop of lines 213 holds:

,

and are cells of the partitions of and , respectively, where both partitions are induced by a vertex invariant such that vertices in and vertices in have the same labels.
Prior to the first iteration, , . Thus, the first part of the invariant holds. By taking , the partitions and are trivial, and so and vertices in and vertices in have the same labels. Thus, the property (ii) holds as well.
To see that each iteration maintains the loop invariant, we assume that before the iteration , the properties (i) and (ii) hold and that at the end of iteration the condition in line 13 is false. Consequently, and . Without loss of generality, we assume that and .
First, since is a distinguishable word for some and some , at least one of and is nonempty. But then, since , both and are nonempty. Moreover, since , and since , it follows that , and the first part of the invariant holds.
To prove (ii), let
Comments
There are no comments yet.