Permutation and Matrix Groups

For an overview of computational methods for permutation groups see the book [Se03] of Ákos Seress. Historically, these methods started with Charles Sims' method for finding the order and a stabilizer chain nowadays known as the Schreier-Sims method, which is the basis of many functions implemented in GAP. To give a small sample of further special methods:

The nearly linear time methods for permutation groups include functions to compute

• a stabilizer chain,
• p-core,
• radical,
• centre,
• composition series.

There are also tasks for which no polynomial time methods are known and for which GAP relies on partition backtrack methods, for example

• centralizer,
• normalizer, or
• intersection of subgroups.

The GAP4 package RCWA provides methods for computations with the so-called Residue Class-Wise Affine mappings of certain euclidian rings R into themselves and the groups generated by bijective mappings of this type. The latter mappings form a proper subgroup of Sym(R).

For matrix groups. there are also special methods in the GAP library and a private GAP4 package matrixss implements a Schreier-Sims algorithm for matrix groups, including both the standard deterministic and the standard probabilistic approach.

The package Polenta allows to find polycyclic presentations for matrix groups.

Routines to recognize isomorphism types of matrix groups using the Aschbacher classification (which recently have been in the focus of attention in computational group theory) are still (2005) only available through the GAP 3 package matrix.

Also the very powerful package CHEVIE for dealing with groups of Lie type and Chevalley groups still (2005) only exists with GAP 3.