# Permutation encoding of a group

## Definition

A permutation encoding of a group $G$ is the following data:

• An integer $n$ and the standard encoding for the symmetric group of order $n$ (as described in encoding of symmetric groups)
• A specification of the given group $G$ as a subgroup of the symmetric group by means of a generating set $A$ (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 $G$ within the symmetric group. Hence, we get an encoding of $G$ 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.

## 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.