Sylow's theorem in polynomial time

摘要

Given a set Γ of permutations of an n-set, let G be the group of permutations generated by Γ. If p is a prime, a Sylow p-subgroup of G is a subgroup whose order is the largest power of p dividing |G|. For more than 100 years it has been known that a Sylow p-subgroup exists, and that for any two Sylow p-subgroups P1, P2 of G there is an element gϵG such that P2 = g−1P1 g. We present polynomial-time algorithms that find (generators for) a Sylow p-subgroup of G, and that find gϵG such that P2 = g−1P1 g whenever (generators for) two Sylow p-subgroups P1, P2 are given. These algorithms involve the classification of all finite simple groups.