Efficient representation of perm groups
type: Item
instance of: scholarly article
title: Efficient representation of perm groups
zbMATH Open document ID: 0803.20005
DOI: 10.1007/BF01375471
author: Donald E. Knuth
published in: Combinatorica
publication date: 1992-06-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/math/9201304
review text: 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.
reviewed by: K. G. Brokate
Mathematics Subject Classification ID: 20B40
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 20-04
Mathematics Subject Classification ID: 20C40
Mathematics Subject Classification ID: 20F05
zbMATH DE Number: 25758
zbMATH Keywords: strong generator set
zbMATH Keywords: permutation group
zbMATH Keywords: generating permutations
zbMATH Keywords: algorithm
zbMATH Keywords: generating transversal system
MaRDI profile type: Publication
arXiv ID: math/9201304
cites work: On the length of subgroup chains in the symmetric group
cites work: The mathematics of perfect shuffles
cites work: Q3912839
cites work: The simple group of order 604,800
cites work: A compact representation for permutation groups
cites work: Q3895641
Recommended article: A compact representation for permutation groups
Recommended article: A method for building permutation representations of finitely presented groups
Recommended article: Space efficient representations of finite groups
Recommended article: Q4234297
Recommended article: On permutation representations of polyhedral groups
Recommended article: Effective Invariant Theory of Permutation Groups Using Representation Theory
Recommended article: The use of permutation representations in structural computations in large finite matrix groups
Recommended article: Q4247375
Recommended article: Q4264376
Recommended article: Constructing permutation representations for matrix groups
description: scientific article