zbMATH — the first resource for mathematics

Reconstructing simple group actions. (English) Zbl 0939.20002
Cossey, John (ed.) et al., Geometric group theory down under. Proceedings of a special year in geometric group theory, Canberra, Australia, July 14-19, 1996. Berlin: de Gruyter. 147-180 (1999).
For calculations with permutation groups it is desirable to proceed to an isomorphic group of smaller degree, for example by acting on blocks. However even for simple groups the degree of a primitive action is often far from optimal.
The authors present methods to construct a “natural” small-degree primitive action of a primitive simple group \(G\leq S_n\). Here “natural” means an action on \(r\)-sets if \(G\cong A_r\) and an action on 1-spaces for a classical group.
The global assumption \(|G|>n^5\) excludes all exceptional Lie type groups, sporadic groups (except \(M_{23}\) and \(M_{24}\) which are excluded separately) and “unfamiliar” primitive actions of the remaining groups.
In contrast to earlier results [W. M. Kantor, J. Algorithms 6, 478-514 (1985; Zbl 0604.20001)] the method used does not reconstruct a matrix action but proceeds directly from one permutation action to another, never requiring intermediate permutation actions of degree much larger than the initial degree \(n\). The authors also discuss how to recover not only the (projective) action but also the underlying vector space structure.
All subtasks required are “efficient” not only in practice, but also in most theoretical models. (The only exception is the action on the cosets of a subgroup which cannot be done (yet) in “nearly linear” time).
For the entire collection see [Zbl 0910.00040].
20B40 Computational methods (permutation groups) (MSC2010)
20D06 Simple groups: alternating groups and groups of Lie type
51N30 Geometry of classical groups
20G40 Linear algebraic groups over finite fields
20B15 Primitive groups