A practical model for computation with matrix groups. (Q480641): Difference between revisions

In computational problems with finite groups, typically the group \(G\) is described very economically by providing a set of generators of \(G\) from some larger well-known group; for example, the generators are permutations from a symmetric group, or matrices from a general linear group over a finite field. The object is then to use this description to determine various group theoretic properties of \(G\) such as: order, Sylow subgroups, solvability, simplicity, etc. In the 1960s Charles Sims introduced the idea of a basis and strong generating set to deal with (what were then) very large groups. This technique is based on the existence of a chain of subgroups of \(G\) in which successive indices are small compared to the size of the group. When \(G\) is a permutation group, such subgroup chains occur naturally by computing stabilizers, and Sims' ideas have been central in computing with such groups. For matrix groups, however, Sims' method will often fail because there is no suitable subgroup chain; for example, in some matrix groups, every maximal subgroup has a large index. This has led to the ``matrix group recognition program'' [see \textit{C. R. Leedham-Green}, in: Groups and computation III. Proceedings of the international conference at the Ohio State University, Columbus, OH, USA, 1999. Berlin: Walter de Gruyter. Ohio State Univ. Math. Res. Inst. Publ. 8, 229-247 (2001; Zbl 1052.20034)] in which the subgroup chain is replaced by a subnormal subgroup chain and recognizing the factor groups plays a central role. In the present paper, the authors define a composition tree for \(G\) to be a full binary tree whose vertices are labelled by subnormal sections of \(G\). The root is labelled \(G\) and a non-leaf node labelled \(H\), say, has two children \(H_0\) and \(H_1\) and an associated exact sequence \(H_0\hookrightarrow H\twoheadrightarrow H_1\). The tree is constructed recursively and the data structure used enables rewriting in sections of \(G\). The process of constructing a composition tree for a characteristic series for \(G\) uses detailed knowledge about the simple groups and their automorphisms. The algorithms and their implementation incorporate work of many authors, and the technical details are involved. The algorithms have been implemented in MAGMA, and the paper ends by describing how well the program works in solving some challenge problems.