Permutation group algorithms based on partitions. I: Theory and algorithms (Q1192233)

Algorithms for computing in permutation groups are developed. Given a property \(\mathcal P\) on a symmetric group (this is a boolean valued function on the group) two general types of problems are considered: Subgroup type problems, i.e. computation of \(G_{\mathcal P} = \{g \in G \mid {\mathcal P}(g)\}\), if this subset forms a subgroup, and coset type problems, i.e. computation of subgroups \(G_{{\mathcal P}_ L}\) and \(G_{{\mathcal P}_ R}\), such that \(G_{\mathcal P}\) forms a left coset of \(G_{{\mathcal P}_ R}\) and a right coset of \(G_{{\mathcal P}_ L}\), where \(\mathcal P\), \({\mathcal P}_ L\), and \({\mathcal P}_ R\) are given properties. Canonical representative type problems, where a canonical representative of a right coset \(G_{\mathcal P}x\) for a subgroup \(G_{\mathcal P}\) with a property \({\mathcal P}\) has to be computed, are planned for a subsequent paper of the author. First the general concepts of bases and strong generating sets are presented. Then ordered partitions of the sets on which the permutation groups operate are introduced. Stacks of partitions (which can also be considered as a kind of sequence) that are refined from one partion to the next by special refinement processes are discussed. Finally \(\mathcal R\)- bases of families of elementary \(\mathcal P\)-refinement processes are defined. Here \(\mathcal P\) is again a property as above and thus each \(\mathcal R\)-base depends on a specific property. Algorithms to solve subgroup and coset-type problems by use of \(\mathcal R\)- bases are developed. As an application \({\mathcal R}\)-bases for several standard permutation group problems are given. The algorithms perform a backtrack search on a special tree structure. Usually a leftmost-first or LMF traversal is used. The actual \(\mathcal R\)-base and thus the actual property \(\mathcal P\) is used only in a few subprocedures of the algorithms. This allows flexible implementations where one implementation of the algorithm can be used for a number of problems just by exchanging very few small parts. Examples of subgroup-type problems include set stabilizers, group intersections, normalizers, and centralizers of elements or groups. Similarly several examples of coset-type problems are discussed in detail, e.g. set images, coset intersections, conjugacy of elements or groups.