The computation of normalizers in permutation groups (Q1192230): Difference between revisions

The author describes an algorithm for computing the normalizer of a subgroup \(H\) of a permutation group \(G\). The algorithm consists of a backtrack search procedure on a tree structure, which is given by the cosets of the groups in a stabilizer chain for a base of \(G\) (endpoints correspond to the elements of \(G\)). At a specific node, the algorithm tests whether any element belonging to the corresponding coset might normalize \(H\). For this purpose it is checked whether such an element respects the orbits of \(H\) and if it could possibly induce an automorphism of \(H\) by conjugation. The paper gives the details for an implementation of the algorithm and mentions some applications for computing automorphism groups and Sylow subgroups of permutation groups. The author compares the performance of his algorithms with those of \textit{G. Butler} [J. Algorithms 4, 163-175 (1983; Zbl 0552.20004)] and \textit{G. Butler} and \textit{J. Cannon} [J. Symb. Comput. 8, 241-252 (1989; Zbl 0677.20001)].