Algorithms in Finite Groups

本课题研究有限矩阵群的渐近有效算法的设计与分析。虽然计算群论三十年的工作已经导致了对置换群的许多算法方面的理论和实践的透彻理解，但直到最近才在可能更重要的矩阵群领域设计出有效的算法。然而，后一个领域目前正在经历爆炸式增长。本研究主要集中在理论方面和多项式时间算法。过去的经验表明，这种方法具有产生可能导致有效实现的重要见解的潜力。事实上，受多项式时间范式启发的算法已经进入了广泛使用的群论包GAP。主要目标是映射出由一组生成器给出的矩阵群的正规结构。这个项目的组件包括许多需要在“黑盒组”的更一般的上下文中处理的问题（组操作由“黑盒”执行）。一个关键因素是有限单群的黑箱识别。另一个组成部分是“超越”一个简单的顶商。这些方法包括有限简单群中元素阶数性质的统计分析（基于有限简单群的分类）。其中一个主要障碍似乎需要研究简单群的模表示。在分析随机抽样启发式问题时，似乎需要组合方法，而大多数现有的矩阵群算法都需要组合方法。

This project investigates the design and analysis of asymptotically efficient algorithms for finite matrix groups. While three decades of work in computational group theory have resulted in a thorough understanding, both theoretical and practical, of many algorithmic aspects of permutation groups, virtually no efficient algorithms have been designed until recently in the potentially more important domain of matrix groups. This latter area, however, is currently experiencing explosive growth. This research focuses on theoretical aspects and polynomial time algorithms. Past experience shows that this approach has the potential of yielding important insights which may lead to efficient implementations. Indeed, algorithms inspired by the polynomial-time paradigm have made their way into the widely used group theory package GAP. The main objective is to map out the normal structure of a matrix group given by a list of generators. Components of this project include a number of problems to be handled in the more general context of "black-box groups" (the group operations are performed by a "black box"). A key ingredient is the black-box recognition of finite simple groups. Another component consists in "getting past" a simple top quotient. The methods include the statistical analysis of number theoretic properties of the orders of elements in finite simple groups (based on the classification of finite simple groups). One of the main obstacles seems to require the study of modular representations of simple groups. Combinatorial methods seem to be called for in the analysis of random sampling heuristics which are required for most existing matrix group algorithms.