\documentclass{amsart}[12pt]
\usepackage{amsmath, amsthm}
\usepackage{amscd}
\usepackage[arrow,matrix,curve]{xy}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\newcommand{\bs}{\mathrm{BS}\,}
\newcommand{\Area}[1]{{\mathrm{Area} }\left({#1}\right)}
\newcommand{\link}[1]{\mathrm{link}(#1)}
\newcommand{\ang}[1]{\angle(#1)}
\newcommand{\mr}[1]{\mathrm{#1}}
\newcommand{\lra}{\longrightarrow}

\begin{document}

\section*{Lecture 17}

\begin{theorem}
Let $G$ be finitely presented $C(4)-T(4)$ group. Then $G$ is automatic.
\end{theorem}
{\sc Proof. }We prove special case when $G=\pi_1X$ with $X$ a $(4,4)$
complex. Without loss of generality, each $2$-cell is a square
(obtain this by subdividing). Without loss of generality, $X$ has
one $0$-cell (treat general case using ``$A*B$ is automatic
$\Leftrightarrow$ $A,B$ are automatic'' and
$\pi_1(X/X^0)\cong\pi_1X*f_{|X^0|-1}$).

The regular language $L$ consists of geodesic paths in
$(\widetilde{X})'$ which do not contain certain subpaths.
($\widetilde{X}=$ Cayley graph of $G$.)

Forbidden paths:
\begin{verse}
(figure) no ``backtracks'' (in fact, already forbidden by geodesic
requirement),\\
(figure) no ``wrap around'' a single $2$-cell (in fact, already
forbidden by geodesic requirement),\\
(figure) no ``postponed turns.''
\end{verse}

We need to show that for each $v\in \tilde{X}^0$ there is a nonforbidden
geodesic path from $1$ to $v$. Show that starting with a geodesic
$\gamma$.

(figure) Gradually transforming the geodesic obtain nonforbidden one.
Process stops because each transformation yields a geodesic less
with respect to lexicographical order, induced by assigning ``t'' to
turn vertices and ``n'' to non-turn vertices.

Obtained a language $L$ that surjects to $G$. Interestingly, it is
language we were talking about last time. (figure)

Prove fellow travelling property. Suppose $U,V$ are paths in $L$ such
that $d_G(u,v)\le1$.

(figure)

Then there is a disc diagram for $uev^{-1}$ where $e=1$ or a single
edge.

Combinatorial Gauss--Bonet theorem: curvature argument implies
$D$ is a ladder, so $U,V$ fellow travel. Namely, note that
curvature given by the top path is at most $\pi\over2$, as is curvature
given by the bottom. Indeed,
\begin{verse}
path can't have $\pi\over2$ curvature right after $0$ (figure),\\
path can't have two $\pi\over2$ in a row (figure),\\
can't happen (figure),\\
after string of $0$, there is a negative curvature
before positive (figure).\\
\end{verse}

(figure) Sum is $2\pi$, so at the ``end'' we have two positive angles,
which gives a ladder.

Note that $\pi$ curvature at the ``start'' may be ignored, as language
is closed under subpath (figure), and note also that $\pi\over2$
curvature at the ``start'' gives nonpositive curvature on the top and
bottom (figure).
\begin{flushright}$\Box$\end{flushright}

\begin{definition}
$G$ is biautomatic if there is a language in monoid generators $S$
of $G$ such that
\begin{verse}
1) $L\to G$ is a surjection,\\
2) $K$-fellow travelling property between the paths $U,V$ such that
initial and end points of $U,V$ are at distance $\le1$ in $\Gamma(G,S)$.
\end{verse}
\end{definition}

\begin{definition}
A combing of a group $G$ with monoid generators $S$
is a map $\phi:G\to M$ ($M=M(S)$) such that
with $\rho:M\to G$ induced by generators,
$\rho\circ\phi=\mathrm{Id}$ (i.e. it's assignment of normal
form for each $g\in G$). (figure)

Require that:\\
1) $|\phi(g)|\le Kd(1,g)$ for some universal constant,\\
2) if $d(g,h)\le1$, then $\phi(g),\phi(h)$ K-fellow travel.\\
1') $\phi(g)$ is quasigeodesic.

For bicombing, require\\
2') left $+$ right fellow travel.
\end{definition}

$\mathrm{CAT}(0)$ groups are combable, automatic groups are combable.
Unknown if a combable group is always automatic.

If $G$ is combable then
\begin{verse}
1) $G$ is finitely presented,\\
2) $G$ has a quadratic isoperimetric function.
\end{verse}
Draw all combings, use fellow travelling.

(figure)
\end{document}
