After proving that double cosets are equivalence classes, we now count their elements. The ordinary coset formula says that every left or right coset of a subgroup has the same size as the subgroup. A double coset has two subgroups acting at once, so the count is more subtle. The repeated representations of an element $h\circ a\circ k$ are controlled by the subgroup $H\cap aKa^{-1}$. In this lecture, we prove the double coset cardinality formula and use it to compute examples. :::definition[Conjugate Subgroup] Let $(G,\circ)$ be a group and let $K$ be a subgroup of $G$. For $a\in G$, the $conjugate subgroup$ of $K$ by $a$ is the subset $$\begin{equation*} aKa^{-1}=\{a\circ k\circ a^{-1}:k\in K\}. \end{equation*}$$ ::: :::lemma Let $(G,\circ)$ be a group and let $K$ be a subgroup of $G$. If $a\in G$, then $aKa^{-1}$ is a subgroup of $G$. ::: :::proof Given that $(G,\circ)$ is a group, $K$ is a subgroup of $G$, and $a\in G$. To prove that $aKa^{-1}$ is a subgroup of $G$. Since $e\in K$, we get $$\begin{align*} a\circ e\circ a^{-1} &=a\circ a^{-1}\\ &=e. \end{align*}$$ Therefore $$\begin{equation*} e\in aKa^{-1}. \end{equation*}$$ Let $x,y\in aKa^{-1}$. Then there exist $k_1,k_2\in K$ such that $$\begin{equation*} x=a\circ k_1\circ a^{-1} \end{equation*}$$ and $$\begin{equation*} y=a\circ k_2\circ a^{-1}. \end{equation*}$$ Now $$\begin{align*} x\circ y^{-1} &=(a\circ k_1\circ a^{-1})\circ(a\circ k_2\circ a^{-1})^{-1}\\ &=a\circ k_1\circ a^{-1}\circ a\circ k_2^{-1}\circ a^{-1}\\ &=a\circ k_1\circ k_2^{-1}\circ a^{-1}. \end{align*}$$ Since $K$ is a subgroup of $G$ and $k_1,k_2\in K$, we get $$\begin{equation*} k_1\circ k_2^{-1}\in K. \end{equation*}$$ Therefore $$\begin{equation*} x\circ y^{-1}\in aKa^{-1}. \end{equation*}$$ By the subgroup test, $aKa^{-1}$ is a subgroup of $G$. Hence, $aKa^{-1}$ is a subgroup of $G$. $\square$ ::: :::theorem Let $(G,\circ)$ be a group and let $H$ and $K$ be finite subgroups of $G$. If $a\in G$, then $$\begin{equation*} |HaK|=\frac{|H||K|}{|H\cap aKa^{-1}|}. \end{equation*}$$ ::: :::proof Given that $(G,\circ)$ is a group, $H$ and $K$ are finite subgroups of $G$, and $a\in G$. To prove that $$\begin{equation*} |HaK|=\frac{|H||K|}{|H\cap aKa^{-1}|}. \end{equation*}$$ Define $f:H\times K\to HaK$ by $$\begin{equation*} f(h,k)=h\circ a\circ k \end{equation*}$$ for all $h\in H$ and $k\in K$. By the definition of $HaK$, the map $f$ is onto. Fix $h\in H$ and $k\in K$. Suppose $$\begin{equation*} f(h_1,k_1)=f(h,k). \end{equation*}$$ Then $$\begin{align*} h_1\circ a\circ k_1=h\circ a\circ k &\implies h^{-1}\circ h_1\circ a\circ k_1=a\circ k\\ &\implies h^{-1}\circ h_1\circ a=a\circ k\circ k_1^{-1}\\ &\implies h^{-1}\circ h_1=a\circ k\circ k_1^{-1}\circ a^{-1}. \end{align*}$$ Let $$\begin{equation*} t=h^{-1}\circ h_1. \end{equation*}$$ Then $t\in H$. Also $$\begin{equation*} t=a\circ k\circ k_1^{-1}\circ a^{-1}. \end{equation*}$$ Since $k\circ k_1^{-1}\in K$, we get $$\begin{equation*} t\in aKa^{-1}. \end{equation*}$$ Therefore $$\begin{equation*} t\in H\cap aKa^{-1}. \end{equation*}$$ From $t=h^{-1}\circ h_1$, we get $$\begin{equation*} h_1=h\circ t. \end{equation*}$$ Since $t\in aKa^{-1}$, there exists $u\in K$ such that $$\begin{equation*} t=a\circ u\circ a^{-1}. \end{equation*}$$ From $$\begin{equation*} t=a\circ k\circ k_1^{-1}\circ a^{-1}, \end{equation*}$$ we get $$\begin{align*} a\circ u\circ a^{-1}=a\circ k\circ k_1^{-1}\circ a^{-1} &\implies u=k\circ k_1^{-1}\\ &\implies k_1=u^{-1}\circ k. \end{align*}$$ Since $t=a\circ u\circ a^{-1}$, we have $$\begin{equation*} u=a^{-1}\circ t\circ a. \end{equation*}$$ Therefore $$\begin{equation*} k_1=(a^{-1}\circ t^{-1}\circ a)\circ k. \end{equation*}$$ Thus every preimage of $f(h,k)$ has the form $$\begin{equation*} (h\circ t,\;(a^{-1}\circ t^{-1}\circ a)\circ k) \end{equation*}$$ for some $t\in H\cap aKa^{-1}$. Conversely, let $t\in H\cap aKa^{-1}$. Then $h\circ t\in H$. Since $t\in aKa^{-1}$, we get $$\begin{equation*} a^{-1}\circ t^{-1}\circ a\in K. \end{equation*}$$ Therefore $$\begin{equation*} (a^{-1}\circ t^{-1}\circ a)\circ k\in K. \end{equation*}$$ Now $$\begin{align*} f(h\circ t,\;(a^{-1}\circ t^{-1}\circ a)\circ k) &=(h\circ t)\circ a\circ(a^{-1}\circ t^{-1}\circ a)\circ k\\ &=h\circ t\circ t^{-1}\circ a\circ k\\ &=h\circ e\circ a\circ k\\ &=h\circ a\circ k\\ &=f(h,k). \end{align*}$$ Therefore every element of $HaK$ has exactly $$\begin{equation*} |H\cap aKa^{-1}| \end{equation*}$$ preimages under $f$. Since $$\begin{equation*} |H\times K|=|H||K|, \end{equation*}$$ we get $$\begin{align*} |H||K| &=|HaK||H\cap aKa^{-1}|. \end{align*}$$ Therefore $$\begin{equation*} |HaK|=\frac{|H||K|}{|H\cap aKa^{-1}|}. \end{equation*}$$ Hence, $$\begin{equation*} |HaK|=\frac{|H||K|}{|H\cap aKa^{-1}|}. \end{equation*}$$ $\square$ ::: The cardinality formula comes from counting how many pairs $(h,k)\in H\times K$ produce the same element of $HaK$. In an additive cyclic group, the conjugate subgroup $aKa^{-1}$ behaves like $K$, so the overlap is $H\cap K$. Enter finite subsets $H$ and $K$ in $\mathbb{Z}_n$, and the preview groups all pairs $(h,k)$ by the value of $h+a+k$. Large groups of repeated outputs show why $|H||K|$ must be divided by an intersection size. The displayed comparison connects the formula to the actual computed set. :::scientific-preview[Preimage Counting Explorer]