Sylow Subgroups in Parallel

✍ Scribed by William M Kantor; Eugene M Luks; Peter D Mark

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 389 KB
• Volume: 31
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.0982

✦ Synopsis

Sylow subgroups are fundamental in the design of asymptotically efficient group-theoretic algorithms, just as they have been in the study of the structure of Ž . finite groups. We present efficient parallel NC algorithms for finding and conjugating Sylow subgroups of permutation groups, as well as for related problems. Polynomial-time solutions to these problems were obtained more than a dozen years ago, exploiting a well-developed polynomial-time library. We replace some of those highly sequential procedures with ones that work through a polylog-length normal series that is a by-product of NC membership-testing. As in previous investigations, we reduce to the base case of simple groups, and handle this by a case-by-case analysis that depends heavily upon the classification of finite simple groups.