\documentclass[11pt,twoside]{amsart}
\usepackage{amssymb, amsmath, enumerate, palatino, hyperref, xypic, mathabx, epsfig}

%%% Theorem environments %%%
\theoremstyle{remark}
\newtheorem{prob}{Problem}
%%%%%%%%%%%%%%%%%%

%%% Macros %%%%%%%%%%%
\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}

\newcommand{\normal}{\trianglelefteq}
\newcommand{\ul}{\underline}
\newcommand{\action}{\mathrel{\reflectbox{$\righttoleftarrow$}}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\Inn}{\operatorname{Inn}}
\newcommand{\Out}{\operatorname{Out}}
\newcommand{\GSet}{G\text{-}\operatorname{Set}}
%%%%%%%%%%%%%%%%%%

\title{Math 332: Homework 4}
%\author{Your name here --- delete the % at the start of the line}
\date{23.II.15}

\begin{document}
\maketitle

\begin{prob}
Let $\ul{3} = \{1,2,3\}$ and let $S_3$ act on $\ul{3}^2 = \ul{3}\times\ul{3}$ via $\sigma\cdot (i,j) = (\sigma(i),\sigma(j))$.
\begin{enumerate}[(a)]
\item Find the orbits of $S_3$ on $\ul{3}^2$.
\item For each $\sigma\in S_3$ find the cocycle decomposition of $\sigma$ under this action.  (\emph{I.e.}, the action affords a permutation representation $S_3\to S_{\ul{3}^2}\cong S_9$ where the final isomorphism is given by choosing a labelling by $\ul{9}$ of the elements of $\ul{3}^2$.  Find the cycle decomposition of the image of each elements of $S_3$ in $S_9$.)
\item For each orbit $\mathcal{O}\subset \ul{3}^2$ of $S_3\action \ul{3}^2$, pick some $a\in \mathcal{O}$ and find the stabilizer of $a$ in $S_3$.
\end{enumerate}
\emph{Bonus}: Can you generalize any of this to $S_n\action \ul{n}^2$?
\end{prob}

\begin{prob}[Double your cosets, double your fun]
Let $H,K\le G$ be subgroups of a group $G$.  For each $x\in G$ define the $HK$ \emph{double coset} of $x$ in $G$ to be
\[
  HxK = \{hxk\mid h\in H,k\in K\}.
\]
\begin{enumerate}[(a)]
\item  Let $H$ act by left multiplication on the set of left cosets of $K$ (\emph{i.e.} $H\action G/K$ via left multiplication) and let $\mathcal{O}$ be the orbit of $xK$ under this action.  Prove that
\[
  HxK = \bigcup_{gK\in \mathcal{O}} gK.
\]
\item Prove that $HxK$ can also be written as a union of right cosets of $H$.
\item Show that the set of $HK$ double cosets partitions $G$.
\item Prove that
\[
  |HxK| = |K|\cdot [H:H\cap xKx^{-1}] = |H|\cdot [K:K\cap x^{-1}Hx].
\]
\end{enumerate}
\end{prob}

\begin{prob}
Use the left regular representation of $Q_8$ (\emph{i.e.} the permutation representation of $Q_8\action Q_8$ via left multiplication) to produce two elements of $S_8$ which generate a subgroup of $S_8$ isomorphic to the quaternion group $Q_8$.
\end{prob}

\begin{prob}
Find all conjugacy classes and their sizes in the following groups:
\begin{enumerate}[(a)]
\item $D_8$
\item $Q_8$
\item $A_4$
\item $S_3\times S_3$.
\end{enumerate}
\end{prob}

\begin{prob}
Find all finite groups which have exactly two conjugacy classes.  \emph{Bonus}:  Exactly three conjugacy classes?  \emph{Hint}: The class equation.
\end{prob}

\begin{prob}
Let $G$ be a group.  If $\sigma\in \Aut(G)$ and $\varphi_g$ is conjugation by $g$, prove that $\sigma \varphi_g \sigma^{-1} = \varphi_{\sigma(g)}$.  Deduce that $\Inn(G)\normal \Aut(G)$.  (The group $\Aut(G)/\Inn(G)$ is called the \emph{outer automorphism group} of $G$ and is denoted $\Out(G)$.)
\end{prob}

\begin{prob}
Let $G = \langle x\rangle$ be a cyclic group of order $n$.  Recall that $\Aut(G)\cong (\ZZ/n\ZZ)^\times$ via the assignment $a\in (\ZZ/n\ZZ)^\times\mapsto \psi_a$, where $\psi_a(x) = x^a$.  For $n=2,3,4,5,6$, write out explicitly what $\psi_a$ does to the elements $1,x,x^2,\ldots,x^{n-1}$ of $G$.
\end{prob}

Fix a group $G$.  Let $\GSet$ denote the collection of \emph{left $G$-sets}, that is, sets $X$ equipped with a left $G$-action $G\action X$.  A \emph{$G$-equivariant map} of $G$-sets (or just \emph{$G$-map} for short) is a function $f:X\to Y$ between $G$-sets such that $f(g\cdot x) = g\cdot f(x)$ for all $g\in G$, $x\in X$.  A function between $G$-sets is a \emph{$G$-isomorphism} if it is a bijective $G$-map.  Two $G$-sets $X$, $Y$ are \emph{$G$-isomorphic} if there exists a $G$-isomorphism $X\to Y$; in this case, we write $X\cong_G Y$.  It is easy to check that $\cong_G$ is an equivalence relation on $\GSet$ (do so!).

The following two problems give us a way to think about $G$-isomorphism classes in $\GSet$.  By the end of Problem \ref{prob:decomp} we will see that every $G$-set $X$ can be written (up to $G$-isomorphism) as a disjoint union
\[
  X \cong_G \coprod_{i\in I}G/H_i
\]
where $\{H_i\mid i\in I\}$ is a collection (possibly with redundancy) of subgroups $H_i\le G$.  (Of course, $G\action G/H_i$ via $g\cdot xH_i = (gx)H_i$ for $g,x\in G$.)  If you complete the optional Problem \ref{prob:subconj}, you will find out which coset $G$-sets $G/H$ are $G$-isomorphic to each other, thus completely settling the problem of $G$-isomorphism classes in $\GSet$ (each $G$-isomorphism class is determined by a list [with multiplicity] of conjugacy classes of subgroups of $G$ up to permutation).  In fact, if you return to Problem \ref{prob:subconj} after you've learned what a \emph{category} is, you will discover that you now know the structure of the category of $G$-sets.

\begin{prob}\label{prob:orbit-stab}
Prove the \emph{orbit-stabilizer theorem}: Let $X$ be a $G$-set and for $x\in X$ let $Gx=\{g\cdot x\mid g\in G\}$ denote the orbit of $x$ under $G$. Then $G/G_x \cong_G Gx$ via $gG_x\mapsto g\cdot x$.  You are welcome to proceed via the following outline:
\begin{enumerate}[(a)]
\item Show that if $H\le G$ and $G\action G$ via left multiplication, then a $G$-map $F:G\to X$ extends to a $G$-map $\bar{F}:G/H\to X$ given by $\bar{F}(gH) = F(g)$ if and only if $F(h) = F(1)$ for all $h\in H$.
\item Use (a) to show that $f:G/G_x\to Gx$ given by $f(gG_x) = g\cdot x$ is well-defined.
\item Show that $f$ is bijective.  (Surjective should be easy; injective requires a slightly more substantial argument.)
\end{enumerate}
\end{prob}
\begin{proof}
\begin{enumerate}[(a)]
\item First suppose that $F(h) = F(1)$ for all $h\in H$.  We must show that $F(g) = F(g')$ whenever $g,g'\in gH$.  Since $g'\in gH$, $g' = gh$ for some $h\in H$.  Thus $F(g') = F(gh) = gF(h) = gF(1) = F(g)$, as desired.  (Here we have used the fact that $F(g_1g_2) = g_1F(g_2)$ for all $g_1,g_2\in G$ twice.)

Now suppose that $\bar{F}(gH) = F(g)$ is well-defined.  Then $F(g)=F(gh)$ for all $g\in G$, $h\in H$.  In particular, if $g=1$, we get $F(1) = F(h)$ for all $h\in H$, as desired.

\vspace{1em}

\noindent \emph{Parts (b) and (c) are still up to you!}
\end{enumerate}
\end{proof}

\begin{prob}\label{prob:decomp}
Let $G\action X$ be a set $X$ with a left $G$-action.  Show that the orbits of elements of $X$ partition $X$.  Now assume $X\in \GSet$ and use the orbit-stabilizer theorem of Problem \ref{prob:orbit-stab} to show that $X$ is $G$-isomorphic to a disjoint union of $G$-sets of the form $G/H$, $H\le G$.  (Here $G/H$ has the obvious left $G$-action.)
\end{prob}

\begin{prob}[\emph{Bonus} -- the category of $G$-orbits]\label{prob:subconj}
Let $H,K\le G$ be subgroups of a group $G$.  Prove the following statements:
\begin{enumerate}[(a)]
\item There exists a $G$-map $G/H\to G/K$ if and only if $H$ is subconjugate to $K$.  (Here \emph{subconjugate} means that $H$ is conjugate to a subgroup of $K$, \emph{i.e.}, there exists $x\in G$ such that $x^{-1}Hx\le K$.)
\item Every $G$-map $G/H\to G/K$ has the form $R_x:gH\mapsto gxK$ where $x\in G$ such that $x^{-1}Hx\le K$.
\item The maps $R_x=R_y$ if and only if $x^{-1}y\in K$.
\item The $G$-sets $G/H$ and $G/K$ are $G$-isomorphic if and only if $H$ and $K$ are conjugate in $G$.
\end{enumerate}
\end{prob}

We conclude with a cute and useful application of Problem \ref{prob:orbit-stab}.

\begin{prob}
Suppose $G$ is a finite group and $X$ is a finite $G$-set.  Use the orbit-stabilizer theorem (Problem \ref{prob:orbit-stab}) and Lagrange's theorem to prove that for all $x\in X$,
\[
  |Gx| = \frac{|G|}{|G_x|}.
\]
\end{prob}

\end{document}