Groups, Algorithms and Geometries

群、算法和几何

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

DMS-0242983Kantor, William M.AbstractTitle: Groups, algorithms and geometryAlgorithmic and asymptotic properties of finite groups will continue to be studied, including the statistical analysis of random elements of a finite simple group as well as probabilistic generation. The emphasis will be on algorithmic questions concerning permutation groups and matrix groups, and to more general questions concerning "black box groups". The main focus is the design and analysis of efficient algorithms to determine the normal structure of a large-dimensional matrix group given by a small set of generators, where the algorithms have both fast asymptotic running time and good practical performance. This should produce a polynomial-time algorithm for the basic manipulation of arbitrary matrix groups, assuming that discrete logarithms in suitable fields can be computed quickly. Recent algorithms devised or proposed for the constructive recognition of most classes of finite simple groups are a major ingredient in this plan. The study of polynomial-time, nearly linear time and parallel (complexity class NC) permutation group algorithms also will be continued. Additional new practical algorithms will be obtained based on methods developed in these theoretical situations. All of this work will make detailed use of the classification and properties of the finite simple groups. Some of these algorithms depend on geometric methods. Other geometric projects will be continued, including asymptotic investigations into planes, designs and codes. There will be special emphases on nonassociative division algebras and their planes (and in some cases, associated codes), as well as on automorphism groups of symmetric designs.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 the generation of a finite group from a probabilistic standpoint, which also has applications in computer science. A third portion of the proposal concerns finite geometries, especially 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. This proposal will fund graduate students who will study and work in these areas on the border between mathematics and its applications.

DMS-0242983 Kantor，William M.摘要标题：群、算法和几何有限群的算法和渐近性质将继续研究，包括对有限单群的随机元素的统计分析以及概率生成。重点将放在关于置换群和矩阵群的算法问题上，以及关于“黑箱群”的更一般的问题上。重点是设计和分析由少量生成元给出的确定高维矩阵群正规结构的高效算法，该算法具有快速的渐近运行时间和良好的实用性能。这应该会产生一个多项式时间算法，用于任意矩阵组的基本操作，假设适当域中的离散对数可以快速计算。最近设计或提出的用于对大多数有限单群类进行建设性识别的算法是该计划的主要组成部分。多项式时间、近线性时间和并行(复杂性类NC)置换群算法的研究也将继续进行。基于在这些理论情况下开发的方法，将获得其他新的实用算法。所有这些工作都将详细地利用有限单群的分类和性质。其中一些算法依赖于几何方法。其他几何项目将继续进行，包括对平面、设计和代码的渐近调查。将特别强调非结合除法代数及其平面(在某些情况下，还包括相关码)，以及对称设计的自同构群。群论领域是对称的数学理论，并与许多其他学科相互作用，例如数学之外的计算机科学、物理和化学、数论、拓扑学和数学内部的几何。有限群的基本构件是有限单群。有限单群的分类是近几十年来数学研究的重要成果之一。这项研究建议的主要部分是将这些简单群的性质用于计算机辅助研究任意有限群。群论算法是计算机群论软件包GAP和MAGMA的基础，GAP和MAGMA在群论和组合学中有着广泛的应用。PI的研究计划的许多方面已经或将导致这一广泛可用的软件的显著改进。这项建议的另一部分涉及从概率的角度生成有限群，这在计算机科学中也有应用。提案的第三部分涉及有限几何，特别是设计和代码。设计最早出现在统计实验的设计中，并在其他学科中有许多应用，包括光学、编码理论和计算机算法。纠错码是“纯”数学的基本工程应用。这项提议将资助那些将在数学及其应用之间的这些领域学习和工作的研究生。