A black-box group algorithm for recognizing finite symmetric and alternating groups, I

Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, Ákos Seress

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

We present a Las Vegas algorithm which, for a given black-box group known to be isomorphic to a symmetric or alternating group, produces an explicit isomorphism with the standard permutation representation of the group. This algorithm has applications in computations with matrix groups and permutation groups. In this paper, we handle the case when the degree n of the standard permutation representation is part of the input. In a sequel, we shall treat the case when the value of n is not known in advance. As an important ingredient in the theoretical basis for the algorithm, we prove the following result about the orders of elements of Sn: the conditional probability that a random element σ ∈ Sn is an n-cycle, given that σn = 1, is at least 1/10.

Original languageEnglish (US)
Pages (from-to)2097-2113
Number of pages17
JournalTransactions of the American Mathematical Society
Volume355
Issue number5
DOIs
StatePublished - May 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Keywords

  • Black-box groups
  • Constructive recognition
  • Probabilistic method
  • Symmetric groups

Fingerprint

Dive into the research topics of 'A black-box group algorithm for recognizing finite symmetric and alternating groups, I'. Together they form a unique fingerprint.

Cite this