Algorithms in Finite Groups

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

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.