Fast computation of the centralizer of a permutation group in the symmetric group (Q6149148): Difference between revisions

Let \(G \leq \mathrm{Sym}(\Omega)\) be a permutation group acting on a set \(\Omega\) and let \(X\) be a generating set for \(G\). Best known algorithms for computing the \(C_{\mathrm{Sym}(\Omega)}\) are based on the same approach that involves solving the following two fundamental problems: \begin{itemize} \item[(1)] given a \(G\)-orbit \(\Delta\) of size \(n\), compute the centralizer of the restriction of \(G\) to \(\Delta\) in \(\mathrm{Sym}(\Delta)\); \item[(2)] given two \(G\)-orbits \(\Delta\) and \(\Gamma\), each of size \(n\), find an equivalence between the action of \(G\) restricted to \(\Delta\) and the action of \(G\) restricted to \(\Gamma\) when one exists. \end{itemize} Solutions to both problems are known that take \(O(|X|n^{2})\) time. In particular \textit{M. Fontet} [Bull. Soc. Math. Fr., Suppl., Mém. 49--50 (Conf. Limoges 1975), 53--63 (1977; Zbl 0376.20001)] developed an algorithm that computes \(C_{\mathrm{Sym}(\Omega)}(G)\) in \(O (|X| \cdot |\Omega|^{2})\) worst-case time. In the paper under review, the author first solves each fundamental problem in \(O(\delta n +|X| n \log n)\) time, where \(\delta\) is the depth of the breadth-first-search Schreier tree for \(X\) rooted at some fixed vertex. Moreover, if \(\lceil 20 \log n\rceil\) uniformly distributed random elements of \(G\) are given in advance, the solution has, with probability at least \(1-1/n\), a running time of \(O(n \log^{2} n + |X| n \log n)\). With experimental evaluations, the author shows that his algorithm is substantially faster than previously known algorithms.