Computing normalizers in permutation groups (Q3344111)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3879126
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Computing normalizers in permutation groups |
scientific article; zbMATH DE number 3879126 |
Statements
Computing normalizers in permutation groups (English)
0 references
1983
0 references
backtrack algorithms
0 references
CAYLEY
0 references
base
0 references
strong generating set
0 references
Schreier method
0 references
normal closures
0 references
commutator
0 references
upper central series
0 references
lower central series
0 references
Fibonacci group
0 references
permutation groups
0 references
performance statistics
0 references
0.86061030626297
0 references
0.83796626329422
0 references
The three papers (and forthcoming ones, presently circulating as preprints and technical reports) describe the state of the art of methods for computing with large permutation and matrix groups as presently implemented in J. J. Cannon's CAYLEY system. These methods are based on the notion of base and strong generating set of a permutation group and the techniques for their generation and use introduced by \textit{C. C. Sims} in three fundamental papers [Comput. Probl. abstract Algebra, Proc. Conf. Oxford 1967, 169-183 (1970; Zbl 0215.10002); SIAM-AMS Proc. 4, 191-195 (1971; Zbl 0253.20001); Symbolic and algebraic manipulation, Proc. 2nd Symp., Los. Angeles 1971, 23-28 (1971; Zbl 0449.20002)]. The first of the papers briefly presents notions and mainly describes a modification of Sims' Schreier method that extends a base and strong generating set of a subgroup \(H<G\) to a base and strong generating set of \(<H,g>\) for some \(g\in G\). This is used in the construction of normal closures, commutator, lower and upper central series following in essence the procedure of an earlier paper of the second author [SIAM-AMS Proc. 4, 161-176 (1971; Zbl 0253.20027]. While most of the algorithms work very efficiently for fairly big groups (e.g. 91 sec on a CYBER 170/730 for the lower central series of a homomorphic image of order \(2^ 3\cdot 5^{18}\cdot 19\), degree 190, of the Fibonacci group F(2,9)) the algorithm for the upper central series supposes the conjugacy classes of elements of the group to be determined previously, which at the time of the writing of the paper was a bottleneck restricting its use in the present implementation to groups of order \(\leq 10^ 4\). As already described by Sims, backtrack search techniques in permutation groups are a central tool for many applications. They are used e.g. in the computation of centralizers in permutation groups and of automorphism groups of graphs, groups, codes, etc. The main part of the second paper is a detailed discussion of the backtrack method. Particular applications described are the computation: of the intersection of two subgroups, of a set-stabilizer, of the centralizer of an element and of the centralizer of a subgroup. Both, hints to implementation techniques and performance statistics are given. The third paper describes, after some repetition of background, as further application of the backtrack method algorithms for the computation of the normalizer of a subgroup of a permutation group and for deciding whether two subgroups of a permutation group are conjugate. Again performance statistics for the implementation of these as part of the CAYLEY system are given. (Reviewer's remark: It is regrettable that today's publishing policies prevented that these closely related papers were not published as just one.)
0 references