Algorithmic recognition of group actions on orbitals

Abstract: An algorithm is given that recognises (in O(lN ² log N) time, where N is the size of the input and l the depth of a precalculated Schreier tree) when a transitive group (G, Ω) is the action on one orbit of the action of G on the set Γ⁽²⁾ of ordered pairs of distinct elements of some G-set (that is, Ω is isomorphic to an orbital of (G, Γ)). This may be adapted to list all essentially different such actions in O(lN ⁴ log N) time, where N is the sum of the sizes of the input and output. This will be a useful tool for reducing the degree of a permutation group as an aid to further study of the group. This algorithm is then extended to provide an algorithm that will (in O(lN ³ log N) time) recognise when a transitive group is the action on one orbit of the action of G on the set Γ^{2} of unordered pairs of distinct elements of some G-set Γ. An algorithm for finding all essentially different such actions is also provided, running in O(lN ⁴ log N) time. (Again, N is the sum of the input and output sizes.) It is also indicated how these results may be applied to the more general problem of recognising when an intransitive group Ω is isomorphic to (G, Γ ^{2}) for some G-set Γ. All the algorithms are practical; most have been implemented in GAP, and the code is made available with this paper. In some cases the algorithms are considerably more practical than their asymptotic analyses would suggest.