\documentclass[11pt]{article} % Define the document type. The 11pt refers to font size.

% Include packages required to compile document:

\usepackage{amssymb, amsthm, amsmath} % These packages are used for the basic math symbols and environments.
\usepackage{enumerate} % This package is used to provide various types of numbering for lists.
\usepackage[margin=1.25in]{geometry} % This is to set wide margins, so there is room to leave comments
\usepackage[parfill]{parskip} % This provides formatting for paragraphs so that there are no indents and paragraphs are separated by a line skip.
\usepackage[pdftex,colorlinks=true,urlcolor=blue]{hyperref}
% You may need to add additional packages depending on the commands you want to use.
\usepackage{graphicx}
%%%%%%%%%%%%%%%%%%%%
% User defined commands:

\newcommand{\br}{\mathbb R} % this is the symbol for the real numbers.  mathbb is the "blackboard bold" font
\newcommand{\bz}{\mathbb Z} % integers
\newcommand{\bq}{\mathbb Q} % rationals
\newcommand{\bn}{\mathbb N} % natural numbers

\newcommand{\co}{\colon\thinspace} % this is a good way to write functions, i.e instead of $f: X \to Y$, you would write $f\co X \to Y$.  It looks nicer.

% You may add shortcuts for any commands you find yourself using frequently.  

\DeclareMathOperator{\ord}{ord} % This command lets you declare math operators.  Some built in operators are \sin for sine and \cos for cosine.  This makes the operators appear nicely in the math environment.  If I wanted to make the sine operator myself, it would look like \DeclareMathOperator{\sin}{sine}.  

% Ender user defined commands
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% These establish different environments for stating Theorems, Lemmas, Remarks, etc.

\newtheorem{Thm}{Theorem}
\newtheorem{Prop}[Thm]{Proposition}
\newtheorem{Lem}[Thm]{Lemma}
\newtheorem{Cor}[Thm]{Corollary}

\theoremstyle{definition}
\newtheorem{Def}[Thm]{Definition}

\theoremstyle{remark}
\newtheorem{Rem}[Thm]{Remark}
\newtheorem{Ex}[Thm]{Example}

\theoremstyle{definition}
\newtheorem{Exercise}{Exercise}
\newtheorem{ExGraded}[Exercise]{*Exercise}
\newtheorem{ExChallenge}[Exercise]{**Exercise}

\newenvironment{Solution}{\noindent{\it Solution.}}{\qed}

%End environments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Now we're ready to start
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

% This is for the title
{\Large {\bf Homework 7}} \hfill MATH 301/601 \\
{Due Wednesday, March 27, 2024} \\[-2mm]
\line(1,0){470}

\medskip

{\bf Instructions.} \textit{Read the appropriate homework guide (\href{http://qc.edu/~nvlamis/301S24/Homework_Guide_301.pdf}{Homework Guide for 301} or \href{http://qc.edu/~nvlamis/301S24/Homework_Guide_601.pdf}{Homework Guide for 601}) to make sure you understand how to successfully complete the assignment. 
All claims must be sufficiently justified. }



\medskip
\begin{Exercise}
Complete the following exercises from \href{http://abstract.ups.edu/aata/permute-exercises.html}{Section~5.4} in the course textbook:

\# 7, 8, 9, 11, 14, 18,  23, \textbf{*25}, 37(a,b)

\end{Exercise}

\medskip
\begin{Exercise}
Let \( n \in \bn \).
\begin{enumerate}[(a)]
\item Prove that \( A_n \) is a subgroup of \( S_n \).
\item Explain why the subset of odd permutations in \( S_n \) is not a subgroup of \( S_n \). 
\end{enumerate}
\end{Exercise}

\medskip
\begin{ExGraded}
From a previous homework exercise, \( |S_4| = 4! = 24 \). 
Show that for any divisor \( d \) of 24 there exists a subgroup \( H \) such that \( |H| = d \). 
\end{ExGraded}

\medskip
\begin{ExGraded}
Let \( \Gamma = (V,E) \) be the graph with \( V = \bz \) and \( (m,n) \in \bz \) if and only if \( |m-n| = 1 \). 
So, \( \Gamma \) is just the number line (a portion of which is drawn here):
\begin{figure}[h]
\centering
\includegraphics{numberline}
\end{figure} 

The \emph{infinite dihedral group}, denoted \( D_\infty \), is the automorphism group of the graph \( \Gamma \).
Let \( \tau, \rho \in D_\infty \) be given by \( \tau(n) = n+1 \) and \( \rho(n) = -n \) for \( n \in \bz \). 
\begin{enumerate}[(a)]

\item For \( k \in \bz \), write down a formula for \( \tau^k \). 
\item Prove that if \( f \in D_\infty \) such that \( f(0) = 0 \) and \( f(1) = 1 \), then \( f \) is the identity. 
(Hint: Let's first focus on the natural numbers.  Use strong induction: Let \( k \in \bn \smallsetminus \{1\} \). Suppose that \( f(j) = j \) for all \( 0\leq j < k \) and prove that \( f(k) = k \). A similar argument works for the negative integers.)
\item Prove that every element of \( D_\infty \) can be written as either \( \tau^k \) or \( \tau^k  \rho \) for some \( k \in \bz \). (Hint: let \( f \in D_\infty \).  Use a power of \( \tau \) to get \( f(0) \) back to \( 0 \), and then use \( \rho \) to get 1 back to itself if necessary.)
\end{enumerate}
\end{ExGraded}

\medskip
\begin{ExChallenge}
Let \( \sigma = (1 \,\, 2 \,\, 3 \,\, 4 \,\, 5) \in A_9 \) and \( \tau = ( 5 \,\, 6 \,\, 7 \,\, 8 \,\, 9 ) \in A_9 \). 
Prove that the permutation \( ( 1 \, \, 2 \, \, 3 ) \) can be written as a word in \( \{\sigma, \tau\} \), i.e., there exists \( r \in \bn \) and \( n_1, \ldots, n_r, m_1, \ldots m_r \in \bz \) such that \( ( 1 \, \, 2 \, \, 3 ) = \sigma^{n_1}\tau^{m_1}\sigma^{n_2}\tau^{m_2} \cdots \sigma^{n_r}\tau^{m_r} \). 

(Hint: It will help to visualize the problem.
Look at the figure on the next page.
Imagine \( \sigma \) as a counterclockwise rotation of the left circle and \( \tau \) as a counterclockwise rotation of the right circle.
Imagine playing a game where you are rotating the two circles to get the points in the desired position.
Record the moves you take.)

(From Exercise 5 you should feel confident  in the fact that every 3-cycle can be expressed as a word in \( \{\sigma, \tau\} \), and hence by \S5.4 \#25, every permutation in \( A_9 \) can be expressed as a word in \( \sigma \) and \( \tau \)). 
\end{ExChallenge}

\begin{figure}[t]
\centering
\includegraphics{5cycles}
\caption{Visualizing Exercise 5}
\end{figure}

\end{document}

