Efficient Computation in Finite Groups

有限群中的高效计算

• 批准号: 0097995
• 负责人: Akos Seress
• 金额: --
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-10-01 至 2004-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0097995&HistoricalAwards=false
• 关键词: Efficient; Computation; Finite; Groups

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.

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