Coset

# Coset

Discussion

Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, if G is a group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

, and H is a subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

of G, and g is an element of G, then
gH = {gh : h an element of H } is a left coset of H in G, and
Hg = {hg : h an element of H } is a right coset of H in G.

Only when H is normal
Normal subgroup
In abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....

will the right and left cosets of H coincide, which is one definition of normality of a subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

.

A coset is a left or right coset of some subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

in G. Since Hg = g ( g−1Hg ), the right cosets Hg (of H ) and the left cosets g ( g−1Hg ) (of the conjugate
Conjugacy class
In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure...

subgroup g−1Hg ) are the same. Hence it is not meaningful to speak of a coset as being left or right unless one first specifies the underlying subgroup
Subgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

. In other words: a right coset of one subgroup equals a left coset of a different (conjugate) subgroup. If the left cosets and right cosets are the same then H is a normal subgroup
Normal subgroup
In abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....

and the cosets form a group called the quotient group
Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...

.

The map
gH→(gH)−1=Hg−1 defines a bijection
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

between the left cosets and the right cosets of H, so the number of left cosets is equal to the number of right cosets. The common value is called the index
Index of a subgroup
In mathematics, specifically group theory, the index of a subgroup H in a group G is the "relative size" of H in G: equivalently, the number of "copies" of H that fill up G. For example, if H has index 2 in G, then intuitively "half" of the elements of G lie in H...

of H in G.

For abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...

s, left cosets and right cosets are always the same. If the group operation is written additively then the notation used changes to g+H or H+g.

Cosets are a basic tool in the study of groups, for example they play a central role in Lagrange's theorem
Lagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....

.

## Examples

Let G be the additive group of integers Z = {… , −2, −1, 0, 1, 2, …} and H the subgroup mZ = = {…, −2m, −m, 0, m, 2m, …} where m is a positive integer. Then the cosets of H in G are the m sets mZ, mZ+1, … mZ+(m−1), where mZ+a={…, −2m+a, −m+a, a, m+a, 2m+a, …}. The coset mZ+a is the congruence classes
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

of a modulo m.

Another example of a coset comes from the theory of vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

s. The elements (vectors) of a vector space form an abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...

under vector addition. It is not hard to show that subspaces
Linear subspace
The concept of a linear subspace is important in linear algebra and related fields of mathematics.A linear subspace is usually called simply a subspace when the context serves to distinguish it from other kinds of subspaces....

of a vector space are subgroups of this group. For a vector space V, a subspace W, and a fixed vector a in V, the sets

are called affine subspaces, and are cosets (both left and right, since the group is abelian). In terms of geometric
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

vectors, these affine subspaces are all the "lines" or "planes" parallel to the subspace, which is a line or plane going through the origin.

## Definition using equivalence classes

Some authors define the left cosets of H in G to be the equivalence classes under the equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

on G given by x ~ y if and only if x−1yH. The relation can also be defined by x ~ y if and only if xh=y for some h in H. It can be shown that the relation given is, in fact, an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

and that the two definitions are equivalent. It follows that any two left cosets of H in G are either identical or disjoint . In other words every element of G belongs to one and only one left coset and so the left cosets form a partition
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

of G. Corresponding statements are true for right cosets.

## Double cosets

Given two subgroups, H and K of a group G, the double coset of H and K in G are sets of the form HgK = {hgk : h an element of H , k an element of K }. These are the left cosets of K and right cosets of H when H=1 and K=1 respectively.

## General properties

The identity is in precisely one left or right coset, namely H itself. Thus H is both a left and right coset of itself.

A coset representative is a representative in the equivalence class sense. A set of representatives of all the cosets is called a transversal
Transversal
In geometry , when two coplanar lines exist such that a third coplanar line passes thru both lines. This third line is named the Transversal....

. There are other types of equivalence relations in a group, such as conjugacy, that form different classes which do not have the properties discussed here. Some books on very applied group theory erroneously identify the conjugacy class as 'the' equivalence class as opposed to a particular type of equivalence class.

### Index of a subgroup

All left cosets and all right cosets have the same order
Order (group theory)
In group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....

(number of elements, or cardinality in the case of an infinite H), equal to the order of H (because H is itself a coset). Furthermore, the number of left cosets is equal to the number of right cosets and is known as the index of H in G, written as [G : H ]. Lagrange's theorem
Lagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....

allows us to compute the index in the case where G and H are finite, as per the formula:
|G | = [G : H ] · |H |.

This equation also holds in the case where the groups are infinite, although the meaning may be less clear.

### Cosets and normality

If H is not normal
Normal subgroup
In abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....

in G, then its left cosets are different from its right cosets. That is, there is an a in G such that no element b satisfies aH = Hb. This means that the partition of G into the left cosets of H is a different partition than the partition of G into right cosets of H. (It is important to note that some cosets may coincide. For example, if a is in the center
Center (group theory)
In abstract algebra, the center of a group G, denoted Z,The notation Z is from German Zentrum, meaning "center". is the set of elements that commute with every element of G. In set-builder notation,...

of G, then aH = Ha.)

On the other hand, the subgroup N is normal if and only if gN = Ng for all g in G. In this case, the set of all cosets form a group called the quotient group
Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...

G /N with the operation ∗ defined by (aN )∗(bN ) = abN. Since every right coset is a left coset, there is no need to differentiate "left cosets" from "right cosets".

## Applications

• Cosets of Q in R are used in the construction of Vitali set
Vitali set
In mathematics, a Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable, found by . The Vitali theorem is the existence theorem that there are such sets. There are uncountably many Vitali sets, and their existence is proven on the assumption of the axiom of...

s, a type of Non-measurable set
Non-measurable set
In mathematics, a non-measurable set is a set whose structure is so complicated that it cannot be assigned any meaningful measure. Such sets are constructed to shed light on the notions of length, area and volume in formal set theory....

.
• Cosets are central in the definition of the transfer
Transfer (group theory)
In mathematics, the transfer in group theory is a group homomorphism defined given a group G and a subgroup of finite index H, which goes from the abelianization of G to that of H.-Formulation:...

.
• Cosets are important in computational group theory. For example Thistlethwaite's algorithm for solving Rubik's Cube
Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...

relies heavily on cosets.
In the field of coding theory, a coset leader is defined as a word of minimum weight in any particular coset - that is, a word with the lowest amount of non-zero entries...

s are used in decoding received data in Linear error-correcting codes
Linear code
In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...

.

• Double coset
Double coset
In mathematics, an double coset in G, where G is a group and H and K are subgroups of G, is an equivalence class for the equivalence relation defined on G by...

• Heap
Heap (mathematics)
In abstract algebra, a heap is a mathematical generalisation of a group. Informally speaking, a heap is obtained from a group by "forgetting" which element is the unit, in the same way that an affine space can be viewed as a vector space in which the 0 element has been "forgotten"...

• Lagrange's theorem
Lagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....

• Quotient group
Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...

• Coset enumeration
Coset enumeration
In mathematics, coset enumeration is the problem of counting the cosets of a subgroup H of a group G given in terms of a presentation. As a by-product, one obtains a permutation representation for G on the cosets of H...