Coset representative function

This article gives a subgroup description, that is, a way of describing a subgroup with reference to an ambient group

Description

Setup

Let $G$ be a group with an encoding $C$. That is, $C$ associates to each element of $G$ a string over a fixed (say, binary) alphabet, along with algorithms for testing validity of a code-word, for multiplying group elements, and for finding the inverse of a group element.

Let $HG$ be a subgroup.

Definition part

A coset representative function for $H$ in $G$ is a function $f:G\to G$ that is constant on the left cosets and that sends each left coset to an element in that left coset.

Another way of viewing this is that a coset representative function for $H$ in $G$ involves first choosing a system of coset representatives for $H$ in $G$, and then defining a map that sends each element to the coset representative of its left coset.

Relation with other descriptions

Weaker descriptions

• Coset enumeration
• Coset-separating function
• Membership test

Relation with subgroup operators

Intersection of subgroups

Given subgroups $H_{1}$ and $H_{2}$ of $G$ with coset representative functions $f_{1}$ and $f_{2}$, can we obtain a coset representative function for $H_{1}\cap H_{2}$?

Composition operator

Suppose we have a coset representative function for $H$ in $K$, and a coset representative function for $K$ in $G$. Then, we can use both of them to obtain a coset representative function for $H$ in $G$, as follows:

• The set of coset representatives is the set of products $gh$ where $g$ is a coset representative for $K$ in $G$, and $h$ is a coset representative for $H$ in $K$.

• To find the coset representative of an element of $G$ with respect to $H$, we first compute the coset representative with respect to $K$, then take the quotient and compute the coset representative of the quotient with respect to $H$. Multiplying the two values out gives the coset representative.

Transfer operator

It is not clear how we can use the coset representative function for $H$ in $G$ to obtain a coset representative function for $H\cap K$ in $K$.