Efficient representation of perm groups (Q1180408): Difference between revisions

For computing a strong generator set of a permutation group (order \(n\)) given by a defining set of \(m\) generating permutations a version of an algorithm is developed and discussed extensively. It relies on producing a suitable generating transversal system which is of interest for its own sake as completely representing the group. The method does not increase the number of stored permutations which remain the \(n\) originally input (defining generators) and become each one provided with a fixed number (about 20, with length \(O(m)\) independent of \(n\)) of computed attributes -- mostly references --; it needs time proportional to \(O(n^ 5) + O(m n^ 2)\). The resulting transversal is a set of \(n\) disjunctive subsets of the input set with increasing size up to \(n\), but may still contain elements in a subset which are already a product out of the subset and the smaller ones (at most one factor out of each subset in sequence of increasing size) [counter-example by \(\pi=\sigma_{21}\cdot\sigma_{31}\); \(\sigma=\{\sigma_{21},\sigma_{31}\}\), contrary to the wording in section 1 of the paper]. On various assumptions better limits are derived. Subtle algorithmic improvements and suggestions for storing redundant information are elaborated (causing together with proof of correctness the bulk of the paper) and make tractable even very large complex groups. Some historical remarks (concerning priority) and a covering list of references including later publications with further improvements conclude the paper. Reviewer's remark: The author's proposed name shortening for the concept permutation into ``perm'' should not be adopted as should anyhow generally any tendency to cryptic language for concepts used by non- experts too; in this case raising even ambiguity with geology.