Sylow's theorem in polynomial time (Q1063109)

The main theorem of the paper states that there are polynomial-time algorithms which, when given a subgroup G of the symmetric group \(S_ n\) and a prime p, solve the following problems: (i) given a p-subgroup P of G, find a Sylow p-subgroup of G containing P; and (ii) given Sylow p- subgroups \(P_ 1\), \(P_ 2\) of G, find \(g\in G\) conjugating \(P_ 1\) to \(P_ 2\). (G and its subgroups are specified in terms of generating permutations.) The result is mainly of theoretical interest as the running time of the algorithms is \(O(n^ 9)\). The proof makes use of the classification of finite simple groups. To solve the problems for a simple group \(G\leq S_ n\), \(| G| >n^ 8\), the ''natural'' permutation representation of G is constructed in polynomial time: if \(G\simeq A_ m\) then an m-element set and the action of G on it; if G is isomorphic to a classical group then a vector space V \((| V| <n^ 2)\), a form on V if G is symplectic, orthogonal, or unitary, and the action of G on the set of 1-spaces of V. Having a solution for simple groups, the algorithms consist of several reductional procedures. For solvable groups the algorithms can be simplified and extended to finding Hall \(\pi\)-subgroups and finding conjugating elements for Hall \(\pi\)- subgroups; these algorithms are given in the Appendix.