Groups, Algorithms and Geometries

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

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.