\documentclass{amsart}
\usepackage{ae,verbatim} 
\usepackage[margin=0.5 in]{geometry}
\usepackage{rotating} %for \includegraphix[angle=270]
\usepackage{amssymb}
%\usepackage{amsmath,amssymb,epsfig,amscd,xy,amsthm}
%\xyoption{all}
%\usepackage[active]{srcltx}
%\CompileMatrices


\hyphenation{arch-i-med-e-an}


%%Change to Roman for enumerate
\renewcommand{\labelenumi}{(\roman{enumi})}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{quest}[theorem]{Question}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{exercise}{Exercise}
\newtheorem{conjecture}[theorem]{Conjecture}

%Main thms
\theoremstyle{plain}
%\newtheorem*{I1}{Theorem \ref{periodic}}
%\newtheorem*{I2}{Theorem \ref{per height}}
\numberwithin{equation}{theorem}


\theoremstyle{remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{exam}[theorem]{Example}
\newtheorem{remarks}[theorem]{Remarks}
\newtheorem{assume}[theorem]{Assumption}
\newtheorem{conclude}[theorem]{Conclusion}
\newcommand{\C}{{\mathbb C}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\Fp}{{\mathbb F}_p}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\oQ}{{\overline{\mathbb Q}}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\M}{{\mathcal M}}
\newcommand{\cX}{{\mathcal X}}
\newcommand{\cY}{{\mathcal Y}}
\newcommand{\cXb}{{\overline \cX}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cA}{{\mathcal A}}
\newcommand{\cV}{{\mathcal V}}
\newcommand{\cW}{{\mathcal W}}
\newcommand{\cK}{{\mathcal K}}
\newcommand{\cZ}{{\mathcal Z}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\matO}{{\mathcal O}}
\newcommand{\OO}{{\mathcal O}}
\newcommand{\Ltilde}{{\tilde{\mathcal L}}}
\newcommand{\tensor}{\otimes}
\newcommand{\abcd}{\left( \begin{array}{cc} a & b \\ c & d \end{array} \right)}
\newcommand{\too}{\longrightarrow}
\newcommand{\bij}{\longleftrightarrow}
\newcommand{\bs}{\backslash}
\newcommand{\fO}{\mathfrak o}
\newcommand{\fo}{\mathfrak o}
\newcommand{\fq}{\mathfrak q}
\newcommand{\fr}{\mathfrak r}
\newcommand{\fm}{\mathfrak m}
\newcommand{\fp}{\mathfrak p}
\newcommand{\pp}{\mathfrak p}
\newcommand{\fZ}{\mathfrak Z}
\newcommand{\tfp}{\tilde \fp}
\newcommand{\Cs}{{\mathcal C}}
\renewcommand{\H}{{\mathcal H}}
\renewcommand{\L}{{\mathcal L}}
\newcommand{\inj}{\hookrightarrow}
\newcommand{\ba}{ {\overline \alpha} }
\newcommand{\bL} {\overline L }

\newcommand{\ffp}{{\mathbb F}_p}

\newcommand{\vb}{\vec{\beta}}
\newcommand{\Kbar}{\overline K}
\newcommand{\kbar}{\overline{k}}
\DeclareMathOperator{\length}{length}
\DeclareMathOperator{\Alg}{Alg}
\DeclareMathOperator{\Per}{Per}
\DeclareMathOperator{\Fin}{Fin}
\DeclareMathOperator{\Orb}{Orb}
\DeclareMathOperator{\PSL}{PSL}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\mymod}{mod}
\def\Frac{\operatorname{Frac}}
\newcommand{\Pl}{{\mathbb P}}
\newcommand{\Qbar}{\overline{\Q}}
\newcommand{\Zbar}{\overline{\Z}}
\newcommand{\fbar}{\bar{f}}
\newcommand{\surj}{\twoheadrightarrow}
\DeclareMathOperator{\Spec}{Spec} \DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\Proj}{Proj} \DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\fin}{fin}
\DeclareMathOperator{\bNorm}{Norm}

\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Disc}{Disc}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\N}{N}
\DeclareMathOperator{\Norm}{Norm}
\DeclareMathOperator{\tth}{^{th}}
\DeclareMathOperator{\trdeg}{trdeg}
\DeclareMathOperator{\sep}{sep}
\DeclareMathOperator{\red}{red}
\DeclareMathOperator{\tor}{tor}
\DeclareMathOperator{\car}{char}
\DeclareMathOperator{\group}{\GL_d\left(\widehat{A}\right)}
\DeclareMathOperator{\aut}{Gal(K^{\sep}/K)}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\CC}{\mathbb{C}_{\infty}}
\DeclareMathOperator{\Pic}{Pic}
\DeclareMathOperator{\bNum}{Num}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\smooth}{smooth}
\DeclareMathOperator{\order}{order}
\DeclareMathOperator{\hor}{hor}
\DeclareMathOperator{\ver}{ver}
\DeclareMathOperator{\Supp}{Supp}
\DeclareMathOperator{\Div}{div}
\DeclareMathOperator{\Ar}{Ar}
\DeclareMathOperator{\mg}{MG}
\DeclareMathOperator{\finite}{finite}
\DeclareMathOperator{\bN}{\mathbb{N}}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\PGL}{PGL}
\newcommand{\isomto}{\overset{\sim}{\rightarrow}}
\newcommand{\prob}{{\operatorname{Prob}}}
\newcommand{\cycle}{{\mathcal{C}}}
\newcommand{\ramification}{{\mathcal{R}}}
\newcommand{\erfc}{{\operatorname{erfc}}}
\newcommand{\A}{{\mathbb A}}
%\newcommand{\fp}{{\mathbb F}_p}

\newcommand{\kb}{{\bar k}}
\newcommand{\bP}{{\mathbb P}}
\newcommand{\bZ}{{\mathbb Z}}
\newcommand{\bG}{{\mathbb G}}
\newcommand{\Zp}{{\mathbb{Z}_p}}
\newcommand{\bM}{{\mathbb M}}
\newcommand{\bC}{{\mathbb C}}
\newcommand{\bR}{{\mathbb R}}
\newcommand{\bA}{{\mathbb A}} 
\newcommand{\bQ}{{\mathbb Q}}
\newcommand{\bF}{{\mathbb F}}
\newcommand{\Fq}{\bF_q}
\newcommand{\lra}{\longrightarrow}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\bQb}{\bar{\bQ}}
\newcommand{\bK}{\overline{K}}
\newcommand{\hhat}{{\widehat h}}

\newcommand{\Drin}{{\bf \varphi}}

\newcommand{\Cp}{\bC_p}
\newcommand{\PCp}{\bP^1(\bC_p)}
\newcommand{\PCv}{\bP^1(\bC_v)}

\newcommand{\Dbar}{\overline{D}}


\begin{document}

\section*{Assignment 2: Due Feb. 28, 2019}
The purpose of the first few exercises on this assignment is to show that subgroups of free groups are free (you can do exercises $9$ and $10$ first if you prefer).  For exercises $1$--$8$, we let $F$ be a free group on a set $X$ and we let $W$ be a subgroup of $F$.  We let $\{W_i\colon i\in I\}$ be the set of right cosets of $W$, so they are indexed by a set $I$ and we assume our index set contains an element $1$ and that $W_1=W$.  We recall that a right transversal to a subgroup is just a collection of right coset representatives (i.e., an element from each coset).  We choose a right transversal to $W$ with the representative of the coset $W_i$ denoted $\overline{W_i}$, so $\overline{Wa}$ is the coset representative for $Wa$. We assume that our transversal has the property $\overline{W}=\overline{W_1}=1$.  To each element $x\in X$ and $i\in I$ we associate a symbol $y_{i,x}$ and we let $G$ denote the free group on the set $Y:=\{y_{i,x}\colon i\in I, x\in X\}$.  
\begin{enumerate}
\item[(1)] Show that the map $y_{i,x}\mapsto \overline{W_i} x \overline{(W_i x)}^{-1}$ induces a homomorphism $\tau: G\to W$.
\item[(2)] To each $u\in F$ and each $i\in I$ we construct an element $u^{W_i}$ of $G$ as follows.  We may assume that $u$ is a word in $X\cup X^{-1}$ with no occurrences of $xx^{-1}$ or $x^{-1}x$ with $x\in X$.  Define $1^{W_i}=1$, $x^{W_i}=y_{i,x}$ for $x\in X$, and $(x^{-1})^{W_i} = (x^{W_i x^{-1}})^{-1}$ for $x\in X$.  Then in general we define the map inductively by saying that if $u = v x$ with $y\in X\cup X$ and $v$ is a reduced word shorter than $u$ with the last letter of $v$ not being $y^{-1}$, then we define $u^{W_i}:=v^{W_i}\cdot y^{W_i v}$. Show, using induction on the length of $v$ that under this assignment that for $u,v\in F$ we have $(uv)^{W_i}=u^{W_i} v^{W_i u}$ and $(u^{-1})^{W_i} = (u^{W_i u^{-1}})^{-1}$. 
\item[(3)] Show by induction on the length of $u$ that if $u\in F$ and $i\in I$ then 
$\tau(u^{W_i}) = \overline{W_i} u \overline{W_i u}^{-1}$
\item[(4)] Now we construct a map $\psi: W\to G$ by $u\mapsto u^W$.  Show that $\psi$ is a homomorphism and that $\tau(\psi(u))=u$ for all $u\in W$ and conclude that $\psi$ is one-to-one and $\tau$ is onto and $W\cong G/{\rm ker}(\tau)$.
\item[(5)] Let $\chi$ be the endomorphism of $G$ given by $\chi = \psi\circ \chi: G\to G$. of $G$.  Show that ${\rm ker}(\chi)={\rm ker}(\tau)$ and so $W\cong G/{\rm ker}(\chi)$.  Show that the kernel of $\chi$ is the normal closure, $N$, of the set $b_{i,x}:=y_{i,x}^{-1}\chi(y_{i,x})$ with $i\in I$, $x\in X$.  (Hint: show that each $b_{i,x}$ is in the kernel of $\chi$ and conclude that $N$ is contained in ${\rm ker}(\chi)$.  To do the other inclusion take an element $g$ of $G$ that is in the kernel of $\chi$.  Write $g$ as a reduced word in the $y_{i,x}$.  Use the fact to show that $\chi(y_{i,x})\equiv y_{i,x}~(\bmod ~N)$ and the fact that $\chi$ is a homomorphism to conclude that $\chi(g)\equiv g~(\bmod~N)$; that is $\chi(g) g^{-1}\in N$.  But $\chi(g)=1$ since $g$ is in the kernel!
\item[(6)] Show in fact that the normal closure, $K$, of the elements $u^W$, with $u$ a non-trivial element of our transversal, is equal to the kernel of $\tau$. 
\item[(7)] We're almost done! We say that a transversal $\Sigma$ to $W$ is a \emph{Schreier transversal} if $v\in \Sigma$ whenever $vy\in \Sigma$ and $x\in X$ and $vy$ is in reduced form (that is, the transversal is closed under taking prefixes of reduced words).  Show that a Schreier transversal to $W$ exists.  (Hint: define the length of a coset $Wa$ to be the minimum length of a word in $Wa$.  So the only coset of length zero is $W=W_1$, which has the word empty-word $1$.  Suppose we have produced (reduced) coset representatives $\overline{W_i}$ for each coset $W_i$ of length $<\ell$ in such a way that our set is closed under taking prefixes.  Then if $Wa$ is a coset of length $\ell$ and $u\in Wa$ has length $\ell$, then we can write $u=vy$ with $v$ of length $\ell-1$ and $y\in X\cup X^{-1}$.  Define $\overline{Wa}= \overline{Wv}y$ and show that this procedure inductively produces a Schreier transversal.)
\item[(8)] Now we'll prove that subgroups of free groups are free.  Let $\Sigma$ be a Schreier transversal to $W$ in $F$ and let $K={\rm ker}(\tau)={\rm ker}(\chi)$.  Then from exercise 6, we have that $K$ is the normal closure of $u^W$ where $u$ is a non-trivial word in the transversal.  Show that if we have $u=vx^{\epsilon}$ with $v$ of length $<u$ and $x\in X$ and $\epsilon \in \{\pm 1\}$ then $u^W=v^W y_{k,x}^{\epsilon}$ for some $k\in I$. Since $v$ is in the transversal, conclude that $K$ is the normal closure of these elements $y_{k,x}$ we obtain, which is a subset $Y'$ of $Y$.  Conclude that $$W\cong G/K \cong \langle Y | Y'\rangle \cong F_{Y\setminus Y'}.$$ 
\item[(9)] Let $F$ be a free group and let $R$ be a subset of $F$.  Show that the normal closure of $R$ is the set of elements that can be expressed in the form $g_1 r_1^{\epsilon_1} g_1^{-1} g_2 r_2^{\epsilon_2} g_2^{-1}\cdots g_s r_s^{\epsilon_s} g_s^{-1}$ with $s\ge 1$, $\epsilon_1,\ldots ,\epsilon_s\in \{\pm 1\}$, and $g_1,\ldots ,g_s\in F$ and $r_1,\ldots ,r_s\in R$. 
\item[(10)] Let $F$ be a free group on a set $X$ and let $R=\{xyx^{-1}y^{-1}\colon x,y\in X\}$.  Show that $\langle X|R\rangle \cong \mathbb{Z}^{\oplus X}$, the free abelian group on $X$.  (Hint: let $G= \mathbb{Z}^{\oplus X}$ be the free abelian group with generators $e_x$, with $x\in X$.  Show we have a homomorphism $\Phi: F \to G$ induced by the set map $x\mapsto e_x$ and that the kernel contains $R$ and so the normal closure, $N$, of $R$ is contained in the kernel of $\Phi$.  Hence $\Phi$ induces a surjective homomorphism $\Phi' : \langle X|R\rangle \to G$.    Next show that $\langle X|R\rangle$ is abelian and generated by elements $x$ and so we have a surjective homomorphism $\Psi : G \to  \langle X|R\rangle$ that sends $e_x$ to the coset $xN$.  Show that $\Phi\circ \Psi: G\to G$ is an isomorphism and finish it off!
\item[(11)] Let $F$ be a free group on $d\ge 2$ generators $x_1,\ldots ,x_d$.  From the above $F/F'$ ($F'$ is the normal subgroup generated by all commutators) is the free abelian group on $x_1,\ldots ,x_d$. Use this to show that $x_1^{a_1}\cdots x_d^{a_d}$ form a Schreier transversal to $F'$. Then use the argument above to show that $F'$ is a free group on a countably infinite set of generators.  Conclude that every noncyclic free group contains a free group on infinitely many generators.  
\end{enumerate}
\end{document}
