Permutation encoding of a group
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.
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.