\documentclass{amsart}
\usepackage{verbatim} 
\usepackage[margin=0.5 in]{geometry}
\usepackage{rotating} %for \includegraphix[angle=270]
\usepackage{amssymb,ae}
%\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 3: Due Mar. 14, 2019}
The purpose of the first few exercises on this assignment is to construct the Grigorchuk group.\begin{enumerate}
\item[(1)] Let $G$ be a graph.  We say that $f$ is an automorphism of $G$ if $f$ is a bijective map from the set of vertices of $G$ to itself, such that $f(x)$ and $f(y)$ are adjacent vertices if and only if $x$ and $y$ are bijective vertices.  Show that the collection of automorphisms of $G$ forms a group ${\rm Aut}(G)$ under composition. 
\item[(2)] We let $T$ denote the graph whose set of vertices is the collection of finite words over the alphabet $\{0,1\}$ and in which there is an edge between $w$ and $v$ if and only if either $w=v0$ or $w=v1$ or $v=w0$ or $v=w1$.  In other words, the longer word is obtained from the shorter word by appending a letter on the right.  This is an infinite tree whose root is the empty word.  We identify $T$ with its set of vertices $\{0,1\}^*$. Recursively construct four maps $a,b,c,d: T\to T$ as follows.  We define $a(\epsilon)=b(\epsilon)=c(\epsilon)=d(\epsilon)=\epsilon$ (where $\epsilon$ is the empty word) and if we have defined the maps on all words of length $\le n$, and $w$ is a word of length $n$, we define
$$a(0w)=1w, a(1w)=0w, b(0w)=0a(w), b(1w)=1c(w), c(0w)=0a(w), c(1w)=1d(w), d(0w)=0w, d(1w)=1b(w).$$
Show that $a,b,c,d$ all give automorphisms of $T$ and $a^2=b^2=c^2=d^2={\rm id}$.  We let $\Gamma$ denote the subgroup of ${\rm Aut}(T)$ generated by $a,b,c,d$.
\item[(3)] Show that every non-identity element of $\Gamma$ is expressible in one of the four forms $ax_1 a x_2 a \cdots a x_n a$, $a x_1 a x_2 a \cdots x_{n} $, $x_1 a x_2 \cdots a x_n a$, $x_1 a x_2 \cdots a x_n$ with $x_1,\ldots ,x_n\in \{b,c,d\}$.  Hint: show that $b,c,d$ commute and generate a group of order $4$ with $bc=cb=d, bd=db=c, cd=dc=b$.  
\item[(4)] Show that if $T$ is as above then we have an injective group homomorphism $\phi : {\rm Aut}(T)\times {\rm Aut}(T)\to {\rm Aut}(T)$, defined by $\phi(f,g)(\epsilon)=\epsilon$ and word a word $w$ of length $\ge 0$ we have $\phi(f,g)(0w)=0f(w)$ and $\phi(f,g)(1w)=1g(w)$, and that we have $b=\phi(a,c)$, $c=\phi(a,d)$, and $d=\phi({\rm id},b)$.  Show that the image of $\phi$ is all automorphisms of $T$ that send the vertex $0$ to $0$ and the vertex $1$ to $1$.
\item[(5)] Let $H$ denote the set of $g\in \Gamma$ such that $g(0)=0$ and $g(1)=1$.  Show that $H$ is a proper index-two subgroup of $\Gamma$ and show $b,c,d,aba,aca,ada$ are all in $H$ and use question 3 to show that they generate $H$, arguing that you need to have an even number of copies of $a$ to be in $H$.  Next show that $\phi^{-1}(H) \subseteq \Gamma\times \Gamma$, by showing that $\phi^{-1}(b)=(a,c)$, $\phi^{-1}(aba)=(c,a)$, $\phi^{-1}(c)=(a,d)$, $\phi^{-1}(aca)=(d,a)$, $\phi^{-1}(d)=({\rm id},b)$, $\phi^{-1}(ada)=(b,{\rm id})$.
\item[(6)] Use the preceding question to show that $\Gamma$ is infinite.  Hint: Show that if $\pi_1 : \Gamma \times \Gamma \to \Gamma$ is projection onto the first coordinate then show that 
$\pi_1(\psi^{-1}(H))=\Gamma$.  If $\Gamma$ is finite and $H$ has index two, how is that possible?
\item[(7)] Show that every element of $\Gamma$ has finite order.  (Hint: This is tricky---I'll give a sketch and leave it to you to work out the details).  Use question 3, and argue by induction on the length of a word in $a,b,c,d$ doing words of length $1$ and $2$ as the base cases.  Now if a word is of the form $ax_1 a x_2 a \cdots a x_n a$, then this is just $a w a^{-1}$ with $w$ of shorter length.  If it is of the form $x_1 a x_2 \cdots a x_n$, then use the fact that $bc=d, cd=b, db=c$ and write this as $x_1 (a x_2 \cdots a x_n')x_1^{-1}$ and use the induction hypothesis. The other two cases are a bit trickier, but they are both handled in the same way, so I'll show you how to do one and you can do the other.  If you have $w=a x_1 a x_2 a \cdots x_{n}$, then let's first look at when $n$ is even.  Write 
$w=(ax_1a) x_2 (ax_3a) x_4 \cdots (ax_{n-1}a) x_n$. Then each $ax_i a$ and $x_j$ is in $H$ so we can apply the homomorphism $\phi^{-1}: H\to \Gamma\times \Gamma$ and we get 
$\phi^{-1}(w) =\phi^{-1}(ax_1a) \phi^{-1}(x_2) \phi^{-1}(ax_3a) \phi^{-1}(x_4) \cdots \phi^{-1}(ax_{n-1}a) \phi^{-1}(x_n)$.  Show this is of the form $(w',w'')$ with $w',w''$ of length $\le n$ and use the induction hypothesis.  What about when $n$ is odd? Then $w=a x_1 a x_2 a \cdots x_{n}$, so $w^2=a x_1 a x_2 a \cdots x_{n} a x_1 a x_2 a \cdots x_{n}$, and as before we compute $\psi^{-1}(w^2)$ as before and we get that it is of the form $(w',w'')$ with $w'$ and $w''$ of length $2n$.  This doesn't seem to get us much, but remember $\phi^{-1}(d)=({\rm id},b)$ and $\phi^{-1}(ada)=(b,{\rm id})$.  That means we can apply the induction hypothesis if when we break up 
$w^2=(a x_1 a)( x_2) a \cdots x_{n} ( x_1) (a x_2 a) \cdots (x_{n})$, if any of the $x_i=d$ then $w'$ and $w''$ have length $<2n$ (why?).  Otherwise, it looks like we're stuck, but think about this: we just need to show $w'$ and $w''$ are torsion, and so we can assume that they are of the remaining forms since otherwise we can use the induction hypothesis.  So let's look at $w'$ and assume that it is of the form we are considering If some $x_i$ is $c$ then $w'$ has a $d$ in its representation---think about it!  Show it either reduces to something of shorter length, or it is torsion, or it is already in the reduced form and in the last case we can apply $\psi^{-1}$ to $w'$ and apply the induction hypothesis since now we'll get a shorter length.  That means that every $x_i=b$ but you showed in the base case that $ab$ is torsion!)
\item[(8)] Let $S=\{a,b,c,d\}$ and let $f(n)=d_S(n)$ denote the growth function.  Let's try to count $f(n)$---this is really tricky, so I'm just giving an idea and I'll let you work through this.  Reserve a lot of time to think about this.  Show that every word of length $\le n$ can be written in the form $uv$ where $u$ has length $\le n$ is in the form  $u=a x_1 a x_2 a \cdots x_{m}$ or $u=x_1 a x_2 a \cdots x_{m}a$ with $m$ even and $v$ a word of length at most $\le 3$ and length $u+$ length $v$ less than or equal to $n$.  Let $C$ be the number of words of length $\le 3$.  Now by an earlier question, we showed that $(ab)^L=1$ for some $L$.  That means that if we have $L$ consecutive $x_i=b$ in $u$ then we can reduce our word, so we can assume that we never have $L$ consecutive $b$'s in our $u$ or else we'd reduce it.  So now let $s$ be the number of $d$'s and let $t$ be the number of $c$'s in $u$.  Then show that after reducing we must have $s+t\ge \lfloor m/L \rfloor$.  Now write $\phi^{-1}(u)=(w',w'')$.  Show that the length of $w'$ as an expression in our generators plus the length of $w''$ is at most
$n-s$.  Now $w'$ and $w''$ are not necessarily in reduced form from (3), but notice that any interior $c$ occurring in the expressions for $w'$ and $w''$ that is not sandwiched between two $a$'s can be reduced using the rules $bc=cb=d, bd=db=c, bb=1$.  Write $w'=u' v'$ and $w''=u'' v''$ where $v',v''$ have length at most $3$ and $u', u''$ both of the form $a x_1 a x_2 a \cdots x_{m}$ or $x_1 a x_2 a \cdots x_{m}a$ with $m$ even.  Now apply $\phi^{-1}(u')$ and get $(w_1',w_1'')$ and $\phi^{-1}(u'')=(w_2',w_2'')$ and show the sum of the lengths of $w_1'$, $w_1''$, $w_2'$, $w_2''$ is at most the sum of the lengths of $u'$ and $u''$ and if it has length $u'$ + length $u''$ $-r$ then we have at least $t-r$ copies of $d$ occurring in the union of the words $w_1',w_1'', w_2',w_2''$.  Show that when you write it of the form $uv$ above and reduce and apply the procedure again, you get 8 words (two from each of $w_1', w_1'', w_2', w_2''$ and the sum of the lengths of these 8 words after you reduce is at most $n-s-t\le n-n/L+1$.  
OK, so now you have to think a lot! At each step we are taking words $w$ and writing them of the form $uv$, we have at most $C$ choices for $C$.  Show using this idea that
$$f(n) \le C^{16} \sum_{n_1+n_2+\cdots +n_8=n-n/L+1} f(n_1)f(n_2)\cdots f(n_8).$$ Use this to show that $f(n)$ is asymptotically dominated by the exponential function $2^n$.
\item[(9)] Let $G$ be a finitely generated nilpotent-by-finite torsion group and suppose that $G$ is torsion. Show that $G$ is finite.  (Hint: Suppose that $G$ is infinite and fix a finite-index normal nilpotent subgroup $N$ of $G$.  Let $X$ denote the set of normal subgroups $E$ of $G$ such that $G/E$ is infinite.  Show using Zorn's lemma that $X$ has a maximal element $E$ and replace $G$ by $G/E$ and thus we may assume that every non-trivial normal subgroup of $G$ has finite-index in $G$.  Now since $N$ is nilpotent it has a non-trivial center.  Pick $z\neq 1$ in the centre.  Let $Z$ denote the group generated by $gzg^{-1}$ with $g\in G$.  Show that $Z$ is a normal subgroup of $G$ that is finite.   Why are you done?
\item[(10)] Use Gromov's theorem to conclude that $\Gamma$ has super-polynomial growth.  So it is an infinite finitely generated torsion group whose growth is not polynomially bounded and not exponential.  


\end{enumerate}
\end{document}