Groups, Algorithms and Geometries

kantor, William m . abstract标题：群，算法和几何有限群的算法和渐近性质将继续研究，包括有限简单群随机元素的统计分析以及概率生成。重点是关于置换群和矩阵群的算法问题，以及关于“黑箱群”的更一般的问题。重点是设计和分析由一组小生成器给出的大维矩阵群的正规结构的有效算法，该算法具有快速的渐近运行时间和良好的实用性能。这应该产生一个多项式时间算法，用于任意矩阵群的基本操作，假设在合适的域中可以快速计算离散对数。最近为构造识别大多数有限简单群类而设计或提出的算法是这一计划的主要组成部分。对多项式时间、近线性时间和并行（复杂度类NC）置换群算法的研究也将继续。基于在这些理论情况下开发的方法，将获得更多新的实用算法。所有这些工作都将详细地利用有限单群的分类和性质。其中一些算法依赖于几何方法。其他几何项目将继续进行，包括对平面、设计和规范的渐近研究。将特别强调非结合除法代数及其平面（以及在某些情况下，关联码），以及对称设计的自同构群。群论领域是对称的数学理论，并与许多其他学科相互作用，例如计算机科学，数学之外的物理和化学，数学内部的数论，拓扑和几何。有限群的基本组成部分是有限单群。近几十年来最杰出的数学成果之一是有限单群的分类。本研究计划的一个主要部分旨在利用这些简单群的性质在计算机辅助研究任意有限群。群论算法是计算机群论软件包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.