Coset representative function: Difference between revisions

Latest revision as of 23:24, 7 May 2008

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 $H G$ 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

Stronger descriptions

Weaker descriptions

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 $g h$ 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$ .

@@ Line 6: / Line 6: @@
 Let <math>G</math> be a [[group]] with an [[encoding of a group|encoding]] <math>C</math>. That is, <math>C</math> associates to each element of <math>G</math> 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 <math>H \leq K \leq G</math> be subgroups.
+Let <math>H  G</math> be a subgroup.
 ===Definition part===
-A coset representative function for <math>H</math> in <math>K</math> is a function <math>f:K \to K</math> that is constant on the left cosets and that sends each left coset to an element in that left coset.
+A coset representative function for <math>H</math> in <math>G</math> is a function <math>f:G \to G</math> 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 <math>H</math> in <math>K</math> involves first choosing a system of coset representatives for <math>H</math> in <math>K</math>, and then defining a map that sends each element to the coset representative of its left coset.
+Another way of viewing this is that a coset representative function for <math>H</math> in <math>G</math> involves first choosing a system of coset representatives for <math>H</math> in <math>G</math>, and then defining a map that sends each element to the coset representative of its left coset.
 ==Relation with other descriptions==
@@ Line 27: / Line 27: @@
 ===Intersection of subgroups===
+Given subgroups <math>H_1</math> and <math>H_2</math> of <math>G</math> with coset representative functions <math>f_1</math> and <math>f_2</math>, can we obtain a coset representative function for <math>H_1 \cap H_2</math>?
+===Composition operator===
+Suppose we have a coset representative function for <math>H</math> in <math>K</math>, and a coset representative function for <math>K</math> in <math>G</math>. Then, we can use both of them to obtain a coset representative function for <math>H</math> in <math>G</math>, as follows:
+* The set of coset representatives is the set of products <math>gh</math> where <math>g</math> is a coset representative for <math>K</math> in <math>G</math>, and <math>h</math> is a coset representative for <math>H</math> in <math>K</math>.
+* To find the coset representative of an element of <math>G</math> with respect to <math>H</math>, we first compute the coset representative with respect to <math>K</math>, then take the quotient and compute the coset representative of the quotient with respect to <math>H</math>. Multiplying the two values out gives the coset representative.
+===Transfer operator===
+It is not clear how we can use the coset representative function for <math>H</math> in <math>G</math> to obtain a coset representative function for <math>H \cap K</math> in <math>K</math>.