Two-closure of odd permutation group in polynomial time (Q5937934)
From MaRDI portal
scientific article; zbMATH DE number 1621243
Language | Label | Description | Also known as |
---|---|---|---|
English | Two-closure of odd permutation group in polynomial time |
scientific article; zbMATH DE number 1621243 |
Statements
Two-closure of odd permutation group in polynomial time (English)
0 references
9 January 2002
0 references
The 2-closure of a permutation group is the largest subgroup of \(S_n\) that has the same orbits on pairs (\textit{H. Wielandt} [Lecture Notes, Ohio State University (1969)]). The authors give an algorithm to compute the 2-closure of an odd-order permutation group. By \textit{W. Feit, J. G. Thompson} [Pac. J. Math. 13, 775-1029 (1963; Zbl 0124.26402)] such a group is solvable. The main ingredient of the algorithm is proposition~3.1 which shows that taking the 2-closure ``commutes'' with forming direct products and wreath products. The algorithm consequentially uses the O'Nan-Scott structure theory (\textit{L. L. Scott} [Finite groups, Santa Cruz Conf. 1979, Proc. Symp. Pure Math. 37, 319-331 (1980; Zbl 0458.20039)]) and reduces recursively first to the case of a transitive group, then to a primitive (and thus affine) group and finally to an affine group with primitive linear part. Finally, following \textit{Á. Seress} [J. Lond. Math. Soc., II. Ser. 53, No. 2, 243-255 (1996; Zbl 0854.20004)], the authors show that a group remaining after these reductions is either 2-closed or consists of semilinear transformations of \(\text{GF}(p^d)\), for which the maximal 2-closed group is known. A theorem of \textit{L. Babai} and \textit{E. Luks} [Proc. 15th ACM Symp. Theory of Computing 1983, 171-183 (1983)] implies that all reduction steps can be performed in polynomial time.
0 references
2-closures
0 references
solvable groups
0 references
permutation groups
0 references
computations
0 references
algorithms
0 references