Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-24T13:19:07.994Z Has data issue: false hasContentIssue false
  • English
  • Français

Algorithmic Recognition of Group Actions on Orbitals

Published online by Cambridge University Press:  01 February 2010

Graham R. Sharp
Graham R. Sharp
Affiliation:
The Queen's College, Oxford, OX1 4AW, [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

An algorithm is given tjat recognises (in O(lN2 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 Γ(2) of ordered pairs of distinct elements of some G-set Γ (that us, Ωis isomorphic to an orbital of (G,Γ)). This may be adapted to list all essentially different such actions in O(lN4log N)time, where N is the sum of 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(lN3 log N) time) recognise when a transiteve group is the action on one orbit of the action of G on the set Γ{2} ofunorderd pairs of distinct elements of some G-set Γ. An algorithm for finding all essentially different such actions is also provided, running in O(lN4logN) 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 (G,Ω) is isomorphic to (G, Γ{2}) for some G-set Γ.

All the algorithms are practical; most have been implementd 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.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 2 , 1999 , pp. 1 - 27
Copyright
Copyright © London Mathematical Society 1999

References

1.Babai, L., Cooperman, G., Finkelstein, L. and Seress, Á., ‘Nearly linear time algorithms for permutation groups with a small base’, Proceedings 1991 ACM International Symposium on Symbolic and Algebraic Computation (1991) 200–209.CrossRefGoogle Scholar
2.Beals, R., ’Computing blocks of imprimitivity for small-base groups in nearly linear time’, Groups and Computation, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 11 (ed. Finkelstein, L. and Kantor, W. M., Amer. Math. Soc, Providence, RI, 1993) 17–26.CrossRefGoogle Scholar
3.Brown, Cynthia A., Finkelstein, Larry and Purdom, Paul W., ‘A new base change algorithm for permutation group ’, SIAM J. Comput. 18 (1989) 1037–1047.CrossRefGoogle Scholar
4.Butler, Gregory, Fundamental algorithms for permutation groups, Lecture Notes in Computer Science 559 (Springer-Verlag, 1991).CrossRefGoogle Scholar
5.Cooperman, Gene and Finkelstein, Larry, ‘Random algorithms for permutation groups’, CWI Quarterly 5 (1992) 107–125.Google Scholar
6.Schönert, Martin and Seress, Ákos, ‘Finding blocks of imprimitivity in small-base groups in nearly linear time’, Proceedings 1994 ACM-SIGSAM International Symposium on Symbolic and Algebraic Computation (1994) 154–157.Google Scholar
7.Schönert, Martin et al. , GAP — Groups, algorithms and programming (Lehrstuhl D für Mathematik, Rheinisch Westfalische Technische Hochschule, Aachen, Germany, 1994).Google Scholar
8.Sharp, Graham, ‘Algorithmic recognition of actions of 2-homogeneous groups on pairs’, LMSJ. Comput. Math. 1 (1998) 109–147 http://www.lms.ac.uk/jcm/1/lms97008/.Google Scholar
Supplementary material: File

JCM 2 Sharp Appendix A Part 1

Sharp Appendix A Part 1

Download JCM 2 Sharp Appendix A Part 1(File)
File 9.7 KB
Supplementary material: File

JCM 2 Sharp Appendix A Part 2

Sharp Appendix A Part 2

Download JCM 2 Sharp Appendix A Part 2(File)
File 28 KB
Supplementary material: File

JCM 2 Sharp Appendix A Part 3

Sharp Appendix A Part 3

Download JCM 2 Sharp Appendix A Part 3(File)
File 29.4 KB
Supplementary material: File

JCM 2 Sharp Appendix A Part 4

Sharp Appendix A Part 4

Download JCM 2 Sharp Appendix A Part 4(File)
File 19 KB
Supplementary material: File

JCM 2 Sharp Appendix A Part 5

Sharp Appendix A Part 5

Download JCM 2 Sharp Appendix A Part 5(File)
File 28.9 KB
Supplementary material: File

JCM 2 Sharp Appendix A Part 6

Sharp Appendix A Part 6

Download JCM 2 Sharp Appendix A Part 6(File)
File 9.8 KB