\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage{cancel}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage{multicol}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{9: Groups}{Due Friday, Week 5}

Do \textbf{three} of the \textbf{six} problems below! 

\begin{enumerate}
\item  When we defined a group in class, we used the following definition:
\begin{defn}
A \textbf{group} $\langle G, \cdot\rangle$ is any set $G$ along with a binary operation $\cdot: G\times G \to G$ that satisfies the following three properties:
\begin{itemize}
\item[i.] \textbf{Left identity}: there is some identity element $e \in G$ such that for any other $g \in G$, we have $e \cdot g = g$.  
\item[ii.] \textbf{Right inverses}: for any $g \in G$, there is some $g^{-1}$ such that $g \cdot g^{-1} = e$, where $e$ is some identity element. 
\item[iii.] \textbf{Associativity}: for any three $a,b,c \in G$, $a \cdot (b \cdot c) = (a \cdot b) \cdot c.$  
\end{itemize}
However, there are additional properties people usually ask for, like the following:
\begin{itemize}
\item[iv.] \textbf{Uniqueness of the identity}: if $e_1, e_2$ are two elements that satisfy the identity property, then $e_1 = e_2$.  
\item[v.] \textbf{Left and right identity}: if $e$ is an identity, then for any $g \in G$, $g \cdot e = e \cdot g = g$.
\item[vi.] \textbf{Left and right inverses}: For any $g \in G$, there is a inverse element $g^{-1} \in G$ such that  $g \cdot g^{-1} = g^{-1} \cdot g = e$, where $e$ is the unique inverse element.
\end{itemize}
On its face, our first definition of a group doesn't look like it necessarily satisfies these three properties!  

In this problem, you are challenged to do exactly one of the following:
\begin{enumerate}
\item Prove that anything satisfying properties i-iii satisfies properties iv-vi.  In other words, using just properties i-iii and logic, show that iv-vi must hold.
\item Prove that properties i-iii \textbf{do not} satisfy properties iv-vi.  Any such proof here would almost surely need to consist of a concrete counterexample, that would satisfy the first 3 properties but fail the other three.
\end{enumerate}
\end{defn}

\item Suppose that $p$ is a prime number.  Prove that $(p-1)! \equiv -1 \mod p$.
\item \begin{definition}
A \textbf{latin square} of order $n$ is a $n \times n$ array filled with $n$ distinct symbols (usually $\{1, \ldots n\}$, but they could be any set of $N$ distinct symbols), such that no symbol is repeated twice in any row or column. 

Here are all of the latin squares of order 2:
\begin{align*}
\begin{array}{|c|c|}\hline
 1 & 2 \\\hline
 2 & 1\\\hline
\end{array}
\quad
\begin{array}{|c|c|c|c}\hline
 2 & 1 \\\hline
 1 & 2\\\hline
\end{array}
\end{align*}
Here is a Latin square of order 4:
\begin{align*}
\begin{array}{|c|c|c|c|}\hline
 2 & 1 &4 & 3\\\hline
 1 & 2 & 3 & 4\\\hline
 3 & 4 & 1 & 2\\\hline
 4 & 3 & 2 & 1 \\\hline
\end{array}
\end{align*}
\end{definition}
\begin{enumerate}
\item Take any finite group $\langle G, \cdot\rangle$ of order $n$.  Make a \textbf{group table} for $G$ (as defined in class/the notes.)  Show that this table is a Latin square of order $n$.
\item Does the converse hold?  That is: is it true that every Latin square corresponds to some group table of some group $G$?  Or is there some Latin square that cannot correspond to any group table of any group?
\end{enumerate}

\item Suppose that $G$ is a set with a binary operation $\cdot$ that has the following properties:
\begin{itemize}
\item \textbf{Associativity.}
\item \textbf{Left cancellation}: For any $a,b,c \in G$, if $a \cdot b = a \cdot c$, then $b = c$.
\item \textbf{Suspicious}\footnote{As always, I made up any particularly strange words.}: There exists some element $a \in G$ such that for any $x \in G$, we have $x^3 = axa$.
\end{itemize}

Show that $G$ is an abelian group.  (Abelian means \textbf{commutative}, which means ``For all $x, y \in G, x\cdot y = y\cdot x$.'')



\item The \textbf{free group} on $n$ generators $a_1, \ldots a_n$, denoted 
\begin{align*}
\langle a_1, \ldots a_n \rangle,
\end{align*}
is the following group:
\begin{itemize}
\item The elements of the group are all of the finite-length strings of the form
\begin{align*}
a_{i_1}^{\pm1}a_{i_2}^{\pm1}a_{i_3}^{\pm1}a_{i_4}^{\pm1}\ldots a_{i_l}^{\pm1}
\end{align*}
where the indices $i_1, \ldots i_l$ are all between $1$ and $n$, with possible repetitions.  
\item We denote the ``string of length zero, the ``empty string,'' with the symbol $e$.
\item Given two strings $s_1, s_2$, we \textbf{concatenate} these two strings into the word $s_1s_2$ by writing the string that consists of the string $s_1$ followed by the string $s_2$.  
\item Finally, if we ever have an $a^{+1}a^{-1}$ or an $a^{-1}a^{+1}$ occurring next to each other in a string, we simply remove those two elements from our string.
\end{itemize}
\begin{enumerate}
\item Prove that this is a group!
\item Consider the free group on one generator, $\langle a \rangle$.  Prove that this group is isomorphic to the integers under addition.
\end{enumerate}
\item In our above discussion, we have primarily defined groups by giving a set and an operation on that set.  There are other ways of defining a group, though! 
\begin{defn} A \textbf{group presentation} is a collection of $n$ generators $a_1, \ldots a_n$ and $m$ words $R_1, \ldots R_m$ from the free group $\langle a_1, \ldots a_n\rangle$, which we write as
\begin{align*}
\langle a_1, \ldots a_n ~|~ R_1 = e, \ldots R_m = e\rangle.
\end{align*}
We associate this presentation with the group defined as follows:
\begin{itemize}
\item Start off with the free group $\langle a_1, \ldots a_n\rangle$.
\item Now, declare that within this free group, the words $R_1, \ldots R_m$ are all equal to the empty string $e$: i.e. if we have any words that contain some $R_i$ as a substring, we can simply ``delete'' this $R_i$ from the word.
\end{itemize}
\end{defn}
\begin{exmp}
Consider the group with presentation
\begin{align*}
\langle a ~|~ a^n = e\rangle,
\end{align*}
where we let $a^n$ denote the string consisting of $n$ $a$'s in a row.  Notice that this is the collection of all words written with one symbol $a$, where we regard $a^n = e$: i.e.\ it's just
\begin{align*}
e, a, a^2, a^3, \ldots a^{n-1}.
\end{align*}
This is because given any string $a^k \in \langle a \rangle$, we have $a^k = a^l$ for any $k \equiv l \mod n$.  This is because we can simply concatenate copies of the strings $a^n, a^{-n}$ as many times as we want without changing a string, as $a^n = e$!
\end{exmp}
\begin{enumerate}
\item Show that $\langle a ~|~ a^n = e\rangle$ is isomorphic to the group given by $\mathbb{Z}/n\mathbb{Z}$ with respect to addition.
\item Describe $D_8$, the collection of symmetries of a square, via a group presentation.  (In other words, create a group with presentation that is isomorphic to $D_8$.)
\end{enumerate}
\end{enumerate}

\end{document}