What is a coset?

Honestly. I just don't understand the word and keep running into highly technical explanations (wikipedia, I'm looking at you!). If somebody would be so awesome as to explain the concept assuming basic knowledge of group theory and high school algebra I would be delighted.

• (Cosets are "basic knowledge of group theory.") What exactly in the Wikipedia article (or any other place you looked up a definition) are you having trouble understanding? – anon Oct 5 '13 at 3:24
• Maybe if somebody gives a concrete example and explains why it is a coset that will help. I am trying to understand exactly why factoring is an example of the abelian hidden subgroup problem – frogeyedpeas Oct 5 '13 at 3:25
• Two comments: (a) even and odd integers in $\Bbb Z$ under addition, (b) I recommend familiarizing yourself with basic group theory before trying to understand any kind of hidden subgroup problem (which is relatively advanced). – anon Oct 5 '13 at 3:27
• When you write two elements of a group next to each other, it is to be understood that the group operation is being performed on those two elements (in the given order). For example, if $2\Bbb Z$ is the set of all even integers, then the coset $1+2\Bbb Z$ is the coset of all integers which are $1$ greater than an even integer, i.e. the odd integers. If $L$ is a subspace of a vector space, then $v+L$ is the set of all vector displaced from an element of $L$ by $v$ (thus, the cosets of $L$ are parallel hyperplanes). And so on. – anon Oct 5 '13 at 3:29
• The sets (that you encountered in high school trigonometry) of the form $$\{x+n\cdot2\pi\mid n\in\Bbb{Z}\}$$ ($x$ is a fixed real number here) are cosets of the additive group $2\pi\Bbb{Z}$ in the bigger additive group of all real numbers. – Jyrki Lahtonen Oct 5 '13 at 4:26

Let's start with a concrete example. Let our group be $\mathbb{Z}$, the integers with addition. There is a subgroup here of even integers, written $2\mathbb{Z}$. This is a subgroup because the sum of even integers is an even integer, and because the number $0$ is even. Since subgroups need to have identity elements, it is important that $0$ is in $2\mathbb{Z}$. Now, the integers also contain $2\mathbb{Z} + 1$, the collection of odd integers. This isn't quite a subgroup, because it doesn't contain an identity element. However, it looks like a shifted copy of the subgroup $2\mathbb{Z}$, which makes sense because it is a shifted copy of $2\mathbb{Z}$ -- we are shifting by adding $1$. What's more, every integer is either even or odd (but not both!), so the (disjoint) union of $2\mathbb{Z}$ with its shifted copy $2\mathbb{Z}+1$ is all of $\mathbb{Z}$.

One thing to observe is that the shift $2\mathbb{Z} + 1$ and $2\mathbb{Z}+3$ both give you the odd integers, so it is wrong to say that every element shifts a subgroup in a unique way.

If we took the subgroup $3\mathbb{Z}$ of multiplies of $3$, we would get two shifts: $3\mathbb{Z} + 1$ and $3\mathbb{Z}+2$. These are all disjoint from one another, they all look very similar, and their union is the entirety of $\mathbb{Z}$.

One more example before we move to generalities. Let $G$ be the group of symmetries of the square, which is a rather common example in group theory. We have a subgroup here of rotational symmetries $H$. $H$ has four elements: rotation by $0$ degrees, rotation by $90$ degrees, rotation by $180$ degrees, and rotation by $270$ degrees. Rotation by $0$ degrees is the identity element. $G$ contains an element $f$ which represents flipping the square upside down. $f$ is not an element of $H$. Suppose you "shift" $H$ by taking every symmetry in $H$ and following it by flipping the square upside down. We would write this $fH$, and this is not a group, since it does not contain the identity element. However, it looks like a shifted subgroup $H$, it has the same number of elements of $H$, it has no overlap with $H$, and $G$ is the union of $H$ and $fH$, because every symmetry is either a rotation or a rotation followed by a flip.

Speaking generally, let $G$ be a group. Given a subgroup $H$, you can shift $H$ by multiplying it by an element $g$ in $G$. If $g$ is also an element of $H$, the shift $gH$ is the same as $H$. But if $g$ is not in $H$, $gH \neq H$, and $gH$ is not a subgroup. The shift $gH$ is called a coset of $H$, and it looks a lot like a copy of $H$. Actually, $H$ is also a coset of $H$, since you can shift by the identity element. Just like every integer was even or odd, if you take all the cosets of $H$ they fill up the entirety of $G$, so you can break up any group into a collection of pieces that look like "shifted copies" of a subgroup.

• I see we had the same idea at about the same time, +1. – Carl Mummert Oct 5 '13 at 12:33
1. Think of $G = \mathbb{R}^2$, and $H = \{(x,x) : x\in \mathbb{R}\}$ be the line $y=x$. Then any coset of $H$ is another line parallel to the line $y=x$. In group theory notation, one would write it as $$(a,b)+H = \{(a,b) + (x,y) : (x,y)\in H\} = \{(x+a,x+b) : x\in \mathbb{R}\}$$

2. Let $G = \mathbb{C}^{\times}$, and $H = \{z\in \mathbb{C}^{\times} : |z| = 1\}$ be the unit circle. Then any coset of $H$ is another circle centred at the origin. Again this would be $$w_0H = \{w_0z : z\in H\} = \{w_0z : |z| = 1 \} = \{w : |w| = |w_0|\}$$

3. Suppose $A$ is an $n\times n$ matrix, and $G = \mathbb{R}^n$. Let $$H = \{x \in G : Ax = 0\}$$ For any $b\in \mathbb{R}^n$, the solution set $$\{y \in \mathbb{R}^n : Ay = b \}$$ is a coset of $H$ (if it is non-empty)

• Generalizing 3., for every group homomorphism $G \to G'$ with kernel $N$, every non-empty fiber is a coset of $N$. – Martin Brandenburg Oct 5 '13 at 11:31
• @MartinBrandenburg : yes, but the purpose of this answer was to give the OP some concrete examples to flesh out the theory. "non-empty fiber" is rather vague when first seeing groups! – Prahlad Vaidyanathan Oct 5 '13 at 11:34

A coset is what you get by taking a subgroup and shifting it by some element of the group.

For example, the line $y = 4x$ is a subgroup of the additive group of the points on the plane. If I shft the line upwards by adding $0\vec i + 1 \vec j$ to every point on the line, I get the line $y = 4x+1$. That is not a subgroup any longer, because it does not contain the identity $0\vec i + 0 \vec j$. But it has the same "shape" as the original subgroup, just shifted away from the origin.

For another example, in the group $\mathbb{Z}_{12}$, with modular addition, let $H$ be the subgroup $\{0,3,6,9\}$. If I shift it by adding $1$ to each element, I get a coset $1 + H = \{1,4,7,10\}$. If I shift it by adding $2$ to each element of $H$ I get the coset $2 + H = \{2,5,8,11\}$. These are not subgroups, because they do not contain $0$, but they have the same "shape" as the original subgroup $H$, in some intuitive sense.

Most of the proofs about cosets use the fact that the original subgroup actually was a subgroup. The coset is usually not a subgroup, but the fact that it came from a subgroup means that it has a similar type of internal structure that you can use to prove things about it.

here's a definition of coset, and some examples and ideas..

Let $N$ be a subgroup of some group $G$. Then, a coset of $N$ is a set of form $xN$, where $x\in G$. That is to say that $xN$ is the set of all elements of G that are of form $ng$ for some $g\in N$. This is the standard definition of a coset.

Consider the integers under addition. This is an Abelian group Clearly, the integers is a subgroup of the intgerers. The coset $n \mathbb{Z}$ consists of all integer multiples of n.

Exercise:

Prove that all cosets of a a subgroup of a finite group $G$ have the same size. Prove that the set of all cosets of a subgroup N in G partition G.

Assuming G is finite, find an expression for the size of G in terms of the number, and size, of cosets.

• I didn't say that N was normal anywhere – RougeSegwayUser Oct 5 '13 at 14:48

Co-sets are used to enumerate the size of a set, when one can not find a single generator. It's kind of like a subset parallel to a subgroup, or a subgroup $\times$ something not in it.

So, if you have $AA = BB = CC = 1$, and $ABA = BAB$ and $BCB = CBC$ and $AC=CA$. This is the tetrahedral group, by the way.

What you do is to generate a set out of $AA = BB = 1$, and $ABA = BAB$. This will generate one face, the six members walk around the centre of the face. It's a subgroup of the set.

Since $C$ is a new step, we can step from any member of the first group with a $C$ step, and then generate the whole subgroup with $A,B$ over this new member. This is not a subgroup as such, but is kind of like 'parallel' to it. You have now created a 'co-set'.

When you finished using a single new member, you have generated all of the co-sets or parallel items of a sub-group, in a larger subgroup. This is repeated until all of the operators of the larger subgroup are found.

Using co-sets is how the size of groups without a simple geometry was found.

• Could you expand on what you mean by "the size"? You say it two times, but I don't follow. – Carl Mummert Oct 5 '13 at 12:33
• The size is the count of members in the group. – wendy.krieger Oct 5 '13 at 12:38

If $H$ is a subgroup of $G$, then you can define a relation on $G$ by setting $$a\sim_H b\qquad\text{if and only if}\qquad ab^{-1}\in H$$ It's a useful exercise in applying group laws proving that $\sim_H$ is an equivalence relation and that the equivalence class of $1\in G$ is $$_{\sim_H}=H$$ This equivalence relation has very pleasant properties; for instance, if $a\in G$, then there is a bijection $\varphi_a\colon H\to [a]_{\sim_H}$ given by $$\varphi_a(x)=xa$$ (prove it). In particular, all equivalence classes are equipotent so, in the finite case, they all have the same number of elements. This bijection shows also that $$[a]_{\sim_H}=\{\,ha:h\in H\,\}=Ha$$ the right coset (somebody calls this a left coset, check with your textbook) determined by $H$ and $a$.

This readily proves Lagrange's theorem: if we denote by $[G:H]$ the number of equivalence classes and $G$ is finite, we have $$|G|=|H|\,[G:H]$$ because we can just count the number of elements in one equivalence class ($H$ or anyone else) and multiply by the number of classes, since they share the number of elements.

There is of course no preference for the right side; one can define $$a\mathrel{_H{\sim}} b\qquad\text{if and only if}\qquad a^{-1}b\in H$$ and prove the same results as before, with the only difference that the map will be $$\psi_a\colon H\to[a]_{_H{\sim}},\quad \psi_a(x)=ax$$ and the equality $$[a]_{_H{\sim}}=aH.$$

In general the two equivalence relations are distinct. They are the same precisely when the subgroup $H$ is normal or, equivalently, one of them is a congruence, that is, for $\sim_H$, from $a\sim_H b$ and $c\sim_H d$ we can deduce $ac\sim_H bd$.

Here's a small finite group example using $G=(\{1,-1,i,-i,j,-j,k,-k\},\cdot)$ where $i^2 =j^2 =k^2 =-1$, $-i=(-1)i,$ $1^2 =(-1)^2 =1$, $ij=-ji=k$, $jk=-kj=i$, and $ki=-ik=j$.

Having a Cayley table helps to see this structure.

$$\begin{array}{r|rrrrrrrr} * & 1 & -1 & i & -i & j & -j & k & -k \\ \hline 1 & 1 & -1 & i & -i & j & -j & k & -k\\ -1 & -1 & 1 & -i & i & -j & j & -k & k\\ i & i & -i & 1 & -1 & k & -k & -j & j\\ -i & -i & i & -1 & 1 & -k & k & j & -j\\ j & j & -j & -k & k & 1 & -1 & i & -i\\ -j & -j & j & k & -k & -1 & 1 & -i & i\\ k & k & -k & j & -j & -i & i & 1 & -1\\ -k & -k & k & -j & j & i & -i & -1 & 1\\ \end{array}$$ Clearly, $H=(\{1,-1\},\cdot)$ is a subgroup. If I multiply all my members of $G$ with the members on the left, $$1\{1,-1\}=\{1,-1\},$$ $$-1\{1,-1\}=\{-1,1\}=\{1,-1\},$$ $$i\{1,-1\}=\{i,-i\},$$ $$-i\{1,-1\}=\{-i,i\}=\{i,-i\}$$ $$j\{1,-1\}=\{j,-j\}$$ $$-j\{1,-1\}=\{-j,j\}=\{j,-j\}$$ $$k\{1,-1\}=\{k,-k\}$$ $$-k\{1,-1\}=\{-k,k\}=\{k,-k\}$$

I can see that my cosets of my subgroup $H$ are $\{1,-1\}, \{i,-i\}, \{j,-j\}$ and $\{k,-k\}$. If I multiply on the right ($Hg$), I think I can convince you without work that the left cosets are equal to the right cosets. In that case, our subgroup is defined as Normal.

Obviously these are not the only cosets I can find, but the cosets are in relation to a particular subgroup. If my subgroup was $N=(\{1,-1,i,-i\},\cdot)$, my cosets would be $\{1,-1,i,-i\}$ and $\{j,-j,k,-k\}$. I hope this helps. Perhaps you could try to find the left and right cosets of the subgroup $(\{1,i\},\cdot)$

If my operation were addition, my cosets would just look like $g+H$ or $H+g$.