Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

# Simple Search

Query:
Enter a query and click »Search«...
Format:
Display: entries per page entries
Zbl 0573.20022
Kantor, William M.
Sylow's theorem in polynomial time.
(English)
[J] J. Comput. Syst. Sci. 30, 359-394 (1985). ISSN 0022-0000

The main theorem of the paper states that there are polynomial-time algorithms which, when given a subgroup G of the symmetric group $S\sb 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\sb 1$, $P\sb 2$ of G, find $g\in G$ conjugating $P\sb 1$ to $P\sb 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\sp 9)$. The proof makes use of the classification of finite simple groups. To solve the problems for a simple group $G\le S\sb n$, $\vert G\vert >n\sp 8$, the "natural" permutation representation of G is constructed in polynomial time: if $G\simeq A\sb 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 $(\vert V\vert <n\sp 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.
[P.P.Pálfy]
MSC 2000:
*20D20 Sylow subgroups of finite groups
20-04 Machine computation, programs (group theory)
68Q25 Analysis of algorithms and problem complexity
20D05 Classification of simple and nonsolvable finite groups

Keywords: polynomial-time algorithms; symmetric group; Sylow p-subgroups; classification of finite simple groups; permutation representation; solvable groups; Hall $\pi$ -subgroups

Highlights
Master Server