Quotient descriptions

Description

Basic descriptions

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

There are three ways:

• Equality test: Find a way of checking, from the code-words of two elements, whether they belong to the same coset. The equality test boils down to the membeship test for the normal subgroup $N$
• Coset enumeration: Find a system of coset representatives of $N$ in $G$
• Generating system of relations: Find a subset whose normal closure is $N$

Relation with subgroup descriptions

• The equality test for the quotient corresponds to a membership test for the normal subgroup.
• The coset enumeration for the quotient is also a coset enumeration viewed as a subgroup description
• The generating system of relations is an equivalent of generating set. The difference is that when we are working with the generating set, we are only looking at the subgroup generated while when talking of a generating system of relations, we are looking at the smallest normal subgroup containing the given set or equivalently, at the normal closure of the subgroup generated.

The various descriptions

Equality test

An equality test is a test that, given the code-words for two elements of $G$, determines whether they arise from the same coset of $N$. If we have an equality test, we can pass from a multi-encoding of the whole group to a multi-encoding of the subgroup, by associating to each coset $G/N$ the union of the code-word sets for all members in that coset.

Note that an equality test for the quotient is equivalent to a membership test for the normal subgroup.

Coset enumeration

Here, we explicitly choose one representative of every coset. In other words, we describe a transversal of the subgroup (since it is normal, left and right notions coincide). Further, we give an algorithm that, given any element, can compute the coset representative of that element.

In general, choosing coset representatives defines an association of a unique string to every coset, and hence, to every element in the quotient group. However, it may not in general be true that the product of coset representatives is a coset representative. Thus, we need to make use of the fact that we can find the coset representative for this element.

Note that coset enumeration in this case is somewhat different from coset enumeration in the general case of a group acting on an arbitrary (not necessarily normal) subgroup.

Generating system of relations

Here, we find a subset of elements which generates (as a normal subgroup) the entire kernel.

When $G$ is a free group, such a description is the same as a presentation.

Relation between the three descriptions

Coset enumeration versus equality test

A coset enumeration clearly gives an equality test (all we have to do is check whether the coset representatives of the two elements are the same). Proving the other way around is a little tricky, but it essentially is the same as the proof that a membership test of a subgroup gives a coset enumeration.

Coset enumeration versus generating system of relations

A coset enumeration can in fact give us a generating set for the subgroup (using Schreier's lemma) which will thus also serve as a generating system of relations.

However, establishing anything the other way around is hard, because a generating system of relations may be much smaller than a generating set.

Equality test versus generating system of relations

The direction from an equality test to a generating system of relations follows by proceeding via a coset enumeration (that is, the two pats described above). The other direction doesn't seem obvious at all -- in fact, a special case of that is the word problem in combinatorial group theory which we know is not solvable in general.