Fast recognition of alternating groups of unknown degree

JOURNAL OF ALGEBRA

卷:392

Article

Jambor, Sebastian¹  Leuner, Martin²  Niemeyer, Alice C.^3,4  Plesken, Wilhelm² 

[1] Univ Auckland, Dept Math, Auckland, New Zealand

[2] Rhein Westfal TH Aachen, Lehrstuhl Math B, D-52062 Aachen, Germany

[3] Rhein Westfal TH Aachen, Lehrstuhl Math D, D-52062 Aachen, Germany

[4] Univ Western Australia, Ctr Math Symmetry & Computat, Nedlands, WA 6009, Australia

关键词: Black-box group;    Constructive recognition;    Alternating group;    Probabilistic methods;    Proportions of elements;   

DOI  :  10.1016/j.jalgebra.2013.06.005

来源: Elsevier

【 摘 要 】

We present a constructive recognition algorithm to decide whether a given black-box group is isomorphic to an alternating or a symmetric group without prior knowledge of the degree. This eliminates the major gap in known algorithms, as they require the degree as additional input. Our methods are probabilistic and rely on results about proportions of elements with certain properties in alternating and symmetric groups. These results are of independent interest: for instance, we establish a lower bound for the proportion of involutions with small support. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free