Groups, Algorithms and Geometries

群、算法和几何

• 批准号: 0753640
• 负责人: William Kantor
• 金额: $ 14.7万
• 依托单位: University of Oregon Eugene
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0753640&HistoricalAwards=false
• 关键词: Groups; Algorithms; Geometries

Algorithmic and asymptotic properties of finite permutation groups and matrix groups will continue to be studied, using properties of all finite simple groups. Alternating and classical composition factors are reasonably well understood. Exceptional finite simple groups of Lie type have been a major stumbling block for research in this area. Crucial components of this proposal are algorithms, efficient both in theory and practice, for constructive recognition as well as for standard Sylow problems for these groups. These algorithms will use standard structural properties of these groups, as well as probabilistic estimates for generating important subgroups. This should produce a polynomial-time algorithm for the basic manipulation of arbitrary large-dimensional matrix groups, assuming that discrete logarithms in suitable fields can be computed quickly. Some of these algorithms depend on recent very efficient presentations for finite simple groups. Others depend on geometric methods. Additional geometric projects will be continued, including asymptotic investigations into planes, designs and codes, with special emphases on nonassociative division algebras and their planes. The field of group theory is the mathematical theory of symmetry and interacts with many other disciplines, for example computer science, physics and chemistry outside of mathematics, number theory, topology and geometry inside mathematics. The fundamental building blocks of finite groups are the finite simple groups. One of the outstanding mathematical results in recent decades is the classification of the finite simple groups. A major portion of this research proposal is aimed at using properties of these simple groups in the computer-assisted study of arbitrary finite groups. Group-theoretic algorithms are fundamental to the computer group theory packages GAP and Magma, which are widely used in group theory and combinatorics. Many aspects of the PI's research program have led or will lead to significant improvements in this widely-available software. Another portion of this proposal concerns finite geometries, including designs and codes. Designs first arose in the design of statistical experiments, and have many applications in other disciplines, including optics, coding theory and computer algorithms. Error-correcting codes are a fundamental engineering application of "pure" mathematics.

将利用所有有限单群的性质继续研究有限置换群和矩阵群的算法和渐近性质。 交替和经典的构图因素是相当容易理解的。 李类型的特殊有限单群一直是该领域研究的主要障碍。该提案的关键组成部分是在理论和实践上都有效的算法，用于建设性识别以及这些群体的标准 Sylow 问题。这些算法将使用这些组的标准结构属性，以及生成重要子组的概率估计。 假设可以快速计算合适域中的离散对数，这应该产生用于任意大维矩阵组的基本操作的多项式时间算法。 其中一些算法依赖于最近对有限简单群的非常有效的表示。 其他则取决于几何方法。其他几何项目将继续进行，包括对平面、设计和代码的渐近研究，特别强调非结合除代数及其平面。 群论领域是数学对称理论，与许多其他学科相互作用，例如数学之外的计算机科学、物理和化学，数学内部的数论、拓扑和几何。有限群的基本构建块是有限单群。近几十年来杰出的数学成果之一是有限单群的分类。该研究提案的主要部分旨在利用这些简单群的性质对任意有限群进行计算机辅助研究。群论算法是计算机群论软件包 GAP 和 Magma 的基础，广泛应用于群论和组合学中。 PI 研究计划的许多方面已经或将导致这款广泛使用的软件的重大改进。该提案的另一部分涉及有限几何形状，包括设计和代码。设计首先出现在统计实验的设计中，并在其他学科中有许多应用，包括光学、编码理论和计算机算法。纠错码是“纯”数学的基本工程应用。