Book contents
- Frontmatter
- Contents
- Introduction
- Galois groups through invariant relations
- Construction of Co3. An example of the use of an integrated system for computational group theory
- Embedding some recursively presented groups
- The Dedekind-Frobenius group determinant: new life in an old problem
- Group characters and π-sharpness
- Permutation group algorithms via black box recognition algorithms
- Nonabelian tensor products of groups: the commutator connection
- Simple subalgebras of generalized Witt algebras of characteristic zero
- Applications of the Baker-Hausdorff formula in the theory of finite p-groups
- Generalizations of the restricted Burnside problem for groups with automorphisms
- The ∑m-conjecture for a class of metabelian groups
- Rings with periodic groups of units II
- Some free-by-cyclic groups
- The residually weakly primitive geometries of the Suzuki simple group Sz(8)
- Semigroup identities and Engel groups
- Groups whose elements have given orders
- The Burnside groups and small cancellation theory
- Solvable Engel groups with nilpotent normal closures
- Nilpotent injectors in finite groups
- Some groups with right Engel elements
- The growth of finite subgroups in p-groups
- Symplectic amalgams and extremal subgroups
- Primitive prime divisor elements in finite classical groups
- On the classification of generalized Hamiltonian groups
- Permutability properties of subgroups
- When Schreier transversals grow wild
- Probabilistic group theory
- Combinatorial methods: from groups to polynomial algebras
- Formal languages and the word problem for groups
- Periodic cohomology and free and proper actions on ℝn × Sm
- On modules over group rings of soluble groups of finite rank
- On some series of normal subgroups of the Gupta-Sidki 3-group
Permutation group algorithms via black box recognition algorithms
Published online by Cambridge University Press: 04 August 2010
- Frontmatter
- Contents
- Introduction
- Galois groups through invariant relations
- Construction of Co3. An example of the use of an integrated system for computational group theory
- Embedding some recursively presented groups
- The Dedekind-Frobenius group determinant: new life in an old problem
- Group characters and π-sharpness
- Permutation group algorithms via black box recognition algorithms
- Nonabelian tensor products of groups: the commutator connection
- Simple subalgebras of generalized Witt algebras of characteristic zero
- Applications of the Baker-Hausdorff formula in the theory of finite p-groups
- Generalizations of the restricted Burnside problem for groups with automorphisms
- The ∑m-conjecture for a class of metabelian groups
- Rings with periodic groups of units II
- Some free-by-cyclic groups
- The residually weakly primitive geometries of the Suzuki simple group Sz(8)
- Semigroup identities and Engel groups
- Groups whose elements have given orders
- The Burnside groups and small cancellation theory
- Solvable Engel groups with nilpotent normal closures
- Nilpotent injectors in finite groups
- Some groups with right Engel elements
- The growth of finite subgroups in p-groups
- Symplectic amalgams and extremal subgroups
- Primitive prime divisor elements in finite classical groups
- On the classification of generalized Hamiltonian groups
- Permutability properties of subgroups
- When Schreier transversals grow wild
- Probabilistic group theory
- Combinatorial methods: from groups to polynomial algebras
- Formal languages and the word problem for groups
- Periodic cohomology and free and proper actions on ℝn × Sm
- On modules over group rings of soluble groups of finite rank
- On some series of normal subgroups of the Gupta-Sidki 3-group
Summary
Abstract
If a black box simple group is known to be isomorphic to a classical group over a field of known characteristic, a Las Vegas algorithm is used to produce an explicit isomorphism. This is used to upgrade all nearly linear time Monte Carlo permutation group algorithms to Las Vegas algorithms when the input group has no composition factor isomorphic to an exceptional group of Lie type or a 3–dimensional unitary group.
Key words and phrases: computational group theory, black box groups, classical groups, matrix group recognition
1991 Mathematics Subject Classification: Primary 20B40, 20G40; Secondary: 20P05, 68Q25, 68Q40
Introduction
There is a large library of nearly linear time permutation group algorithms [BCFS, BS, CF, LS, Mo, Ra, SchS, Ser]. Most of these are Monte Carlo (which means that the algorithm can return an incorrect answer, although the probability of that can be made as small as desired). The main result of this note is that Monte Carlo can be upgraded to Las Vegas (which means that the output is always correct, but the algorithm may also report failure, although the probability of that can be made as small as desired), whenever there are suitable recognition algorithms for the simple groups occurring as composition factors.
There is a growing literature of recognition algorithms for quasisimple groups of Lie type. The first of these, due to Neumann and Praeger [NP], solved the following problem: given a group G ≤ GL(d, q) by a set of generating matrices, decide whether G contains SL(d, q).
- Type
- Chapter
- Information
- Groups St Andrews 1997 in Bath , pp. 436 - 446Publisher: Cambridge University PressPrint publication year: 1999
- 1
- Cited by