Efficient Computation in Finite Groups

提出的研究是在有限群的有效操作和估计其参数的领域。潜在的应用领域包括计算群论、图同构测试（与化学文档相关）、基于组的高效互连网络和基于组的密码学。我们的工作属于计算理论、群论、符号代数和组合学领域。基于我们之前在群算法复杂性理论方面的成果，我们提出了几个研究方向。本文的研究重点是设计和分析高阶变异群和大维矩阵群的有效算法。我们正在寻找既能满足快速渐近运行时间又能满足良好实用性能要求的算法。在置换组设置中，我们的近线性时间算法为相当广泛的算法任务实现了这一目标；现在我们要扩展这类算法。我们用GAP编程语言实现了大多数算法，它们作为GAP标准库包的一部分向公众开放。这些算法代表了人们期待已久的计算置换群论的理论和实践方法的结合。我们打算继续执行工作。我们的主要目标是为任意矩阵群的基本操作的第一个多项式时间算法。在特征为p的域上定义的矩阵群中，如果我们可以计算GF（pe）域上的离散对数，我们将给出一个计算阶数和复合级数的多项式时间算法。我们最近用于构造识别某些类有限单群的算法是这个计划的主要组成部分。最后，我们计划研究一些“纯”代数和组合问题，这些问题是由我们的算法研究激发的，或者通过与我们的算法结果相关的方法进步变得更容易理解。我们特别感兴趣的是置换群的基大小问题，群在置换域幂集上的作用问题，以及与Cayley图有关的问题：Cayley图的直径和具有顶点传递自同构群的非Cayley图的研究。小基数对于快速实现和改进算法的运行时间估计非常重要。Cayley图的直径估计与膨胀率密切相关，并由此涉及计算理论和概率论的许多基本问题。

The proposed research is in the area of efficient manipulation of finite groups and estimation of their parameters. Potential application areas include computational group theory, graph isomorphism testing (of relevance to chemical documentation), efficient interconnection networks based on groups, and group-based cryptography.Our work belongs to the areas of the Theory of Computing, Group Theory, Symbolic Algebra, and Combinatorics. Building on our previous results in the complexity theory of group algorithms, we propose to pursue several directions of research.The main focus is the design and analysis of efficient algorithms for high degree per-mutation groups and for large dimensional matrix groups. We are looking for algorithms which satisfy both the requirements of fast asymptotic running time and good practical performance. In the permutation group setting, our nearly linear time algorithms achieved this goal for a quite broad class of algorithmic tasks; now we would like to extend this class of algorithms. We implemented most of our algorithms in the GAP programming language and they are available for the public as part of the standard library package of GAP. These algorithms represent the long-awaited marriage of theoretical and practical approaches to computational permutation group theory. We intend to continue the implementation effort.Our major goal is the first polynomial-time algorithm for the basic manipulation of arbitrary matrix groups. In matrix groups defined over a field of characteristic p, we would like to give a polynomial-time algorithm computing the order and a composition series, provided that we can compute discrete logarithms in the fields GF(pe ). Our recent algorithms for the constructive recognition of certain classes of finite simple groups are a major ingredient in this plan.Finally, we plan to investigate some "pure" algebraic and combinatorial problems, which are motivated by our algorithmic investigations or became more accessible through the methodological advances achieved in connection with our algorithmic results. In particular, we are interested in base size problems for permutation groups, problems concerning the action of groups on the power set of the permutation domain, and problems related to Cayley graphs: the diameter of Cayley graphs and the investigation of non-Cayley graphs with vertex-transitive automorphism group. Small bases are important for fast implementations and for improving the running time estimates of algorithms. Estimates of diameters of Cayley graphs are closely related to the expansion rate and through this to a host of basic questions of the Theory of Computing and Probability Theory.