Permutation encoding of a group

From Groupprops
Jump to: navigation, search

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.

Related notions

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.