Book contents
- Frontmatter
- Contents
- Introduction
- Addresses of registered participants
- Addresses of non-participating authors
- Programme of lectures
- Conference photograph and key
- Symmetric presentations and orthogonal groups
- A constructive recognition algorithm for the special linear group
- Relations in M666
- A survey of symmetric generation of sporadic simple groups
- Harish-Chandra theory, q-Schur algebras, and decomposition matrices for finite classical groups
- The Meataxe as a tool in computational group theory
- Branching rules for modular projective representations of the symmetric groups
- Characters and surfaces: a survey
- On the characterization of finite groups by characters
- Finite linear groups of small degree
- Minimal parabolic systems for the symmetric and alternating groups
- Probabilistic methods in the generation of finite simple groups
- Condensing tensor product modules
- Intersections of Sylow subgroups in finite groups
- Anatomy of the Monster: I
- An integral ‘Meat-axe’
- Finite rational matrix groups: a survey
- Chamber graphs of sporadic group geometries
- An Atlas of sporadic group representations
- Presentations of reductive Fischer groups
- A brief history of the ATLAS
The Meataxe as a tool in computational group theory
Published online by Cambridge University Press: 19 May 2010
- Frontmatter
- Contents
- Introduction
- Addresses of registered participants
- Addresses of non-participating authors
- Programme of lectures
- Conference photograph and key
- Symmetric presentations and orthogonal groups
- A constructive recognition algorithm for the special linear group
- Relations in M666
- A survey of symmetric generation of sporadic simple groups
- Harish-Chandra theory, q-Schur algebras, and decomposition matrices for finite classical groups
- The Meataxe as a tool in computational group theory
- Branching rules for modular projective representations of the symmetric groups
- Characters and surfaces: a survey
- On the characterization of finite groups by characters
- Finite linear groups of small degree
- Minimal parabolic systems for the symmetric and alternating groups
- Probabilistic methods in the generation of finite simple groups
- Condensing tensor product modules
- Intersections of Sylow subgroups in finite groups
- Anatomy of the Monster: I
- An integral ‘Meat-axe’
- Finite rational matrix groups: a survey
- Chamber graphs of sporadic group geometries
- An Atlas of sporadic group representations
- Presentations of reductive Fischer groups
- A brief history of the ATLAS
Summary
Abstract
The Meataxe is a practical algorithm, first introduced by Richard Parker, for testing finite dimensional modules over finite fields for irreducibility, and for finding explicit submodules in the reducible case. This and associated algorithms are described briefly, together with more recent improvements. The possibility of extending these methods to fields of characteristic zero, such as the rational numbers, is also discussed.
Chopping up modules
The problem of explicitly finding the irreducible constituents of a finite dimensional KG-module, where K is a field and G is a finite group, is without doubt the most basic problem in computational group-representation theory. It corresponds roughly to finding the orbits of a finite permutation group, except that it is considerably more difficult.
Most of the research on this problem to date has been restricted to the case where K = GF(q) is finite, and we shall assume this to be true in the first two sections of this paper. The characteristic zero case will be discussed in section 3. We shall denote the degree of the representation by d, throughout.
The theoretical complexity of the problem was proved to be polynomial in d log(q) by Rónyai in [12], but the algorithm described there does not appear to be practical as it stands, and has complexity at least as bad as O(d6log(q)). For current applications, it is essential to find methods that are practical for d equal to at least several thousand and, to achieve this, we must aim for complexity O(d3log(q)). In practice, this is equal to the complexity of multiplying two matrices, inverting a matrix, or performing a Gaussian reduction.
- Type
- Chapter
- Information
- The Atlas of Finite Groups - Ten Years On , pp. 74 - 81Publisher: Cambridge University PressPrint publication year: 1998
- 5
- Cited by