Algorithmic Recognition of Group Actions on Orbitals

Let \(G\) be a (finite) permutation group acting transitively on a set \(\Omega\). The author is interested in the question of whether one can find another set \(\Gamma\) on which \(G\) acts, such that \(\Gamma\) is smaller than \(\Omega\) and so that the action of \(G\) on \(\Omega\) is equivalent to the action of \(G\) on one of the orbitals of \(\Gamma\) (that is, on an orbit consisting of distinct pairs \((\alpha,\beta)\) with \(\alpha,\beta\in\Gamma\)). The object is to simplify computations with \(G\) by reducing the degree of the permutation representation. As the author notes, his problem is equivalent to finding a subgroup \(J\) (equal to the stabilizer \(G_\gamma\) of some point \(\gamma\in\Gamma\)) and an element \(x\in G\) such that \(J\cap J^x\) is equal to the stabilizer \(G_\omega\) of some point \(\omega\in\Omega\). He describes an algorithm to compute all such pairs \((J,x)\) (up to a natural equivalence) starting from a set of permutations generating \(G\) and a precomputed Schreier tree of depth \(l\). The time complexity is \(O(lN^4\log N)\) where \(N\) represents the sum of the sizes of the input and the output. Enough details are included to enable the reader to implement the algorithm, and it is reported that such an implementation in GAP is quite practical for groups of degree up to \(10,000\). The author shows that a modified version of the algorithm can find the equivalent actions of \(G\) on sets of unordered pairs of points of a set \(\Gamma\), and he indicates how these results might be applied to recognize whether a given intransitive action of \(G\) is equivalent to the action of \(G\) on the set \(\Gamma^{\{2\}}\) of all unordered pairs of points from some set \(\Gamma\). See the author's earlier paper [LMS J. Comput. Math. 1, 109-147 (1998; Zbl 0920.20002)] for some related results.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Algorithmic Recognition of Group Actions on Orbitals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4252656)