Generalised Sifting in Black-Box Groups

DOI10.1112/S1461157000000978MaRDI QIDQ3430812zbMATH OpenFDO

Authors Sophie Ambrose, Max Neunhöffer, Cheryl E. Praeger, Csaba Schneider

Publication date 4 April 2007

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0501346, http://www.lms.ac.uk/jcm/8/lms2005-005/

zbMATH Keywords

black-box groupscomputational procedures for groupsGAPMonte Carlo algorithmssporadic simple groupssubset chains

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to group theory (20-04) Simple groups: sporadic groups (20D08) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Abstract: We present a generalisation of the sifting procedure introduced originally by Sims for computation with finite permutation groups, and now used for many computational procedures for groups, such as membership testing and finding group orders. Our procedure is a Monte Carlo algorithm, and is presented and analysed in the context of black-box groups. It is based on a chain of subsets instead of a subgroup chain. Two general versions of the procedure are worked out in detail, and applications are given for membership tests for several of the sporadic simple groups. Our major objective was that the procedures could be proved to be Monte Carlo algorithms, and their costs computed. In addition we explicitly determined suitable subset chains for six of the sporadic groups, and we implemented the algorithms involving these chains in the {sf GAP} computational algebra system. It turns out that sample implementations perform well in practice. The implementations will be made available publicly in the form of a {sf GAP} package.

Recommendations

• Constructive membership testing in black-box classical groups.
• scientific article; zbMATH DE number 1302464
• scientific article; zbMATH DE number 2038701
• scientific article; zbMATH DE number 4072209
• Discrete evidence based on grouping optimization
• Probabilistic analysis of a grouping algorithm
• Black box scatter search for general classes of binary optimization problems
• Enhancing Target Group Selection Using Belief Functions

Cites work

• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture
• Permutations with Restricted Cycle Structure and an Algorithmic Application
• Standard generators for sporadic simple groups
• The Magma algebra system. I: The user language

Describes a project that uses

Uses Software

• Magma
• GAP

This page was built for publication: Generalised Sifting in Black-Box Groups

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