%% LyX 2.0.2 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english,british]{article}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{geometry}
\geometry{verbose,tmargin=2cm,bmargin=2cm,lmargin=2cm,rmargin=2cm}
\usepackage{babel}
\usepackage{units}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[all]{xy}
\PassOptionsToPackage{normalem}{ulem}
\usepackage{ulem}
\usepackage[unicode=true]
 {hyperref}
\usepackage{breakurl}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\numberwithin{equation}{section}
\numberwithin{figure}{section}
\numberwithin{table}{section}
\usepackage{enumitem}		% customizable list environments
\newlength{\lyxlabelwidth}      % auxiliary length 
  \theoremstyle{definition}
  \newtheorem*{example*}{\protect\examplename}
  \theoremstyle{remark}
  \newtheorem*{notation*}{\protect\notationname}
 \newcommand\thmsname{\protect\theoremname}
 \newcommand\nm@thmtype{theorem}
 \theoremstyle{plain}
 \newtheorem*{namedtheorem}{\thmsname}
 \newenvironment{namedthm}[1][Undefined Theorem Name]{
   \ifx{#1}{Undefined Theorem Name}\renewcommand\nm@thmtype{theorem*}
   \else\renewcommand\thmsname{#1}\renewcommand\nm@thmtype{namedtheorem}
   \fi
   \begin{\nm@thmtype}}
   {\end{\nm@thmtype}}
\theoremstyle{plain}
\newtheorem{thm}{\protect\theoremname}[section]
  \theoremstyle{definition}
  \newtheorem{defn}[thm]{\protect\definitionname}
  \theoremstyle{plain}
  \newtheorem{lem}[thm]{\protect\lemmaname}
  \theoremstyle{plain}
  \newtheorem{prop}[thm]{\protect\propositionname}
% labeling-like list based on enumitem's description list with
% mandatory second argument (label-pattern):
\newenvironment{elabeling}[2][]%
{\settowidth{\lyxlabelwidth}{#2}
\begin{description}[font=\normalfont,style=sameline,
leftmargin=\lyxlabelwidth,#1]}
{\end{description}}
  \newcounter{casectr}
  \newenvironment{caseenv}
  {\begin{list}{{\itshape\ \protect\casename} \arabic{casectr}.}{%
   \setlength{\leftmargin}{\labelwidth}
   \addtolength{\leftmargin}{\parskip}
   \setlength{\itemindent}{\listparindent}
   \setlength{\itemsep}{\medskipamount}
   \setlength{\topsep}{\itemsep}}
   \setcounter{casectr}{0}
   \usecounter{casectr}}
  {\end{list}}
  \theoremstyle{plain}
  \newtheorem*{ax*}{\protect\axiomname}
  \theoremstyle{definition}
  \newtheorem*{xca*}{\protect\exercisename}
  \theoremstyle{remark}
  \newtheorem*{note*}{\protect\notename}
  \theoremstyle{definition}
  \newtheorem{example}[thm]{\protect\examplename}
  \theoremstyle{plain}
  \newtheorem{cor}[thm]{\protect\corollaryname}
  \theoremstyle{remark}
  \newtheorem*{rem*}{\protect\remarkname}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\xyR}[1]{
 \xydef@\xymatrixrowsep@{#1}}
\newcommand{\xyC}[1]{
  \xydef@\xymatrixcolsep@{#1}}

\makeatother

  \addto\captionsbritish{\renewcommand{\axiomname}{Axiom}}
  \addto\captionsbritish{\renewcommand{\casename}{Case}}
  \addto\captionsbritish{\renewcommand{\corollaryname}{Corollary}}
  \addto\captionsbritish{\renewcommand{\definitionname}{Definition}}
  \addto\captionsbritish{\renewcommand{\examplename}{Example}}
  \addto\captionsbritish{\renewcommand{\exercisename}{Exercise}}
  \addto\captionsbritish{\renewcommand{\lemmaname}{Lemma}}
  \addto\captionsbritish{\renewcommand{\notationname}{Notation}}
  \addto\captionsbritish{\renewcommand{\notename}{Note}}
  \addto\captionsbritish{\renewcommand{\propositionname}{Proposition}}
  \addto\captionsbritish{\renewcommand{\remarkname}{Remark}}
  \addto\captionsbritish{\renewcommand{\theoremname}{Theorem}}
  \addto\captionsenglish{\renewcommand{\axiomname}{Axiom}}
  \addto\captionsenglish{\renewcommand{\casename}{Case}}
  \addto\captionsenglish{\renewcommand{\corollaryname}{Corollary}}
  \addto\captionsenglish{\renewcommand{\definitionname}{Definition}}
  \addto\captionsenglish{\renewcommand{\examplename}{Example}}
  \addto\captionsenglish{\renewcommand{\exercisename}{Exercise}}
  \addto\captionsenglish{\renewcommand{\lemmaname}{Lemma}}
  \addto\captionsenglish{\renewcommand{\notationname}{Notation}}
  \addto\captionsenglish{\renewcommand{\notename}{Note}}
  \addto\captionsenglish{\renewcommand{\propositionname}{Proposition}}
  \addto\captionsenglish{\renewcommand{\remarkname}{Remark}}
  \addto\captionsenglish{\renewcommand{\theoremname}{Theorem}}
  \providecommand{\axiomname}{Axiom}
  \providecommand{\casename}{Case}
  \providecommand{\corollaryname}{Corollary}
  \providecommand{\definitionname}{Definition}
  \providecommand{\examplename}{Example}
  \providecommand{\exercisename}{Exercise}
  \providecommand{\lemmaname}{Lemma}
  \providecommand{\notationname}{Notation}
  \providecommand{\notename}{Note}
  \providecommand{\propositionname}{Proposition}
  \providecommand{\remarkname}{Remark}
  \providecommand{\theoremname}{Theorem}
\providecommand{\theoremname}{Theorem}

\begin{document}
\selectlanguage{english}%
\global\long\def\zz{\mathbb{Z}}
\global\long\def\im{\operatorname{im}}
\global\long\def\re{\operatorname{re}}
\global\long\def\rr{\mathbb{R}}
\global\long\def\cc{\mathbb{C}}
\global\long\def\vv{\mathbb{V}}
\global\long\def\SL{\operatorname{SL}}
\global\long\def\ord{\operatorname{ord}}
\global\long\def\Spec{\operatorname{Spec}}
\global\long\def\qq{\mathbb{Q}}
\global\long\def\pp{\mathbb{P}}
\global\long\def\Hom{\operatorname{Hom}}
\global\long\def\id{\operatorname{id}}
\global\long\def\gcd{\operatorname{gcd}}
\global\long\def\lcm{\operatorname{lcm}}
\global\long\def\Sym{\operatorname{Sym}}
\global\long\def\ff{\mathbb{F}}
\global\long\def\nn{\mathbb{N}}
\global\long\def\hh{\mathbb{H}}
\global\long\def\Ann{\operatorname{Ann}}
\global\long\def\End{\operatorname{End}}
\global\long\def\sgn{\operatorname{sgn}}
 \global\long\def\rk{\operatorname{rk}}
\global\long\def\Br{\operatorname{Br}}
 \global\long\def\Hasse{\operatorname{Hasse}}
\global\long\def\GL{\operatorname{GL}}
\global\long\def\Coll{\operatorname{Col}}
 \global\long\def\Tr{\operatorname{Tr}}
\global\long\def\aa{\mathbb{A}}
\global\long\def\ld{\operatorname{in}_{<}}
\global\long\def\ob{\operatorname{Ob}}
\global\long\def\mor{\operatorname{mor}}
\global\long\def\ext{\operatorname{Ext}}
\global\long\def\tor{\operatorname{Tor}}
\global\long\def\cok{\operatorname{coker}}
\global\long\def\aut{\operatorname{Aut}}
\global\long\def\PSL{\operatorname{PSL}}


\selectlanguage{british}%

\title{Presentation of Groups}


\author{Derek Holt\\
Notes by Florian Bouyer}

\maketitle
\begin{center}
Copyright (C) Bouyer 2013. 
\par\end{center}

\begin{center}
Permission is granted to copy, distribute and/or modify this document 
\par\end{center}

\begin{center}
under the terms of the GNU Free Documentation License, Version 1.3 
\par\end{center}

\begin{center}
or any later version published by the Free Software Foundation; 
\par\end{center}

\begin{center}
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
Texts. 
\par\end{center}

\begin{center}
A copy of the license can be found at \href{http://www.gnu.org/licenses/fdl.html}{http://www.gnu.org/licenses/fdl.html}
\par\end{center}

\tableofcontents{}

\newpage{}


\section{Introduction}


\subsection{Motivation}

This course is about group presentations, $\left\langle X|R\right\rangle $
where $X$ is the set of generators and $R$ the set of relations
which are equations between words in $A^{*}$, with $A=X\cup X^{-1}$.
\begin{example*}
$X=\{x,y\}$ and $R=\{x^{5}=1,y^{2}=1,y^{-1}xy=x^{-1}\}$. Usually
write as $\left\langle x,y|x^{5}=y^{2}=1,y^{-1}xy=x^{-1}\right\rangle $. 
\end{example*}
A presentation $\left\langle X|R\right\rangle $ defines a group,
which is roughly the ``largest group'' which is generated by $X$
such that all equations in $R$ holds in $G$. In the above example
we can show any group $G=\left\langle x,y\right\rangle $ with $x^{5}=y^{2}=1,y^{-1}xy=x^{-1}$
has at most $10$ elements, and dihedral group $D_{10}$ is unique
group of order $10$. So we can say $G\cong D_{10}$ . The advantage
of this way of defining groups:
\begin{enumerate}
\item For many groups, it is the most compact definition, particularly useful
for systematically enumerating small groups.
\item Many groups from algebraic topology arises naturally in this form,
so we need to study them.
\end{enumerate}
Disadvantage: In general it is impossible to analyse a group by a
presentation. For example we cannot decide if $\left\langle X|R\right\rangle $
is finite, trivial or even abelian. It has been proven that there
are no algorithm to decide this. There exist specific presentations
$\left\langle X|R\right\rangle $ with $X,R$ finite for which we
cannot decide whether an element $g\in G$, given as $w\in(X\cup X^{-1})^{*}$
is the identity $1_{G}$ (this is know as the word problem).


\subsection{Preliminaries}
\begin{notation*}
{}
\begin{itemize}
\item If $G$ is a group, $H\subseteq G$ then $H$ is a subset of $G$.
$H\leq G$ then $H$ is a subgroup of $G$. $H\lhd G$ then $H$ is
a normal subgroup of $G$.
\item $C_{k}$ is the cyclic group of order $k$.
\item Infinite cyclic group is $\zz$ (under $+$)
\item $S_{k}$ is the symmetric group of degree $k$ on $\{1,2,\dots,k\}$
\item $A_{k}$ is the alternating group degree $k$
\item $H\leq G,$ $G=\sqcup Hg_{i}$, so $g_{i}$ are right coset representative.
Call $\{g_{i}|i\in I\}$ a \emph{right transversal }of\emph{ }$H$
in $G$.
\item If $H\lhd G$, $\{Hg_{i}|i\in I\}$ forms the quotient group $G/H$.
\item Group homomorphism: $\theta:G\to H$ such that $\theta(g_{1}g_{2})=\theta(g_{1})\theta(g_{2})$
\item Group monomorphism: If $\theta$ is injection if and only if $\ker(\theta)=\{1\}$
\item Group epimorphism: if $\theta$ is surjection, $\im\theta=H$
\item Group isomorphism: $\theta$ bijective
\item Group endomorphism if $G=H$
\item Group automorphism: isomorphism with $G=H$
\item $\mbox{Aut}(G)=\{\theta|\theta:G\to G\mbox{ automorphism \}}$ is
a group under composition
\end{itemize}
\end{notation*}
\begin{namedthm}[The isomorphism Theorem]

\begin{enumerate}
\item Let $\theta:G\to H$ is a homomorphism and $K=\ker(\theta)$. Then
$\overline{\theta}:G/K\to\im\theta$ defined by $\overline{\theta}(gK)=\theta(g)$
is an isomorphism. So $G/K\cong\im\theta$
\item If $M\le G,N\lhd G$ then $MN/N\cong M/(N\cap M)$ \emph{(Recall:
if $A\leq G$ and $B\leq G$ then $AB$ not always a subgroup, but
it is if $A\lhd G$ or $B\lhd G$ and it is normal if $A\lhd G$ and
$B\lhd G$.}
\item If $M\leq N\lhd G$ with $M\lhd G$ then $\frac{G/M}{N/M}\cong G/N$
\end{enumerate}
\end{namedthm}
\begin{proof}
{}
\begin{enumerate}
\item See Algebra II course
\item Define $\theta:M\to MN/N$ by $\theta(m)=mN$. Then $\im\theta=MN/N$
and $\ker(\theta)=M\cap N$. Then the result follows from the 1st
isomorphism theorem (part 1 of this theorem)
\item Define $\theta:G\to\frac{G/N}{N/M}$ by $\theta(g)=(gM)(N/M)$ (i.e.
$G\to G/M\to\frac{G/M}{N/M}$). Then we have $\im\theta=\frac{G/M}{N/M}$
and $\ker\theta=N$. Then the result follows from the 1st isomorphism
theorem.
\end{enumerate}
\end{proof}
\begin{notation*}
(non-standard) If $G$ is a group permutation of $\Omega$ (i.e.,
$G\leq\Sym\Omega$). Given $\alpha\in\Omega$, $g\in G$ then we write
the image of $\alpha$ under $g$ as $\alpha^{g}$ rather than $g(\alpha)$.
This means that $gh$ means $g$ followed by $h$ (not $h$ then $g$)\end{notation*}
\begin{example*}
$\Omega=\{1,2,3,4\}$, $g=(1,2,3)$ and $h=(3,4)$. Then $2^{g}=3,3^{h}=4$
so $2^{gh}=(2^{g})^{h}=4$. Note $gh=(1,2,4,3)$ while $hg=(1,2,3,4)$.
\end{example*}

\subsection{Generators of Groups}

Let $A$ be a set. A \emph{word} over $A$ is a finite string $w=a_{1}a_{2}\dots a_{l}$
with each $a_{i}\in A$. The \emph{length} of $w$ is $l=l(w)=\left|w\right|$.
We allow $l=0$, this is the \emph{empty word}, which we denote by
$\epsilon$. 
\begin{defn}
Let $X\subseteq G$ with $G$ a group. We define \emph{subgroup }$\left\langle X\right\rangle $
of $G$ generated by $X$ in two ways:
\begin{enumerate}
\item $\left\langle X\right\rangle =$intersection of all subgroups of $G$
that contains $X$, i.e., $\left\langle X\right\rangle =\cap_{H\le G,X\subseteq H}H$ 
\item Let $X^{-1}=\{x^{-1}|x\in X\}$. $A=X\cup X^{-1}$. We define $A^{*}$
to be the set of all words over $A$. Elements of $A^{*}$ represent
elements of $G$, it is closed under concatenation and inversion.
So it is a subgroup of $G$. We define $\left\langle X\right\rangle =A^{*}$.
The empty word represents $1_{G}$
\end{enumerate}
\end{defn}
\begin{lem}
The two definition of $\left\langle X\right\rangle $ are equivalent\end{lem}
\begin{proof}
Let $X\subseteq G$. Let $H_{1}$ and $H_{2}$ be $\left\langle X\right\rangle $
according to definition 1. and 2.

If $g\in H_{2}$, then $g=a_{1}a_{2}\dots a_{l}$, $l\geq0$ $a_{i}\in X\cup X^{-1}$
. Then since subgroups are closed under multiplication and inversion,
$g$ is contained in any $H\leq G$ with $X\subseteq H$. Hence $g\in H_{1}$,
i.e., $H_{2}\subseteq H_{1}$.

But $H_{2}$ is a subgroup of $G$ containing $X$, so $H_{1}\subseteq H_{2}$.
Hence $H_{1}=H_{2}$.\end{proof}
\begin{example*}
{}
\begin{enumerate}
\item $G=(\zz,+)$ and $X=\{12,18\}$. Then by definition 2, $\left\langle X\right\rangle =\{12a+18b|a,b\in\zz\}=\left\langle 6\right\rangle =6\zz$ 
\item $G=S_{4}$, $X=\{a,b\}$ with $a=(1,2,3)$ and $b=(2,3,4)$. Now $a,b\in A_{4}$
so $\left\langle X\right\rangle \leq A_{4}$ (by the 1st definition),
and $ab=(1,3)(2,4)$ while $ba=(1,2)(3,4)$ and $abba=(1,4)(2,3)$.
So $\{1,ab,ba,abba\}\leq\left\langle X\right\rangle $ so $4|\left|\left\langle X\right\rangle \right|$
and $3=\left|a\right||\left|\left\langle X\right\rangle \right|$
so $12|\left|\left\langle X\right\rangle \right|,$so $\left\langle X\right\rangle =A_{4}$.
\end{enumerate}
\end{example*}
\newpage{}


\section{Free Groups}

These are groups $\left\langle X|\:\right\rangle $ with $R=\emptyset$
with no relations.

We define them using their principal property. If $V,W$ are vector
spaces, $V$ with basis $B$. Any map $\theta:B\to W$ uniquely determines
a linear map $\theta':V\to W$ with $\theta'(b)=\theta(b)\,\forall b\in B$.
Free groups have a similar property (but all vector spaces have bases,
but not all groups are free)
\begin{defn}
Let $F$ be a group and $X\subseteq F$. Then $F$ is \emph{free}
on $X$ if for any group $G$ and any map $\theta:X\to G$ $\exists!$
homomorphism $\theta':F\to G$ with $\theta'(x)=\theta(x)\,\forall x\in X$,
i.e the diagram
\[
\xymatrix{X\ar[r]^{\theta}\ar[d]_{i} & G\\
F\ar[ur]_{\theta'}
}
\]
commutes. I.e., $\theta$ has a unique \emph{extension $\theta':F\to G$.
}I.e. $\theta=\theta'$ where $i:X\to F$ is the \emph{insertion/inclusion}
map defined by $i(x)=x\,\forall x\in X$
\end{defn}
We will prove existence later, first we prove a few properties.
\begin{prop}
\label{prop:2.1}Let $F$ be free on $X$. Then $F=\left\langle X\right\rangle $
(i.e., $X$ generates $F$)\end{prop}
\begin{proof}
Assume $F$ is free on $X$ and let $H=\left\langle X\right\rangle \leq F$.
\[
\xymatrix{X\ar[r]^{\theta}\ar[d]_{i} & H\ar[r]^{j} & F\\
F\ar[ur]^{\theta'}\ar[urr]_{\id_{F}}
}
\]
Let $\theta:X\to H,i:X\to F$ be insertion maps (i.e., $i(x)=\theta(x)=x$).
Then there exists $\theta':F\to H$ with $\theta'i=\theta$. Let $j:H\to F$
be insertion map, then $\theta'j$ and $\id_{F}$ are both extension
of $j\theta:X\to F$. So by the uniqueness part of the definition
we have $\theta'j=\id_{F}$. Since $\id_{F}$ is surjective, we have
$j$ is surjective hence $H=F$\end{proof}
\begin{prop}
\label{prop:2.2}Let $F_{1}$ be free on $X_{1}$ and $F_{2}$ be
free on $X_{2}$. Then $F_{1}\cong F_{2}$ if and only if $|X_{1}|=|X_{2}|$.
(In particular any two free groups on $X$ are isomorphic)\end{prop}
\begin{proof}
{}
\begin{elabeling}{00.00.0000}
\item [{``$\Rightarrow$'':}] Let $G$ be any non-trivial finite group
(such as $C_{2}$). The number of maps $X_{1}\to G$ is $|G|^{|X_{1}|}$.
Since each map uniquely determines a homomorphism, we get $|G|^{|X_{1}|}=|\hom(F_{1},G)|$.
Similarly we find $|G|^{|X_{2}|}=|\hom(F_{2},G)|$. Now $F_{1}\cong F_{2}\Rightarrow\left|\hom(F_{1},G)\right|=\left|\hom(F_{2},G)\right|$
(exercise show this). This means $|G|^{|X_{1}|}=|G|^{|X_{2}|}\Rightarrow|X_{1}|=|X_{2}|$,
which is clear if $|X_{i}|$ are finite. (In fact for infinite cardinal
numbers $2^{\alpha}=2^{\beta}\Rightarrow\alpha=\beta$ is independent
of the axioms of set theory). In fact it can be proved that for $X$
infinite, $F$ free on $X$ implies $|F|=|X|$ so result is true anyway.
(proof omitted).
\item [{``$\Leftarrow$'':}] Assume $|X_{1}|=|X_{2}|$ and let $\kappa:X_{1}\to X_{2}$
be a bijection.
\[
\xymatrix{X_{1}\ar[r]^{\kappa}\ar[d]^{i_{1}} & X_{2}\ar[r]^{i_{2}} & F_{2}\\
F_{1}\ar[urr]_{\alpha}
}
\]
 where $i_{1},i_{2}$ are insertions. So $i_{2}\kappa$ extends to
$\alpha:F_{1}\to F_{2}$
\[
\xymatrix{X_{2}\ar[r]^{\kappa^{-1}}\ar[d]^{i_{2}} & X_{1}\ar[r]^{i_{1}} & F_{1}\\
F_{2}\ar[urr]_{\beta}
}
\]
so similarly, $i_{1}\kappa^{-1}$ extends uniquely to $\beta:F_{2}\to F_{1}$.
For $x\in X_{1}$, $\beta\alpha(x)=\beta i_{2}\kappa(x)=\beta\kappa(x)=i_{1}\kappa\kappa^{-1}(x)=i_{1}(x)=x$.
So $\beta\alpha:F_{1}\to F_{2}$ extends identity map $X_{1}\to F_{1}$.
So by uniqueness $\beta\alpha=\id_{F_{1}}$. Similarly we find $\alpha\beta=\id_{F_{2}}$.
So $\alpha,\beta$ are isomorphism.
\end{elabeling}
\end{proof}
We now prove existence of free groups:

$F=\left\langle X|\,\:\right\rangle $ should be generated by $X$,
so elements represented by strings in $x,x^{-1},x\in X$, i.e. elements
of $A^{*}$ where $A=X\cup X^{-1}$. All words should be distinct?
Except we want $xx^{-1}=x^{-1}x=1$. Let $X$ be any set, let $X^{-1}$
be a set with $|X|=|X^{-1}|$ and $X^{-1}\cap X=\emptyset$, denote
elements of $X^{-1}$ by $\left\{ x^{-1}|x\in X\right\} $. Define
$(x^{-1})^{-1}=x\,\forall x\in X$. Let $A=X\cup X^{-1}$. A word
in $A^{*}$ is called reduced if it contains no subwords $xx^{-1}$
or $x^{-1}x$ for $x\in X$. For example $X=\{x,y\}$, $xy^{-1}xxy^{-1}y^{-1}$
is reduced while $xyx^{-1}xyyx^{-1}$ is not
\begin{prop}
\label{Prop 2.3}For any set $X$, there exists a free group $F_{X}$
on $X$.\end{prop}
\begin{proof}
Define $X^{-1}$ and $A$ as above, and let $F_{X}$ be the set of
reduced words in $A^{*}$. Make $F_{X}$ into as follows. Let $\alpha,\beta\in F_{X}$.
We define $\alpha\beta$ by concatenating $\alpha$ and $\beta$ and
deleting any strings $xx^{-1}$ or $x^{-1}x$ in the middle. 
\begin{example*}
$X=\{x,y\}$, $\alpha=xyx^{-1}$ and $\beta=x^{-1}$, then $\alpha\beta=xyx^{-2}$.
If $\alpha=xyx^{-1}y^{-1}$ and $\beta=yxyx$ then $\alpha\beta=xy^{2}x$.
If $\alpha=xyx$, $\beta=x^{-1}y^{-1}x^{-1}$ then $\alpha\beta=\epsilon$.
\end{example*}
We have an identity element, $\epsilon$. Given $\alpha$, we get
$\alpha^{-1}$ by reversing $\alpha$ and replacing every letter by
its inverse. Finally we need to show associativity. Let $\alpha,\beta,\gamma\in F_{X}$,
let $l=|\alpha|,m=|\beta|$ and $n=|\gamma|$. When we multiply $\alpha\beta$,
let $r$ be the length of suffix of $\alpha$ that is cancelled (could
have $r=0$). Loose prefix of length $r$ from $\beta$, so $|\alpha\beta|=l+m-2r$.
Similarly let $s$ be the length of suffix of $\beta$ that is cancelled
in $\beta\gamma$, then $|\beta\gamma|=m+n-2s$.
\begin{caseenv}
\item $r+s\leq m$. The cancelled prefix and suffix of $\beta$ do not intersect.
Let $\alpha=ab^{-1},\beta=bcd$ and $\gamma=d^{-1}e$, where $b,d$
are cancelled parts and $|c|\geq0$. So $\alpha\beta=acd$, $(\alpha\beta)\gamma=ace$.
On the other hand $\beta\gamma=bce$, $\alpha(\beta\gamma)=ace$ as
required.
\item $r+s>m$. Then the cancelled prefix and suffix of $\beta$ overlaps.
So let $\alpha=ac^{-1}b^{-1},\beta=bcd$ and $\gamma=d^{-1}c^{-1}e$.
Then we have $\alpha\beta=ad$ and $(\alpha\beta)\gamma=ac^{-1}e$.
On the other hand $\beta\gamma=be$, $\alpha(\beta\gamma)=ac^{-1}e$
as required.
\end{caseenv}
So $F_{X}$ is a group. We now show that it is free on $X$. Let $G$
be any group and $\theta:X\to F$ a map. If $\theta':F_{X}\to G$
is a homomorphism extending $\theta$ we must have $\theta'(x^{-1})=\theta'(x)^{-1}\,\forall x\in X$.
We also must have $\theta'(a_{1}a_{"}\dots a_{k})=\theta'(a_{1})\dots\theta'(a_{k})\,\forall a_{1}a_{2}\dots a_{k}\in F_{X}$.
So $\theta'$ is unique. But defining $\theta'$ like this, does define
a homomorphism $\theta':F_{X}\to G$ which extends $\theta$. Hence
$F_{X}$ is free on $X$. \end{proof}
\begin{notation*}
For a set $X$, $F_{X}$ denotes $F_{X}$ as defined in the above
proof. (So any free group on $X$ is isomorphic to $F_{X}$ by Proposition
\ref{prop:2.2})\end{notation*}
\begin{defn}
Let $F_{X}$ be the free group on $X$. Then $|X|$ is called the
\emph{rank} of $F_{X}$\end{defn}
\begin{example*}
{}
\begin{enumerate}
\item If $X=\emptyset$, then $F_{X}=\{\epsilon\}$ the trivial group.
\item $X=\{x\}$, then $F_{X}=\{x^{n}|n\in\zz\}\cong\zz$, the infinite
cyclic group.
\item $X=\{x,y\}$, then $F_{X}$ is ``big group'' which is non-abelian. 
\end{enumerate}
\end{example*}
\begin{lem}
\label{lem:2.4} If $F$ is free on $X$ and $\theta:F\to F'$ is
an isomorphism, then $F'$ is free on $\{\theta(x)|x\in X\}$.\end{lem}
\begin{proof}
Easy exercise\end{proof}
\begin{prop}
\label{prop:2.5} If $X\subseteq G$, then $G$ is free on $X$ if
and only if $G=\left\langle X\right\rangle $ and all reduced words
in $(X\cup X^{-1})^{*}$ represent distinct elements of $G$.\end{prop}
\begin{proof}
{}
\begin{elabeling}{00.00.0000}
\item [{``$\Leftarrow$'':}] Define $\theta:X\to G$ by $\theta(x)=x$.
This extends uniquely to $\theta':F_{X}\to G$. So $G=\left\langle X\right\rangle $
implies $\theta'$ is surjective and assumption on reduced words being
distinct in $G$, implies $\theta'$ is injective. Hence $\theta'$
is an isomorphism, so $G$ is free on $X$.
\item [{``$\Rightarrow$''}] $G=\left\langle X\right\rangle $ by Proposition
\ref{prop:2.1}. By Proposition \ref{prop:2.2}, all free groups on
$X$ are isomorphic, and there exist an isomorphism $\theta:F_{X}\to G$
with $\theta(x)=x\,\forall x\in X$. So elements of $F_{X}$, the
reduced words in $A^{*}$, have distinct images in $G$.
\end{elabeling}
\end{proof}
\begin{prop}
\label{prop:2.6}Any group $G$ is isomorphic to a quotient group
of a free group.\end{prop}
\begin{proof}
Choose any set $X\subseteq G$ with $G=\left\langle X\right\rangle $
(could even choose $X=G$). The map $\theta:X\to G$ extends to $\theta':F_{X}\to G$.
Now $G=\left\langle X\right\rangle $ implies $\theta'$ is surjective.
So by the first isomorphism theorem $G=\im(\theta')\cong F_{X}/\ker(\theta')$\end{proof}
\begin{defn}
$w=a_{1}a_{2}\dots a_{n}\in A^{*}$ is called \textit{cyclically reduced,
}\textit{\emph{if $w$ is reduced and either $n=0$ or $a_{i}\neq a_{n}^{-1}$.}}\end{defn}
\begin{prop}
\label{prop:2.7} If $F$ is a free group and $1\neq w\in F$, then
$|w|=\infty$, i.e., $F$ has no elements of finite order. ($F$ is
\emph{torsion free})\end{prop}
\begin{proof}
Let $F=F_{X}$. Let $w\in F$, $w\neq1$. Note if $w$ is cyclically
reduced then so is $w^{n}$, (since $a_{n}\neq a_{1}^{-1}$). Hence
$w^{n}\neq\epsilon$, so $|w|=\infty$.

In general, we can write $w=a_{1}a_{2}\dots a_{r}(a_{r+1}\dots a_{l-r})a_{r}^{-1}\dots a_{2}^{-1}a_{1}^{-1}$
where $l=|w|$ and $a_{r+1}\neq a_{l-r}^{-1}$. (Note the whole of
$w$ can not cancel like this or $w$ would not be reduced). Hence
$w=\beta\alpha\beta^{-1}$ with $\alpha$ cyclically reduced and $\alpha\neq1$.
Then $w^{n}=\beta\alpha^{n}\beta^{-1}$ with $\alpha^{n}$ cyclically
reduced. Hence $w^{n}\neq1$, so $|w|=\infty$.\end{proof}
\begin{prop}
\label{prop:2.8}Let $F$ be a free group. Let $a,b\in F$, then $ab=ba$
if and only if $\exists u\in F$ with $a=u^{h}$, $b=u^{k}$ for some
$h,k\in\zz$. (i.e., $a,b$ commutes if and only if they are powers
of a common element $u$)\end{prop}
\begin{proof}
``$\Leftarrow$'': Clear since $ab=ba=u^{h+k}$

``$\Rightarrow$'': Let $F=F_{X}$, $a=a_{1}a_{2}\dots a_{l}$ and
$b=b_{1}b_{2}\dots b_{m}$. Proof by induction on $l+m$ and without
loss of generality assume $l\leq m$

If $l=0$, then $a=1$ so $a=b^{0}$ and $b=b^{1}$, so the result
is true with $u=b$.

Hence we can assume that $l>0$. Let $r$ be the length of the suffix
of $a$ that cancels when calculating $ab$. So $0\leq r\leq l$ and
$l(ab)=l+m-2r$. Since $ba=ab$, we get $l(ba)=l+m-2r$, so also get
cancellation length $r$ in $ba$. 
\begin{caseenv}
\item $r=0$, i.e., no cancellation. Here $ab=a_{1}\dots a_{l}b_{1}\dots b_{m}$
and $ba=b_{1}\dots b_{m}a_{1}\dots a_{l}$ are equal as words. Since
$l\leq m$, $a_{i}=b_{i}$ for $1\leq i\leq l$. So $a$ is a prefix
of $b$, hence let $b=ac$ with $l(c)=m-l$. Since $ab=ba$, we have
$b\in C_{F}(a)=\{x\in F|xa=ax\}$ (the \emph{centraliser}). Also $a\in C_{F}(a)$,
since $C_{F}(a)$ is a subgroup of $F$, so $c=a^{-1}b\in C_{F}(a)$.
Hence $ac=ca$. Since $l(c)<l(b)$, we can use induction on $ac$
to get $\exists u$ such that $a=u^{h},c=u^{k}$. So $b=ac=u^{h+k}$
and we are done.
\item $r=l$, i.e., the whole of $a$ cancels is $ab$. So $b=a^{-1}c$
for some $c$ with $l(c)=m-l$. Then we are back in case 1
\item $0<r<l$. In this case we have $ab=a_{1}\dots a_{l-r}b_{r+1}\dots b_{m}=ba=b_{1}\dots b_{m-r}a_{r+1}\dots a_{l}$.
Since $r<l$, we have $a_{1}=b_{1}$ and $b_{m}=a_{l}$. Since $0<r$,
there is some cancellation, so $a_{l}=b_{1}^{-1}$ and similarly $b_{m}=a_{1}^{-1}$.
Putting all this together we get $a_{l}=b_{1}^{-1}=a_{1}^{-1}=b_{m}$,
i.e., $a=a_{1}\alpha a_{1}^{-1}$ and $b=a_{1}\beta a_{1}^{-1}$,
where $l(\alpha)=l-2$ and $l(\beta)=m-2$. Now $ab=ba\Rightarrow a_{1}\alpha a_{1}^{-1}a_{1}\beta a_{1}^{-1}=a_{1}\beta a_{1}^{-1}a_{1}\alpha a_{1}^{-1}\Rightarrow\alpha\beta=\beta\alpha$.
So by induction, we have that $\exists u$ such that $\alpha=u^{h}$
and $\beta=u^{k}$. Then $a=a_{1}u^{h}a_{1}^{-1}=(a_{1}ua_{1}^{-1})^{h}$
and $b=(a_{1}ua_{1}^{-1})^{k}$, and we are done using $a_{1}ua_{1}^{-1}$
\end{caseenv}
\end{proof}
\newpage{}


\section{Subgroups of Free Groups}

The main result of this section is that subgroups of free groups are
free. {[}Can easily deduce Proposition \ref{prop:2.7},\ref{prop:2.8}
directly from this{]}. There exists two algebraic proofs: Schreier
and Nielsen. Really need them both for advance work, but in this course
we will just do Schreier's proof. Both are in Johnson's Book. There
also exists proofs from Algebraic Topology.
\begin{defn}
A relation $\leq$ on a set $A$ is a \emph{well ordering} if it is
a total ordering ($\forall a,b\in A$, we have $a<b$,$b<a$ or $a=b$)
such that each subset of $A$ has a least element\end{defn}
\begin{example*}
$\leq$ on $\nn$ is well ordering, but $\leq$ on $\zz,$$\qq$ are
not. \end{example*}
\begin{ax*}
{}
\begin{enumerate}
\item Any set can be well ordered
\item Axiom of choice
\item Zorn's Lemma
\end{enumerate}
\end{ax*}
These three axioms are all equivalent (using basis set theory) and
independent of basic axioms of set theory. Moth mathematicians assume
them.

So we will assume our set $A=X\cup X^{-1}$ has a well ordering $\leq$.
(In most of our examples $X$ will usually be finite, so this is clearly
true)
\begin{defn}
We define the \emph{lenlex} \emph{ordering }of $A^{*}$ as follows.
Let $a=a_{1}\dots a_{l}$ and $b=b_{1}\dots b_{m}$ in $A^{*}$. We
say $a<b$ if either:
\begin{enumerate}
\item $l<m$
\item $l=m$ and for some $i<l$ we have $a_{j}=b_{j}$ for $j<i$ but $a_{i+1}<b_{i+1}$.
\end{enumerate}
\end{defn}
\begin{xca*}
Check that the lenlex ordering is a well-ordering.\end{xca*}
\begin{note*}
The \emph{lex} ordering (dictionary) is not a well ordering. $A=\{x,y\}$
and $x<y$ then $\{x^{k}y|k\geq0\}$ has no least element.
\end{note*}
Lenlex has the following properties (exercise): 
\[
\,\forall v,w\in A^{*},u<w\Rightarrow\begin{cases}
vx<wx\\
xv<xw
\end{cases}\,\forall x\in A\quad(\dagger)
\]
Any well-ordering of $A^{*}$ that satisfies $(\dagger)$ can be used
in the following theory.
\begin{defn}
Let $F$ be a group (not necessarily free) generated by $X$. Let
$E\leq F$ and $A=X\cup X^{-1}$. Let $U\subset A^{*}$ then $U$
is called a \emph{Schreier transversal} of $E$ in $F$ if it is a
right transversal and it is prefix-closed, i.e., if $a_{1}a_{2}\dots a_{l}\in U\Rightarrow a_{1}a_{2}\dots a_{l-1}\in U$. 

So in particular $\epsilon\in U$ as representative of coset $E$.
Also all words in$U$ must be reduced, since otherwise we would get
two different words representing the same group element ($yxx^{-1}\in U\Rightarrow y\in U$)\end{defn}
\begin{prop}
\label{prop:3.1}Every $E\leq F$ has a Schreier transversal. We can
define one by choosing well-ordering of $A^{*}$ satisfying $(\dagger)$
and taking least element of each coset $Eg$ as its representative
in $U$.\end{prop}
\begin{proof}
Define $U$ as in the statement. Let $a_{1}a_{2}\dots a_{l}\in U$.
If $a_{1}\dots a_{l-1}\notin U$ then there exists $b_{1}b_{2}\dots b_{m}\in Ea_{1}a_{2}\dots a_{l-1}$
with $b_{1}\dots b_{m}<a_{1}\dots a_{l-1}$. By $(\dagger)$ $b_{1}\dots b_{m}a_{l}<a_{1}\dots a_{l-1}a_{l}$
contradicting $a_{1}a_{2}\dots a_{l}\in U$\end{proof}
\begin{example*}
Let $F=F_{X}$ and $X=\{x,y\}$. Let $G=\left\langle g\right\rangle $,
be cyclic of order $6$. By definition of free groups $\exists\theta:F\to G$
with $\theta(x)=g^{2},\theta(y)=g^{3}$. Now $g=\theta(yx^{-1})\in\im(\theta)$,
so $\im(\theta)=G$. Take $E=\ker(\theta)$. Take $F/E\cong G\Rightarrow|F\cdot E|=|G|=6$.
Note $Ea=Eb$ if and only if $ab^{-1}\in E\Rightarrow\theta(a)=\theta(b)$.
So a transversal consist of $6$ elements with distinct images under
$\theta$. Could choose $U=\{\epsilon,x,y,x^{2},xy,x^{2}y\}$, then
under $\theta$ the elements are $1,g^{2},g^{3},g^{4},g^{5},g^{7}=g$.
This is a Schreier Transversal (but by guessing it worked). More systematically
we can compute $U$ using Proposition \ref{prop:3.1} by considering
$\theta(a)$ for increasing $a$ under the ordering. $A=\{x,y,x^{-1},y^{-1}\}$
need ordering on $A$, say $x<x^{-1}<y<y^{-1}$. Using lenlex:

\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|}
\hline 
$w\in A^{*}$ & $\epsilon$ & $x$ & $x^{-1}$ & $y$ & $y^{-1}$ & $x^{2}$ & $xy$ & $xy^{-1}$ & $x^{-2}$ & $x^{-1}y$\tabularnewline
\hline 
$\theta(w)$ & $1$ & $g^{2}$ & $g^{4}$ & $g^{3}$ & $g^{3}$ & $g^{4}$ & $g^{5}$ & $g^{5}$ & $g^{2}$ & $g$\tabularnewline
\hline 
\end{tabular}

delete repeated $\theta(w)$ and get $U=\{\epsilon,x,x^{-1},y,xy,x^{-1}y\}$
\end{example*}
Let $U$ be a Schreier transversal of $E$ in $F$. For $g\in E$,
let $\overline{g}$ be the unique element of $Eg\cap U$. Now $\overline{g}\in Eg\Rightarrow g\overline{g}^{-1}\in E\,(*)$.
For $u\in U$, $x\in F$ we have $\overline{\overline{ux}x^{-1}}$
is in the same coset as $\overline{ux}x^{-1}$ in the same coset as
$u$. That is $\overline{\overline{ux}x^{-1}},u\in Eu\cap U$, so
$\overline{\overline{ux}x^{-1}}=u$ $(**)$. Define $Z=\{ux\overline{ux}^{-1}|u\in U,x\in X\}$.
By $(*)$, $Z\subseteq E$. 
\begin{lem}
\label{lem:3.2} Let $Z$ be as define above, then $Z^{-1}=S$ where
$S=\{ux^{-1}\overline{ux^{-1}}^{-1}|u\in U,x\in X\}$\end{lem}
\begin{proof}
Let $g\in Z^{-1}$, then $g=(ux\overline{ux}^{-1})^{-1}=\overline{ux}x^{-1}u^{-1}$.
Let $v\in\overline{ux}\in U$. By $(**)$ $\overline{vx^{-1}}=u\Rightarrow g=vx^{-1}\overline{vx^{-1}}^{-1}\in S$.

Conversely, let $g=ux^{-1}\overline{ux^{-1}}^{-1}\in S$. Then $g^{-1}=\overline{ux^{-1}}xu^{-1}$,
let $v=\overline{ux^{-1}},$$\overline{vx}=u$ by $(**)$ so $g=vx\overline{vx}^{-1}\in Z^{-1}$. \end{proof}
\begin{notation*}
For $u,v\in A^{*}$, $u=_{F}v$ means $u,v$ define same elements
of $G$\end{notation*}
\begin{prop}
\label{prop:3.3} With the above notation $E=\left\langle Z\right\rangle $\end{prop}
\begin{proof}
Let $h\in E$ so $h=a_{1}a_{2}\dots a_{l}$ with $a_{i}\in A$. Define
$u_{0}=\epsilon$ and $u_{i}=\overline{a_{1}a_{2}\dots a_{l}}$ for
all $1\leq i\leq l$. So $h\in E\Rightarrow u_{l}=\overline{h}=\epsilon$.
Now $h=_{F}(u_{0}a_{1}u_{1}^{-1})(u_{1}a_{2}u_{2}^{-1})\dots(u_{l-1}a_{l}u_{l}^{-1})$
since $u_{0}=u_{l}=\epsilon$. We have $u_{i+1}=\overline{u_{i}a_{i}}$
by definition of $u_{i}$. So $h=_{F}(u_{0}a_{1}\overline{u_{0}a_{1}}^{-1})(u_{1}a_{2}\overline{u_{1}a_{2}}^{-1})\dots(u_{l-1}a_{l}\overline{u_{l-1}a_{l}}^{-1})$
which (by Lemma \ref{lem:3.2}) is a product of elements of $Z$ and
$Z^{-1}$, hence in $(Z\cup Z^{-1})^{*}$\end{proof}
\begin{example}
With the above notation $Z$ is called the \emph{set of Schreier generators}
of $E$ (this depends on $U$)\end{example}
\begin{cor}
\label{cor:3.4}A subgroup of finite index in a finitely generated
group is itself finitely generated.\end{cor}
\begin{proof}
$X$, $U$ are finite, then $|Z|=|X|\cdot|U|$ hence $Z$ is finite.\end{proof}
\begin{example*}
Going back to the previous example, we had $U=\{\epsilon,x,x^{-1},y,xy,x^{-1}y\}$.
We now calculate $Z$.

\begin{tabular}{|c|c|cc|cc|cc|}
\hline 
$\theta(u)$ & $u$ & $ux$ & $uy$ & $\overline{ux}$ & $\overline{uy}$ & $ux\overline{ux}^{-1}$ & $uy\overline{uy}^{-1}$\tabularnewline
\hline 
\hline 
$1$ & $\epsilon$ & $x$ & $y$ & $x$ & $y$ & $1$ & $1$\tabularnewline
\hline 
$g^{2}$ & $x$ & $x^{2}$ & $xy$ & $x^{-1}$ & $xy$ & $x^{3}$ & $1$\tabularnewline
\hline 
$g^{4}$ & $x^{-1}$ & $1$ & $x^{-1}y$ & $\epsilon$ & $x^{-1}y$ & $1$ & $1$\tabularnewline
\hline 
$g^{3}$ & $y$ & $yx$ & $y^{2}$ & $xy$ & $\epsilon$ & $yxy^{-1}x^{-1}$ & $y^{2}$\tabularnewline
\hline 
$g^{5}$ & $xy$ & $xyx$ & $xy^{2}$ & $xy^{-1}$ & $x$ & $xyxy^{-1}x$ & $xy^{2}x^{-1}$\tabularnewline
\hline 
$g$ & $x^{-1}y$ & $x^{-1}yx$ & $x^{-1}y^{2}$ & $y$ & $x^{-1}$ & $x^{-1}yxy^{-1}$ & $x^{-1}y^{2}x$\tabularnewline
\hline 
\end{tabular}

To find $\overline{ux}$, calculate $\theta(ux)$, find elements of
$U$ with same image under $\theta$. For example $\theta(x^{2})=g^{4}=\theta(x^{-1})$
and $x^{-1}\in U$. Hence we have $Z=\{1,x^{3},yxy^{-1}x^{-1},y^{2},xyxy^{-1}x,xy^{2}x^{-1},x^{-1}yxy^{-1},x^{-1}y^{2}x\}$. 

To express $xy^{-1}x^{-1}y\in E$ as word in $Z\cup Z^{-1}$. We follow
the proof of Proposition \ref{prop:3.3}. 
\[
\begin{pmatrix}u_{0} & a_{1} & \overline{u_{0}a_{1}}^{-1}=u_{1}^{-1}\\
\epsilon & x & x^{-1}
\end{pmatrix}\begin{pmatrix}u_{1} & a_{2} & u_{2}^{-1}\\
x & y^{-1} & y^{-1}x^{-1}
\end{pmatrix}\begin{pmatrix}u_{2} & a_{3} & u_{3}^{-1}\\
xy & x^{-1} & y^{-1}
\end{pmatrix}\begin{pmatrix}u_{3} & a_{4} & u_{4}^{-1}\\
y & y & \epsilon^{-1}
\end{pmatrix}=(xy^{2}x^{-1})^{-1}(yxy^{-1}x^{-1})^{-1}(y^{2})
\]

\end{example*}
We don't want $1$ in our generating set. So define $Y=\{ux\overline{ux}^{-1}|u\in U,x\in X,ux\neq\overline{ux}\}$.
We still have $Y^{-1}=\{ux^{-1}\overline{ux^{-1}}^{-1}|u\in Y,x\in X,ux^{-1}\neq\overline{ux^{-1}}\}$
We still have $E=\left\langle Y\right\rangle $ since $Y=Z\setminus\{1\}$

For the remainder of the section let $F$ be free on $X$ and we assume
$F=F_{X}$. We will prove $E$ is free on $Y$.
\begin{lem}
\label{lem:3.5}Let $ua\overline{ua}^{-1}\in Y\cup Y^{-1}$ (with
$u\in U$ and $a\in A=X\cup X^{-1}$). Then in the word $ua\overline{ua}^{-1}$
the letter $a$ does not cancel. \end{lem}
\begin{proof}
Let $u,\overline{ua}\in U$ so they are reduced words. Hence if $a$
cancels, it cancels with final letter of $u$ or the first letter
of $\overline{ua}^{-1}$.
\begin{caseenv}
\item Let $u=a_{1}a_{2}\dots a_{l}$ with $a_{l}=a^{-1}$. Then $ua=a_{1}a_{2}\dots a_{l-1}\in U$
by the prefix closure condition. This means $ua=\overline{ua}$ so
$ua\overline{ua}^{-1}\notin Y\cup Y^{-1}$. This is a contradiction.
\item Let $\overline{ua}=a_{1}\dots a_{l}$ with $a_{l}=a$. Then $\overline{ua}a^{-1}=a_{1}\dots a_{l-1}\in U$
. But $\overline{\overline{ua}a^{-1}}=u$ by $(**)$ so $\overline{ua}a^{-1}=u$$\Rightarrow ua=\overline{ua}$.
This is again a contradiction.
\end{caseenv}
\end{proof}
\begin{rem*}
By this lemma the words $ua\overline{ua}^{-1}$ in $Y$ are reduced
as words, hence they are distinct, that is different $u,a$ give different
words.\end{rem*}
\begin{lem}
\label{lem:3.6}Let $ua\overline{ua}^{-1},vb\overline{vb}^{-1}\in Y\cup Y^{-1}$
with $ua\overline{ua}^{-1}\neq_{F}(vb\overline{vb}^{-1})^{-1}$. Then
in product $u\underline{a}\overline{ua}^{-1}v\underline{b}\overline{vb}^{-1}$
neither of the underlined $a$ or $b$ cancels.\end{lem}
\begin{proof}
By the last lemma, $a$ cannot cancel with $u$ or $\overline{ua}^{-1}$,
$b$ not with $b$ or $\overline{vb}^{-1}$. So for one of them to
cancel:
\begin{caseenv}
\item all of $\overline{ua}^{-1}$ would cancel with $v$ or
\item all of $v$ would cancel with $\overline{ua}^{-1}$
\end{caseenv}
We deal with Case 1. as Case 2. is similar. Let $\overline{ua}=a_{1}\dots a_{l},v=b_{1}\dots b_{m}$.
In Case 1. we have $l\leq m$. 

First suppose $l<m$, then $a_{i}=b_{i}$ for $1\leq i\leq l$, so
$a$ cancels with $b_{l+1}$, i.e., $b_{l+1}=a^{-1}$. Hence $\overline{ua}a^{-1}=a_{1}\dots a_{l}b_{l+1}=b_{1}\dots b_{l}b_{l+1}\in U$.
So $\overline{ua}a^{-1}=u\Rightarrow\overline{ua}=ua$. Contradiction
as before.

Next suppose $l=m$. So $a_{i}=b_{i}$ for $1\leq i\leq l$ and $\overline{ua}=v$,
$a=b^{-1}$. So $\overline{vb}=\overline{\overline{ua}b}=\overline{\overline{ua}a^{-1}}=u$.
So $(ua\overline{ua}^{-1})^{-1}=\overline{ua}a^{-1}u^{-1}=vb\overline{vb}^{-1}$,
contradicting our assumption.\end{proof}
\begin{cor}
\label{cor:3.7}Let $b_{i}=u_{i}a_{i}\overline{u_{i}a_{i}}^{-1}\in Y\cup Y^{-1}$
for $1\leq i\leq l$, where $b_{i}\neq b_{i+1}^{-1}$. Then in the
product $b_{1}b_{2}\dots b_{l}$ none of the letters $a_{i}$ cancel,
so $b_{1}b_{2}\dots b_{l}\neq_{F}1$.\end{cor}
\begin{proof}
This follows immediately.\end{proof}
\begin{thm}[Main Theorem]
\label{thm:3.8}  If $F$ is free on $X$, $E\leq F$ and $U$ a
Schreier transversal of $E$ in $F$ then $E$ is free on the set
$Y$as defined above. Furthermore if $U,X$ are finite, $|U|=n$ and
$|X|=r$, then $|Y|=(r-1)n+1=nr-(n-1)$.\end{thm}
\begin{proof}
We have $E=\left\langle Y\right\rangle $ by Proposition \ref{prop:3.3}.
So by Proposition \ref{prop:2.5} it is enough to prove distinct words
in $Y\cup Y^{-1}$ define distinct elements of $E$. 

So let $b_{1}\dots b_{l},c_{1}\dots c_{m}$ be distinct reduced words
in $Y\cup Y^{-1}$ with $b_{1}\dots b_{l}=_{F}c_{1}\dots c_{m}$.
So $b_{1}\dots b_{l}c_{m}^{-1}\dots c_{1}^{-1}=_{F}1$ by Corollary
\ref{cor:3.7}. Now $b_{1}\dots b_{l}c_{m}^{-1}\dots c_{1}^{-1}$
is now reduced in $Y\cup Y^{-1}$. So we must have $b_{l}=c_{m},b_{l-1}=c_{m-1}$
etc. and we get $b_{1}\dots b_{l}=c_{1}\dots c_{m}$ (as words), which
is a contradiction.

Now assume $|U|=n$ and $|X|=r$ are finite. By the remark above,
all elements of $Y$ are distinct, so $|Y|=nr-t$ where $t$ is the
number of pairs $(u,x)$ with $ux=_{F}\overline{ux}$. Let $v=a_{1}a_{2}\dots a_{l}\in U\setminus\{\epsilon\}$.
If $a_{l}=x\in X$ then $u=a_{1}\dots a_{l-1}\in U$ and $ux=v\in U$
so $ux=\overline{ux}$. Otherwise $a_{l}=x^{-1}\in X^{-1}$. Then
$ux=\overline{ux}$ with $u=v$. So each $v\in U\setminus\{\epsilon\}$
gives rise to a $(u,x)$ with $ux=\overline{ux}$. Conversely if $ux=\overline{ux}$,
$ux\overline{ux}^{-1}=_{F}1$ then $x$ must cancel against end of
$u$, or beginning of $\overline{ux}$. So this $(u,x)$ arises in
one of the two ways above. 

So the pairs $(u,x)$ with $ux=\overline{ux}$ are in 1-1 correspondence
with $U\setminus\{\epsilon\}$, so $t=|U\setminus\{\epsilon\}|=n-1$.
Hence $|Y|=nr-(n-1)=n(r-1)+1$.\end{proof}
\begin{example*}
Carrying on the previous example, we have $\left|\left\langle g\right\rangle \right|=6$,
so $n=6,r=2$ and $5$ elements of $Z$ where trivial. We had $|Y|=7$
\end{example*}
If $|F:E|$ infinite, is $Y$ infinite? No, you can take $E=\{1\}$,
then $|Y|=0$. Or a slightly less trivial example, let $X=\{x,y\}$
and $E=\left\langle x\right\rangle $, then $|Y|=1$. 
\begin{prop}
\label{prop:3.9}Let $F$ be free, $E\leq F,|F:E|=\infty$ and suppose
there exists $\{1\}\neq N\lhd F$ with $N\leq E$. Then $Y$ is infinite.\end{prop}
\begin{proof}
Let $U$ be a Schreier Transversal of $E$ in $F$. Let $1\neq w=a_{1}\dots a_{l}\in N\leq E$.
For $u\in U$, then $Euw=Euwu^{-1}u=Eu$ since $uwu^{-1}\in N\leq E$.
So $\overline{uw}=u\neq uw$ (as words), so $uw\notin U$. Choose
the least $k$ such that $ua_{1}\dots a_{k}\notin U$. So $ua_{1}\dots a_{k-1}\in U$
but $ua_{1}\dots a_{k}\notin U$, since $U$ is infinite there exists
$1\leq k\leq l$ and an infinite subset $V\subseteq U$ with $ua_{1}\dots a_{k-1}\in U$
and $ua_{1}\dots a_{k}\notin U$ for all $u\in V$. So let $u_{k}=ua_{1}\dots a_{k-1}$for
$u\in U$ then $\{u_{k}a_{k}\overline{u_{k}a_{k}}^{-1}|u\in V\}$
is an infinite subset of $Y$. Hence $Y$ is infinite.\end{proof}
\begin{example*}
Let $F$ be free on $X=\{x,y\}$. Let $G=\left\langle g\right\rangle $
infinite cyclic. Define $\theta:F\to G$ with $\theta(x)=\theta(y)=g$.So
$\im(\theta)=G$ and let $E=\ker(\theta)$. So $|F:E|=|G|=\infty$.
Since $\theta(x^{i})=g^{i}$, $i\in\zz$, we can take $U=\{x^{i}|i\in\zz\}$.
So $ux=\overline{ux}\,\forall u\in U$. Then $Y=\{uy\overline{uy}^{-1}|u\in U\}=\{x^{i}yx^{-i-1}|i\in\zz\}$. 
\end{example*}
\newpage{}


\section{Presentation of Groups}
\begin{defn}
Let $G=\left\langle X\right\rangle $ and $A=X\cup X^{-1}$. A \emph{relator}
of $G$ is a word $w\in A^{*}$ with $w=_{G}1$.
\end{defn}
So in free groups, relators are like $xyxx^{-1}y^{-1}x^{-1}$
\begin{defn}
A \emph{relation }of $G$ is an equation $w_{1}=_{G}w_{2}$ with $w_{1},w_{2}\in A^{*}$. 
\end{defn}
Both definition are quite related as $w_{1}=w_{2}$ is a relation
of $G$ if and only if $w_{1}w_{2}^{-1}$ is a relator of $G$
\begin{defn}
Let $R\subseteq G$. The \emph{normal closure} $\left\langle R^{G}\right\rangle $
is the intersection of all normal subgroups of $G$ that contain $R$,
i.e., the smallest normal subgroup of $G$ that contains $R$.\end{defn}
\begin{lem}
\label{lem:4.1} We have $\left\langle R^{G}\right\rangle =\left\langle g^{-1}rg|g\in G,r\in R\right\rangle $\end{lem}
\begin{proof}
Denote $H_{1}:=\left\langle R^{G}\right\rangle $ and $H_{2}:=\left\langle g^{-1}rg|g\in G,r\in R\right\rangle $.

We must have $g^{-1}rg\in N$ for any $N\lhd R$ with $R\subseteq N$.
So $H_{2}\leq H_{1}$.

For the other way, we have $H_{1}\leq G$, $R\subset H_{2}$, from
the definition $g^{-1}H_{2}g=H_{2}\,\forall g\in G$, so $H_{2}\lhd G$.
Hence $H_{1}\leq H_{2}$.\end{proof}
\begin{defn}
Let $F=F_{X}$ be the free group on a set $X$. Let $R\subseteq F$.
Then the group defined by the \emph{presentation} $\left\langle X|R\right\rangle $
is $F/N$ with $N=\left\langle R^{F}\right\rangle $.
\end{defn}
So elements of $G=\left\langle X|R\right\rangle $ are cosets $Nw$
with $w\in A^{*}$ where $A=X\cup X$. Normally we just write $w\in G$
not $wN$ . But note that $w$ now has three meanings:
\begin{enumerate}
\item A word in $A^{*}$
\item An element of $F$
\item An element of $G$
\end{enumerate}
So $w_{1}=_{G}w_{2}$ means $w_{1},w_{2}$ are the same elements of
$G$, i.e., $w_{1}N=w_{2}N\iff w_{1}w_{2}^{-1}\in N$. For elements
$r\in R$ we have $r\in N$, so $r=_{G}1$, hence elements of $R$
are relators of $G$. They are called the \emph{defining relators}
of $G$. So we can think of $\left\langle X|R\right\rangle $ as ``the
largest group'' generated by $X$ in which elements of $R$ are relators.
\begin{example*}
{}
\begin{enumerate}
\item Let $X=\{x,y\}$ and $R=\{x^{4},y^{3},(xy)^{2}\}$. We write $\left\langle X|R\right\rangle $
as $\left\langle x,y|x^{4},y^{3},(xy)^{2}\right\rangle $. We can
also use equivalent relations, as $\left\langle x,y|x^{4},y^{2}=y^{-1},xy=y^{-1}x^{-1}\right\rangle $.


$w_{1}=w_{"}$ is a presentation is defined to be the same as writing
$w_{1}w_{2}^{-1}$

\item $\left\langle X|\:\right\rangle =F_{X}$ (i.e., $R=\emptyset$)
\item $\left\langle x|x^{k},k\neq0\right\rangle =\left\langle x\right\rangle /\left\langle x^{k}\right\rangle \cong C_{|k|}$.
The finite cyclic group of order $|k|$. 
\end{enumerate}
\end{example*}
Presentation is finite if $X,R$ are finite
\begin{prop}
\label{prop:4.2} All groups have presentations and finite groups
have finite presentations.\end{prop}
\begin{proof}
Choose $X\subset G$ with $G=\left\langle X\right\rangle $. Let $F=F_{X}$
be the free group of $X$. By the definition of free group $\theta:X\to G$
with $\theta(x)=x\,\forall x\in X$ extends to $\theta':F\to G$.
So $G\cong F/N$ where $N=\ker(\theta)$. Choose $R\subset N$ such
that $N=\left\langle R\right\rangle $. Then $G=\left\langle X|R\right\rangle $

If $G$ is finite, choose $X$ finite. Then $|F\cdot N|=|G|=$finite
so can choose $R$ is finite by Corollary \ref{cor:3.4}.\end{proof}
\begin{note*}
We have chosen $R$ with $N=\left\langle R\right\rangle $, but we
only need $N=\left\langle R^{G}\right\rangle $. So usually a smaller
set $R$ will work.\end{note*}
\begin{namedthm}[Fundamental Theorem of Presentation of Groups]
 \label{thm:4.3} Let $G=\left\langle X|R\right\rangle $,$H$ any
groups and $\theta:X\to H$ a map. For $x\in X$ define $\theta(x^{-1})$
by $\theta(x)^{-1}$. Suppose that for all $r=a_{1}\dots a_{l}\in A^{*}$
with $r\in R$, we have $\theta(a_{1})\theta(a_{2})\dots\theta(a_{l})=_{G}1$.
Then $\theta$ extends uniquely to a homomorphism $\theta':G\to H$. \end{namedthm}
\begin{proof}
If $\theta$ extends at all then we must have $\theta(x^{-1})=\theta(x)^{-1}$
and $\theta(a_{1}\dots a_{l})=\theta(a_{1})\dots\theta(a_{l})$, so
$\theta'$ is unique is it exists.

Let $F$ be free on $X$. Then $\theta$ extends to $\psi:F\to H$.
The hypothesis on $\theta$ says $\psi(r)=_{G}1\,\forall r\in R$,
so $R\subset N=\ker(\psi)$. Now $N\lhd G\Rightarrow\left\langle R^{F}\right\rangle \leq N$,
so $\psi$ induces a well defined map $\theta':R/\left\langle R^{F}\right\rangle \to H$
by $\theta'\left(\left\langle R^{F}\right\rangle w\right)=\psi(w)$
with $w\in F$. So $\theta'$ extends $\theta$ as required.\end{proof}
\begin{note*}
The hypothesis on $\theta$ is also necessary for $\theta$ to extend
to $\theta':G\to H$ (exercise)
\end{note*}
In general we cannot say much about a group defined by $\left\langle X|R\right\rangle $.

A general approach is to manipulate the relators to get an upper bound
on $|G|$ and they use the Fundamental Theorem to find an epimorphism
$\theta:G\to H$ and hence prove $|G|\geq|H|$. If $|H|$ is the same
as the upper bound, then $\theta$ is an isomorphism. 
\begin{example*}
Let $G=\left\langle x,y,|x^{n},y^{2},(xy)^{2}\right\rangle $ with
$n>1$. Consider $w\in A^{*}$ with $w\in G$, so $w$ is a string
in $x,x^{-1},y,y^{-1}$. Now $x^{n}\in R$ implies $x^{-1}=_{G}x^{n-1}$,
so we can replace any $x^{-1}$ in $w$ by $x^{n-1}$. Similarly,
we have $y=_{G}y^{-1}$ so replace $y^{-1}$ in $y$. Finally $(xy)^{2}=_{G}1$
means $yx=_{G}x^{-1}y^{-1}=_{G}x^{n-1}y$. So we can replace $w$
by a word of the form $x^{k}y^{l}$ with $k,l\geq0$. Since $x^{n}=_{G}1$
and $y^{2}=_{G}1$ we can assume $0\leq k<n$ and $0\leq l<2$. (This
is a \emph{normal form} for group elements). So we have that $|G|\leq2n$.

For $H$ we choose $D_{2n}$, with is the rotations and reflections
of a regular $n$-gon. Let $g=(1,2,\dots,n)$ be the rotation. Let
$h=(2,n)(3,n-1),\dots$ be the reflection fixing $1$. We can see
that $g^{n}=1$ and $h^{2}=1$. We calculate $gh=(1,n)(2,n-1)(3,n-2)\dots$,
so $(gh)^{2}=1$. Hence we can apply the Fundamental Theorem to $\theta:X\to H$
with $\theta(x)=g$, $\theta(y)=h$, hence $\theta$ extends to $\theta':G\to H$.
Since $g,h\in\im(\theta')$ we have $G=\left\langle g,h\right\rangle \subseteq\im(\theta')$,
so $|G|\geq|H|=2n$. Hence $|G|=2n$, so $\theta'$ is an isomorphism.\end{example*}
\begin{prop}
\label{prop:4.4}Let $G=\left\langle X\right\rangle ,$$H\leq G$
and $S=\cup_{i=1}^{r}Hg_{i}$ for some $g_{i}\in G$ and $g_{1}=1$.
If $g_{i}a\in S\,\forall a\in A$ ($=X\cup X^{-1}$) then $G=S$.
If we know $|x|$ is finite for all $x\in X$ , then enough to assume
$g_{i}a\in S\,\forall a\in X$.\end{prop}
\begin{proof}
Let $g\in G$ , we want to prove $g\in S$. Let $g=a_{1}\dots a_{l},a_{i}\in A$.
We use induction on $l$.

If $l=0$ then $g=1=g_{1}\in S$.

If $l>0$, by induction $a_{1}\dots a_{l-1}=hg_{i}\in S$ for some
$g\in H,g_{i}$. By assumption $g_{i}a_{l}=h'g_{j}\in S$, so $g=hg_{i}a_{l}=hh'g_{j}\in S$ 

If all $|x|\in X$ have finite order ($x^{n}=1\Rightarrow x^{-1}=x^{n-1}$)
, we can write $g=a_{1}a_{2}\dots a_{l}$ with $a_{i}\in X$\end{proof}
\begin{example*}
$G=\left\langle x,y|x^{3},y^{3},(xy)^{2}\right\rangle $. Choose $H=\left\langle y\right\rangle $.
We have $A_{5}=\left\langle g,h\right\rangle $ where $g=(1,2,3),h=(2,3,4)$.
Then $g^{3}=1,h^{3}=1,gh=(1,3)(2,4)$, hence $(gh)^{2}=1$. Define
$\theta:X\to A_{4}$ by $\theta(x)=g$ and $\theta(y)=h$. Then by
the Fundamental Theorem $\theta$ extends to $\theta:G\to A_{4}$.
Now $\im(\theta)=A_{4}$, so $|G|\geq12$. 

We want to prove $|G|=12$, i.e., $|G\cdot H|=4$. So we want to find
$g_{1},g_{2},g_{3},g_{4}$ so we can apply the last proposition. Since
$\theta(H)=\left\langle (2,3,4)\right\rangle =\mbox{Stab}_{A_{4}}(1)$,
$\theta(g_{i})$ should be coset representations of $\theta(H)$ in
$A_{4}$. We want $1^{\theta(g_{i})}=i$, so we can choose $g_{1}=1,g_{2}=x,g_{3}=xy,g_{4}=xy^{-1}$.
So by Proposition \ref{prop:4.4}, we want to prove that $g_{i}x,g_{i}y\in S,1\leq i\leq4$
where $S=\cup_{i=1}^{4}Hg_{i}$. (Since $x^{3}=y^{3}=1\Rightarrow|x|,|y|$
are finite)

\begin{tabular}{|c|c|c|}
\hline 
$g_{i}$ & $x$ & $y$\tabularnewline
\hline 
\hline 
$1$ & $x\in Hx$ & $y\in H$\tabularnewline
\hline 
$x$ & $x^{2}=x^{-1}=yxy\in Hxy$ & $x\in Hxy$\tabularnewline
\hline 
$xy$ & $xyx=y^{-1}\in H$ & $xy^{2}=xy^{-1}\in Hxy^{-1}$\tabularnewline
\hline 
$xy^{-1}$ & $xy^{-1}x=y^{-1}xy^{-1}\in Hxy^{-1}$ & $x\in Hx$\tabularnewline
\hline 
\end{tabular}

So $G=S,|G|\leq12$, hence $\theta$ is an isomorphism and $G\cong A_{4}$\end{example*}
\begin{defn}
The \emph{commutator }is $[x:y]:=x^{-1}y^{-1}xy$.
\end{defn}
Note that $[x,y]=1$ if and only if $xy=yx$.
\begin{example*}
Let $G=\left\langle x,y|[x,y]\right\rangle =\left\langle x,y|xy=yx\right\rangle $.
Using $yx=xy$, we get $G=\{x^{a}y^{b}|a,b\in\zz\}$ . We want to
show that $x^{a}y^{b}$ is normal form for group elements. 

Let $H\cong\zz^{2}$, free abelian of rank $2$. Then $H=\left\langle g\right\rangle \times\left\langle h\right\rangle =\{g^{a}h^{b}|a,b\in\zz\}$
(Writing $H$ multiplicatively). Define $\theta:X\to H$ by $\theta(x)=g,\theta(y)=h$.
Now $\theta([x,y])=g^{-1}h^{-1}gh=1_{H}$ so $\theta$ extends to
$\theta:G\to H$. And $\theta(x^{a}y^{b})=g^{a}h^{b}$. Clearly bijection
so isomorphism.

Similarly $\left\langle x_{1},\dots,x_{n}|[x_{i},x_{j}]:1\leq i<j\leq n\right\rangle \cong\zz^{n}$
(free abelian of rank $n$). This is also an example of a direct product,
for which we have:\end{example*}
\begin{prop}
\label{prop:4.5}Let $G=\left\langle X|R\right\rangle ,H=\left\langle Y|S\right\rangle $
with $X\cap Y=\emptyset$. Let $[X,Y]=\{[x,y]|x\in X,y\in Y\}$ and
$T=R\cup S\cup[X,Y]$. Define $F=\left\langle X\cup Y|T\right\rangle $,
then $G\times H\cong K$ .\end{prop}
\begin{proof}
$G\times H=\{(g,h)|g\in G,h\in H\}$. Define $\theta:X\cup Y\to G\times H,\theta(x)=(x,1),\theta(y)=(1,y)$.
Let $r=a_{1}\dots a_{l}\in T,a_{i}\in X\cup Y\cup X^{-1}\cup Y^{-1}$.
If $r\in R,r=_{G}1$ so $\theta(r)=(1,1)=1_{G\times H}$. Similarly
$r\in S\Rightarrow\theta(r)=1_{G\times H}$. If $r\in[x,y]$ then
$r=x^{-1}y^{-1}xy,x\in X,y\in Y$ so we get $\theta(r)=(x^{-1},1)(1,y^{-1})(x,1)(1,y)=(1,1)=1_{G\times H}$.
So $\theta$ extends to $\theta:K\to G\times H$ by the Fundamental
Theorem. It is clearly surjective since $G=\left\langle X\right\rangle $
and $H=\left\langle Y\right\rangle $. 

It remains to show that $\ker(\theta)=1$. Since $xy=yx,x\in X,y\in Y$
any element of $K$ can be written as $g=a_{1}a_{2}\dots a_{l}b_{1}\dots b_{m}$
with $a_{i}\in X\cup X^{-1}$ and $b_{i}\in Y\cup Y^{-1}$. Then $\theta(g)=(a_{1}\dots a_{l},b_{1}\dots b_{m})$,
so if $g\in\ker(\theta)$ then $a_{1}\dots a_{l}=_{G}1$ and $b_{1}\dots b_{m}=_{H}1$.
So $a_{1}\dots a_{l}\in\left\langle R^{F_{X}}\right\rangle $ and
$b_{1}\dots b_{m}\in\left\langle S^{F_{Y}}\right\rangle $, so both
in $\left\langle T^{F_{X\cup Y}}\right\rangle .$ So $a_{1}\dots a_{l}=_{K}1=_{K}b_{1}\dots b_{m}$.
\end{proof}

\subsection{Tietze Transformations}

Some group presentation ``clearly'' isomorphic. For example $\left\langle x,y|x^{3},y^{2}\right\rangle \cong\left\langle x,y|x^{2},y^{3}\right\rangle $
or $\left\langle x,y|y=x^{2}\right\rangle \cong\left\langle x|\:\right\rangle $
(eliminate $y$). Tietze Transformation enable us to justify such
manipulations of presentations.
\begin{prop}
\label{prop:4.6} Let $G=\left\langle X|R\right\rangle =F/N$, $N-\left\langle R^{F}\right\rangle .$
\begin{enumerate}
\item If $r$ is a relator of $G$, then $G=\left\langle X|R\cup\{r\}\right\rangle $ 
\item If $y\notin X$ and $w\in A^{*}$. Then $G\cong\left\langle X\cup\{y\}|R\cup\{yw^{-1}\}\right\rangle =:G'$,
where the isomorphism induces the identity on $X$.
\end{enumerate}
\end{prop}
\begin{proof}
{}
\begin{enumerate}
\item If $r\in R$ then $r\in N$ by definition. So $N=\left\langle (R\cup\{r\})^{F}\right\rangle $.
\item Since relators in $R$ are also relators of $G'$. So the map $\theta:X\to G'$
with $\theta(x)=x\,\forall x\in X$ satisfies $\theta(r)=_{G'}1$,
so by the Fundamental Theorem it extends to $\theta:G\to G'$. 


Define $\theta':X\cup\{y\}\to G$ by $\theta'(x)=x\,\forall x\in X$
and $\theta'(y)=w$. Again $\theta'(r)=_{G}1\,\forall r\in R$, and
$\theta'(yw^{-1})=\theta'(y)\theta'(w^{-1})=ww^{-1}=1$ (since $w$
is a word in $(X\cup X^{-1})^{*}$). So $\theta'$ maps relators of
$G'$ to $1_{G}$. So by the Fundamental Theorem, it extends to $\theta':G'\to G$.


Look at $\theta\circ\theta':G'\to G'$ and $\theta'\circ\theta:G\to G$,
they both extends the identity map on generators $X\cup\{y\}$ of
$G'$ and $X$ of $G$. So by the uniqueness of the Fundamental Theorem,
we have $\theta\theta'=I_{G'}$ and $\theta'\theta=1_{G}$, so both
isomorphism.

\end{enumerate}
\end{proof}
\begin{defn}
We define four types of \emph{Tietze Transformation} on $G=\left\langle X|R\right\rangle $.
\begin{elabeling}{00.00.0000}
\item [{$R^{+}$:}] Add a relator: If $r$ is a relator of $G$, then replace
$\left\langle X|R\right\rangle $ by $\left\langle X|R\cup\{x\}\right\rangle $
\item [{$R^{-}$:}] Remove a relator: If there exists $r\in R$ with $\left\langle (R\setminus\{r\})^{G}\right\rangle =\left\langle R^{G}\right\rangle $,
then replace $\left\langle X|R\right\rangle $ by $\left\langle X|R\setminus\{r\}\right\rangle $
\item [{$X^{+}$:}] Add a new generator: For any $w\in A^{*}$, replace
$\left\langle X|R\right\rangle $ by isomorphic group $\left\langle X\cup\{y\}|R\cup\{yw^{-1}\}\right\rangle $
\item [{$X^{-}$:}] Remove a generator: If there exists $r\in R$ with
$r=yw^{-1}$ for some $y\in X$, such that $w$ and all other $s\in R$
do not contain $y$ or $y^{-1}$, then replace $G$ by isomorphic
group $\left\langle X\setminus\{y\}|R\setminus\{r\}\right\rangle $.
\end{elabeling}
\end{defn}
This is mostly used in combinators.
\begin{example*}
{}
\begin{enumerate}
\item Let $G=\left\langle X|R\cup\{r\}\right\rangle $, $r=_{G}1\Rightarrow r^{-1}=_{G}1$,
so $G=\left\langle X|R\cup\{r,r^{-1}\}\right\rangle $. Now $r^{-1}=_{G}1\Rightarrow r=_{G}1$,
so $r$ is redundant, so $G=\left\langle X|R\cup\{r^{-1}\}\right\rangle $.
Call these two moves $R^{\pm}$, replace relator by inverse
\item Similarly $G=\left\langle X|R\cup\{r\}\right\rangle =\left\langle X|R\cup\{g^{-1}rg\}\right\rangle $
(since $r=1\iff g^{-1}rg=1$ for any $g\in G)$. So can use $R^{\pm}$
to replace relator by conjugate. Often used for cyclic conjugates.
Replace $xyz$ by $yzx$ ($=x^{-1}(xyz)x$). 
\end{enumerate}
Whenever some generator $y$ or $y^{-1}$ appears just once in some
relators we can use $R^{\pm}$ followed by $X^{-1}$ to eliminate
$y$.
\begin{enumerate}[resume]
\item $\left\langle x,y,z|(xz)^{2},(yz)^{3},xyz\right\rangle $. We can
eliminate $x$ using $xyz=_{G}1\iff z=y^{-1}x^{-1}$. Since $x=y^{-1}x^{-1}$
we have 
\begin{eqnarray*}
(xz)^{2}=1 & \iff & (xy^{-1}x^{-1})^{2}=1\\
 & \iff & xy^{-2}x^{-1}=1\\
 & \iff & y^{-2}=1\\
 & \iff & y^{2}=1
\end{eqnarray*}
so can use $R^{\pm}$ to replace $(xy)^{2}=1$ by $y^{2}=1$. Similarly
$(yz)^{3}=1\iff x^{3}=1$. So by $R^{\pm}$, $G=\left\langle x,y,z|y^{2},x^{3},zxy\right\rangle $.
Now we can apply $X^{-}$ to get $G\cong\left\langle x,y|y^{2},x^{3}\right\rangle $
\end{enumerate}
Examples 1-3 were to illustrate how we use them, while Examples 4-5
are ``real'' examples.
\begin{enumerate}[resume]
\item $\left\langle x,y|xyxyx=yxyxy\right\rangle \cong_{X^{+}}\left\langle x,y,a|xyxyx=yxyxy,a=xy\right\rangle $,
now use $RX^{-}$ to eliminate $y=x^{-1}a$, so $G\cong\left\langle x,a|aax=x^{-1}aaa\right\rangle \cong_{X^{+}}\left\langle x,a,b|a^{2}x=x^{-1}a^{3},b=xa^{2}\right\rangle $
. Eliminate $x=a^{2}b$ by $RX^{-}$, $G\cong\left\langle a,b|b=b^{-1}a^{5}\right\rangle =\left\langle a,b|b^{2}=a^{5}\right\rangle $.
\item For $l,m,n\geq1$ define $D=(l,m,n)=\left\langle x,y|x^{l},y^{m},(xy)^{n}\right\rangle $.
(Note that $D(2,2,n)\cong D_{2n}$). Introduce $a=xy$ then eliminate
$y=x^{-1}a$. So $\left\langle x,a|x^{l},x^{-1}a)^{m},a^{n}\right\rangle $.
Replace $x$ by $x^{-1}$, $\left\langle x,a|x^{-l},(xa)^{m},a^{n}\right\rangle =\left\langle x,a|x^{l},(xa)^{m},a^{n}\right\rangle =D(l,n,m)$.
We also have clearly $D(l,m,n)\cong D(m,l,n)$. Since $(m,n)$ and
$(l,m)$ generate $S_{3}$ on $\{l,m,n\}$ we have $D(l,m,n)\cong D(l',m',n')$.
For any permutation $l',m',n'$ of $l,m,n$ (so we can assume $l\leq m\leq n$
if we want to)
\end{enumerate}
\end{example*}
The following is a basic result, but less useful than it appears because
is practice we might not know in whether $\left\langle X|R\right\rangle \cong\left\langle Y|S\right\rangle $.
Therefore it does not enable you to decide this. (It has been proved
to be undecidable in general)
\begin{prop}
\label{prop:4.7} Let $G\cong\left\langle X|R\right\rangle \cong\left\langle Y|S\right\rangle $.
Then by using a sequence of Tietze Transformation, we can transform
$\left\langle X|R\right\rangle $ to $\left\langle Y|S\right\rangle $.\end{prop}
\begin{proof}
$G\cong\left\langle X|R\right\rangle \cong\left\langle Y|S\right\rangle $.
Think of $X,Y$ as subsets of $G$. Think of $X,Y$ as subsets of
$G$. $G=\left\langle X\right\rangle =\left\langle Y\right\rangle $,
so elements of $X$ can be written as words in $(Y\cup Y^{-1})^{*}$
and vice versa. Write this $X=X(Y)$, $Y=Y(X)$, so 
\begin{flalign*}
G & \cong\left\langle X|R\right\rangle \\
 & \cong\left\langle X|R(X)\right\rangle \\
 & \cong\left\langle X\cup Y|R(X)\cup\{Y=Y(X)\}\right\rangle  &  & X^{+}\\
 & =\left\langle X\cup Y|R(X)\cup\{Y=Y(X)\}\cup\{X=X(Y)\}\right\rangle  &  & R^{+}\\
 & =\left\langle Y|R(X(Y))\cup\{Y=Y(X(Y))\right\rangle  &  & R^{-}\\
 & =\left\langle Y|R(X(Y))\cup\{Y=Y(X(Y))\cup S(Y)\right\rangle  &  & R^{+}\\
 & =\left\langle Y|S(Y)\right\rangle  &  & R^{-}
\end{flalign*}

\end{proof}

\subsubsection{A Presentation of symmetric group $S_{n}$}

$S_{n}$ acts on $\{1,2,\dots,n\}$. Let $\tau_{i}=(i,i+1)$, for
$1\leq i\leq n-1$.
\begin{lem}
\label{lem:4.8} $S_{n}=\left\langle \tau_{i}|1\leq i\leq n-1\right\rangle $\end{lem}
\begin{proof}
Well known.
\end{proof}
What are the relations? We have $\tau_{i}^{2}=1$, $(\tau_{i}\tau_{i+1})^{3}=1$
since $\tau_{i}\tau_{i+1}=(i,i+2,i+1)$. Finally $(\tau_{i}\tau_{j})^{2}=1$
(equivalently $\tau_{i}\tau_{j}=\tau_{j}\tau_{i}$) for $|i-j|>1$.
\begin{prop}
\label{prop:4.9} Let $G_{n}=\left\langle X|R_{1}\cup R_{2}\cup R_{3}\right\rangle $
with $X=\{x_{1},\dots,x_{n-1}\}$, $R_{1}=\{x_{i}^{2}|1\leq i\leq n-1\}$,
$R_{2}=\{(x_{i}x_{i+1})^{3}|1\leq i\leq n-2\}$ and $R_{3}=\{(x_{i}x_{j})^{2}|i<j,|j-i|>i\}$.
Then $G_{n}\cong S_{n}$ with isomorphism $x_{i}\mapsto\tau_{i}$.\end{prop}
\begin{note*}
This presentation defines a Coxeter group. The general definition
of them is $\left\langle x_{1},\dots,x_{n}|x_{i}^{2},(x_{i}x_{j})^{m_{ij}}\,1\leq i,j\leq n\right\rangle $
with $2\leq m_{ij}\leq\infty$ and $m_{ij}=m_{ji}$. The case $n=2$
gives the Dihedral groups. They include Weyl groups studied in Lie
Algebra. Out presentation for $S_{n}$ is the Weyl group of type $A_{n-1}$. \end{note*}
\begin{proof}
By the Fundamental Theorem, the map $\theta:x_{i}\mapsto\tau_{i}$
extends to a homomorphism $\theta:G_{n}\to S_{n}$, which is surjective
by Lemma \ref{lem:4.8}. So $|G_{n}|\geq|S_{n}|=n!$.

Claim: $|G_{n}|\leq n!$ (which will prove the result)

Use induction on $n$. The case $n=1,2,3$ there is nothing to show
$(S_{3}=\left\langle x_{1},x_{2}|x_{1}^{2},x_{2}^{2},(x_{1}x_{2})^{3}\right\rangle $)

So assume $|G_{n}|\leq n!$ and we prove $|G_{n+1}|\leq(n+1$)!. Define
$H=\left\langle x_{2},\dots,x_{n}\right\rangle \leq G_{n+1}$. The
relations of $G_{n}$ are satisfied by generators of $H$ (renumbered
as $x_{1},\dots,x_{n-1}$). So by induction $|H|\leq n!$. So we want
to prove $|G:H|\leq n+1$. Note $\theta(H)\cong S_{n}$ is the stabilizer
of $1$ in $S_{n+1}$. So if $g_{0},\dots,g_{n}$ coset representation
we want $\theta(g_{0}),\dots,\theta(g_{n})$ to map $1$ to $1,2,\dots,n+1$.
So we can choose $\theta(g_{i})=\tau_{1}\dots\tau_{i}$. Then $1^{\theta(g_{i})}=1^{\tau_{1}\dots\tau_{i}}=i+1$.
Define $g_{0}=1,g_{i}=x_{2}x_{2}\dots x_{i}$, i.e., $g_{i}=g_{i-1}x_{i}$.
Define $S=\cup_{i=0}^{n}Hg_{i}$, it is enough to prove $S=G_{n}$.
So by Proposition \ref{prop:4.4} it is enough to prove $g_{i}x_{j}\in S\,\forall i,j$.
\begin{caseenv}
\item $j>i+1:$ We have $g_{i}x_{j}=x_{j}g_{i}\in S$ (since $x_{j}\in H$)
\item $j=i+1$: We have $g_{i}x_{j}=g_{i+1}\in S$
\item $j=i$: We have $g_{i}x_{j}=g_{i-1}\in S$
\item $j<i$: We prove by induction of $i-j$ that $g_{i}x_{j}=x_{j+1}g_{i}\in S$
since $x_{j+1}\in H$.


Base case: $i-j=1$ ($\Rightarrow i\geq2$ and $j=i-1$). $g_{i}x_{j}=g_{i-2}x_{i-1}x_{i}x_{i-1}=g_{i-2}x_{i}x_{i-1}x_{i}=x_{i}g_{i-2}x_{i-1}x_{i}=x_{i}g_{i}=x_{j+1}g_{i}$


Induction step: If $i=j>1$ then $g_{i}x_{j}=g_{i-1}x_{i}x_{j}=g_{i-1}x_{j}x_{i}=x_{j+1}g_{i-1}x_{i}=x_{j+1}g_{i}$
.

\end{caseenv}
So we can apply Proposition \ref{prop:4.4} to get $G_{n}=S$, hence
$|G_{n}:H|\leq n+1$, hence $|G_{n}|\leq(n+1)!$. Hence $\theta$
is an isomorphism.
\end{proof}

\subsubsection{Presentation of $(\qq,+)$}

The group $(\qq,+)$ is not finitely generated. To see this let $H=\left\langle g_{1},\dots,g_{k}\right\rangle \leq(\qq,+)$.
Then $g_{i}=m_{i}/n_{i}$ for some $m_{i}\in\zz$ and $n_{i}\in\zz_{>0}$.
Elements of $H$ all have denominators at most $\lcm(n_{1},\dots,n_{k})$,
so we cannot have $H=\qq$. 

$(\qq,+)$ is generated by $\{\nicefrac{1}{n}|n\in\zz_{>0}\}$. Also
by $\{\nicefrac{1}{n!}|n\in\zz_{>0}\}$ since any $\nicefrac{m}{n}=m(n+1)!\cdot\nicefrac{1}{n!}$
\begin{prop}
\label{prop:4.10}Let $G=\left\langle x_{i}(i\geq\zz_{>0})|x_{n}^{n}=x_{n-1}(n>1)\right\rangle $.
Then $G\cong(\qq,+)$.\end{prop}
\begin{note*}
$G$ is multiplicative, while $(\qq,+)$ is additive\end{note*}
\begin{proof}
Define $\theta:\{x_{i}\}\to(\qq,+)$ by $\theta(x_{n})=\nicefrac{1}{n!}$.
Then $\theta(x_{n}^{n})=\nicefrac{n}{n!}=\nicefrac{1}{(n-1)!}=\theta(x_{n-1})$.
So by the Fundamental Theorem $\theta$ extends to homomorphism $\theta:G\to(\qq,+)$
surjective, since $(\qq,+)$ is generated by $\{\nicefrac{1}{n!}\}$. 

We now need to prove $\ker(\theta)=1$. Given generators $x_{n},x_{m}$
of $G$, $n>m$, $x_{m}$ is some power of $x_{n}$ so $x_{n}x_{m}=x_{m}x_{n}$.
So $G$ is abelian. So for each $g\in G$, $g=x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{n}^{k_{n}}$
for some $n$, $k_{i}\in\zz$. Since $x_{j}^{j}=x_{j-1}$ for $j>1$,
we can replace $x_{j}^{j}$ by $x_{j-1}$ and assume $0\leq k_{j}<j$
for $j>1$ (and $k_{n}\neq0$). So $\theta(g)=\frac{k_{1}}{1!}+\frac{k_{2}}{2!}+\dots+\frac{k_{n}}{n!}$.
Suppose $1\neq g$, $\theta(g)=0$ (i.e., $g\in\ker(\theta)$). So
$(n-1)!\left(\frac{k_{1}}{1!}+\dots+\frac{k_{n-1}}{(n-1)!}\right)+\frac{k_{n}}{n}=m+\frac{k_{n}}{n}=0$
with $m\in\zz$. But if $n>1$ then $\frac{k_{n}}{n}\notin\zz$ since
$0<k_{n}<n$. Hence $n=1$, $g=x_{1}^{k_{1}}$ and $\theta(g)=k_{1}=0$,
hence $k_{1}=0$ and $g=1$. So $\ker(\theta)=1$.
\end{proof}

\subsection{Groups Acting on Sets (Recap)}

We use right actions (as opposed to left actions used in Algebra II)
For a group $G$ acting on a set $\Omega$, we write $\alpha^{g}$
for the action of $g\in G$ on $\alpha\in\Omega$. We can define an
\emph{action} as a homomorphism $\phi:G\to\Sym(\Omega)$ where we
write $\alpha^{g}$ instead of $\alpha^{\phi(g)}$ {[}$\phi(g)$ is
a permutation of $\Omega${]}. The \emph{kernel} of the action $\ker(\phi)=\{g\in G|\alpha^{g}=\alpha\,\forall\alpha\in\Omega\}$.
An action is \emph{faithful} if $\ker(\phi)$ is trivial, if and only
if, $G\cong\im(\phi)$. An action is \emph{transitive} if there is
a single orbit $\Omega$, i.e., $\forall\alpha,\beta\in\Omega\,\exists g\in G,\alpha^{g}=\beta$.

Two actions $\phi_{1}:G\to\Sym(\Omega_{1})$, $\phi_{2}:G\to\Sym(\Omega_{2})$
are \emph{equivalent} if there exist a bijection $\tau:\Omega_{1}\to\Omega_{2}$
with $\tau(\alpha)^{\phi_{2}(g)}=\tau(\alpha^{\phi_{1}(g)})\,\forall g\in G$. 


\subsubsection{Coset Actions}

Let $G$ be a group, $H\leq G$. Let $\Omega=\{Hg:g\in G\}$ be the
set of distinct right cosets. Define action of $G$ on $\Omega$ by
$(Hk)^{g}=Hkg$ (by right multiplication). So $\phi(g):Hk\to Hkg$,
check that $\phi(g),\phi(g^{-1})$ are inverses of each other, so
$\phi(g)\in\Sym(\Omega)$. It is clearly a homomorphism. Given $Hk_{1},Hk_{2}\in\Omega$,
$(Hk_{1})^{k_{1}^{-1}k_{2}}=Hk_{2}$, so it is transitive.

\begin{eqnarray*}
\ker(\phi) & = & \{g\in G|Hkg=Hk\,\forall k\in G\}\\
 & = & \{g\in G|kgk^{-1}\in H\,\forall k\in G\}\\
 & = & \{g\in G|g\in k^{-1}Hk\,\forall k\in G\}\\
 & = & \bigcap_{k\in G}k^{-1}Hk\\
 & =: & \mbox{Core}_{G}(H)
\end{eqnarray*}
This is the largest normal subgroups of $G$ contained in $H$. So
$H\lhd G$ if and only if $\mbox{Core}_{G}(H)=H$. So we have $1\leq\mbox{Core}_{G}(H)\leq H\leq\left\langle H^{G}\right\rangle \leq G$. 

\newpage{}


\section{Coset Enumeration}

(Todd - Coxeter 1930)

Given $G=\left\langle X|R\right\rangle $ with $X,R$ finite and a
finite set $Y\leq A^{*}$ generating $H=\left\langle Y\right\rangle \leq G$.
Algorithm tries to prove that $|G:H|$ is finite and to compute the
coset action of $G$ on the cosets of $H$. If $|G:H|$ is infinite
it will not halt. If $|G:H|$ is finite it will succeed but there
is no upper bound on the time taken. 

At any time we have a set $\Omega$ of positive, $\Omega=\{i_{1},\dots,i_{n}\}$
positive integers, which represent cosets of $H$ in $G$. For each
$i\in\Omega$ there is an associated word. For each $i\in\Omega$
there is an associated word $a_{i}\in A^{*},i\hookrightarrow a_{i}$
where $i=$coset $Ha_{i}$. We always have $1\in\Omega,a_{1}=\epsilon$.
So $1=H$. For $i\in\Omega,x\in A$, $ix$ may or may not be defined.
If defined $ix\in\Omega$. (This means $Ha_{i}x=Ha_{j}$ where $ix=j$).
We always have
\begin{description}
\item [{(R1)}] $ix=j$ if and only if $jx^{-1}=i$. 
\end{description}
For $a_{1}a_{2}\dots a_{k}\in A^{*}$ with $a_{i}\in A$. Then $ia_{1}\dots a_{k}$
is defined recursively to $(ia_{1}\dots a_{k-1})a_{k}$ provided everything
is defined.
\begin{description}
\item [{(R2)}] If $i\hookrightarrow a_{i}\in A^{*}$ with $i\in\Omega$,
then $1a_{i}$ is defined and equal to $i$. 
\end{description}
If some $ix$ is not define then we can choose some $j>0$, $j\notin\Omega$,
replace $\Omega$ by $\Omega\cup\{j\}$ and define $ix=j,jx^{-1}=i$
and put $a_{j}=a_{i}x$. So $1a_{j}=1a_{i}x=ix=j$ (Hence (R1) and
(R2) remains true)
\begin{example*}
Let $G=\left\langle x,y|x^{2},y^{3},xyxy\right\rangle $ and $H=\left\langle xy\right\rangle $. 
\begin{enumerate}
\item We have a table with a single row for each generator of $H$. For
each relator, we have a table with one row for each elements of $\Omega$.
Start with $\Omega=\{1\}$, $1\hookrightarrow\epsilon$.


\begin{tabular}{|c|c|c|c|}
\hline 
 & $x$ & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  &  & $1$\tabularnewline
\hline 
\end{tabular}


\begin{tabular}{|c|c|c|c||c|c|c|c|c||c|c|c|c|c|c|}
\hline 
 & $x$ & $x$ &  &  & $y$ & $y$ & $y$ &  &  & $x$ & $y$ & $x$ & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  &  & $1$ & $1$ &  &  &  & $1$ & $1$ &  &  &  &  & $1$\tabularnewline
\hline 
\end{tabular}

\item Now let $\Omega=\{1,2\}$, $2\hookrightarrow x$. Definitions $1x=2$,
so $2x^{-1}=1,1y^{-1}=2$: Deduction $2y=1$ (from $(a)$), $2x=1$
(from $(b)$). (Note $\_$ stands for, by definition)


\begin{tabular}{|c|c|c|c|c|}
\hline 
 & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ & $\_$ & $2$ & $\overset{(a)}{=}$ & $1$\tabularnewline
\hline 
\end{tabular}


\begin{tabular}{|c|c|c|c|c||c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|}
\hline 
 & $x$ &  & $x$ &  &  & $y$ &  & $y$ &  & $y$ &  &  & $x$ &  & $y$ &  & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ & $\overset{(b)}{=}$ & $1$ & $1$ &  &  &  & $2$ &  & $1$ & $1$ &  & $2$ &  & $1$ &  & $2$ &  & $1$\tabularnewline
\hline 
$2$ &  & $1$ &  & $2$ & $2$ &  & $1$ &  &  &  & $2$ & $2$ &  & $1$ &  &  &  &  &  & $2$\tabularnewline
\hline 
\end{tabular}

\item Now let $\Omega=\{1,2,3\}$, $3\hookrightarrow y$. Definitions: $1y=3$.
Deductions: $3y=2$ (from $(c)$), $3x=3$ (from $(d)$)


\begin{tabular}{|c|c|c|c|c|}
\hline 
 & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ & $\_$ & $2$ & $\overset{(a)}{=}$ & $1$\tabularnewline
\hline 
\end{tabular}


\begin{tabular}{|c|c|c|c|c||c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|}
\hline 
 & $x$ &  & $x$ &  &  & $y$ &  & $y$ &  & $y$ &  &  & $x$ &  & $y$ &  & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ & $\overset{(b)}{=}$ & $1$ & $1$ & $\_$ & $3$ & $\overset{(c)}{=}$ & $2$ &  & $1$ & $1$ &  & $2$ &  & $1$ &  & $2$ &  & $1$\tabularnewline
\hline 
$2$ &  & $1$ &  & $2$ & $2$ &  & $1$ &  & $3$ &  & $2$ & $2$ &  & $1$ &  & $3$ & $\overset{(d)}{=}$ & $3$ &  & $2$\tabularnewline
\hline 
$3$ &  & $3$ &  & $3$ & $3$ &  & $2$ &  & $1$ &  & $3$ & ,3 &  & $3$ &  & $2$ &  & $1$ &  & $3$\tabularnewline
\hline 
\end{tabular}

\end{enumerate}
Now $ix$ is defined for all $i\in\Omega,x\in A$. All tables are
complete, so the process stops. We have shown that $|G:H|=3$ with
$i\to ia$ defining an action $\phi$ of $G$ on $\Omega=\{1,2,3\}$
defined by $x\mapsto(1,2),y\mapsto(1,2,3)$. So $\phi:G\to\Sym(\Omega)$,
hence $\im(\phi)=\Sym(3)$ which has order $6$. Hence $|G|\geq6$.
Since $H=\left\langle xy\right\rangle $ with $(xy)^{2}=1$, $|H|\leq2$,
hence $|G|\leq6$. So $|G|=6$. 
\end{example*}
We also have:
\begin{description}
\item [{(R3)}] If $i\hookrightarrow a_{i},j\hookrightarrow a_{j}$ and
$ix=j$, then $Ha_{i}x=Ha_{j}$. \end{description}
\begin{prop}
\emph{(R3)} remains true during the process.\end{prop}
\begin{proof}
$ix=j$ is either a definition or a deduction. If it is a definition
then we define $a_{j}$ so to make (R3) true.

So assume that it is a deduction, from a row of a table.
\begin{caseenv}
\item From row $k$ of relator $x_{1}x_{2}\dots x_{s}$, of a relator table.


\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & $x_{1}$ & $x_{2}$ & $\dots$ &  & $x_{t}=x$ &  & $x_{t+1}$ & $\dots$ & $x_{s}$ & \tabularnewline
\hline 
\hline 
$k$ & \multicolumn{1}{c}{} & \multicolumn{1}{c}{all defined} &  & $i$ & deduced $ix=j$ & $j$ & \multicolumn{1}{c}{} & \multicolumn{1}{c}{all defined} &  & $k$\tabularnewline
\hline 
\end{tabular}Can assume by induction that (R3) is true for all equations $i'x'=j'$
that are know prior to deduction of $ix=j$. So $Ha_{k}x_{1}\dots x_{t-1}=Ha_{i}$,
$Ha_{j}x_{t+1}\dots x_{s}=Ha_{k}$. So $Ha_{j}x_{t+1}\dots x_{s}x_{1}\dots x_{t-1}=Ha_{i}$.
Hence $x_{1}x_{2}\dots x_{s}=_{G}1\Rightarrow x_{t+1}\dots x_{s}x_{1}\dots x_{t}=_{G}1$
(cyclic conjugate). So $Ha_{i}x_{t}=Ha_{j}x_{t+1}\dots x_{s}x_{1}\dots x_{t+1}x_{t}=Ha_{j}$

\item Deduction as above, but from a subgroup generator, so $k=1$ and $Ha_{k}=H$.
So $x_{1}x_{2}\dots x_{s}\in H$. As $Ha_{i}x=Ha_{i}x_{t}=Hx_{1}\dots x_{t}=Hx_{s}^{-1}\dots x_{t-1}^{-1}=Ha_{j}$,
since $x_{1}x_{2}\dots x_{s}\in H$. 
\end{caseenv}
\end{proof}
\begin{thm}
\label{thm:5.2} Suppose the process terminates with $H=\left\langle y\right\rangle \leq G=\left\langle X|R\right\rangle $.
Then there exists an action $\theta$ of $G$ on $\Omega$ with $i^{\theta(x)}=i^{x}=j\iff ix=j$.
The action is equivalent to the coset action of $G$ on right cosets
of $\Omega$, with equivalence $\tau$, with $\tau(i)=Ha_{i}$ for
$i\in\Omega$. \end{thm}
\begin{proof}
When the process stops all $ix$ are defined. So define $\theta(x):\Omega\to\Omega$
by $i^{\theta(x)}=i^{x}=ix$, for all $x\in A$. Now (R1) says $\theta(x^{-1})=\theta(x)^{-1}$,
so $\theta\in\Sym(\Omega)$. The fact that relators tables are full,
says exactly that all relators $r$, $k^{\theta(r)}=k$ for all $k\in\Omega$.
So $\theta(r)$ is the identity and by the Fundamental Theorem $\theta$
extends to $\theta:G\to\Sym(\Omega)$. 

Define $\tau:\Omega\to\{Hg:g\in\Omega\}$ by $\tau(i)=Ha_{i}$ with
$i\hookrightarrow a_{i}$. Show that $\tau$ is a surjection. Let
$g\in G$, $g=x_{1}x_{2}\dots x_{s}$ (for $x_{i}\in A$) . $1g=1x_{1}x_{2}\dots x_{s}=i$
for some $i\in\Omega$. By (R3), $Hg=Ha_{i}$ with $i\hookrightarrow a_{i}$.
So $\tau(i)=Ha_{i}=Hg$. So $\tau$ is indeed a surjection.

Now to show $\tau$ is injective. Suppose $\tau(i)=\tau(j)$ ($i\hookrightarrow a_{i},j\hookrightarrow a_{j}$),
then $Ha_{i}=Ha_{j}$, so $a_{i}a_{j}^{-1}\in H=\left\langle y\right\rangle $.
So $a_{i}a_{j}^{-1}=y_{1}\dots y_{t}$ with $y_{i}\in Y\cup Y^{-1}$.
From subgroups tables, $1y_{i}=1\,\forall y_{i}\in Y$. So $1a_{i}a_{j}^{-1}=1^{y_{1}\dots y_{t}}=1$.
Hence $1a_{i}=1a_{j}\Rightarrow i=j$ by (R2).

By (R3) we have $ix=j\Rightarrow Ha_{i}x=Ha_{j}$. Hence $\tau$ is
an equivalence of actions. \end{proof}
\begin{example*}
Let $G=\left\langle x,y|x^{3},y^{4},(xy)^{2}\right\rangle =D(3,4,2)$
and $H=\left\langle y\right\rangle $, so we have one subgroup table
\begin{tabular}{|c|c|c|}
\hline 
 & $y$ & \tabularnewline
\hline 
\hline 
$1$ & $=$ & $1$\tabularnewline
\hline 
\end{tabular}
\begin{itemize}
\item Starting table of the relators:


\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|}
\hline 
 & $x$ &  & $x$ &  & $x$ &  &  & $y$ &  & $y$ &  & $y$ &  & $y$ &  &  & $x$ &  & $y$ &  & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  &  &  &  &  & $1$ & $1$ &  & $1$ &  & $1$ &  & $1$ &  & $1$ & $1$ &  &  &  &  &  & $1$ &  & $1$\tabularnewline
\hline 
\end{tabular}

\item Next define $1x=2,2x=3$


\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|}
\hline 
 & $x$ &  & $x$ &  & $x$ &  &  & $y$ &  & $y$ &  & $y$ &  & $y$ &  &  & $x$ &  & $y$ &  & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $3$ & $=$ & $1$ & $1$ &  & $1$ &  & $1$ &  & $1$ &  & $1$ & $1$ &  & $2$ & $=$ & $3$ &  & $1$ &  & $1$\tabularnewline
\hline 
$2$ &  & $3$ &  & $1$ &  & $2$ & $2$ &  & $3$ &  &  &  &  &  & $2$ & $2$ &  & $3$ &  &  &  &  &  & $2$\tabularnewline
\hline 
$3$ &  & $1$ &  & $2$ &  & $3$ & $3$ &  &  &  &  &  & $2$ &  & $3$ & $3$ &  & $1$ &  & $1$ &  & $2$ &  & $3$\tabularnewline
\hline 
\end{tabular}

\item Next defined $3y=4$ and $4y=5$ 


\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|}
\hline 
 & $x$ &  & $x$ &  & $x$ &  &  & $y$ &  & $y$ &  & $y$ &  & $y$ &  &  & $x$ &  & $y$ &  & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $3$ & $=$ & $1$ & $1$ &  & $1$ &  & $1$ &  & $1$ &  & $1$ & $1$ &  & $2$ & $=$ & $3$ &  & $1$ &  & $1$\tabularnewline
\hline 
$2$ &  & $3$ &  & $1$ &  & $2$ & $2$ &  & $3$ &  & $4$ &  & $5$ & $=$ & $2$ & $2$ &  & $3$ &  & $4$ & $=$ & $5$ &  & $2$\tabularnewline
\hline 
$3$ &  & $1$ &  & $2$ &  & $3$ & $3$ &  & $4$ &  & $5$ &  & $2$ &  & $3$ & $3$ &  & $1$ &  & $1$ &  & $2$ &  & $3$\tabularnewline
\hline 
$4$ &  & $5$ &  &  &  & $4$ & $4$ &  & $5$ &  & $2$ &  & $3$ &  & $4$ & $4$ &  & $5$ &  & $2$ &  & $3$ &  & $4$\tabularnewline
\hline 
$5$ &  &  &  &  &  & $5$ & $5$ &  & $2$ &  & $3$ &  & $4$ &  & $5$ & $5$ &  &  &  &  &  & $4$ &  & $5$\tabularnewline
\hline 
\end{tabular}

\item Finally define $5x=6$


\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|}
\hline 
 & $x$ &  & $x$ &  & $x$ &  &  & $y$ &  & $y$ &  & $y$ &  & $y$ &  &  & $x$ &  & $y$ &  & $x$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $3$ & $=$ & $1$ & $1$ &  & $1$ &  & $1$ &  & $1$ &  & $1$ & $1$ &  & $2$ & $=$ & $3$ &  & $1$ &  & $1$\tabularnewline
\hline 
$2$ &  & $3$ &  & $1$ &  & $2$ & $2$ &  & $3$ &  & $4$ &  & $5$ & $=$ & $2$ & $2$ &  & $3$ &  & $4$ & $=$ & $5$ &  & $2$\tabularnewline
\hline 
$3$ &  & $1$ &  & $2$ &  & $3$ & $3$ &  & $4$ &  & $5$ &  & $2$ &  & $3$ & $3$ &  & $1$ &  & $1$ &  & $2$ &  & $3$\tabularnewline
\hline 
$4$ &  & $5$ &  & $6$ & $=$ & $4$ & $4$ &  & $5$ &  & $2$ &  & $3$ &  & $4$ & $4$ &  & $5$ &  & $2$ &  & $3$ &  & $4$\tabularnewline
\hline 
$5$ &  & $6$ &  & $4$ &  & $5$ & $5$ &  & $2$ &  & $3$ &  & $4$ &  & $5$ & $5$ &  & $6$ & $=$ & $6$ &  & $4$ &  & $5$\tabularnewline
\hline 
$6$ &  & $4$ &  & $5$ &  & $6$ & $6$ &  & $6$ &  & $6$ &  & $6$ &  & $6$ & $6$ &  & $4$ &  & $5$ &  & $6$ &  & $6$\tabularnewline
\hline 
\end{tabular}

\end{itemize}
Then we are done as all tables are complete and all definition have
been made. So $|G:H|=6$ and since $|H|\leq4$, we have $|G|\leq24$.
We can also show $|G|\geq24$ by the map $\phi:G\to S_{4}$ with $\phi(x)=(1,2,3)$,
$\phi(y)=(1,3,2,4)$ and $\phi(xy)=(1,4)$. This easily shows that
$\im(\phi)=S_{4}$ so $|G|\geq24$, hence $G\cong S_{4}$. So $\phi$
is an isomorphism.
\end{example*}
\textbf{Coincidences}: Sometimes we get a deduction $ix=j$ where
we already know $ix=k$ with $k\neq j$, (or $kx=j$ for $k\neq i$).
This means coset $Ha_{j}$ and $Ha_{k}$ (respectively $Ha_{i},Ha_{k}$)
are equal. This is a deduction $j=k$. 

If we find $Ha_{j}=Ha_{k}$ with $k>j$, then we replace all $k$
by $j$ in tables which often leads to more coincidences.
\begin{example*}
Let $G=\left\langle a,b|a^{-1}ba=b^{3},b^{-1}ab=a^{3}\right\rangle $
and $H=\left\langle a\right\rangle $. Then the subgroup table is
just %
\begin{tabular}{|c|c|c|}
\hline 
 & $a$ & \tabularnewline
\hline 
\hline 
$1$ & $=$ & $1$\tabularnewline
\hline 
\end{tabular}
\begin{itemize}
\item Setting up the table:


{\footnotesize }%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & {\footnotesize $a^{-1}$} &  & {\footnotesize $b$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $ $} & {\footnotesize $b^{-1}$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} & \tabularnewline
\hline 
\hline 
{\footnotesize $1$} &  & {\footnotesize $1$} &  &  &  &  &  &  &  &  &  & {\footnotesize $1$} & {\footnotesize $1$$ $} &  &  &  &  &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$}\tabularnewline
\hline 
\end{tabular}{\footnotesize \par}

\item Define $1b=2$


{\footnotesize }%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & {\footnotesize $a^{-1}$} &  & {\footnotesize $b$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $ $} & {\footnotesize $b^{-1}$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} & \tabularnewline
\hline 
\hline 
{\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  &  &  & {\footnotesize $2$} &  & {\footnotesize $1$} & {\footnotesize $1$$ $} &  &  &  &  &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$}\tabularnewline
\hline 
{\footnotesize $2$} &  &  &  &  &  &  &  &  &  &  &  & {\footnotesize $2$} & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  &  &  &  &  & {\footnotesize $2$}\tabularnewline
\hline 
\end{tabular}{\footnotesize \par}

\item Defined $1b^{-1}=3$


{\footnotesize }%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & {\footnotesize $a^{-1}$} &  & {\footnotesize $b$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $ $} & {\footnotesize $b^{-1}$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} & \tabularnewline
\hline 
\hline 
{\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $3$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} & {\footnotesize $1$$ $} &  & {\footnotesize $3$} & {\footnotesize $=$} & {\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$}\tabularnewline
\hline 
{\footnotesize $2$} &  &  &  &  &  &  &  &  &  &  &  & {\footnotesize $2$} & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  &  &  &  &  & {\footnotesize $2$}\tabularnewline
\hline 
{\footnotesize $3$} &  & {\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $3$} & {\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $3$} &  & {\footnotesize $3$} &  & {\footnotesize $3$} &  & {\footnotesize $3$}\tabularnewline
\hline 
\end{tabular}{\footnotesize \par}

\item But we are deducing $2b=1$, but $3b=1$, so $2=3$. Hence replace
$3$ by $2$


{\footnotesize }%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & {\footnotesize $a^{-1}$} &  & {\footnotesize $b$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $ $} & {\footnotesize $b^{-1}$} &  & {\footnotesize $a$} &  & {\footnotesize $b^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} &  & {\footnotesize $a^{-1}$} & \tabularnewline
\hline 
\hline 
{\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} & {\footnotesize $1$$ $} &  & {\footnotesize $2$} & {\footnotesize $=$} & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$}\tabularnewline
\hline 
{\footnotesize $2$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $2$} &  & {\footnotesize $2$} &  & {\footnotesize $2$}\tabularnewline
\hline 
{\footnotesize $2$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} & {\footnotesize $2$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $2$} &  & {\footnotesize $2$} &  & {\footnotesize $3$}\tabularnewline
\hline 
\end{tabular}{\footnotesize \par}

\end{itemize}
So we didn't need the last row, and the table is complete. We get
$|G:H|=2$ and $b\to(1,2)$ and $a\to\id$. Since $|H:G|=2$ we have
$H\lhd G$, so $b^{2}\in H=\left\langle a\right\rangle .$So $b^{2}a=ab^{2}$
(since $H$ is abelian). Hence $a^{-1}ba=b^{3}$ implies $a^{-1}b^{2}a=(a^{-1}ba)^{2}=b^{6}$,
but $a^{-1}b^{2}a=b^{2},$ we get $b^{6}=b^{2}$ and hence $b^{4}=1$.
By symmetry $a^{4}=1$, so $|H|\leq4$ and $|G|\leq8$. To prove $|G|\geq8$,
let $H$ be the multiplicative group of complex $2\times2$ matrices
generated by $g=\begin{pmatrix}0 & 1\\
-1 & 0
\end{pmatrix}$ and $h=\begin{pmatrix}i & 0\\
0 & -i
\end{pmatrix}$. Then $g^{2}=h^{2}=-I_{2}$ and $g^{-1}=\begin{pmatrix}0 & -1\\
1 & 0
\end{pmatrix}$ and $h^{-1}=\begin{pmatrix}-i & 0\\
0 & i
\end{pmatrix}$. We have $g^{-1}hg=\begin{pmatrix}0 & i\\
i & 0
\end{pmatrix}g=\begin{pmatrix}-i & 0\\
0 & i
\end{pmatrix}=h^{3}$. Similarly $h^{-1}gh=g^{3}$. So we get $\phi:G\to H$, since $|g|=4$
and $h\notin\left\langle g\right\rangle $, $|H|>4$, since $|H|\,|\,|G|\,|8$
we must have $|G|=|H|=8$, so $\theta$ is an isomorphism. This group
is called the quaternion $Q_{8}$. 
\end{example*}
It can be shown that (R1),(R2),(R3) remain true after processing coincides.
So Theorem \ref{thm:5.2} is still true.

We have not discussed how we can decide which new definition to make.
By hand the natural choice is to fill small gaps in tables to get
deductions. But this can result in long relations being ignored, which
could be bad.

There are two main systematic strategies used in programming. 
\begin{enumerate}
\item Choose the first $i\in\Omega$ for which $ia$ is undefined for some
$a\in A=X\cup X^{-1}$ and define it. This means we define cosets
$Ha_{i}$ is order of increasing $a_{i}$ in the lenlex order.
\item Go through relator tables in order filling in gaps as you go (even
for long gaps)
\end{enumerate}
Generally 1.~ is better for work by hand. Also 2.~leads to many
more coincidences, but it is easier to program and runs fast on computers
for routine examples. Another advantage of 2.~is that each row of
each relator table only needs to be scanned once while with one 1.~need
to keep revisiting row. It is important that strategy satisfies 
\begin{description}
\item [{(R4)}] $\forall i\in\Omega,a\in A$, $ia$ will eventually be defined. 
\end{description}
(R4) is satisfied with 1~but not necessarily with 2~so we must occasionally
use 1~($xx^{-1},x^{-1}x$)
\begin{thm}
\label{thm:5.3}If $|G:H|$ is finite and definition strategy satisfies
\emph{(R4)} then it will eventually finish.\end{thm}
\begin{proof}
With a coincidence $i=j$, $i>j$ meaning $Ha_{i}=Ha_{j}$, we eliminate
larger number $i$, so numbers in $\Omega$ representing $Ha_{i}$
can only decrease so must eventually stabilise as $Ha_{k}$. From
then on, $k\in\Omega$ and remains there.

Let $\overline{\Omega}$ be the set of stabilised numbers in $\Omega$.
(Note: We have no way of knowing during the run whether a number is
in $\overline{\Omega}$. It is in $\overline{\Omega}$ if it would
not change any more however long the process ran.)
\begin{caseenv}
\item $\overline{\Omega}$ is finite. Then once all elements that will ever
be in $\overline{\Omega}$ are in $\overline{\Omega}$, then $\overline{\Omega}$
stabilise. By (R4) eventually all $ia$ are defined and in $\overline{\Omega}$,
with $i\in\overline{\Omega}$, $a\in X$. At that point, $\Omega=\overline{\Omega}$
(since all elements of $\Omega$ can be reached by definitions from
cosets) and the process stops
\item $\overline{\Omega}$ is infinite. It is still true that $ia$ are
eventually defined and in $\overline{\Omega}$ for all $i\in\Omega$,
$a\in A$ by (R4). (R1), (R2), (R3) still all hold. So Theorem \ref{thm:5.2}
applies to action of $G$ on $\overline{\Omega}$, so this action
is equivalent to coset action. Hence $|\overline{\Omega}|=|G:H|$
contradicting $|G:H|$ finite.
\end{caseenv}
\end{proof}
\newpage{}


\section{Presentation of Subgroups}


\subsection{Digression}
\begin{defn}
For $g,h\in G$, we define the \emph{commutator} of $g,h$ to be $[g,h]=g^{-1}h^{-1}gh$.
\end{defn}
Note that $[g,h]=1$ if and only if $gh=hg$. Also $[g,h]^{-1}=[h,g]$.
\begin{defn}
The \emph{Commutator Subgroup} (or \emph{Derived} \emph{Group}) of
$G$ denoted $[G,G]$ (or $G'$) is the group $\left\langle [g,h]|g,h\in G\right\rangle $.
i.e., the subgroup of $G$ generated by the commutators. 
\end{defn}
There exists $G$ where not all elements of $[G,G]$ are commutators,
for example in the free group on $a,b,c,d$ we have $[a,b][c,d]$
is not a commutator.
\begin{defn}
A subgroup $H$ of $G$ is \emph{characteristic }if $\alpha(H)=H\,\forall\alpha\in\aut(G)$
(write $H\mbox{char}G$)
\end{defn}
Since for $g\in G$ the map $c_{g}:G\to G$ defined by $h\mapsto g^{-1}hg$
is in $\aut(G)$, we have $H\mbox{char}G$ implies $H\lhd G$.

Note that for $\alpha\in\aut(G)$ we have $\alpha([g,h])=[\alpha(g),\alpha(h)]$.
So $\alpha$ permutes the set of commutators so $[G,G]\mbox{char}G$
(and hence $[G,G]\lhd G$). 

We have $G/[G,G]$ is abelian since $g,h\in G,[g,h]\in[G,G]$ so $[g,h]=1$
in $G/[G,G]$. 
\begin{thm}
\label{thm:5.a}For any $N\lhd G$, we have $G/N$ is abelian if and
only if $[G,G]\leq N$\end{thm}
\begin{proof}
We have
\begin{eqnarray*}
G/N\mbox{ abelian} & \iff & [gN,hN]=1\,\forall g,h\in G\\
 & \iff & [g,h]\in N\,\forall g,h\in G\\
 & \iff & \left\langle [g,h]|g,h\in G\right\rangle \leq N\\
 & = & [G,G]
\end{eqnarray*}
\end{proof}
\begin{prop}
\label{prop:6.1} Let $G=\left\langle X|R\right\rangle $, then $G/[G,G]\cong\left\langle C|R\cup C\right\rangle $
where $C=\{[x,y]|x,y\in X\}$\end{prop}
\begin{proof}
Let $F$ be free on $X$, $N=\left\langle R^{F}\right\rangle ,$$M=\left\langle (R\cup C)^{F}\right\rangle $.
So $G=F/N$ and let $\overline{G}=\left\langle X|R\cup C\right\rangle =F/M$.
Since $[x,y]\in M\,\forall x,y\in X$ the generators of $\overline{G}$
all commutes. Hence $\overline{G}$ is abelian. By the third isomorphism
theorem we have 
\[
\overline{G}=F/M\cong\frac{F/N}{M/N}=\frac{G}{M/N}
\]
 which is abelian. So $[G,G]\leq M/N$. 

$M=\left\langle g^{-1}kg|g\in H,k\in R\cup C\right\rangle $ for $k\in R$
we have $g^{-1}kg\in N$. So $M/N$ is generated by the elements $g^{-1}kgN$,
$g\in F,k\in C$. So $g^{-1}kg$ is a commutator, hence so is $g^{-1}kgN$.
So $M/N$ is generated by commutators, hence $M/N\leq[G,G]$.

Hence $M/N=[G,G]$, and so $G/[G,G]\cong G/(M/N)\cong\overline{G}$.\end{proof}
\begin{example*}
If $G=\left\langle x,y|x^{2},y^{3},(xy)^{6}\right\rangle $ , then
$G/[G,G]=\left\langle x,y|x^{2},y^{3},(xy)^{6},[x,y]\right\rangle $. 
\end{example*}

\subsection{Presentation of subgroups}

Let $G=\left\langle X|R\right\rangle ,H=\left\langle Y\right\rangle $
with $X,R,H,|G:H|$ all finite. We describe the Reidemeister - Schreier
algorithm to derive a presentation of $H$. Recall, let $U$ be a
Schreier Transversal of $H$ in $G$, $u\in G$, $\overline{u}=$coset
representation of $u$. Then $Z=\{ux\overline{ux}^{-1}|u\in U,x\in X,ux\neq\overline{ux}\}$
is a Schreier Generator of $H$.

This method gives presentation of $H$ with generators of $Z$. A
variant gives a presentation on user supplied generating set $Y$,
this is more complicated.

The method requires coset representation of $G$ on right cosets of
$H$. Theorem \ref{thm:5.2} says that coset enumeration gives this.
But in our first example, we just work it out without coset enumeration.
We describe the process while working through the example. 
\begin{example*}
Let $G=\left\langle x,y|x^{2},y^{3},(xy)^{6}\right\rangle =D(2,3,6)$.
We define $H=[G:G]$, as we saw before $G/H\cong\left\langle x,y|x^{2},y^{3},(xy)^{6},xy=yx\right\rangle $.
In $G/H$ the relator $(xy)^{6}=x^{6}y^{6}=1$, so it is redundant.
So $G/H\cong\left\langle x,y|x^{2},y^{3},xy=yx\right\rangle \cong C_{2}\times C_{3}\cong C_{6}$
by Proposition \ref{prop:4.6}. So $|G:H|=6$. We will write down
the coset action ( which is the same as the regular representation
of $G/H$).

Define $\theta:G\to\Sym(6)$ by $\theta(x)=(1,2)(3,4)(5,6)$ and $\theta(y)=(1,3,5)(2,4,6)$.
{[}We use the facts that $|\theta(x)|=2,|\theta(y)|=3,\theta(x)$
and $\theta(y)$ fixes no points, and the fact $\theta(x)\theta(y)=\theta(y)\theta(x)${]}
So we have $\theta(xy)=(1,4,5,2,3,6)$, $\theta(xy)^{4}=\theta(y),\theta(xy)^{5}=\theta(x)$.
So $\im(\theta)=\left\langle \theta(xy)\right\rangle $, hence $|\im(\theta)|=6$.
Since it is abelian we have $G/\ker(\theta)\cong\im(\theta)$, so
$[G:G]\leq\ker(\theta)$. Hence $|G/H|=|G/\ker(\theta)|=6$, so $\ker(\theta)=H$.
\begin{xca*}
Show $\theta$ is equivalent to coset representation on cosets of
$H$
\end{xca*}
Write action of $\theta$ down as a table:

\begin{tabular}{|c||c|c|c|c|}
\hline 
 & $x$ & $y$ & $x^{-1}$ & $y^{-1}$\tabularnewline
\hline 
\hline 
$1$ & $\underline{2}$ & $\underline{3}$ & $2$ & $\underline{5}$\tabularnewline
\hline 
$2$ & $1$ & $\underline{4}$ & $1$ & $\underline{6}$\tabularnewline
\hline 
$3$ & $4$ & $5$ & $4$ & $1$\tabularnewline
\hline 
$4$ & $3$ & $6$ & $3$ & $2$\tabularnewline
\hline 
$5$ & $6$ & $1$ & $6$ & $3$\tabularnewline
\hline 
$6$ & $5$ & $2$ & $5$ & $4$\tabularnewline
\hline 
\end{tabular}

Scan the rows, and underline new numbers, regard the underline of
numbers as definitions of these numbers. (Its important to do this
even if you have definitions already from coset enumerations, since
otherwise might not get Schreier transversal). So we have the definitions:
$1x=2,1y=3,1y^{-1}=5,2y=4$ and $2y^{-1}=6$. We are also going to
underline (twice) the inverse of the definitions:

\begin{tabular}{|c||c|c|c|c|}
\hline 
 & $x$ & $y$ & $x^{-1}$ & $y^{-1}$\tabularnewline
\hline 
\hline 
$1$ & $\underline{2}$ & $\underline{3}$ & $2$ & $\underline{5}$\tabularnewline
\hline 
$2$ & $1$ & $\underline{4}$ & $\underline{\underline{1}}$ & $\underline{6}$\tabularnewline
\hline 
$3$ & $4$ & $5$ & $4$ & $\underline{\underline{1}}$\tabularnewline
\hline 
$4$ & $3$ & $6$ & $3$ & $\underline{\underline{2}}$\tabularnewline
\hline 
$5$ & $6$ & $\underline{\underline{1}}$ & $6$ & $3$\tabularnewline
\hline 
$6$ & $5$ & $\underline{\underline{2}}$ & $5$ & $4$\tabularnewline
\hline 
\end{tabular}

For the other entries, such as $2x=1$, we get associated Schreier
generators. Things of the entries are of the from $ux=\overline{ux}$,
Schreier generators $ux\overline{ux}^{-1}$. Call these $a,b,c,\dots$
so that $ux\overline{ux}^{-1}=a$ implies $ux=a\overline{ux}$. So
$2x=1$ becomes $2x=a\cdot1$, with $a$ a Schreier generator.

\begin{tabular}{|c||c|c|c|c|}
\hline 
 & $x$ & $y$ & $x^{-1}$ & $y^{-1}$\tabularnewline
\hline 
\hline 
$1$ & $\underline{2}$ & $\underline{3}$ & $2$ & $\underline{5}$\tabularnewline
\hline 
$2$ & $a1$ & $\underline{4}$ & $\underline{\underline{1}}$ & $\underline{6}$\tabularnewline
\hline 
$3$ & $b4$ & $c5$ & $4$ & $\underline{\underline{1}}$\tabularnewline
\hline 
$4$ & $d3$ & $e6$ & $3$ & $\underline{\underline{2}}$\tabularnewline
\hline 
$5$ & $f6$ & $\underline{\underline{1}}$ & $6$ & $3$\tabularnewline
\hline 
$6$ & $g5$ & $\underline{\underline{2}}$ & $5$ & $4$\tabularnewline
\hline 
\end{tabular}

So we have $\{a,b,c,d,e,f,g\}=Z$. Recall that $Z^{-1}=\{ux^{-1}\overline{ux^{-1}}^{-1}|u\in U,x\in X\}$,
so we can fill these in. For example $2x=a1$ implies $1x^{-1}=a^{-1}2$.

\begin{tabular}{|c||c|c|c|c|}
\hline 
 & $x$ & $y$ & $x^{-1}$ & $y^{-1}$\tabularnewline
\hline 
\hline 
$1$ & $\underline{2}$ & $\underline{3}$ & $a^{-1}2$ & $\underline{5}$\tabularnewline
\hline 
$2$ & $a1$ & $\underline{4}$ & $\underline{\underline{1}}$ & $\underline{6}$\tabularnewline
\hline 
$3$ & $b4$ & $c5$ & $d^{-1}4$ & $\underline{\underline{1}}$\tabularnewline
\hline 
$4$ & $d3$ & $e6$ & $b^{-1}3$ & $\underline{\underline{2}}$\tabularnewline
\hline 
$5$ & $f6$ & $\underline{\underline{1}}$ & $g^{-1}6$ & $c^{-1}3$\tabularnewline
\hline 
$6$ & $g5$ & $\underline{\underline{2}}$ & $f^{-1}5$ & $e^{-1}4$\tabularnewline
\hline 
\end{tabular}

Now all entries are either underlined or have a letter.
\begin{thm}
\label{thm:6.2}Let $G=\left\langle X|R\right\rangle =F/N$ with $F$
free on $X$ and $N=\left\langle R^{F}\right\rangle $. Let $H=E/N\leq G$.
Let $U$ be a Schreier Transversal of $E$ in $F$ (or equivalently
of $H$ in $G$, since we are using the same letters $x\in X$ to
denote elements of $G$ and $F$). Then $N=\left\langle S^{E}\right\rangle $
where $S=\{uwu^{-1}|u\in U,w\in R\}$ (so $|S|=|G:H|\times|R|\}$. \end{thm}
\begin{proof}
$N=\left\langle R^{F}\right\rangle $, with $R^{F}=\{gwg^{-1}|g\in F,w\in R\}$.
Each $g=_{F}hu$ with $h\in E,u\in U$. So $R^{F}=\{h(uwu^{-1})h^{-1}|h\in E,w\in R,u\in U\}=S^{E}$.
So $N=\left\langle R^{F}\right\rangle =\left\langle S^{E}\right\rangle $\end{proof}
\begin{cor}
\label{cor:6.3} Let $Y$ be the set of Schreier generators of $H$
in $G$ (or equivalently of $E$ in $F$). Then $H\cong\left\langle Y|S(Y)\right\rangle $
where $S(Y)$ is the set $S=\{uwu^{-1}|u\in U,w\in R\}$, but rewritten
as words in $(Y\cup Y^{-1})^{*}$.\end{cor}
\begin{proof}[Idea of Proof]
 $E$ is free on $Y$ by Theorem \ref{thm:3.8}, and $N=\left\langle S^{E}\right\rangle $
by the previous theorem. So $\left\langle Y|S(Y)\right\rangle $ is
a presentation of $H=E/N$. (Warning this is not a \uline{formal}
proof, because we've not justified the change of generators $S$ to
$S(Y)$. The correctness depends on $U$ being a Schreier transversal,
otherwise $\left\langle Y|S(Y)\cup Y=X(Y(X))\right\rangle $)
\end{proof}
So looking at row $u$ of relator table tracing it through using table
gives us $r$

\begin{tabular}{|c|c|c|c|c|}
\hline 
 & $x$ &  & $x$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $a1$\tabularnewline
\hline 
$2$ &  & $a1$ &  & $a2$\tabularnewline
\hline 
$3$ &  & $b4$ &  & $bd3$\tabularnewline
\hline 
$4$ &  & $d3$ &  & $db4$\tabularnewline
\hline 
$5$ &  & $f6$ &  & $fg5$\tabularnewline
\hline 
$6$ &  & $g6$ &  & $gf6$\tabularnewline
\hline 
\end{tabular}

relators from $w=x^{2}$ are $a,a,bd,db,fg,gf$. If rows of table
are cyclic conjugate then so are the resulting relators, so only need
one of them.

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
 & $y$ &  & $y$ &  & $y$ & \tabularnewline
\hline 
\hline 
$1$ &  & $3$ &  & $c5$ &  & $c1$\tabularnewline
\hline 
$2$ &  & $4$ &  & $e6$ &  & $e2$\tabularnewline
\hline 
\end{tabular}

Note that the rest of the rows ($3$ to $6$) are cyclic conjugates.
The tracing for $1(xy)^{6}$ is as follows:

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
\hline 
 & $x$ &  & $y$ &  & $x$ &  & $y$ &  & $x$ &  & $y$ &  & $x$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $4$ &  & $d3$ &  & $dc5$ &  & $dcf6$ &  & $dcf2$ &  & $dcfa1$\tabularnewline
\hline 
\end{tabular}

\selectlanguage{english}%
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|}
\hline 
\selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$y$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$x$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$y$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$x$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$y$\selectlanguage{english}%
\tabularnewline
\hline 
\hline 
\selectlanguage{british}%
$defa1$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$dcfa3$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$dcfab4$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$dcfabe6$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
$dcfabeg5$\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
\tabularnewline
\hline 
\end{tabular}

\selectlanguage{british}%
Note that all numbers arise in the above row, so all other rows gives
cyclic conjugates of same relators. Usually the resulting presentation
of $H$ can be simplified 
\begin{flalign*}
H & =\left\langle a,b,c,e,d,f,g|a,bd,fg,c,e,dcfabeg\right\rangle \\
 & \cong\left\langle b,d,f,g|bd,fg,dfbg\right\rangle  &  & \mbox{eliminating relators on their own}\\
 & \cong\left\langle b,f|b^{-1}fbf^{-1}\right\rangle  &  & \mbox{eliminating }d,g\mbox{ using }d=b^{-1},g=f^{-1}\\
 & \cong\left\langle b,f|bf=fb\right\rangle \\
 & \cong\zz^{2}
\end{flalign*}


So $G=D(2,3,6)$ is infinite, since $[G:G]\cong\zz^{2}$ (and we say
$|G/[G:G]|=6$
\end{example*}

\begin{example*}
(Question 3 from 2011 Exam). Let $G=\left\langle a,b|a^{3},b^{5},(ab)^{2}\right\rangle =D(3,5,2)$
and let $H=\left\langle b,ab^{-1}ab^{2}a^{-1}\right\rangle .$ 
\begin{itemize}
\item First we start with coset enumeration. 


Subgroup Table: 


\begin{tabular}{|c|c|c|}
\hline 
 & $b$ & \tabularnewline
\hline 
\hline 
$1$ & $=$ & $1$\tabularnewline
\hline 
\end{tabular}%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & $a$ &  & $b^{-1}$ &  & $a$ &  & $b$ &  & $b$ &  & $a^{-1}$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $5$ &  & $6$ & $=$ & $5$ &  & $2$ &  & $1$\tabularnewline
\hline 
\end{tabular}


Relator Tables:


{\footnotesize }%
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|}
\hline 
 & {\footnotesize $a$} &  & {\footnotesize $a$} &  & {\footnotesize $a$} &  &  & {\footnotesize $b$} &  & {\footnotesize $b$} &  & {\footnotesize $b$} &  & {\footnotesize $b$} &  & {\footnotesize $b$} &  &  & {\footnotesize $a$} &  & {\footnotesize $b$} &  & {\footnotesize $a$} &  & {\footnotesize $b$} & \tabularnewline
\hline 
\hline 
{\footnotesize $1$} &  & {\footnotesize $\underline{2}$} &  & {\footnotesize $\underline{3}$} & {\footnotesize $=$} & {\footnotesize $1$} & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} & {\footnotesize $1$} &  & {\footnotesize $2$} & {\footnotesize $=$} & {\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $1$}\tabularnewline
\hline 
{\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} & {\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $4$} &  & {\footnotesize $6$} &  & {\footnotesize $5$} &  & {\footnotesize $2$} & {\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $4$} &  & {\footnotesize $5$} & {\footnotesize $=$} & {\footnotesize $2$}\tabularnewline
\hline 
{\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} & {\footnotesize $3$} &  & {\footnotesize $\underline{4}$} &  & {\footnotesize $6$} &  & {\footnotesize $5$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} & {\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $3$}\tabularnewline
\hline 
{\footnotesize $4$} &  & {\footnotesize $\underline{5}$} &  & {\footnotesize $6$} & {\footnotesize $=$} & {\footnotesize $4$} & {\footnotesize $4$} &  & {\footnotesize $6$} &  & {\footnotesize $5$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $4$} & {\footnotesize $4$} &  & {\footnotesize $5$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $4$}\tabularnewline
\hline 
{\footnotesize $5$} &  & {\footnotesize $\underline{6}$} &  & {\footnotesize $4$} &  & {\footnotesize $5$} & {\footnotesize $5$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $4$} & {\footnotesize $=$} & {\footnotesize $6$} &  & {\footnotesize $5$} & {\footnotesize $5$} &  & {\footnotesize $6$} &  & {\footnotesize $5$} &  & {\footnotesize $6$} &  & {\footnotesize $5$}\tabularnewline
\hline 
{\footnotesize $6$} &  & {\footnotesize $4$} &  & {\footnotesize $5$} &  & {\footnotesize $6$} & {\footnotesize $6$} &  & {\footnotesize $5$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $4$} &  & {\footnotesize $6$} & {\footnotesize $6$} &  & {\footnotesize $4$} &  & {\footnotesize $6$} &  & {\footnotesize $4$} &  & {\footnotesize $6$}\tabularnewline
\hline 
\end{tabular}{\footnotesize \par}


And the Table of Definitions and Deductions we made on the way:


\begin{tabular}{|c||c|c|c|c|}
\hline 
Definitions &  & $1a=2,2a=3$ & $3b=4,4a=5$ & $5a=6$\tabularnewline
\hline 
Deductions & $1b=1$ & $3a=1,2b=3$ & $5b=2$ & $6a=4$,$6b=5$,$4b=6$\tabularnewline
\hline 
\end{tabular}

\item Now we make a table to define $U$ and $Y$


\begin{tabular}{|c||c|c|c|c|}
\hline 
 & $a$ & $b$ & $a^{-1}$ & $b^{-1}$\tabularnewline
\hline 
\hline 
$1$ & $\underline{2}$ & $t$$1$ & $v^{-1}3$ & $t^{-1}1$\tabularnewline
\hline 
$2$ & $\underline{3}$ & $u$$3$ & $\underline{\underline{1}}$ & $x^{-1}5$\tabularnewline
\hline 
$3$ & $v1$ & $\underline{4}$ & $\underline{\underline{2}}$ & $u^{-1}2$\tabularnewline
\hline 
$4$ & $\underline{5}$ & $w6$ & $y^{-1}6$ & $\underline{\underline{3}}$\tabularnewline
\hline 
$5$ & $\underline{6}$ & $x2$ & $\underline{\underline{4}}$ & $z^{-1}6$\tabularnewline
\hline 
$6$ & $y4$ & $z5$ & $\underline{\underline{5}}$ & $w^{-1}4$\tabularnewline
\hline 
\end{tabular}Call the Schreier generators, $t,u,v,w,x,y,z$.

\item Now we trace the relators:


\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
 & $a$ &  & $a$ &  & $a$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $3$ &  & $v1$\tabularnewline
\hline 
$4$ &  & $5$ &  & $6$ &  & $y4$\tabularnewline
\hline 
\end{tabular} (No need to do $2,3$ as they appear in first row, and no need to
do $5,6$ as they appear in the second row)


\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & $b$ &  & $b$ &  & $b$ &  & $b$ &  & $b$ & \tabularnewline
\hline 
\hline 
$1$ &  & $t1$ &  & $t^{2}1$ &  & $t^{3}1$ &  & $t^{4}1$ &  & $t^{5}1$\tabularnewline
\hline 
$2$ &  & $u3$ &  & $u4$ &  & $uw6$ &  & $uwz5$ &  & $uwzx2$\tabularnewline
\hline 
\end{tabular}(No need to do $3,4,5,6$ as they appear in the second row)


\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline 
 & $a$ &  & $b$ &  & $a$ &  & $b$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ &  & $u3$ &  & $uv1$ &  & $uvt1$\tabularnewline
\hline 
$2$ &  & $3$ &  & $4$ &  & $5$ &  & $x2$\tabularnewline
\hline 
$5$ &  & $6$ &  & $z5$ &  & $z6$ &  & $z^{2}5$\tabularnewline
\hline 
$6$ &  & $y4$ &  & $yw6$ &  & $ywy4$ &  & $(yw)^{2}6$ \tabularnewline
\hline 
\end{tabular}(No need to do 3, as $3a$ appears in the first row. $4a$ appears
in the second row, so ignore $4$ as well)

\end{itemize}
Hence we have that 
\begin{eqnarray*}
H & \cong & \left\langle t,u,v,w,x,y|v,y,t^{5},uvwzx,uvt,x,z^{2},(yw)^{2}\right\rangle \\
 & \cong & \left\langle t,u,w,z|t^{5},uwz,ut,z^{2},w^{2}\right\rangle \\
 & \cong & \left\langle t,w,z|t^{5},t^{-1}wz,z^{2},w^{2}\right\rangle \\
 & \cong & \left\langle t,w|t^{5},w^{2},(w^{-1}t)^{2}\right\rangle \\
 & \cong & \left\langle t,w|t^{5},w^{2},(wt)^{2}\right\rangle \\
 & \cong & D(5,2,2)\\
 & \cong & D_{10}
\end{eqnarray*}
So $|H|=10$, and since $|G:H|=6$ we have $|G|=60$, hence $D(2,3,5)$
is finite. In fact $D(2,3,5)\cong A_{5}\cong\mathrm{PSL}_{2}(5)$.
\end{example*}

\begin{example*}
\textbf{An example of computing presentation on given generators of
subgroups (not examinable)}

Let $G=\left\langle x,y|,x^{3},y^{5},(xy)^{2}\right\rangle $, and
$H=\left\langle xy,x^{-1}y^{-1}xyx\right\rangle $. Label generators
of $H$, $a=xy$, $b=x^{-1}y^{-1}xyx$. For this, keep $a,b$ in tables
while doing coset enumeration. 


Generators:


\begin{tabular}{|c|c|c|c|c||c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & $x$ &  & $y$ &  &  & $x^{-1}$ &  & $y^{-1}$ &  & $x$ &  & $y$ &  & $x$ & \tabularnewline
\hline 
\hline 
$1$ &  & $2$ & $=$ & $a1$ & $1$ &  & $3$ &  & $4$ & $=$ & $b4$ &  & $b3$ &  & $b1$\tabularnewline
\hline 
\end{tabular}


Relators:


{\footnotesize }%
\begin{tabular}{|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c|c|c|c|}
\hline 
 & {\footnotesize $x$} &  & {\footnotesize $x$} &  & {\footnotesize $x$} &  &  & {\footnotesize $y$} &  & {\footnotesize $y$} &  & {\footnotesize $y$} &  & {\footnotesize $y$} &  & {\footnotesize $y$} & \tabularnewline
\hline 
\hline 
{\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} & {\footnotesize $=$} & {\footnotesize $1$} & {\footnotesize $1$} &  & {\footnotesize $b^{-1}4$} &  & {\footnotesize $b^{-1}3$} &  & {\footnotesize $b^{-1}5$} & {\footnotesize $=$} & {\footnotesize $a^{-1}2$} &  & {\footnotesize $1$}\tabularnewline
\hline 
{\footnotesize $2$} &  & {\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} & {\footnotesize $2$} &  & {\footnotesize $a1$} &  & {\footnotesize $ab^{-1}4$} &  & {\footnotesize $ab^{-1}3$} &  & {\footnotesize $ab^{-1}5$} &  & {\footnotesize $2$}\tabularnewline
\hline 
{\footnotesize $3$} &  & {\footnotesize $1$} &  & {\footnotesize $2$} &  & {\footnotesize $3$} & {\footnotesize $3$} &  & {\footnotesize $5$} &  & {\footnotesize $ba^{-1}2$} &  & {\footnotesize $b1$} &  & {\footnotesize $4$} &  & {\footnotesize $3$}\tabularnewline
\hline 
{\footnotesize $4$} &  & {\footnotesize $b4$} &  & {\footnotesize $b^{2}4$} &  & {\footnotesize $b^{3}$$4$} & {\footnotesize $4$} &  & {\footnotesize $3$} &  & {\footnotesize $5$} &  & {\footnotesize $ba^{-1}2$} &  & {\footnotesize $b1$} &  & {\footnotesize $4$}\tabularnewline
\hline 
{\footnotesize $5$} &  & {\footnotesize $ab^{-1}5$} &  & {\footnotesize $(ab^{-1})^{2}5$} &  & {\footnotesize $(ab^{-1})^{3}$$5$} & {\footnotesize $5$} &  & {\footnotesize $ba^{-1}2$} &  & {\footnotesize $b1$} &  & {\footnotesize $4$} &  & {\footnotesize $3$} &  & {\footnotesize $5$}\tabularnewline
\hline 
\end{tabular}{\footnotesize \par}


{}


\selectlanguage{english}%
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline 
\selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $x$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $y$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $x$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $y$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
\tabularnewline
\hline 
\hline 
\selectlanguage{british}%
{\footnotesize $1$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $2$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $a1$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $a2$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $a^{2}=1$}\selectlanguage{english}%
\tabularnewline
\hline 
\selectlanguage{british}%
{\footnotesize $2$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $3$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $5$}\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $=$}\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $ab^{-1}5$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $2$}\selectlanguage{english}%
\tabularnewline
\hline 
\selectlanguage{british}%
{\footnotesize $3$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $1$}\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $=$}\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $b^{-1}4$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $4$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $3$}\selectlanguage{english}%
\tabularnewline
\hline 
\selectlanguage{british}%
{\footnotesize $4$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $b4$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $b3$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $b1$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $4$}\selectlanguage{english}%
\tabularnewline
\hline 
\selectlanguage{british}%
{\footnotesize $5$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $ab^{-1}5$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $2$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $3$}\selectlanguage{english}%
 & \selectlanguage{british}%
\selectlanguage{english}%
 & \selectlanguage{british}%
{\footnotesize $5$}\selectlanguage{english}%
\tabularnewline
\hline 
\end{tabular}


\selectlanguage{british}%
Definitions and Deductions:


\begin{tabular}{|c||c|c|c|}
\hline 
Definitions & $1x=2$, $2x=3$ & $3y^{-1}=4$ & $3y=5$\tabularnewline
\hline 
Deductions & $3x=1$,$2y=a1$ & $4x=b4$, $1y=b^{-1}4$ & $5y=ba^{-1}2$,$5x=ab^{-1}5$\tabularnewline
\hline 
relators & $a^{2}=1$ &  & $b^{3}=1$, $(ab^{-1})^{3}$\tabularnewline
\hline 
\end{tabular}


So we have $H=\left\langle a,b|a^{2},b^{3},(ab^{-1})^{3}\right\rangle \cong\left\langle a,b|a^{2},b^{3},(ab)^{3}\right\rangle =D(2,3,3)$
which has order $12$. So $|G|=60$. 


Dealing with coincidence with this method is much harder and has additional
technicalities.

\end{example*}
\begin{prop}
\label{prop:6.4}Let $G=\left\langle X|R\right\rangle $ with $X,R$
finite and $|R|<|X|$, then $G/[G,G]$ is infinite and hence so is
$G$.\end{prop}
\begin{proof}
Let $C=\left\langle t\right\rangle ,$$|t|=\infty$ be the infinite
cyclic group. Consider a map $\theta:X\to C$, let $X=\{x_{1},\dots,x_{m}\}$,
$\theta(x_{i})=t^{\lambda_{i}}$ for some $\lambda_{i}\in\zz$. By
the Fundamental Theorem, $\theta$ extends to $\theta:G\to C$ if
$\theta(r)=1\,\forall r\in R$. Note that $\theta(r)=1\,\forall r\in R$
if and only if the associated system of homogeneous linear equation
in $\lambda_{1},\dots,\lambda_{n}$ as solution (for example if $r=x_{2}x_{1}^{-1}x_{3}^{2}x_{2}^{3}x_{1}^{-1}$
then $\theta(r)=t^{-2\lambda_{1}+4\lambda_{2}+2\lambda_{3}}$, so
$\theta(r)=1$ if and only if $-2\lambda_{1}+4\lambda_{2}+2\lambda_{3}=0$).
If $|X|<|R|$, then we have fewer equations than variables, so by
Linear Algebra, there exists a non-zero solutions $\lambda_{1},\dots,\lambda_{m}\in\qq$.
Multiply by a constant to get a solution $\lambda_{i}\in\zz$. So
there exists a non-trivial homomorphism $\theta:G\to C$ with $\im(\theta)\leq C$,
so $\im(\theta)$ is infinite. So $G/\ker(\theta)$ is infinite and
abelian, hence $[G,G]\leq\ker(\theta)$, so $G/[G,G]$ is infinite.\end{proof}
\begin{lem}
\label{lem:6.5}Let $H\leq G$, $\Omega=\{Hg|g\in G\}$, coset action
of $G$ on $\Omega$. Then for any $g\in G$, $Hk\in\Omega$ we have
$(Hk)^{g}=Hk$ if and only if $g\in H$. That is $\mbox{Stab}_{G}(Hk)=H$. \end{lem}
\begin{proof}
We have $(Hk)^{g}=Hk$, if and only if, $kgk^{-1}\in H$, if and only
if, $g\in k^{-1}Hk=H=Hkg$ since $H\lhd G$.\end{proof}
\begin{thm}
\label{thm:6.6}Let $G=\left\langle x_{1},\dots,x_{r}|w_{1}^{m_{1}},w_{2}^{m_{2}},\dots,w_{s}^{m_{s}}\right\rangle $
where $\sum_{i=1}^{s}\frac{1}{m_{i}}\leq r-1$. Assume also that there
is a group $P$ and a homomorphism $G\to P$ in which $|\theta(w_{i})|=m_{i}$
for $1\leq i\leq s$. Then $G$ is infinite.\end{thm}
\begin{proof}
Assume $\im(\theta)=P$. If $P$ is infinite then $G$ is clearly
infinite, so assume $P$ is finite

Let $H=\ker(\theta)$ so $|G:H|=n$ is finite. Apply Reidemeister
- Schreier to get $H=\left\langle E|S(Y)\right\rangle $, where $|E|=(r-1)n+1$
by Theorem \ref{thm:3.8}. $|S(Y)|=|G:H||R|=ns$, so $|S(Y)|>|E|$.
By we can eliminate cyclic conjugates form $S(Y)$. Consider row $c$
for the relator table for $w_{i}^{m_{i}}$

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
 & $w_{i}$ & $\dots$ & $w_{i}$ & $\dots$ & $w_{i}$ & \tabularnewline
\hline 
\hline 
$c=c_{1}$ &  & $v_{2}c_{2}$ & $\dots$ & $v_{m_{i}}c_{m_{i}}$ &  & $vc_{1}$ \tabularnewline
\hline 
\end{tabular}

so $v$ is a relator. Since $|\theta(w_{i})|=m_{i}$ by assumption,
$\theta(w_{i}^{l})\neq1$ for $l<m_{i}$, so $w_{i}^{l}\notin H$
for $1\leq l<m_{i}$ . So by Lemma \ref{lem:6.5}, for any coset $c_{j}$
we have $c_{j}^{w_{i}^{l}}\neq c_{j}$ for $1\leq l<m_{i}$. So in
the row for $c$, the coset numbers $c_{1},c_{2},\dots,c_{m_{i}}$
are all different, so these $m_{i}$ rows just give cyclic conjugates
of relator $v$ for $c_{1}$. So we only need to keep $n/m_{i}$ of
relators from $w_{i}^{m_{i}}$. So can reduce to presentation of $H$
with $(r-1)n+1$ generators $n\sum_{i=1}^{s}\frac{1}{m_{i}}$ relators
which by assumption is less than $n(r-1)$. So by Proposition \ref{prop:6.4},
we have $H/[H,H]$ is infinite, so $G$ is infinite. \end{proof}
\begin{example*}
Let $G=D(2,4,5)=\left\langle x,y|x^{2},y^{4},(xy)^{5}\right\rangle $.
We have $\frac{1}{2}+\frac{1}{4}+\frac{1}{5}<1$, so to prove infinite
we need to find $\theta:G\to P$. Can look for permutations, $a=(1,2)$,
$b=(2,3,4,5)$ then $ab=(1,3,4,5,2)$. So can take $P=\left\langle (1,2),(2,3,4,5)\right\rangle =S_{5}$

Let $G=\left\langle x,y,z,|x^{3},y^{3},z^{3},(xy)^{3},(yz)^{3},(xz)^{3}\right\rangle ,$then
$\sum\frac{1}{m_{i}}=2\leq3-1$. So for $P$, take $P=\left\langle a,b,c\right\rangle $
where $a=(1,2,3)$, $b=(4,5,6)$ and $c=(7,8,9)$. So $G$ is infinite. 
\end{example*}

\subsection{The groups $D(l,m,n)$}

The groups $D(l,m,n)=\left\langle x,y|x^{l},y^{m},(xy)^{n}\right\rangle $.
Assume $2\leq l\leq m\leq n$. Let $G=\left\langle a,b,c|a^{2},b^{2},c^{2},(ab)^{l},(bc)^{m},(ac)^{n}\right\rangle $.
The subgroup $\left\langle ab,bc\right\rangle $ has index $2$ in
$G$ and is isomorphic to $D(l,m,n)$ (easy proof with Reidemeister
- Schreier). $G$ is a $3$ generators \emph{Coxetor group} and can
be studied as reflection groups. Take the triangular tessellation
of ``plane'' (Euclidean, elliptic or hyperbolic) using triangles
with angles $\nicefrac{\pi}{l},\nicefrac{\pi}{m},\nicefrac{\pi}{n}$.
Then $a,b,c$ are reflections in sides of some fixed triangle. It
can be proved that group generated by $a,b,c$ is isomorphic to group
$G$ defined by presentation. The three cases are:
\begin{description}
\item [{Elliptic~Case}] When $\nicefrac{1}{l}+\nicefrac{1}{m}+\nicefrac{1}{n}>1$.
The only cases are $(2,2,n)=D_{2n}$; $(2,3,3)=A_{4}$; $(2,3,4)=S_{4}$
and $(2,3,5)=A_{5}$. So they are all finite. The plane is the surface
of a sphere, so the tessellation is finite. (For picture look at \href{http://en.wikipedia.org/wiki/Triangle_group}{Triangle Groups}) 
\item [{Euclidean~Case}] When $\nicefrac{1}{l}+\nicefrac{1}{m}+\nicefrac{1}{n}=1$.
This is the ``normal'' plane and the only cases are $(3,3,3)$,
$(2,4,4)$ and $(2,3,6)$. The groups act regularly (transitive, trivial
stabiliser) on triangles
\item [{Hyperbolic~Case}] When $\nicefrac{1}{l}+\nicefrac{1}{m}+\nicefrac{1}{n}<1$.
The plane is the hyperbolic plane. 
\end{description}
So it is not hard to prove (using some hyperbolic geometry) that $D(l,m,n)$
is infinite if and only if $\nicefrac{1}{l}+\nicefrac{1}{m}+\nicefrac{1}{n}\leq1$.
But we will prove this algebraically. We have already considered all
$\nicefrac{1}{l}+\nicefrac{1}{m}+\nicefrac{1}{n}>1$ cases as examples.
\begin{thm}
\label{thm:6.7} $D(l,m,n)$ is infinite when $\nicefrac{1}{l}+\nicefrac{1}{m}+\nicefrac{1}{n}\leq1$.\end{thm}
\begin{proof}
By Theorem \ref{thm:6.6}, it is enough to find a group $P$ containing
elements $x,y$ with $|x|=l$, $|y|=m$ and $|xy|=n$. We can always
find finite permutation with these orders. For example, with $l=5,m=7$and
$n=9$ we can take $x=(1,2,3,4,5)$, $y=(3,4,5,6,7,8,9)$ then $xy=(1,2,4,6,7,8,9,3,5)$.
It is hard to describe in general this process.

In fact we construct $P$ as a quotient group of matrices. Let $K$
be a field of characteristic not $2$. Let $\SL_{2}(K)$ be as usual
the multiplicative group of $2\times2$ invertible matrices with entries
in $K$ and determinant $1$. Let $Z=\{\begin{pmatrix}1 & 0\\
0 & 1
\end{pmatrix},\begin{pmatrix}-1 & 0\\
0 & -1
\end{pmatrix}\}$, note $1\neq-1$ since $\mbox{char}(K)\neq2$. Then $Z\lhd\SL_{2}(K)$
(in fact $Z$ is the centre of $\SL_{2}(K)$. Define $\PSL_{2}(K)=\SL_{2}(K)/Z$.
\begin{lem}
$\begin{pmatrix}-1 & 0\\
0 & -1
\end{pmatrix}$ is the only element of order $2$ in $\SL_{2}(K)$ \end{lem}
\begin{proof}
Let $\begin{pmatrix}a & b\\
c & d
\end{pmatrix}=A$ with $\ord(A)=2$. Then $A^{2}=I$ implies $a^{2}+bc=bc+d^{2}=1$,
so $b(a+d)=c(a+d)=0$ hence either $b=c=0$ or $a+d=0$. If $a+d=0$,
then $d=-a$, but $\det(A)=ab-bc=1$ implies $-a^{2}-bc=1$ contradicting
$a^{2}+bc=1$ (using $1\neq-1$). So $b=c=0$ and hence $a^{2}=1=d^{2}$,
hence either $a=d=1$ or $a=d=-1$\end{proof}
\begin{lem}
\label{lem:2}If $A\in\SL_{2}(K)$ with $\ord(A)=2r$ for some $r\geq1$
then order of $AZ$ in $\PSL_{2}(K)$ is $r$\end{lem}
\begin{proof}
Since $\ord(A)=2r$ then $\ord(A^{r})=2$. So $A^{r}=\begin{pmatrix}-1 & 0\\
0 & -1
\end{pmatrix}\in Z$ and $A^{s}\notin Z$ for $1\leq s<r$, so the result follows.
\end{proof}
Let $A=\begin{pmatrix}a & b\\
c & d
\end{pmatrix}\in S$, then $\Tr(A)=a+d$ and the characteristic polynomial of $A=(a-x)(d-x)-bc=x^{2}-(a+d)x+(ad-bc)=x^{2}-\Tr(A)+1$.
So when $\Tr(A)\neq\pm2$ we have distinct eigenvalues.
\begin{lem}
\label{lem:3}Let $A,B\in S$ and $\Tr(A)=\Tr(B)\neq\pm2$. Then $\ord(A)=\ord(B)$\end{lem}
\begin{proof}
Now $\Tr(A)=\Tr(B)$ implies $A$ and $B$ have the same characteristic
polynomial and eigenvalues (possibly in an extension field $L$ of
$K$) are distinct, so by Linear Algebra, $A,B$ are similar, i.e.,
there exists $P\in\SL_{2}(L)$ such that $P^{-1}AP=B$. So $A,B$
are conjugate in $\SL_{2}(L)$. So $\ord(A)=\ord(B)$. \end{proof}
\begin{lem}
For all $l,m,n\geq2$ and assume that $K$ contains primitive $(2l)^{\mathrm{th}}$,
$(2m)^{\mathrm{th}}$ and $(2n)^{\mathrm{th}}$ root of unity. Then
there exists $A,B\in S$ with $\ord(A)=2l$, $\ord(B)=2m$ and $\ord(AB)=2n$.\end{lem}
\begin{proof}
Let $\lambda,\mu$ be primitive $(2l)^{\mathrm{th}}$ and $(2m)^{\mathrm{th}}$
roots of unity respective. Since $2l,2m\geq4$ we have $\lambda+\lambda'\neq\pm2$
and $\mu+\mu^{-1}\neq\pm2$. (Note $\lambda$ root of unity and $\lambda+\lambda^{-1}=\pm2$
then $\lambda=\pm1$). So let $A=\begin{pmatrix}\lambda & 0\\
1 & \lambda^{-1}
\end{pmatrix}$ and $B=\begin{pmatrix}\mu & \alpha\\
0 & \mu^{-1}
\end{pmatrix}$ for some $\alpha$. Then $\Tr(A)=\lambda+\lambda^{-1}$, so by Lemma
\ref{lem:3} $\ord(A)=2l$. Similarly $\ord(B)=2m$ for any $\alpha\in K$.
Now $AB=\begin{pmatrix}\lambda\mu & \lambda\alpha\\
\mu & \alpha+\mu^{-1}\lambda^{-1}
\end{pmatrix}$. Let $\nu$ be a primitive $(2n)^{\mathrm{th}}$ root of unity. By
Lemma \ref{lem:3} if $\Tr(AB)=\nu+\nu^{-1}$, then $\ord(AB)=2n$.
So we just choose $\alpha=\nu+\nu^{-1}-\lambda\mu-\lambda^{-1}\mu^{-1}$.
\end{proof}
Now by Lemma \ref{lem:2}, in $\PSL_{2}(K)$ element $AZ,BZ,ABZ=(AZ)(BZ)$
have orders $l,m,n$. So we have the required group $P$ and Theorem
\ref{thm:6.7} follows from Theorem \ref{thm:6.6}.
\end{proof}
If we choose $K=\cc$, then $\left\langle AZ,BZ\right\rangle $ will
usually be infinite. Can we find a finite group $P$ with elements
$\alpha,\beta$. 
\begin{thm}
\label{thm:6.8} Let $l,m,n\geq2$, then there exists a finite group
$P$, with $\alpha,\beta\in P$ and $|\alpha|=l,|\beta|=m,|\alpha\beta|=n$.\end{thm}
\begin{proof}
To prove this we just need a finite field $K$, such that $\mbox{char}K\neq2$
and containing primitive $(2l)^{\mathrm{th}}$, $(2m)^{\mathrm{th}}$
and $(2n)^{\mathrm{th}}$ root of unity. Recall that for each prime
power $q=p^{n}$, there exists a unique finite field $\ff_{q}$ of
order $q$ with characteristic $p$, and the multiplicative group
$\ff_{q}\setminus\{0\}$ is cyclic of order $q-1$. So $\ff_{q}$
will have the required roots of unity if and only if $2l,2m,2n$ divides
$q-1$. By Theorem of Dirichlet (from Number Theory), there exists
infinitely many primes $p\equiv1\mod2lmn$. But we don't actually
need this theorem, if we choose any odd prime $p$, coprime to $2lmn$
and let $e$ be the order of $p$ in $U(2lmn)$ (unit group), then
$p^{e}\equiv1\mod2lmn$. So choose $q=p^{e}$.
\end{proof}
\newpage{}


\section{Baumslaq - Solitar Groups}

Let $G(m,n)=\left\langle x,y|y^{-1}x^{m}y=x^{n}\right\rangle $, $m,n\neq0$.
$G(2,3)$ was the first example (1962) of a finitely generated non-Hopfian
group, i.e., there exists $1\neq N\lhd G$ with $G/N\cong G$. Easy
to find non-finitely generated example. The groups with $m=1$ have
an easier structure. So we will consider those first. Note that the
case $m=n=1$ is the free abelian group, so we assume $n>1$.

Consider $G=(1,n)=\left\langle x,y|y^{-1}xy=x^{n}\right\rangle $.
Define $x_{r}=y^{-r}xy^{r}$ for any $r\in\zz$ (so $x_{0}=x$ and
$x_{1}=x^{n}$). 
\begin{lem}
\label{lem:7.1} We have $x_{r}^{n}=x_{r+1}$ for all $r\in\zz$.
More generally $x_{r}^{n^{k}}=x_{r+k}$, $k\geq0$. \end{lem}
\begin{proof}
$x_{r}^{n}=(y^{-r}xy^{r})^{n}=y^{-r}x^{n}y^{r}=y^{-r}y^{-1}xyy^{r}=x_{r+1}$.

Second statement is by induction on $k$. So $x_{r}=x^{n^{r}}$. But
not $x_{-1}=yxy^{-1}$ is not a power of $x$.
\end{proof}
Let $N=\left\langle x_{r}|r\in\zz\right\rangle .$
\begin{cor}
\label{cor:7.2} $N$ is abelian.\end{cor}
\begin{proof}
If $s>r$, then $x_{s}$ is a power of $x_{r}$, so $[x_{r},x_{s}]=1$.\end{proof}
\begin{cor}
\label{cor:7.3} $N=\left\langle x^{G}\right\rangle \lhd G$\end{cor}
\begin{proof}
Recall $\left\langle x^{G}\right\rangle =\left\langle g^{-1}xg|g\in G\right\rangle $.
For any $r,x_{r}=y^{-r}xy^{r}\in\left\langle x^{G}\right\rangle $,
so $N=\left\langle x_{r}\right\rangle \leq\left\langle x^{G}\right\rangle $.

For the other direction, we need to prove that for all $g\in G$,
we have $g^{-1}xg$ is a product of the $x_{r}$ . Write $g$ as a
word in $x^{\pm1}$, $y^{\pm1}$. We do a prove by induction on length
of the word. 

If Length is zero, then $g$ is the identity, so $g^{-1}xg=x=x_{0}$

Let $g=wa$ with $a\in\{x^{\pm1,}y^{\pm1}\}$. Then $g^{-1}xg=a^{-1}(w^{-1}xw)a$
, which by induction is $a^{-1}(x_{r_{1}}\dots x_{r_{k}})a$. If $a=x^{\pm1}$
then $a^{-1}x_{r}a=x_{r}$ for all $r$, hence $g^{-1}xg=w^{-1}xw$
and we are done. If $a=y^{\pm1}$, then $y^{-1}x_{r}y=x_{r+1}$ and
$yx_{e}y^{-1}=x_{r-1}$ , so we still get $g^{-1}xg=$ product of
$x_{r}$. 
\end{proof}
Now $G/N=G/\left\langle x^{G}\right\rangle $, which is what we get
if we add relator $x$ to presentation of $G$. That is $G/\left\langle x^{G}\right\rangle \cong\left\langle x,y|y^{-1}xy=x^{n},x=1\right\rangle \cong\left\langle y|\:\right\rangle $
infinite cyclic. So we have $N$ is abelian (but not finitely generated)
and $G/N$ infinite cyclic, so $G$ is \emph{metabelian group}. We
need a norm form for group elements. Using $x_{r}y=yx_{r+1},x_{r}y^{-1}=y^{-1}x_{r-1}$
we can move $y,y^{-1}$ to the left of a word to get in the form $g=y^{k}x_{r_{1}}^{\pm1}x_{r_{2}}^{\pm1}\dots$.
Since $x_{s}$ is a power of $x_{r}$ for each $s>r$, each $x_{r_{i}}$
is a power of $x_{r}$ with $r=\min r_{i}$. So we get $g=y^{k}x_{r}^{s}$
for some $s\in\zz$. Since $x_{r}^{n}=x_{r+1}$ we can assume that
$n\nmid s$.
\begin{example*}
Let $n=3$, $g=yxyxy^{-1}=y\underbrace{x_{0}y}\underbrace{x_{0}y}=yy\underbrace{x_{1}y^{-1}}x_{-1}=yyy^{-1}x_{0}x_{-1}=yx_{-1}^{4}$. \end{example*}
\begin{prop}
\label{prop:7.4}Each $g\in G$ has a unique expression as $y^{k}x_{r}^{s}$
with $k,r,s\in\zz$ and $n\nmid s$.\end{prop}
\begin{proof}
Let $H=\GL_{2}(\qq)$ (= multiplicative group of $2\times2$ invertible
matrices with entries in $\qq$)

Define $\theta:\{x,y\}\to H$ by $\theta(x)=\begin{pmatrix}1 & 0\\
1 & 1
\end{pmatrix}$ and $\theta(y)=\begin{pmatrix}n & 0\\
0 & 1
\end{pmatrix}$. Then 
\begin{eqnarray*}
\theta(y^{-1}xy) & = & \begin{pmatrix}\nicefrac{1}{n} & 0\\
0 & 1
\end{pmatrix}\begin{pmatrix}1 & 0\\
1 & 1
\end{pmatrix}\begin{pmatrix}n & 0\\
0 & 1
\end{pmatrix}\\
 & = & \begin{pmatrix}\nicefrac{1}{n} & 0\\
1 & 1
\end{pmatrix}\begin{pmatrix}n & 0\\
0 & 1
\end{pmatrix}\\
 & = & \begin{pmatrix}1 & 0\\
n & 1
\end{pmatrix}\\
 & = & \theta(x)^{n}
\end{eqnarray*}
So by the Fundamental Theorem, $\theta$ extends to a homomorphism
$\theta:G\to H$. 

Now 
\begin{eqnarray*}
\theta(x_{r}) & = & \theta(y^{-r}xy^{r})\\
 & = & \begin{pmatrix}n^{-r} & 0\\
0 & 1
\end{pmatrix}\begin{pmatrix}1 & 0\\
1 & 1
\end{pmatrix}\begin{pmatrix}n^{r} & 0\\
0 & 1
\end{pmatrix}\\
 & = & \begin{pmatrix}1 & 0\\
n^{r} & 1
\end{pmatrix}
\end{eqnarray*}
So 
\begin{eqnarray*}
\theta(y^{k}x_{r}^{s}) & = & \begin{pmatrix}n & 0\\
0 & 1
\end{pmatrix}^{k}\begin{pmatrix}1 & 0\\
n^{r} & 1
\end{pmatrix}^{s}\\
 & = & \begin{pmatrix}n^{k} & 0\\
0 & 1
\end{pmatrix}\begin{pmatrix}1 & 0\\
sn^{r} & 1
\end{pmatrix}\\
 & = & \begin{pmatrix}n^{k} & 0\\
sn^{r} & 1
\end{pmatrix}
\end{eqnarray*}
So for distinct $r,k,s$ with $s\nmid n$, the distinct elements $y^{k}x_{r}^{s}$
have distinct images under $\theta$.
\end{proof}
Note $\theta(N)$ is generated by $\theta(x_{r})=\left\{ \begin{pmatrix}1 & 0\\
n^{r} & 1
\end{pmatrix}|r\in\zz\right\} =\left\{ \begin{pmatrix}1 & 0\\
sn^{r} & 1
\end{pmatrix}|r,s\in\zz\right\} $ which is isomorphic to the subgroup $\{sn^{r}|s\in\zz,r\in\zz\}$
of $(\qq,+)$, which is the set of rationals $\frac{a}{b}$ such that
primes dividing $b$ are those dividing $n$. 

Now we move onto the general case $G(m,n)$ with $m,n\geq2$. We still
have $\theta:G\to\GL_{2}(\qq)$ defined by $\theta(x)=\begin{pmatrix}1 & 0\\
1 & 1
\end{pmatrix},\theta(y)=\begin{pmatrix}\nicefrac{n}{m} & 0\\
0 & 1
\end{pmatrix}$, but $\theta$ is not a monomorphism. 
\begin{description}
\item [{Digression~HNN~(Higman,~Neumann,~Neumann)extensions}]~
\end{description}
Let $H=\left\langle X|R\right\rangle $ be a group and $\left\langle z_{1},\dots,z_{k}\right\rangle ,\left\langle z_{1}',\dots,z_{k}'\right\rangle $
be isomorphic subgroups of $H$ with isomorphic $z_{i}\mapsto x_{i}'$.
The associated HNN extension is $G=\left\langle X,y|R,y^{-1}z_{i}y=z_{i}'\right\rangle $.
It can be proved for example that: The natural map $H\to G$ defined
by $X\to X$ is a monomorphism.

$G(m,n)$ is HNN extension, $z_{1}=x^{m},z_{1}'=x^{n}$ so $\left\langle z_{1}\right\rangle ,\left\langle z_{1}'\right\rangle $
are both infinite cyclic, and $H=\left\langle x|\right\rangle $.
HNN are used in proof of unsolvability of word problem for group presentations.
Also used for constructing examples with strange properties. Such
as infinite groups in which all non-identity elements are conjugate. 

We look for a normal form for group elements in $G(m,n)$. (This generalises
easily to arbitrary HNN extensions). We still use $x^{m}y=yx^{n}$
and $x^{n}y^{-1}=y^{-1}x^{m}$ to move $y,y^{-1}$ to the left whenever
possible. In a subword $x^{k}y$, we write $k=t+mu$ with $0\leq t<m$.
Then $x^{k}y=x^{t+mu}y=x^{t}yx^{nu}$. Similarly for $x^{k}y^{-1}$
we can write $k=t+nu$ with $0\leq t<n$ and get $x^{k}y^{-1}=x^{t}y^{-1}x^{mu}$.
So doing this as much as possible brings the word into the form $g=x^{t_{1}}y^{u_{1}}\dots x^{t_{r}}y^{u_{r}}x^{v}$
where:
\begin{enumerate}
\item $t_{i},u_{i},v,r\in\zz$ and $r>0$
\item $t_{i}\neq0$ for all $i>1$ and $t_{1}=0$ if $r=0$
\item $u_{i}\neq0$ for all $i$
\item $u_{i}>0$ then $0\leq t_{i}<m$
\item $u_{i}<0$ then $0\leq t_{i}<n$
\end{enumerate}
Note that 1.~,2.~and 3.~we could do in any groups, while 4.~and
5.~we can impose using substitutions above arising from group relators.
We conjecture that this is a normal form for group elements.
\begin{thm}
\label{thm:7.5} Each $g\in G$ has unique expression satisfying \emph{1.~-5.~}above.\end{thm}
\begin{rem*}
This method of proof can be used in general to prove that a conjectured
normal form for a group really is a normal form. Useful if there is
no representation of the group that can be used. We construct a representation
as group of permutations of set of normal forms, which will be equivalent
to regular group action.\end{rem*}
\begin{proof}
Let $\Omega$ be the set of words satisfying 1.~-5\@. We construct
an action of $G$ on $\Omega$ . First want an action of generators
which should correspond to multiplying on the right. So for $\alpha\in\Omega,a\in\{x^{\pm1},y^{\pm1}\}$
we want $\alpha^{a}$ to be the normal form of $\alpha a$. 

For $\alpha=x^{t_{1}}y^{u_{1}}\dots x^{v}$ as above, let $\beta=x^{t_{1}}y^{u_{1}}\dots x^{t_{r-1}}y^{u_{r-1}}$
or $\beta=\epsilon$ is $r\leq1$. Let $t=t_{r},u=u_{r}$ (with $t=u=0$
if $r=0$). So $\alpha=\beta x^{t}y^{u}x^{v}$, write $v=am+b$, $0\leq b<m$,
and $v=cn+d$,$0\leq d<n$, then we define 
\begin{eqnarray*}
\alpha^{x} & = & \beta x^{t}y^{u}x^{v+1}\\
\alpha^{x^{-1}} & = & \beta x^{t}y^{u}x^{v-1}\\
\alpha^{y} & = & \begin{cases}
\beta x^{t}y^{u}x^{b}yx^{an} & b\neq0\\
\beta x^{t}y^{u+1}x^{an} & b=0,u\neq-1\\
\beta x^{t+an} & b=0,u=-1
\end{cases}\\
\alpha^{-y} & = & \begin{cases}
\beta x^{t}y^{u}x^{d}y^{-1}x^{cm} & d\neq0\\
\beta x^{t}y^{u-1}x^{cm} & d=0,u\neq1\\
\beta x^{t+cm} & d=0,u=1
\end{cases}
\end{eqnarray*}
We defined maps $\theta(a):\Omega\to\Omega$ for $a\in\{x^{\pm1},y^{\pm1}\}$.
To prove $\theta(a)\in\Sym(\Omega)$ (that is $\theta(a)$ is a bijection),
we prove that $\theta(x)$, $\theta(x^{-1})$ and $\theta(y)$, $\theta(y^{-1})$
are inverse maps. This is clear in the case $\theta(x),\theta(x^{-1})$.
So we prove $\theta(y)\theta(y^{-1})=I_{\Omega}$, i.e., $(\alpha^{y})^{y^{-1}}=\alpha\,\forall\alpha\in\Omega$.
(The proof for $(\alpha^{y^{-1}})^{y}=\alpha$ is similar). Consider
3 cases for $\alpha^{y}$
\begin{caseenv}
\item This is Case 3 for $(\alpha^{y})^{y^{-1}}$. We get $(\alpha^{y})^{y^{-1}}=\beta x^{t}y^{u}x^{b+am}=\alpha$.
\item This is Case 2 for $(\alpha^{y})^{y^{-1}}$ (or Case 3 if $u=0$ with
$r=t=0$). In either case we have $(\alpha^{y})^{y^{-1}}=\beta x^{t}y^{u}x^{am}=\alpha$. 
\item If $t\neq0$ this is Case 1 for $(\alpha^{y})^{y^{-1}}$. Then we
have $(\alpha^{y})^{y^{-1}}=\beta x^{t}y^{-1}x^{am}=\alpha$. If $t=0$,
then $r=1$ so $\alpha=y^{-1}x^{am}$. Hence $\alpha^{y}=x^{an}$
and so $(\alpha^{y})^{y^{-1}}=y^{-1}x^{am}=\alpha$.
\end{caseenv}
So we have that $(\alpha^{y})^{y^{-1}}=\alpha$ in all cases (similarly
for $(\alpha^{y^{-1}})^{y}=\alpha$). So $\theta(a)\in\Sym(\Omega)$
for $a\in\{x^{\pm1},y^{\pm1}\}$. To use the Fundamental Theorem to
prove $\theta$ extends to an action on $\Omega$, i.e., $\theta:G\to\Sym(\Omega)$,
we have to check $\theta(y)^{-1}\theta(x)^{m}\theta(y)=\theta(x)^{n}$,
equivalently $\theta(x)^{m}\theta(y)=\theta(y)\theta(x)^{n}$. So
we must check $\alpha^{x^{m}y}=\alpha^{yx^{n}}\,\forall\alpha\in\Omega$
. Again split into the three cases for $\alpha^{y}$
\begin{caseenv}
\item $\alpha=\beta x^{t}y^{u}x^{am+b}$. So $\alpha^{x^{m}}=\beta x^{t}y^{u}x^{(a+1)m+b}$,
so we are still in Case 1 for $\alpha^{x^{m}y}$. Hence $\alpha^{x^{m}y}=\beta x^{t}y^{u}x^{b}yx^{(a+1)n}=\alpha^{yx^{n}}$. 
\item $\alpha=\beta x^{t}y^{u}x^{am}$. So $\alpha^{x^{m}}=\beta x^{t}y^{u}x^{(a+1)m}$
and we are still in Case 2. Hence $\alpha^{x^{m}y}=\beta x^{t}y^{u+1}x^{(a+1)n}=\alpha^{yx^{n}}$
\item $\alpha=\beta x^{t}y^{-1}x^{am}$. So $a^{x^{m}}=\beta x^{t}y^{-1}x^{(a+1)m}$
and we are still in Case 1. Hence $\alpha^{x^{m}y}=\beta x^{t+(a+1)n}=\alpha^{yx^{n}}$.
\end{caseenv}
So by the Fundamental Theorem, we do have an action of $G$ on $\Omega$.
Let $\alpha$ be a normal form word. Then it is easy to see that applying
the group element $\alpha$ represented by $\alpha$ to $\epsilon\in\Omega$,
we get $\epsilon^{\alpha}=\alpha$ . So distinct element $\alpha,\beta\in\Omega$
have distinct images under $\theta$ (since $\epsilon^{\alpha}\neq\beta=\epsilon^{\beta})$
we must have $\alpha\neq_{G}\beta$ and we are done. 
\end{proof}
Same kind of proof can be used more generally to get normal form for
HNN extensions.

Now let $G=G(2,3)=\left\langle x,y|y^{-1}x^{2}y=x^{3}\right\rangle $
and $r=x^{-1}y^{-1}xyx^{-1}y^{-1}xyx^{-1}=[x,y]^{2}x^{-1}$. We want
to put $r$ into normal form. $x^{-1}y^{-1}=x^{2}x^{-3}y^{-1}=x^{2}y^{-1}x^{-2}$.
So 
\begin{eqnarray*}
r & = & \underline{x^{-1}y^{-1}}xyx^{-1}y^{-1}xyx^{-1}\\
 & = & x^{2}y^{-1}\underline{x^{-1}y}x^{-1}y^{-1}xyx^{-1}\\
 & = & x^{2}y^{-1}xy\underline{x^{-4}y^{-1}}xyx^{-1}\\
 & = & x^{2}y^{-1}xyx^{2}y^{-1}\underline{x^{-3}y}x^{-1}\\
 & = & x^{2}y^{-1}xyx^{2}y^{-1}xyx^{-7}
\end{eqnarray*}

\begin{defn}
A group $G$ is \emph{non-Hopfian} if there exists $1\neq N\lhd G$
such that $G/N\cong G$\end{defn}
\begin{thm}
\label{thm:7.6}$G(2,3)$ is non-Hopfian. (In general $G(m,n)$ is
non-Hopfian if and only if there exists primes $p,q$ with $p|m$,$q|n$
and $p\nmid n$, $q\nmid m$)\end{thm}
\begin{proof}
Let $G=G(2,3)$, $r=[x,y]^{2}x^{-1}=x^{2}y^{-1}xyx^{2}y^{-1}xyx^{-7}\neq\epsilon$.
So $r\neq_{G}1$. Let $N=\left\langle r^{G}\right\rangle ,$so $N\neq1$.
To get presentation of $G/N$, we just add $r$ as extra relation
to $G$. So
\begin{eqnarray*}
G/N & \cong & \left\langle x,y|y^{-1}x^{2}y=x^{3},x=[x,y]^{2}\right\rangle \\
 & \cong & \left\langle x,y,w|y^{-1}x^{2}y=x^{3},x=w^{2},w=[x,y]\right\rangle \\
 & \cong & \left\langle y,w|y^{-1}w^{4}y=w^{6},\underset{w=w^{-2}y^{-1}w^{2}y}{\underbrace{w=[w^{2},y]}}\right\rangle \\
 & \cong & \left\langle y,w|y^{-1}w^{4}y=w^{6},y^{-1}w^{2}y=w^{3}\right\rangle \\
 & \cong & \left\langle y,w,|y^{-1}w^{2}y=w^{3}\right\rangle \\
 & \cong & G
\end{eqnarray*}
since $y^{-1}w^{2}y=w^{3}$ implies the relation $y^{-1}w^{4}y=w^{6}$. 

\newpage{}
\end{proof}

\section{The Burnside Problem}

Burnside 1902: Given a finitely generated group $G$ with all elements
having finite order (i.e. $G$ a torsion group), is $G$ finite? (Certainly
true for Abelian groups by the Fundamental Theorem of Finitely Generated
Abelian Groups)

The general answer is no: In 1964 an example was given by Gringorchuk 

Harder question is: Given a finitely generated group $G$ with all
element having finite order, and there is an upper bound on the order,
equivalently assume there exists $n$ such that $g^{n}=1$ for all
$g\in G$. Then is $G$ finite?

The answer is no for large enough $n$ ($n\geq8000$?). The answer
is yes for $n=2,3,4,6$. So there are still a lot of $n$ which is
unknown for.

For large enough primes $p$, there exists \emph{Tarski Monsters}:
$G=\left\langle x,y\right\rangle $ with $G$ infinite and $g^{p}=1$
for all $g\in G$ and only subgroups of $G$ are $\left\langle g\right\rangle $
for $g\in G$. 
\begin{defn}
We define the \emph{Burnside Group} $B(r,n)$ as follows: $B(r,n)=\left\langle x_{1},\dots,x_{r}|w^{n}=1\,\forall w\in A^{*}\right\rangle $
\end{defn}
The above question is now for which $r,n$ is $B(r,n)$ finite. Not
known for $B(2,5)$. 

Restricted Burnside Problem: Is there a largest finite group $G$
with $r$ generators and $g^{n}=1\,\forall g\in G$. Equivalently
does $B(r,n)$ have largest finite quotient. 

The answer is Yes, done by Zelmanov (1990?), there exists largest
finite quotient $RB(r,n)$. In particular $|RB(2,5)|=5^{34},|RB(3,5)|=5^{2282}$
and $|RB(2,7)|=7^{20416}$. 
\begin{thm}
\label{thm:8.1}$B(r,2)$ is abelian of order $2^{r}$\end{thm}
\begin{proof}
Let $G=B(r,2)$, $g,h\in G$. Consider $(gh)^{2}=ghgh=1$ but $g^{2}h^{2}=gghh=1$.
So we get $gh=hg$ and $G$ is abelian.

So $G=\left\langle x_{1},\dots,x_{r}|x_{i}^{2},[x_{i},x_{j}]\right\rangle \cong\left\langle x_{1}\right\rangle \times\dots\times\left\langle x_{r}\right\rangle \cong C_{2}^{r}$
(by Proposition \ref{prop:4.5})\end{proof}
\begin{namedthm}[Cauchy's Theorem]
 If $G$ is a finite group $p||G|$ with $p$ prime, then $G$ has
an element of order $p$\end{namedthm}
\begin{proof}
Let $S=\{(x_{1},\dots,x_{p})|x_{i}\in G,x_{1}x_{2}\dots x_{p}=1\}$.
Since $x_{p}=(x_{1}\dots x_{p-1})^{-1}$, we can choose $x_{1},\dots,x_{p-1}$
arbitrarily so $|S|=|G|^{p-1}$. Hence $p||S|$. Note $(x_{1},\dots,x_{p})\in S$
implies $(x_{2},x_{3},\dots,x_{p},x_{1})\in S$. So we have an action
of cyclic group $\left\langle g\right\rangle =C_{p}$ on $S$ with
$g\cdot(x_{1},\dots,x_{p})=(x_{2},\dots,x_{p},x_{1})$. So orbit of
action has size $1$ or $p$ (since $p$ is prime). Now an orbit of
size $1$ will be $(x,x,\dots,x),x^{p}=1$. There exists at least
one of these $x=1$. But since $p||S|$ we have $p|$number of orbit
of size 1. So there exists $x\neq1$ with $x^{p}=1$. \end{proof}
\begin{thm}
\label{thm:8.3}$B(r,3)$ is finite of order at most $3^{3^{r-1}}$\end{thm}
\begin{proof}
Induction on $r$.

For $r=1$, we clearly have $|B(1,3)|=3=3^{3^{1-1}}$

Let $r>1$. Note for $g,h\in G=B(r,3)$ we have $(gh)^{3}=1$ implies
$ghg=h^{-1}g^{-1}h^{-1}$. Let $H=\left\langle x_{1},\dots,x_{r-1}\right\rangle \leq G$.
By induction, we know $H$ is finite with $|H|\leq3^{3^{r-2}}$. For
any $g=G$ let $g=u_{1}z^{\pm1}u_{2}\dots z^{\pm1}u_{m}$ with $u_{i}\in H$
and $z=x_{r}$ (so $z^{3}=1$). Do this with the smallest $m$. If
we had $zuz$ we can turn that into $u^{-1}zu^{-1}$ which reduces
$m$. So we have that $z$ and $z^{-1}$ must alternate in the word.
Note also that $zuz^{-1}vz=zuzzvz=u^{-1}z^{-1}u^{-1}v^{-1}z^{-1}v^{-1}$
reduces $m$. So we have $m\leq3$ and hence $G$ is finite. Also
$uz^{-1}vzw\to uz^{-1}vz^{-1}z^{-1}w\to uv^{-1}zv^{-1}z^{-1}w$, so
elements of $G$ are 
\begin{itemize}
\item $g=u_{1}$ (we have $|H|$ of them)
\item $g=u_{1}x^{\pm1}u_{2}$ (we have $2|H|^{2}$ of them)
\item $g=u_{1}zu_{2}z^{-1}u_{3}$ (we have $|H|^{3}$ of them)
\end{itemize}
So $|G|\leq|H|+2|H|^{2}+|H|^{3}$. By Cauchy's Theorem, we have $|H|=3^{m}$
for some $m$. So $|G|\leq3^{m}+2\cdot3^{2m}+3^{3m}<3^{3m+1}$. But
$|G|$ is also a power of $3$, so $|G|\leq3^{3m}$. By induction
$m\leq3^{r-2}$ so $|G|\leq3^{3^{r-1}}$.
\end{proof}
In fact $|B(r,3)|=3^{m(r)}\mbox{ where }m(r)=r+{r \choose 2}+{r \choose 3}=O(r^{3})$.
The bounds agree for $|B(1,3)|=3$ and $|B(2,3)|=3^{3}$ . But $|B(3,3)|\leq3^{9}$
when in fact $|B(3,3)|=3^{7}$. 

Let $G$ be a group, define lower central series $\gamma^{i}(G)$
as follows: $\gamma^{1}(G)=G$ and $\gamma^{r+1}(G)=[G,\gamma^{r}(G)]$.
$G$ is of nilpotent class $C$ if $\gamma^{C+1}(G)=1$ ($\gamma^{C}(G)\neq1)$,
so note that Class $1$ means abelian. {[}Note $G$ finite and $G$
nilpotent is the same as all Sylow subgroups normal). $B(r,3)$ is
nilpotent of class 3. $|\gamma^{2}(G)|=3^{{r \choose 2}+{r \choose 3}},|\gamma^{3}(G)|=3^{{r \choose 3}}$
and $\gamma^{4}(G)=1$. 

We can also define the derived series of $G$ as follows, $G^{(0)}=G$
and $G^{(r+1)}=[G^{(r)},G^{(r)}]$. We have $G^{(r)}\leq\gamma^{(r+1)}(G)$
for all $r\geq0$. $G$ is soluble/solvable of derived length $r$
if $G^{(r+1)}=1$ and $G^{(r)}\neq1$. Nilpotent groups are soluble. 

The groups $B(r,4)$ are finite, order $2^{k(r)}$ for some $k(r)$.
No know formula known fro $k(r)$. WE have $k(1)=4,k(2)=12,k(3)=69,k(4)=422$
and $k(5)=2728$. $B(r,4)$ is nilpotent and soluble but its derived
length tends to $\infty$ as $r$ tends to $\infty$. 
\begin{thm}
\label{thm:8.3.1}$B(r,4)$ is finite for all $r\geq1$
\end{thm}
This will follow from:
\begin{thm}
\label{thm:8.4}Let $G=\left\langle K,z\right\rangle $ with $K\leq G$,
$K$ finite, $z^{2}\in K$ and $g^{4}=1$ for all $g\in G$. Then
$G$ is finite.\end{thm}
\begin{proof}[Proof of Theorem\ref{thm:8.3.1} (using Theorem \ref{thm:8.4})]
 We do this by induction on $r$.

For $r=1$, we have $|B(1,4)|=4$

Let $r>1$, $G=\left\langle x_{1},\dots,x_{r}\right\rangle $, let
$H=\left\langle x_{1},\dots,x_{r-1}\right\rangle $then $H$ is finite
by induction. So let $L=\left\langle H,x_{r}^{2}\right\rangle $.
Then applying Theorem \ref{thm:8.4} with $K=H$ and $z=x_{r}$ ,
we have $L$ is finite. Then apply Theorem \ref{thm:8.4} again to
$K=L$ and $z=x_{r}$ to get that $G$ is finite.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:8.4}]
 Since $z^{2}\in K$, we have $z^{-2}\in K$, since $z^{-1}=zz^{-2}$
with $z^{-2}\in K$, we see that in a word we can replace powers of
$z$ by $z^{0}$ or $z^{1}$ times an element of $K$. So for any
$g\in G$ we have $g=u_{0}zu_{1}z\dots u_{m-1}zu_{m}$ with $u_{i}\in K$
and $u_{1},\dots,u_{m-1}\neq1$. Do this with $m$ as small as possible. 

Since $(u_{i}x)^{4}=1$ for $1\leq i\leq m-1$ we have $zu_{i}z=u_{i}^{-1}z^{-1}u_{i}^{-1}z^{-1}u_{i}^{-1}=u_{i}^{-1}zu'zu_{i}^{-1}$
for some $u'\in K$. This does not reduces $m,$ but it replaces $u_{i-1}$
by $u_{i-1}u_{i}^{-1}$. Also $g=\dots u_{i-1}zu_{i}z\dots=\dots u_{i-1}u_{i}^{-1}zu'z\dots$.
So if $u_{i-1}=u_{i}$ then we reduce $m$. 

If $m\geq3$, we can replace $u_{m-2}$ by element in the set $U_{m-2}=\{u_{m-2},u_{m-2}u_{m-1}^{-1}\}$.
Since $u_{m-1}\neq1$, elements of $U_{m-2}$ are distinct and non-trivial,
since otherwise we could reduce $m$.

Similarly if $m\geq4$, we can replace $u_{m-3}$ by elements in the
set $U_{m-3}=\{u_{m-3},u_{m-3}t^{-1},t\in U_{m-2}\}$. All such elements
are distinct, since $t$ are distinct and non-trivial so $|U_{m-3}|=1+|U_{m-2}|=2$.
None are trivial or we could reduce $m$.

So by induction if $m\geq i+1$, we can replace $u_{m-i}$ by any
elements of $U_{m-i}=\{u_{m-i},u_{m-i}t^{-1},t\in U_{m-i+1}\}$. By
induction the elements are distinct and non-trivial. So $|U_{m-i}|=i$. 

So $i=|U_{m-i}|\leq|K|-1$, putting $i=m-1$, gives $m\leq|K|$. So
we have a bound on $m$. Hence $G$ is finite as we get $|G|\leq\sum_{i=0}^{|K|+i}|K|^{i}$,
since there are at most $|K|^{i+1}$ words with $m=i$. Using Geometric
Series argument, we have $|G|\leq|K|^{|K|+2}$. 
\end{proof}
By working harder and using proven properties of $U_{m-i}$, we can
get $|G|\leq|K|^{|K|}$ when $|K|\geq4$. This gives a very bad inaccurate
bound on $|B(r,4)|$, e.g., $|B(2,4)|\leq(4^{4})^{(4^{4})}=2^{2048}$
but $|B(2,4)|=2^{12}$. 

$B(2,6)$ is finite, but the proof is longer and works by induction
by splitting $z^{6}$ into square and a cube. Note for $n=5$, we
cannot split up, $zuz=u^{-1}z^{-1}u^{-1}z^{-1}u^{-1}z^{-1}u^{-1}$
which increases number of $z$, so no techniques for reducing word
length. 


\subsection{The Grigorchuk Group}

First example of an infinite, finitely generated group in which all
elements have a finite order. All elements have order $2^{k}$ but
exists such elements for all $k$. (So it doesn't prove any $B(r,n)$
infinite) 

Let $T$ be infinite rooted binary tree
\[
\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  &  &  &  &  & \circ\ar@{-}[dddrrr]\ar@{-}[dddlll] &  &  &  &  &  & \mathrm{layer\,0}\\
\\
\\
 &  &  & \bullet l\ar@{-}[ddrr]\ar@{-}[ddll] &  &  &  &  &  & \bullet r\ar@{-}[ddrr]\ar@{-}[ddll] &  &  & \mathrm{layer\,1:}2^{1}\mathrm{vertices}\\
\\
 & \bullet ll\ar@{-}[dr]\ar@{-}[dl] &  &  &  & \bullet lr\ar@{-}[dr]\ar@{-}[dl] &  & \bullet rl &  &  &  & \bullet rr & \mathrm{layer\,2:}2^{2}\mathrm{vertices}\\
\bullet lll &  & \bullet llr &  & \bullet lrl &  & \bullet lrr &  &  &  &  &  & \mathrm{layer\,3:}2^{2}\mathrm{vertices}\\
 &  &  &  &  &  &  &  &  &  &  &  & \vdots\\
 &  &  &  &  &  &  &  &  &  &  &  & \mathrm{layer\,}n:2^{n}\mathrm{vertices}
}
\]
At every vertex label $v$, there is a copy $T_{v}$ of $T$ rotted
at $v$.

An automorphism of $T$ is a permutation of vertices that maps edges
to edges. It must fix root vertex since this has just two neighbours,
all other have three. So it must fix the set $\{l,r\}$ of neighbours
of roots, i.e. fixes the set of vertices at level 1 - so either fixes
$l$ and $r$ or interchange them. By easy induction it fixes the
set of vertices at layer $n$ for all $n\geq0$. Let $\id_{T}$ be
the identity map of $T$ and $\pi_{T}$ interchanges the corresponding
vertices in $T_{l}$ and $T_{r}$
\[
\xyC{0.5pc}\xyR{0.5pc}\xymatrix{ &  &  & \bullet\ar@{-}[rrdd]\ar@{-}[lldd]\\
\\
 & \bullet\ar@{-}[rd]\ar@{-}[ld]\ar@{<->}[rrrr] &  &  &  & \bullet\ar@{-}[rd]\ar@{-}[ld]\\
\bullet\ar@(dr,dl)@{<->}[rrrr] &  & \bullet\ar@(dr,dl)@{<->}[rrrr] &  & \bullet &  & \bullet
}
\]
i.e. $\pi_{T}=(l,r)(ll,rl)(lr,rr)(lll,rll)\dots$

The group $G$ to be constructed is defined as $G=\left\langle a,b,c,d\right\rangle $
with $a=\pi_{T}$, $b,c,d$ all fix $l$ and $r$ so can be defined
by specifying their actions on $T_{l}$ and $T_{r}$ which is as follows:

\begin{tabular}{|c|c|c|}
\hline 
 & $T_{l}$ & $T_{r}$\tabularnewline
\hline 
\hline 
$b$ & $a_{T_{l}}$ & $c_{T_{r}}$\tabularnewline
\hline 
$c$ & $a_{T_{l}}$ & $d_{T_{r}}$\tabularnewline
\hline 
$d$ & $I_{T_{l}}$ & $b_{T_{r}}$ \tabularnewline
\hline 
\end{tabular} 

This is a recursive definition. More explicitly
\begin{itemize}
\item $b$
\[
\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet b\ar@{-}[rd]\ar@{-}[ld]\\
\bullet\pi_{T_{l}} &  & \bullet c\ar@{-}[rd]\ar@{-}[ld]\\
 & \bullet\pi_{T_{l}} &  & \bullet d\ar@{-}[rd]\ar@{-}[ld]\\
 &  & \bullet I_{T_{l}} &  & \bullet b\ar@{-}[rd]\ar@{-}[ld]\\
 &  &  & \bullet\pi_{T_{l}} &  & \ddots\\
 &  &  &  & \ddots
}
\]

\item $c$
\[
\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet c\ar@{-}[rd]\ar@{-}[ld]\\
\bullet\pi_{T_{l}} &  & \bullet d\ar@{-}[rd]\ar@{-}[ld]\\
 & \bullet I_{T_{l}} &  & \bullet b\ar@{-}[rd]\ar@{-}[ld]\\
 &  & \bullet\pi_{T_{l}} &  & \bullet c\ar@{-}[rd]\ar@{-}[ld]\\
 &  &  & \bullet\pi_{T_{l}} &  & \ddots\\
 &  &  &  & \ddots
}
\]

\item $d$
\[
\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet d\ar@{-}[rd]\ar@{-}[ld]\\
\bullet I_{T_{l}} &  & \bullet b\ar@{-}[rd]\ar@{-}[ld]\\
 & \bullet\pi_{T_{l}} &  & \bullet c\ar@{-}[rd]\ar@{-}[ld]\\
 &  & \bullet\pi_{T_{l}} &  & \bullet d\ar@{-}[rd]\ar@{-}[ld]\\
 &  &  & \bullet I_{T_{l}} &  & \ddots\\
 &  &  &  & \ddots
}
\]

\end{itemize}
So the recursive definition allows us to calculate actions of $b,c,d$
on any vertex. Clearly $a^{2}=1$. Since for $b,c,d$ all vertices
lie in a subtree $T_{v}$, which action is $a_{T_{v}}$ or $\id_{T_{v}}$
we must have $b^{2}=c^{2}=d^{2}=1$. Furthermore these actions of
$(b,cd)$ on $T_{v}$ are $(\pi,\pi,I),(\pi,I,\pi)$ or $(I,\pi,\pi)$,
we must have $bc=d$ on all such subtrees. So $bc=d$, in fact $\{1,b,c,d\}$
is a Klein 4 groups and $G=\left\langle a,b,c\right\rangle $. 

Consider $aba$: $T_{r}\to T_{l}\underset{a}{\to}T_{l}\to T_{r}$,
so $aba$ acts as $a_{T_{r}}$ on $T_{r}$. 

\begin{tabular}{|c|c|c|c|}
\hline 
 & action on $T_{l}$ & action on $T_{r}$ & image under $\phi$\tabularnewline
\hline 
\hline 
$b$ & $a$ & $c$ & $(a,c)$\tabularnewline
\hline 
$c$ & $a$ & $d$ & $(a,d)$\tabularnewline
\hline 
$d$ & $\id$ & $b$ & $(\id,b)$\tabularnewline
\hline 
$aba$ & $c$ & $a$ & $(c,a)$\tabularnewline
\hline 
$aca$ & $d$ & $a$ & $(d,a)$\tabularnewline
\hline 
$ada$ & $b$ & $\id$ & $(b,\id)$\tabularnewline
\hline 
\end{tabular}
\begin{lem}
\label{lem:8.5}Let $H=\left\langle b,c,d,aba,aca,ada\right\rangle ,$then
$|G:H|=2$. In fact $H$ is the stabiliser $G_{l}$ of $l$ and $r$\end{lem}
\begin{proof}
Clearly $H\leq G_{l}$, $a\notin G_{l}$ so $a\notin H$, hence $|G:H|>1$.
So it is enough to prove $G=H\cup Ha$. We use Proposition \ref{prop:4.4}.
So $G=\left\langle a,b,c\right\rangle $ and $S=H\cup Ha$, $g_{1}=1,g_{2}=a$

\begin{tabular}{|c|c|c|c|}
\hline 
 & $a$ & $b$ & $c$\tabularnewline
\hline 
\hline 
$g_{1}$ & $a\in Ha$ & $b\in H$ & $c\in H$\tabularnewline
\hline 
$g_{2}$ & $1\in H$ & $ab=(aba)a\in Ha$ & $ac=(aca)a\in Ha$\tabularnewline
\hline 
\end{tabular}

So $S=G$.
\end{proof}
Define a homomorphism $\phi:H\to G\times G$ by $\phi(h)=(\mbox{action of }h\mbox{ on }T_{l},\mbox{action of }h\mbox{ on }T_{r})$. 
\begin{prop}
\label{prop:8.6}$G$ is infinite\end{prop}
\begin{proof}
Let $\rho_{1},\rho_{2}$ be projections of $G\times G$ onto its direct
factors, then $a,b,c,d\in\im(\rho_{1}\circ\phi)$ (and also in $\im(\rho_{2}\circ\phi)$).
If $G$ was finite, then $\im(\rho_{1}\circ\phi)\geq|G|$, but domain
$\rho_{1}\circ\phi=H$ and $|H|<|G|$ which is a contradiction.\end{proof}
\begin{prop}
\label{prop:8.7} Every $g\in G$ has finite order (a power of $2$)\end{prop}
\begin{proof}
Let $g\in G$. Write $g$ as a word of length $k$, so $g=g_{1}\dots g_{k}$
with $g_{i}\in\{a,b,c,d\}$. We use induction on $k$

$k=0$: $g=1$ which is fine

$k=1$, then $g=a,b,c$ or $d$ and $g^{2}=1$

$k>1$: If $bc$ is a subword, we can replace by $d$, similarly $bd$
is replaced by $c$ and $cd$ by $b$. So $a$, and a letter in $\{b,c,d\}$
alternate in word. Since conjugate elements have same order, if $g_{1}=g_{k}$
then $|g|=|g_{2}\dots g_{k-1}|$ which is a power of $2$ by induction,
so we can assume $g_{1}\neq g_{k}$. If for example $g_{1}=b$ and
$g_{k}=c$, then $bgb=g_{2}\dots g_{k-1}d$ which is shorter, hence
we can assume $a$ is at one end and $b,c$ or $d$ at the other,
and by conjugating by $a$, we can assume $g_{1}=a$. So $g=ax_{1}ax_{2}\dots ax_{n}$
where $k=2n$ and $x_{i}\in\{b,c,d\}$. 
\begin{caseenv}
\item $n$ is even: $g=(ax_{1}a)x_{2}(ax_{3}a)x_{4}\dots(ax_{n-1}a)x_{n}$.
So $g\in h$. A product of generators of $H$, of length $n$, so
$\phi(g)=(w_{1},w_{2})$ where $w_{i}$ are words of length $n<k=2n$.
So by induction $|w_{1}|,|w_{2}|$ are powers of $2$, and hence so
$|\phi(g)|$. But $\phi$ is clearly injective, so $|g|$ is a power
of $2$.
\item $n$ is odd: $(g\notin H)$, then we have $g^{2}=(ax_{1}a)a_{2}(ax_{3}a)x_{4}\dots(ax_{n}a)x_{1}(ax_{2})\dots(ax_{n-1}a)x_{n}$.
So each $x_{i}$ and each $ax_{i}a$ occurs once in product. Hence
$|g^{2}|=4n$ with $2n$ bracketed terms in $H$, $\phi(g^{2})=(g_{1},g_{2}),g_{1},g_{2}\in G$,
with $|g_{1}|=|g_{2}|=2n$. So cannot immediately apply induction
to $g_{1},g_{2}$. So we get three more cases

\begin{enumerate}
\item If some $x_{i}=d$, then $\phi(x_{i})=(1,b)$ and $\phi(ax_{i}a)=(b,1)$
so there is a $1$ in words for $g_{1},g_{2}$. So $|g_{1}|,|g_{2}|<2n$
by induction have order power of $2$, hence so does $g^{2}$, hence
so does $g$. 
\item If some $x_{i}=c$, then $\phi(x_{i})=(a,d)$ and $\phi(ax_{i}a)=(d,a)$.
So both $g_{1},g_{2}$ involve a $d$ and by case 2.1 we have $|g_{1}|,|g_{2}|$
are power of $2$, so is $g$
\item All $x_{i}=b$, in which case $\phi(x_{i})=(a,c)$, $\phi(ax_{i}a)=(c,a)$
and by case 2.2 we have $|g_{1}||g_{2}|$ are a power of 2, and hence
so is $|g|$
\end{enumerate}
\end{caseenv}
\end{proof}
\begin{example*}
Let $g=ab$, $g^{2}=(aba)b$, so $\phi(g^{2})=(c,a)(a,c)=(ca,ac)$
\[
g^{2}=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
ca &  & ac
}
\]
We have $(ca)^{2}=c(aca)$ and $\phi((ca)^{2})=(a,d)(d,a)(ad,da)$,
$\phi(ac)^{2}=(da,ad)$ so 
\[
g^{4}=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
(ca)^{2} &  & (ca)^{2}
}
=\xymatrix{ &  &  & \bullet\ar@{-}[ddrr]\ar@{-}[ddll]\\
\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
ad &  & da &  & da &  & ad
}
\]
Finally $\phi(ad{}^{2})=\phi((ada)d)=(b,1)(1,b)=(b,b)=\phi((da)^{2}$
\[
g^{8}=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  &  & \bullet\ar@{-}[ddrr]\ar@{-}[ddll]\\
\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
ad &  & da &  & da &  & ad
}
=\xymatrix{ &  &  &  &  &  &  & \bullet\ar@{-}[ddddrrrr]\ar@{-}[ddddllll]\\
\\
\\
\\
 &  &  & \bullet\ar@{-}[ddrr]\ar@{-}[ddll] &  &  &  &  &  &  &  & \bullet\ar@{-}[ddrr]\ar@{-}[ddll]\\
\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
b &  & b &  & b &  & b &  & b &  & b &  & b &  & b
}
\]
Since $b^{2}=1$, we have $g^{16}=1$, so $|g|=16$. Note $b\in H$,
$\phi(b)=(a,c)$. \end{example*}
\begin{thm}
$G$ has elements of order $2^{n}$for all $n\geq0$.\end{thm}
\begin{proof}
Let $g=ab$, let $x=g^{2},\phi(x)=(ca,ac)$. Let $K=\left\langle x^{G}\right\rangle =\left\langle g^{-1}xg|g\in G\right\rangle $.
So $x^{c}=cxc\in K,\phi(x^{c})=\phi(cxc)=(a,d)(ca,ac)(a,d)=(ac,dab)$.

$xx^{c}\in K$, $\phi(xx^{c})=(ca,ac)(ac,dab)=(1,x)$. Conjugating
by $a$ we get $(x,1)\in K$. Hence for all $g\in G$ we have 
\[
h=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
g &  & g'
}
\in H
\]
 for some $g'$. 
\[
h^{-1}xh=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
g^{-1}xg &  & 1
}
\in K
\]
 , this is true for all $g\in G$. Since $K=\left\langle g^{-1}xg|g\in G\right\rangle $,
we have
\[
\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
K &  & 1
}
\leq K
\]
and 
\[
\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\leq K\\
K &  & 1
}
\]
and 
\[
\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
 &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
K &  & 1
}
\leq K
\]
etc.

We now prove $K$ has elements of order $2^{n}$ for all $n\geq1$.
This is true for $n=0,1,2,3$ ($|x|=8$). For induction, let $h\in K$
with $|h|=2^{n}$. By above 
\[
\overline{h}=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
 &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
h &  & 1
}
\in K
\]
, we saw that 
\[
g^{8}=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
 &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & ?\\
 &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & ?\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & ?\\
a &  & ?(c)
}
\]
 so 
\[
g^{8}\overline{h}g^{8}=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
 &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
1 &  & h
}
\]
so 
\[
(\overline{h}g^{8})^{2}=\overline{h}g^{8}\overline{h}g^{8}=\xyC{0.3pc}\xyR{0.3pc}\xymatrix{ &  &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl]\\
 &  &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 &  &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 &  & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
 & \bullet\ar@{-}[dr]\ar@{-}[dl] &  & 1\\
h &  & h
}
\]
Since $|h|=2^{n}$ by assumption, so $|(\overline{h}g^{8})|=2^{n}$,
so $|\overline{h}g^{8}|=2^{n+1}$ completing the induction. 
\end{proof}
Let $G=\left\langle X\right\rangle $, $X$ finite. Let $g=a_{1}a_{2}\dots a_{n}$
with $a_{i}\in A^{*}=(X\cup X^{-1})^{*}$. For $g\in G$, define length
of $|g|$ to be the minimum $n$ with $g=a_{1}\dots a_{n}$, i.e.,
the length of the shortest word for $g$ (it depends on $X$). Define
the growth function $\lambda_{G,X}:\zz_{\geq0}\to\zz_{\geq0}$ by
$\lambda_{G,X}(n)=|\{g\in G||g|\leq n\}|$ (i.e., the ball of radius
$n$ around $1$). 

For free group of rank $k$, $|x|=k$, $\lambda_{G_{k}}(n)=1+2k+\sum_{i=2}^{n}(2k)(2k-1)^{i-1}=O((2k-1)^{n})$,
its an exponential function of $n$. So $G$ has exponential growth
(this property is independent of $X$)

Let $G=\left\langle g_{1},\dots,g_{k}|[g_{i},g_{j}]=1\right\rangle $,
free abelian group of rank $k$. Then $\lambda_{G,X}(n)=O(n^{k})$,
polynomial in $n$. We say $G$ has polynomial growth (again this
property is independent of $X$)
\begin{thm}[Hard (Gromov) ]
 Let $G$ be finitely generated, $G$ has polynomial growth if and
only if there exists $H\leq G$ with $|G:H|$ finite and $H$ nilpotent.
\end{thm}
Grigorchuk's group was the first example with intermediate growth,
that is $\lambda_{G,X}$ less than all polynomial in $n$, but less
than all exponential functions in $n$. 
\end{document}
