Efficient Computation in Finite Groups

点击翻译按钮获取中文摘要

Group theory is the mathematical theory of symmetry. Algorithms for finite groups and their associated graphs have a wide range of applications in mathematics, the physical sciences, and computer science. This project has two main foci. The first one is the development of a unified data structure for the algorithmic treatment of finite groups in their concrete representations as permutation groups or matrix groups; the second one is the design, analysis, and implementation of algorithms for large dimensional matrix groups, applying the unified framework. Implementations of the new algorithms will be distributed worldwide in the GAP computer algebra system and they will contribute to a computational environment in GAP for research in group theory, algebra, graph theory, coding theory, and design theory, and to computer-based educational materials for undergraduate algebra courses.The project will develop divide-and-conquer techniques for various classes of Aschbacher's classification of matrix groups, thereby reducing the computations to smaller dimensional matrix groups or to permutation groups. Also, particular emphasis is placed on algorithms dealing with simple groups, which are the final stages of recursion in this divide-and-conquer scheme. The research also includes problems in group theory and combinatorics which are either necessary for the proof of correctness of the algorithms, or became accessible by the new machinery. In particular, these problems include the minimum base size and minimal suborbit size of primitive permutation groups, diameter estimates of Cayley graphs of almost simple groups, finding short presentations for simple groups, and the construction of highly symmetric graphs with a distinguished set of cycles.