Encoding of a subgroup

This article gives a basic definition in the following area: computational group theory
View other basic definitions in computational group theory |View terms related to computational group theory |View facts related to computational group theory

Description

The encoding of a subgroup problem is as follows. Let $G$ be a group with an encoding $C$. Then given a subgroup $H$ of $G$, and a membership test for $H$ in $G$ (with respect to the coding $C$), we can define the following encoding on $H$:

• The code for any element in $H$ is simply its code as an element of $G$
• The multiplication and inverse operations for elements of $H$ are performed simply as elements of $G$
• To check whether a codeword is valid, we first check whether it is valid in $G$, and then apply the membership test for $H$

Relation between encoding of the group and of the subgroup

Maximum size of a code-word

The maximum size of a code-word for an encoding of the group, is the same as the maximum size of a code-word for an encoding of the subgroup. Hence, even if the encoding of the group is efficient in the sense of using code-words of only logarithmic length, the encoding may be inefficient with respect to the size of the subgroup.

When the index of the subgroup is very small, then the encoding is efficient with respect to the subgroup as well.

Membership testing in the subgroup

If the membership testing problem for the subgroup has a fast solution with respect to the whole group, then the problem of recognizing whether a code represents an element of the subgroup, reduces to the problem of recognizing whether a code represents an element of the whole group.

Relation with generating sets

An alternative way to describe a subgroup given an encoding of the whole group, is via a generating set of the subgroup.

Comparison of the two appraoches

Note that a generating set actually gives a upward description of the subgroup (by starting from generators and continually multiplying out) while a membership test gives a downward construction, that is, it starts with the whole group and then sieves out some elements by a test.

Thus, given generating sets, it becomes easier to go upward (that is, go from a smaller subgroup to a bigger subgroup, take joins) while given a membership test, it becomes easier to go downward (that is, go from a bigger subgroup to a smaller subgroup, take intersections).

Further information: Generating set for a subgroup relative to an encoding

The two natural questions

• How do we use a generating set of the subgroup to obtain a membership test, and hence, an encoding of the subgroup?
• How do we use a membership test (or equivalently, an encoding obtained by restriction from the whole group) for the subgroup to obtain a generating set for it?