# Permutation encoding of a group

## Contents

## Definition

A **permutation encoding of a group** is the following data:

- An integer and the standard encoding for the symmetric group of order (as described in encoding of symmetric groups)
- A specification of the given group as a subgroup of the symmetric group by means of a generating set (preferably a small one)

By a standard algorithm for permutation groups (see generating set to membership test for permutation groups), we get a membership test for within the symmetric group. Hence, we get an encoding of in the standard sense.

A permutation encoding can also be viewed as a concrete, or explicit, description using a faithful group action or a faithful permutation representation.

## Related notions

- Linear encoding is the equivalent notion for a description as a subgroup of a general linear group

## Particular nice things about permutation encodings

### Subgroups can be described by generating sets

For groups described by a permutation encoding, we prefer to describe the subgroups by means of generating sets. This is because for any subgroup, we can easily pass from a generating set to a membership test, and hence obtain an encoding of the subgroup.

Thus, when dealing with permutation encodings, we assume that subgroups are specified by means of their generating sets.

### Generating sets can be trimmed

The nice thing about permutation encodings is that they can be improved. In other words, given a permutation encoding, we can trim down the size of the generating set to an acceptable amount, and this, in iterative procedures where a slightly bigger generating set is produced each time, can be used to keep the generating set in check.

The trimming algorithms include the Sims filter and the Jerrum filter.