\documentclass[12pt]{article}



\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{patterns}
\usepackage{mathabx}
\usepackage{stmaryrd}
\usepackage{shuffle}


\usepgflibrary{arrows}





\newtheorem{theorem}{Theorem}[section]
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem*{example}{Example}
\newtheorem*{examples}{Examples}
\newtheorem*{remark}{Remark}
\newtheorem*{remarks}{Remarks}

\numberwithin{equation}{section}

\setlength{\evensidemargin}{1in}
\addtolength{\evensidemargin}{-1in}
\setlength{\oddsidemargin}{1in}
\addtolength{\oddsidemargin}{-1in}
\setlength{\topmargin}{1in}
\addtolength{\topmargin}{-1.5in}

\setlength{\textwidth}{16.5cm}
\setlength{\textheight}{23cm}


%Special Letters

\newcommand{\CC}{\mathbb{C}} 
\newcommand{\FF}{\mathbb{F}}  
\newcommand{\KK}{\mathbb{K}}
\newcommand{\QQ}{\mathbb{Q}}  
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}

\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}} 
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}} 
\newcommand{\cE}{\mathcal{E}} 
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}  
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}

\newcommand{\fkg}{\mathfrak{g}}
\newcommand{\fkh}{\mathfrak{h}}
\newcommand{\fkn}{\mathfrak{n}}
\newcommand{\fksl}{\mathfrak{sl}}
\newcommand{\fku}{\mathfrak{u}}
\newcommand{\fkS}{\mathfrak{S}}
\newcommand{\fkX}{\mathfrak{X}}
\newcommand{\fkut}{\mathfrak{ut}}
\newcommand{\fkl}{\mathfrak{l}}
\newcommand{\fkc}{\mathfrak{c}}
\newcommand{\fkp}{\mathfrak{p}}
\newcommand{\fkr}{\mathfrak{r}}

\newcommand{\bg}{\mathbf{g}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\bm}{\mathbf{m}}
\newcommand{\bM}{\mathbf{M}}
\newcommand{\bN}{\mathbf{N}}
\newcommand{\bp}{\mathbf{p}}




%Math Roman

\newcommand{\ad}{\mathrm{ad}} 
\newcommand{\tr}{\mathrm{tr}} 
\newcommand{\Hom}{\mathrm{Hom}} 
\newcommand{\End}{\mathrm{End}} 
\newcommand{\Aut}{\mathrm{Aut}}
\newcommand{\Ind}{\mathrm{Ind}}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\ind}{\mathrm{ind}}  
\newcommand{\Res}{\mathrm{Res}} 
\newcommand{\Inf}{\mathrm{Inf}} 
\newcommand{\ch}{\mathrm{ch}}
\newcommand{\Irr}{\mathrm{Irr}}
\newcommand{\Resf}{\mathrm{Resf}}
\newcommand{\wt}{\mathrm{wt}}
\newcommand{\Indf}{\mathrm{Indf}}
\newcommand{\sh}{\mathrm{sh}}
\newcommand{\hgt}{\mathrm{ht}}
\newcommand{\diag}{\mathrm{diag}}
\newcommand{\Card}{\mathrm{Card}}
\newcommand{\Tr}{\mathrm{Tr}}
\newcommand{\btr}{\mathrm{btr}}
\newcommand{\Id}{\mathrm{Id}}
\newcommand{\im}{\mathrm{im}}
\newcommand{\LL}{\mathrm{LL}}
\newcommand{\RL}{\mathrm{RL}}
\newcommand{\UT}{\mathrm{UT}}
\newcommand{\SInd}{\mathrm{SInd}}
\newcommand{\Def}{\mathrm{Def}}
\newcommand{\pack}{\mathrm{pack}}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\mt}{\mathrm{mt}}
\newcommand{\rst}{\mathrm{rst}}
\newcommand{\io}{\mathrm{io}}
\newcommand{\character}{\mathrm{char}}
\newcommand{\st}{\mathrm{st}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\Coeff}{\mathrm{Coeff}}
\newcommand{\nst}{\mathrm{nst}}
\newcommand{\cl}{\mathrm{cf}}
\newcommand{\scl}{\mathrm{scf}}
\newcommand{\scf}{\mathrm{scf}}
\newcommand{\Stab}{\mathrm{Stab}}
\newcommand{\Ext}{\mathrm{Ext}}
\newcommand{\cf}{\mathrm{cf}}
\newcommand{\std}{\mathrm{std}}


%Size

\newcommand{\dd}{\displaystyle}
\newcommand{\scs}{\scriptstyle}
\newcommand{\scscs}{\scriptscriptstyle} 


%Var Variables

\newcommand{\vphi}{\varphi} 
\newcommand{\veps}{\varepsilon} 


%Miscellaneous

\newcommand{\spanning}{\textnormal{-span}}
\newcommand{\One}{{1\hspace{-.14cm} 1}}
\newcommand{\one}{{1\hspace{-.11cm} 1}}
\newcommand{\entryr}[1]{\sss{\overrightarrow{\underset{\circ}{#1}}}}
\newcommand{\entryl}[1]{\sss{\underleftarrow{\overset{\circ}{#1}}}}
\newcommand{\larc}[1]{\hspace{-.4ex}\overset{#1}{\frown}\hspace{-.4ex}}
\newcommand{\slarc}[1]{\overset{#1}{\frown}}
\def\adots{\mathinner{\mkern2mu\raise0pt\hbox{.}  % antidiagonal dots
\mkern2mu\raise4pt\hbox{.}\mkern1mu
\raise7pt\vbox{\kern7pt\hbox{.}}\mkern1mu}}

\newcommand{\pol}{\mathrm{pol}}



\makeatletter
\renewcommand{\@makefnmark}{\mbox{\textsuperscript{}}}
\makeatother


\allowdisplaybreaks[1]


\begin{document}
\begin{center} {\Large \textbf{
Worksheet 3: Symmetric groups}}
\end{center}

\noindent Recall, that a symmetry is a bijection on a set that respects some structure that we care about.  The symmetric groups are the ``largest" group of symmetries for sets.  Specifically, for $n\in \ZZ_{\geq 1}$, let
$$S_n=\{w:\{1,2,\ldots, n\}\rightarrow \{1,2,\ldots, n\}\mid \text{$w$ is a bijection}\}.$$
We typically refer to the elements of $S_n$ as \emph{permutations}.

\begin{enumerate}
\item[\textbf{1.}] What is the order of $S_n$?
\item[2.] Is $S_n$ abelian?
\end{enumerate}

\noindent Given an element $w\in S_n$, we can encode the information of this function into cycles, giving its \emph{cycle decomposition}.  For example, 
$$\begin{array}{ccc} 
1 & \mapsto & 3\\
2 & \mapsto & 12\\
3 & \mapsto &  8\\
4 & \mapsto & 2\\
5 & \mapsto & 5\\
6 & \mapsto &  10\\
7 & \mapsto & 9\\
8 & \mapsto & 1\\
9 & \mapsto &  7\\
10 & \mapsto & 6\\
11 & \mapsto & 4\\
12 & \mapsto &  11\\
\end{array}
\quad \text{has cycle decomposition}\quad
\begin{tikzpicture}[baseline=-.1cm]
\foreach \x/\n in {{.5}/{(},1/{1},2/{3},3/{8},3.5/{)}}
	\node (\n) at (\x/2,0) {\n};
\foreach \x in {1.5,2.5}
	\node at (\x/2,-.2) {,};
\foreach \x/\n in {{4}/{(},4.5/{2},5.5/{12},6.5/{11},7.5/{4},8/{)}}
	\node (\n) at (\x/2,0) {\n};
\foreach \x in {5,6,7}
	\node at (\x/2,-.2) {,};
\foreach \x/\n in {{8.5}/{(},9/{5},9.5/{)}}
		\node (\n) at (\x/2,0) {\n};
\foreach \x/\n in {{10}/{(},10.5/{6},11.5/{10},12/{)}}
	\node (\n) at (\x/2,0) {\n};
\foreach \x in {11}
	\node at (\x/2,-.2) {,};
\foreach \x/\n in {{12.5}/{(},13/{7},14/{9},14.5/{)}}
	\node (\n) at (\x/2,0) {\n};
\foreach \x in {13.5}
	\node at (\x/2,-.2) {,};
\foreach \x/\y in {1/3,3/8,2/12,12/11,11/4,6/10,7/9}
	\draw[->] (\x)  to  [in=105, out=75] (\y);
\foreach \x/\y in {8/1,4/2,10/6,9/7}
	\draw[->] (\x)  to [in=-75, out=-105] (\y);
\end{tikzpicture}.
$$
\begin{enumerate}
\item[3.]  Compute the product $(1,5,4)(2,3)\circ (1)(2,5)(3,4)$.
\item[\textbf{4.}]  What is the order of a permutation $w\in S_n$ is based on its cycle decomposition?
\item[5.] How do you find the inverse of a permutation in cycle decomposition?
\item[\textbf{6.}] Find an explicit copy of $D_n$ sitting inside $S_n$ (ie. what should $r$ and $s$ be?).

\end{enumerate}

\noindent A \emph{cycle} in $w\in S_n$ is a sequence $(i_1,\ldots, i_\ell)$ such that 
$$w(i_1)=i_2,\ w(i_2)=i_3,\ldots, w(i_\ell)=i_1.$$
We call the integer $\ell$ the \emph{length} of the cycle.
A \emph{transposition} $w\in S_n$ is a permutation with all cycles of length 1 except one unique cycle of length 2 (we usually omit the 1-cycles from the cycle decomposition).

\begin{enumerate}
\item[7.] What is the order of a transposition?
\item[\textbf{8.}] Show that every permutation can be written as a product of transpositions.
\end{enumerate}  

\newpage

\section*{Group assignment, due September 20, 2019}

\noindent This assignment finds $D_n$ as a subgroup of $S_n$.  Give a description of how this works.  You should include
\begin{enumerate}
\item Explicit permutations in $S_n$ that realize $r,s\in D_n$, including their cycle decompositions.
\item Find a second different copy of $D_n$ in $S_n$.  What is the difference in terms of symmetries of a polygon implied by your choice?
\item Compute the intersection between the two copies you found.
\end{enumerate}

\end{document}
