A black-box group algorithm for recognizing finite symmetric and alternating groups, I
A black-box group algorithm for recognizing finite symmetric and alternating groups, I
复制标题
用于识别有限对称和交替群的黑盒群算法，I
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
´Akos Seress
中科院分区：
文献类型：
--
作者：
R. Beals;C. Leedham;Alice C. Niemeyer;And CHERYL E. PRAEGER;´Akos Seress
我们提出了一个拉斯维加斯算法，对于一个给定的黑盒组已知是同构的对称或交替组，产生一个明确的同构与标准的置换表示的组。该算法在矩阵群和置换群的计算中有应用。在本文中，我们处理的情况下，当度n的标准置换表示是输入的一部分。接下来，我们将讨论n的值事先未知的情况。作为算法理论基础的一个重要组成部分，我们证明了Sn中元素阶的如下结果：当σ n = 1时，随机元素σ ∈ Sn是n-圈的条件概率至少为1/10.
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 S n : the conditional probability that a random element σ ∈ S n is an n-cycle, given that σ n = 1, is at least 1/10.