Efficient Computation in Finite Groups

建议的研究是在该地区的有效操纵有限群和估计其参数。潜在的应用领域包括计算群论，图同构测试（与化学文献相关），基于群的高效互连网络和基于群的密码学。我们的工作属于计算理论，群论，符号代数和组合数学领域。基于我们以前在群算法复杂性理论方面的研究成果，我们提出了几个研究方向，主要集中在设计和分析高次置换群和高维矩阵群的有效算法。我们正在寻找既满足快速渐近运行时间和良好的实际性能的要求的算法。在置换群设置中，我们的近线性时间算法实现了这一目标，为一个相当广泛的算法任务类，现在我们想扩展这类算法。我们在差距编程语言中实现了我们的大部分算法，它们作为GAP标准库包的一部分可供公众使用。这些算法代表了期待已久的婚姻的理论和实践方法计算置换群理论。我们打算继续努力实现。我们的主要目标是第一个多项式时间算法的基本操作的任意矩阵群。在定义在特征为p的域上的矩阵群中，我们想给出一个计算阶和合成级数的多项式时间算法，只要我们能计算域GF（pe）中的离散矩阵。我们最近的算法的建设性认识某些类的有限简单的群体是一个主要成分在这个planne.Finally，我们计划调查一些“纯”代数和组合的问题，这是出于我们的算法调查或变得更容易通过与我们的算法结果取得的方法进步。特别是，我们感兴趣的置换群的基础大小问题，有关的问题的行动组的权力集的置换域，和问题有关的凯莱图：直径的凯莱图和调查的非凯莱图与顶点传递自同构群。小基数对于快速实现和改进算法的运行时间估计是重要的。凯莱图直径的估计与膨胀率密切相关，并通过膨胀率与计算理论和概率论的许多基本问题密切相关。

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.