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].

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].

Reviewer: Alexander Hulpke (Columbus)

##### MSC:

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 |