Computing Sylow subgroups in permutation groups (Q1369792)

This paper describes practical algorithms for the computation of Sylow subgroups of a permutation group \(G\) as well as for finding group elements that conjugate given Sylow subgroups into each other. For the first problem the following techniques have been in use: 1. Finding the Sylow subgroup in the centralizer of a \(p\)-element of the Sylow subgroups' centre. (\textit{G. Butler} and \textit{J. Cannon} [J. Symb. Comput. 12, No. 4/5, 443-457 (1991; Zbl 0787.20004)]). 2. Reduction to transitive groups with at most one minimal block system and (if imprimitive) the image of the block action being a \(p\)-group, as suggested by \textit{M. D. Atkinson} and \textit{P.M. Neumann} [Congr. Numerantium 79, 55-60 (1990; Zbl 0862.20002)]. 3. Iterative construction of the intersections of the Sylow subgroup with the groups in a composition series. A polynomial time albeit impractical algorithm for this has been designed by \textit{W. M. Kantor} [J. Algorithms 11, No. 4, 523-563 (1990; Zbl 0731.20005)]. The practicality of this has recently been enhanced by \textit{P. Morje} [Groups and computation II. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 257-272 (1997; Zbl 0878.20005)]. The authors improve on strategy 2 by considering further reductions. In the imprimitive case the Sylow subgroup of the kernel of the action on (maximal) blocks is extended by a Frattini-argument construction that requires finding a conjugating element for Sylow subgroups of the kernel. In the primitive case the O'Nan-Scott classification is invoked, referring for the analysis to the authors' preceding paper [J. Symb. Comput. 24, No. 3-4, 285-301 (1997)]. A resulting composed structure of \(G\) is used to reduce the computation to smaller constituents, in the almost simple case strategy 1 is maintained. For the conjugation of Sylow subgroups the same reductions are used, the case of a unique minimal block system and the non-affine primitive cases however is delegated to a backtrack search. The algorithms are given in explicit form that allows immediate implementation in systems like GAP or MAGMA. The authors also mention various implementational tricks that can be used to improve practical performance. The paper closes with example runtimes and a discussion of the algorithms' practical performance. As timings are only given for the authors' new algorithm, it is difficult to assess the improvement in performance. Unfortunately all the wreath product type examples given are full wreath products, which is untypical. The authors conclude that the practical bottleneck of their algorithm is the backtrack that can be invoked when searching a conjugating element; the worst case they list took over 40 hours for computing \(\text{Sylow}(S_{27}\wr S_9,7)\). They expect improvements due to better pruning in the backtrack search.