Polynomial-time theory of matrix groups
Polynomial-time theory of matrix groups
复制标题
DOI：
10.1145/1536414.1536425
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
L. Babai;R. Beals;Á. Seress
中科院分区：
文献类型：
--
作者：
L. Babai;R. Beals;Á. Seress
我们考虑矩阵群，指定的一个列表的生成元，在有限域上。关于这类群体的两个最基本的问题是群体的成员资格和群体的秩序。即使在阿贝尔群的情况下，也不知道如何在不解决困难的数论问题（因子分解和离散对数）的情况下回答这些问题;事实上，1 × 1矩阵情况下的构造性成员测试正是离散对数问题。因此，合理的问题是，这些问题是否可以使用数论预言在随机多项式时间内解决。建立在25年的工作，包括显着的最近几组作者的发展，我们现在能够确定一个矩阵组的顺序在一个有限域的奇特性，并执行建设性的成员资格测试在这样的群体，在随机多项式时间，使用神谕因子分解和离散日志。这一结果的新成分之一如下。一个群称为半单群，如果它没有阿贝尔正规子群。对于有限域上的矩阵群，我们证明了最大半单商的阶可以在随机多项式时间内确定（不需要数论预言，也不需要奇偶性限制）。作为一个副产品，我们得到一个自然的问题，属于BPP和不知道属于RP或CORP。没有这样的问题以外的矩阵群的区域似乎是已知的。问题是上面的判定版本：给定有限域上的非奇异d × d矩阵列表A和整数N，由A生成的群是否有阶> N的半单商？我们也取得了进展，在该地区的建设性承认简单的群体，与推论，为一大类矩阵群，我们的算法成为拉斯维加斯。
We consider matrix groups, specified by a list of generators, over finite fields. The two most basic questions about such groups are membership in and the order of the group. Even in the case of abelian groups it is not known how to answer these questions without solving hard number theoretic problems (factoring and discrete log); in fact, constructive membership testing in the case of 1 × 1 matrices is precisely the discrete log problem. So the reasonable question is whether these problems are solvable in randomized polynomial time using number theory oracles. Building on 25 years of work, including remarkable recent developments by several groups of authors, we are now able to determine the order of a matrix group over a finite field of odd characteristic, and to perform constructive membership testing in such groups, in randomized polynomial time, using oracles for factoring and discrete log. One of the new ingredients of this result is the following. A group is called semisimple if it has no abelian normal subgroups. For matrix groups over finite fields, we show that the order of the largest semisimple quotient can be determined in randomized polynomial time (no number theory oracles required and no restriction on parity). As a by-product, we obtain a natural problem that belongs to BPP and is not known to belong either to RP or to coRP. No such problem outside the area of matrix groups appears to be known. The problem is the decision version of the above: Given a list A of nonsingular d × d matrices over a finite field and an integer N, does the group generated by A have a semisimple quotient of order > N? We also make progress in the area of constructive recognition of simple groups, with the corollary that for a large class of matrix groups, our algorithms become Las Vegas.