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.
The field of group theory is the mathematical theory of symmetry and interacts with many other disciplines, including computer science, physics, chemistry, combinatorics, number theory, topology and geometry. One of the outstanding mathematical results in recent decades is the classification of the finite simple groups, which are the fundamental building blocks of finite groups. Extremely large finite groups can be described using a very small amount of data. One of the fundamental results of this grant is that almost all finite simple groups can be specified, in terms of a "presentation", using an unexpectedly tiny amount of data. This and other grant results concerning generating these groups are significant within the framework of computational group theory. That area is a major portion of the grant research: devising efficient algorithms (computational methods) for computer computations with finite groups. "Exceptional" finite simple groups have long been a fundamental stumbling block for such research. Some of the major results of this grant have been algorithms for handling such groups that are efficient both in theory and in practice. This has required using complicated properties of these simple groups. These algorithms also have been used for the algorithmic study of special subgroups ("Sylow subgroups") of a finite group that are often used to "tear the group apart" in order to investigate the group's structure. All of these algorithms will be significant in the computer-assisted study of arbitrary finite groups, leading (for example) to the basic manipulation of arbitrary large-dimensional matrix groups. Versions of all of this algorithmic research will eventually be incorporated into the computer group theory packages GAP and Magma that are widely used in group theory and combinatorics. Other grant research involved finite geometries, most recently geometries related to basic questions in mathematical physics. New geometries were constructed and studied, and it was shown in many situations that the number of different geometries is very large.
