Subgroup descriptions

Description

Basic descriptions

Let $G$ be a group with an encoding (or multi-encoding) $C$ . We want to find a way of describing an abstract subgroup $H$ of $G$ .

There are three typical ways of describing $H$ :

By specifying a membership test. This is an algorithm that takes as input the code-word for $g\in G$ and outputs, by looking at the code-word for $g$ , whether $g\in H$
By specifying an enumeration algorithm. This is an algorithm that actually outputs all the elements of $H$ in a list.

Now, an enumeration algorithm can be effectively described through a generating set. That is, given a generating set of a group, we can obtain an enumeration algorithm by first listing elements in the generating set, then listing products of length two, then listing all the products of length two, then listing all the products of length three. Hence, the generating set (subgroup description) automatically gives an enumeration algorithm.

By specifying a coset enumeration, viz a system of coset representatives and an algorithm that inputs $g\in G$ and a coset representative $s$ and outputs the coset representative for $gs$ .

By specifying a coset-separating function, viz a function to a set that is constant on all the cosets

The various descriptions

Membership test

Further information: Membership test (subgroup description)

A membership test is basically a top-down way of describing the subgroup -- one starts with all elements in the group, and then sieves out elements which are not in the subgroup.

Given a membership test for a subgroup, we can use that to obtain an encoding of the subgroup from an encoding of the whole group. if $H\leq G$ and $C$ is an encoding of $G$ :

The encoding on $H$ is simply the restriction of the encoding of $G$
The multiplication and inversion maps are also defined by restricting from $G$
To check whether a string represents a valid code-word, we first check whether it represents a valid code-word for an element of $G$ , and then apply the membership test for $H$ .

Note that if we instead start with a multi-encoding of the group (viz something that may associate multiple code-words to the same element) then we'll get a multi-encoding of the subgroup (which just might be an encoding, but is likely not to be).

Membership tests are also important ways of describing subgroups because a membership test for subgroups gives,naturally a membership test for their intersection.

Generating sets

Further information: Generating set (subgroup description)

A generating set is a bottom-up way of describing the subgroup. Starting from the trivial subgroup, we add some generators and obtain the smallest subgroup generated by them.

A generating set also describe an enumeration algorithm, because we can list elements of the subgroup generated as elements obtained by words in the generators, and these words can be enumerated.

Generating sets, being bottom-up, perform well on the join operator. In other words, given generating sets for two subgroups, we can define a generating set for the subgroup generated by them as the union of those generating sets.

Coset enumeration

Further information: Coset enumeration (subgroup description)

A coset enumeration is a way of describing the subgroup by means of its action on the coset space. A coset enumeration comprises the following data:

A list of one representative for each coset
An algorithm that, given any element of the group, can compute the coset representative of that element.

Relation between the three descriptions

Coset enumeration versus membership test

A coset enumeration gives a membership test as follows: to check whether an element lies inside the subgroup, just check whether its coset representative equals the coset representative of the identity element.

The reverse question is: does a membership test give a coset enumeration? That is, given $H\leq G$ , how do we find a system of coset representatives for $H$ in $G$ ? it turns out we can using a generating set $A$ for the bigger group $G$ . The procedure is as follows:

Finding a system of coset representatives: Suppose we have a small generating set for the whole group. Then, we can construct the Cayley graph of the action of $G$ on $G/H$ with respect to the generating set $A$ of $G$ . Now, usingthe BFS as a shortest path-finding algorithm, compute coset representatives for all elements of $G/H$

Constructing the algorithm that outputs the coset representative of any element: The naive idea is as follows. Check, for each coset representative, whether the quotient of this element by the coset representative is in the subgroup. For that check, invoke the membership test.

Coset enumeration versus generating set

It also turns out that a coset enumeration of a subgroup takes us from a generating set of the whole group to a generating set of a subgroup. This follows as a consequence of Schreier's lemma, which explicitly constructs generators for the subgroup in terms of generators of the whole group and coset representatives of the subgroup.

The converse problem (obtaining a coset enumeration from a generating set) is an important problem. It is called the coset enumeration problem and it is resolved using algorithms such as the Todd-Coxeter algorithm and the Knuth-Bendix algorithm.

Generating set versus membership test

There are two interesting problems:

The problem of passing from a membership test to a generating set: We have already seen above an outline of the solution to this problem, namely, we first obtain a coset enumeration, and then we use that coset enumeration to obtain a generating set. This naive approach could take time polynomial in the index of the subgroup, and we need to resort to cleverer techniques (involving towers of subgroups and iterated application of filters).
The problem of passing from a generating set to a membership test. This is also called the membership testing problem. Interestingly, to solve this problem, (which we can do at least in the case of permutation groups) we need to appeal to a specialized instance of the opposite problem (finding a membership test from a generating set).