Groups, Algorithms and Geometries

University Of Oregon Eugene, Eugene OR

Investigators

Abstract

DMS-0242983 Kantor, William M. Abstract Title: Groups, algorithms and geometry Algorithmic 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.