Efficient Computation in Finite Groups

群论是对称性的数学理论。有限群及其相关图的算法在数学、物理科学和计算机科学中具有广泛的应用。该项目有两个主要重点。第一个是开发统一的数据结构，用于将有限群的具体表示形式作为置换群或矩阵群进行算法处理；第二个是应用统一框架的大维矩阵群算法的设计、分析和实现。新算法的实现将在 GAP 计算机代数系统中分布在全球范围内，它们将为 GAP 中的计算环境做出贡献，用于群论、代数、图论、编码理论和设计理论的研究，以及基于计算机的本科代数课程教材。该项目将为矩阵群的阿施巴赫分类的各个类别开发分而治之的技术，从而将计算减少到更小维的矩阵群或排列群。此外，特别强调处理简单组的算法，这是该分而治之方案中递归的最后阶段。该研究还包括群论和组合学中的问题，这些问题对于证明算法的正确性是必要的，或者可以通过新机器来访问。特别是，这些问题包括本原排列群的最小基尺寸和最小子轨道尺寸、几乎简单群的凯莱图的直径估计、找到简单群的简短表示，以及构建具有一组独特循环的高度对称图。

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.