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

Cited in: Zbl 1011.20001 Zbl 0694.20005 Zbl 0642.20019

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]