\section{The Virtual Case} \label{sec:virtual}

Much is already written about virtual knot theory (see for example
\cite{Kauffman:VirtualKnotTheory, Kauffman:RotationalVirtualKnots,
Manturov:VirtualKnots}) here we give a quick summary of some basic ideas. Classical knots, braids, and tangles can all be
defined following the mould ``properly annotated planar graphs with
univalent and quadrivalent vertices and with properties PPP, modulo local
relations RRR''. Virtual knots, braids, and tangles are exactly the same,
except that the word ``planar'' is removed from the mould and otherwise
nothing is changed. See some examples in Figure~\ref{fig:vexamples}.

\begin{figure}
\[ \input{figs/vexamples.pdf_t} \]
\caption{
  A 3-crossing knot and a 2-crossing virtual knot, a 3-crossing braid and
  a 2-crossing virtual braid, and a 3-crossing tangle and a 2-crossing
  virtual tangle.
} \label{fig:vexamples}
\end{figure}

Note that all the virtual examples in Figure~\ref{fig:vexamples} contain
a feature like $\virtualcrossing$, often called a ``virtual crossing''. A
``virtual crossing'' is {\bf not a crossing}: It is merely an artifact of
the fact that when a non-planar graph is drawn on a piece of paper, some
edges will intersect, even though from a graph-theoretic
perspective these intersections are not vertices, and not part of the data of the graph.

In this paper virtual tangles and virtual braids are
always ``pure'': the ordering of the ends of strands around the boundary
of a planar domain has no graph theoretical meaning, for the planar
domain itself has no graph theoretic meaning. Yet it makes sense to
consider virtual objects whose strands are labelled by some finite set
$S$, and once this is done, virtual tangles become a monoid and virtual
braids become a group, where the product\footnote{ 
In the ``Geography vs.\ Identity'' language of~\cite{Talk:GvI},
compositions of classical tangles/braids are ``Geography'', because
they are defined using the placements of the ends being stitched, while
compositions of virtual tangles/braids are ``Identity'' because they
are defined using the identity of the ends being stitched.} of $T_1$ (or $B_1$) with $T_1$
(or $B_2$) is the disjoint union operation of graphs, followed by the
``stitching'' of the head of strand $a$ in $T_1$ (or $B_1$) to the tail of
strand $a$ in $T_2$ (or $B_2$), for every $a\in S$.

Thus the virtual (pure) braid group on $n$ strands is the group with
generators $\sigma_{ij}$ ``strand $i$ crosses over strand $j$ in a
positive crossing'' where $i\neq j\in\underline{n}$ and $\underline{n}$ is
some fixed set with $n$ elements (perhaps $\underline{n}=\{1,\ldots,n\}$),
and with relations matching the R3 move and the fact that crossings that
involve totally distinct strands commute:
\[ \vcalPB_n = \left\langle
    \sigma_{ij}\colon\ 
    \sigma_{ij}\sigma_{ik}\sigma_{jk}=\sigma_{jk}\sigma_{ik}\sigma_{ij}
    \text{ and }
    \sigma_{ij}\sigma_{kl}=\sigma_{kl}\sigma_{ij}
  \right\rangle,
\]
where it is understood that $i,j,k,l$ are arbitrary distinct elements of
$\underline{n}$. For example, the two braids in Figure~\ref{fig:vexamples}
are $\sigma_{12}\sigma^{-1}_{31}\sigma_{23}$ and $\sigma_{12}\sigma_{23}$
(the first was introduced as a classical braid, but it is also a pure
virtual braid).

We let $\vcalPBD_n$ denote the monoid of all virtual braid diagrams on $n$ strands: namely, the monoid of all
words in the generators $\sigma_{ij}^\pm$, with no relations.

With this said, everything in Section~\ref{sec:classical} up to but
not including the Classical Isomorphism Theorem (\ref{thm:iso}) makes sense and holds true in the
virtual case as well, for nothing there depends on the planarity of
diagrams. Hence we have a commutative diagram:
\[ \xymatrix{
  \vcalPBD_n \ar@{^{(}->}[r]^{\iota_v} \ar[d] & \vcalACD_n \ar[r]^{\Gamma_v} \ar[d] & \vcalOUD_n \ar[d] \\
  \vcalPB_n \ar[r]^<>(0.5){\bariota_v} \ar@/_6mm/[rr]_\Ch
    & \vcalAC_n \ar[r]^<>(0.5){\barGamma_v}_<>(0.5)\cong & \vcalROU_n
} \]
In this diagram everything was already defined or is the obvious virtual
analog of its counterpart in the classical case and does not need
a definition, except that we give a special name, the {\em Chterental
map} $\Ch\coloneqq\barGamma_v\circ\bariota_v$, to the composition along the bottom. Yet in contrast with
the Classical Isomorphism Theorem (\ref{thm:iso}) we have the Theorem~\ref{thm:vinj} below. This theorem is originally due to Oleg
Chterental~\cite{Chterental:VBandVCD, Chterental:Thesis} in a different context; our version is reformulated and independently proven, see a comparison in Discussion~\ref{disc:Chterental}. The proof presented in this section also leads to a new graph-valued braid and virtual braid invariant, see Discussion~\ref{disc:EG} and Section~\ref{sec:comp}.

\begin{theorem} \label{thm:vinj} (\cite{Chterental:VBandVCD, Chterental:Thesis}, independent proof
below)
$\Ch=\barGamma_v\circ\bariota_v$, and hence $\bariota_v$, is injective but not surjective.
\end{theorem}

Hence the following corollaries hold true:

\begin{corollary} \label{cor:vbraids} ~\cite{Chterental:VBandVCD, 
Chterental:Thesis}
$\Ch$ is a
complete invariant of virtual pure braids.\footnote{An earlier separation
result for virtual braids is in~\cite{GodelleParis:WordProblems}.} \qed
\end{corollary}

\begin{corollary} ~\cite{Chterental:VBandVCD, 
Chterental:Thesis} The two actions of virtual pure braids on reduced virtual
OU diagrams are simple but not transitive.\qed
\end{corollary}

\begin{corollary} ~\cite{Chterental:VBandVCD, 
Chterental:Thesis} Not all virtual OU tangles are equivalent to virtual pure braids. \qed
\end{corollary}

\begin{discussion} \label{disc:plan}
The rest of this section is devoted to a proof of
Chterental's Theorem (\ref{thm:vinj}). The idea is to ``extract'' as much of a virtual
braid out of a virtual OU tangle $T$ as possible, by extracting one
braid generator at a time while reducing the complexity of what remains
of $T$. The process won't always invert $\Ch$
(for $\Ch$ is not invertible), yet it will
invert $\Ch$ on the image of virtual braids,
which is enough. The main tools will be the Division Lemma (\ref{lem:divquo}) which
gives a necessary and sufficient condition for the extraction of one
braid generator, and the Diamond Lemma (\ref{lem:diamond}), which
will guarantee that this extraction process always terminates with a
well-defined answer.
\end{discussion}

\begin{definition} If $T\in\vcalAC_n$ is a virtual acyclic tangle,
let $\xi(T)$ denote the crossing number of $\barGamma_v(T)$, its R1-
and R2-reduced OU form (not counting virtual crossings, of course). We say
that a virtual braid $\beta\in\vcalPB_n$ divides a virtual acyclic
tangle $T\in\vcalAC_n$, and write $\beta\mid T$, if when $\beta$ is
extracted out of $T$, this reduces the crossing number. In other words,
if $\xi(\beta^{-1}T)<\xi(T)$. In that case, we call $\beta^{-1}T$ the
quotient of $T$ by $\beta$.
\end{definition}

\parpic[r]{
  \def\c{$\sigma_{12}$}
  \input{figs/T1T2.pdf_t}
}
\begin{example} \label{exa:indivisible} The figure on the right shows two virtual OU
tangles, $T_1$ and $T_2$. We have that $\sigma_{12}\mid T_1$ and
$\sigma_{12}^{-1}T_1=T_2$. On the other hand, $T_2$ is not divisible
by anything, as it can be readily verified that $\xi(T_2)=2$
while $\xi(\sigma_{12}^{\pm 1}T_2)>2$ and $\xi(\sigma_{21}^{\pm 1}T_2)>2$.
\end{example}

\Needspace{30mm} % 29mm is not enough
\parpic[r]{
  \def\a{$\sigma_{23}$} \def\b{$\sigma_{13}$} \def\c{$\sigma_{12}$}
  \input{figs/GarsideHexagon.pdf_t}
}
\begin{example} \label{exa:GarsideHexagon} The figure on the right shows in its left part
the Garside ``positive half twist'' braid on 3 strands, which
happens to be OU in its given presentation, fit within a hexagon
summarizing its five divisors $\sigma_{12}$, $\sigma_{23}$,
$\sigma_{12}\sigma_{13}$, $\sigma_{23}\sigma_{13}$,
$\sigma_{12}\sigma_{13}\sigma_{23} = \sigma_{23}\sigma_{13}\sigma_{12}$,
and the five resulting quotients. This hexagon is also an example of an
extraction graph; see Discussion~\ref{disc:EG}.
\end{example}

Please bear with us and read the following two examples carefully,
as they play a role in the proof of Chterental's Theorem (\ref{thm:vinj}).

\begin{example} \label{exa:CinnamonRolls} The $k$-twist braids are the braids
$(\sigma_{12}\sigma_{21})^{k/2}$ (for even $k$) or
$\sigma_{21}(\sigma_{12}\sigma_{21})^{(k-1)/2}$ (for odd $k$). They
are shown along with their reduced OU forms, the Cinnamon Roll
tangles $\CR_k$, in Figure~\ref{fig:CinnamonRolls}. Clearly,
$\sigma_{21}\mid \CR_{2k+1}$ with $\sigma_{21}^{-1}\CR_{2k+1}=\CR_{2k}$
and $\sigma_{12}\mid \CR_{2k}$ with $\sigma_{12}^{-1}\CR_{2k}=\CR_{2k-1}$,
and so we have the following chain of divisibilities and quotients:
\begin{equation} \label{eq:CinnamonRolls}
   \xymatrix{
    \cdots \ar[r] &
    \CR_4 \ar[r]^{\sigma_{12}} &
    \CR_3 \ar[r]^{\sigma_{21}} &
    \CR_2 \ar[r]^{\sigma_{12}} &
    \CR_1 \ar[r]^{\sigma_{21}} &
    \CR_0.
  }
\end{equation}
\end{example}

\begin{figure}
\[
  \input{figs/CinnamonRolls.pdf_t}\qquad
  \raisebox{8mm}{\includegraphics[height=0.75in]{CinnamonRoll.pdf}}
\]
\caption{
  The 3-twist, 4-twist, and 5-twist braids, and their reduced OU forms the
  Cinnamon Roll tangles $\CR_3$, $\CR_4$, and $\CR_5$. The equivalence
  of the twist braids with their respective cinnamon rolls should
  be clear to anyone who has observed how a kink in a band becomes a
  twisted band upon tugging. The bonus cinnamon roll was purchased from
  \url{https://thenounproject.com/}.
} \label{fig:CinnamonRolls}
\end{figure}

\begin{example} \label{exa:SCR} A slashed cinnamon roll is a cinnamon roll with an
extra always-over strand separating the O-parts of its two curving strands, as shown
in (A) of Figure~\ref{fig:SCR}. A slashed cinnamon roll
is divisible by both $\sigma_{21}^{-1}$ and $\sigma_{23}$, and
the quotients, after reductions by many R2 moves, are (B) and (C) of
Figure~\ref{fig:SCR}. These quotients are themselves cinnamon rolls
(with extras on the side), and so they can be divided and reduced further as
in Example~\ref{exa:CinnamonRolls}, leading to (D) and (E)
of Figure~\ref{fig:SCR}. Note also that (D)
can be reduced to (E) by dividing
first by $\sigma_{23}$ and then by $\sigma_{12}$, as shown.
Finally, note that we have two paths going from (A) to (E), via (B)
and (D) and via (C), and that each defines a braid word by reading the
divisors along it. We claim that these two braid words are equal in
$\vcalPB_3$. Namely, that
\begin{equation} \label{eq:SCRBraids1}
   \sigma_{21}^{-1}\sigma_{13}\sigma_{31}\sigma_{13}\sigma_{31}\sigma_{13}\sigma_{23}\sigma_{21}
  = \sigma_{23}\sigma_{13}\sigma_{31}\sigma_{13}\sigma_{31}\sigma_{13}.
\end{equation}
Indeed, to see the equality, slide strand 2 across the 5-twist
in the following picture\footnote{The equality also follows from
Chterental's Theorem (\ref{thm:vinj}), but we haven't proven Chterental's Theorem
yet, and in fact, the proof of Chterental's Theorem depends on the equality.}:
\[ \input{figs/SCRBraids.pdf_t}. \]
\end{example}

\begin{figure}
\[ \def\s#1{$\sigma_{#1}$} \def\sb#1{$\sigma_{#1}^{-1}$}
  \input{figs/SCR.pdf_t}
\]
\caption{A slashed cinnamon roll and its quotients down to the identity.} \label{fig:SCR}
\end{figure}

\begin{discussion} \label{disc:divquo} Next, we would like to understand
precisely when does a braid generator $\sigma_{ij}$ divide a reduced virtual
OU tangle $T$, and what is the quotient $\sigma_{ij}^{-1}T$, as a
reduced OU tangle. This is done in Figure~\ref{fig:divquo}. In (A)
of that figure we display $\sigma_{ij}^{-1}$ at the bottom and $T$ at
the top. $T$ could be complicated, but it turns out we only care about
what it looks like near the O part of strand $j$\footnote{``Near'' in
a combinatorial sense, meaning ``one or two crossings away from''. Not
in any metric sense, of course.}. So in (A) we also display strand $i$
just to remember that it exists, and the O part of strand $j$, up to its
transition point the $\bowtie$. In that part strand $j$ crosses over
a number of other strands, or over its own U part, or $i$'s U part,
and perhaps with multiplicity. We summarize that by showing only two
strands passing under, with no care for their identity or orientation.

\begin{figure}
\[
  \def\i{$i$} \def\j{$j$} \def\g{$\gamma$} \def\vp{$\vdots p$} \def\s{$\longrightarrow\atop\sigma_{ij}$}
  \input{figs/divquo.pdf_t}
\]
\caption{Everything we need to know about divisibility and quotients.}
\label{fig:divquo}
\end{figure}

In (B) of Figure~\ref{fig:divquo} we attach $\sigma_{ij}^{-1}T$ to
$T$. The result is typically not OU and not reduced. In (C) we glide
the part where $i$ goes over $j$ past the $\bowtie$, to make the result
OU. We indicate the part of strand $i$ that got moved,
from one $\bullet$ to the other, by $\gamma$ and note that $\gamma$ has a natural
mid-point, indicated with a $\circ$. Note that the tangle in (C) might
not be reduced! That would be the case if as in (D), strand $i$ was to
follow $\gamma$ (backwards) at least a part of the way. For had this
been the case, the OU form of $\sigma_{ij}^{-1}T$ would look like in
(E), and would be reducible to (F) by R2 moves.

Ergo we care to know precisely how far backwards along $\gamma$ strand
$i$ follows, and when it deviates, precisely how. Four options for the
behaviour of $i$ are shown in the lower half of Figure~\ref{fig:divquo}:
The option ``before middle inward'', (bmi), means that $i$ traces along
$\gamma$ to before its mid-point, and then deviates by reaching its own
transition point $\bowtie$ and turning inwards, to cross under $j$. In
Figure~\ref{fig:divquo} we show both $T$ and the reduced OU form of
$\sigma_{ij}^{-1}T$ for option (bmi). If in $T$ there are $p$ further
strands passing under $j$ after the deviation point, it is easy to see
that $\sigma_{ij}^{-1}T$ gains $2p+2>0$ crossings over $T$. This is
indicated at the bottom of the (bmi) part of Figure~\ref{fig:divquo}.

The remaining three options for $i$ are shown in Figure~\ref{fig:divquo}
following the same pattern. In option (bmo) strand $i$ deviates from
$\gamma$ before the mid-point and turns outwards, into parts of $T$
we don't display. Here again $\xi(\sigma_{ij}^{-1}T)>\xi(T)$, with a
gain of $2p+1$. In option (ami) strand $i$ follows $\gamma$ past the
mid-point and turns inwards, and in (amo) it turns outwards. In the
last two cases $\sigma_{ij}^{-1}T$ loses crossings relative to $T$,
with the precise losses as indicated.

We leave it to the reader to verify that the four options (bmi), (bmo),
(ami), and (amo) are mutually exclusive and complete, and that in all
cases, if $T$ is reduced to start with, then $\sigma_{ij}^{-1}T$ as shown
in Figure~\ref{fig:divquo} is again reduced\footnotemark.
%
\footnotetext{In short, if $T$ is reduced and $T'$ is obtained from
it by adding and/or removing a number of crossings, when is $T'$
non-reduced? If an R1 or an R2 got added, or if a crossing got added
which along with an existing crossing creates an R2, or if crossings
are removed between a pair of existing or newly added crossings so as
to remove the separation between them and turn them into an R2 pair,
or if crossings are removed along a kink to create an R1. One must inspect
that none of these possibilities can occur here.}

Finally we note that we could repeat the whole discussion
for $\sigma_{ij}T$, and everything would be the same,
with only a left-right reflection of all the tangles in
Figure~\ref{fig:divquo}. \endpar{\ref{disc:divquo}}
\end{discussion}

Discussion~\ref{disc:divquo} proves the following lemma, which summarizes it:

\begin{lemma}[Division] \label{lem:divquo} Let $g=\sigma_{ij}^{\pm 1}$ be a generator of $\vcalPB_n$ and $T$
be a reduced virtual OU tangle.
\begin{enumerate}[leftmargin=*,labelindent=0pt]
\item $\xi(gT)$ is never equal to $\xi(T)$, so
  always, either $g^{-1}\mid T$ or $g\mid gT$.
\item $\sigma_{ij}|T$ if and only if $i$ is parallel\,\footnotemark\ to $j$
  on its left to its transition point $\bowtie$, and then immediately
  crosses over $j$ in a positive crossing, as in (ami) and (amo) of
  Figure~\ref{fig:divquo}. Similarly for $\sigma_{ij}^{-1}\mid T$, with
  ``left'' replaced with ``right'' and ``positive'' with ``negative''.
\item If indeed $g\mid T$, the quotient
  $g^{-1}T$ is determined by how far $i$ pushes backwards
  on the other side of $j$, past the point where it crosses over $j$,
  and by whether it turns ``in'' or ``out'' after that. \qed
\end{enumerate} \end{lemma}
%
\footnotetext{\label{foot:parallel}%
Note that we are in topology /
combinatorics, not in geometry, so ``$i$ is left-parallel to $j$''
means ``anything $j$ does $i$ does in tandem'', and not ``$i$ and $j$
maintain a constant distance between them''. More precisely, ``$i$
is left-parallel to $j$'' means ``any strand that crosses under $j$
in a positive crossing then crosses under $i$ in a positive crossing
(with no other crossings in between), any strand that crosses under $j$
in a negative crossings crossed under $i$ right before in a negative crossing
(with no other crossings in between), and $i$ and $j$ encounter those
pairs of crossings in the same order''.}
%It is a mouthful, and we will not repeat it.}

For the continuation of the proof of Chterental's Theorem (\ref{thm:vinj}) we
will need the Diamond Lemma. For completeness we provide a full
formulation and a proof.  While it is well-known~\cite{Bergman:Diamond,
Sapir:CombinatorialAlgebra, Smolka:Confluence}, we were not able to find
a simple exposition in a language sufficiently similar to ours.

\begin{definition} \label{def:diamond}
A binary relation $\to$ defined on a set $\calX$
is called Noetherian if there are no infinite sequences $(x_i)\in\calX$
such that $x_1\to x_2\to\ldots$ (in particular, never $x\to x$,
for $x\in\calX$). The ``transitive closure'' of $\to$, denoted
$\toto$, is the binary relation on $\calX$ defined by
\[ (x\toto y)
  \quad\Longleftrightarrow\quad
  (\exists x_0,\ldots,x_n\in\calX\text{ such that }x=x_0\to x_1\to\ldots\to x_n=y).
\]

\Needspace{17mm} % 16mm is not enough.
\parpic[r]{\input{figs/diamond.pdf_t}}
\noindent It is clear that $\toto$ is transitive and taking $n=0$ we see that it
is reflexive. A non-empty subset $\calY$ of $\calX$ is called connected
if whenever $y\in \calY$ and $x\in\calX$ satisfies $x\to y$ or $y\to x$,
then $x\in \calY$. We say that $\to$ satisfies the diamond condition
if for every $a,b,c\in\calX$ such that $a\to b$ and $a\to c$, there is
some $d\in\calX$ such that $b\toto d$ and $c\toto d$ (``every wedge can be completed to a diamond'', as on the right).
\end{definition}

\begin{lemma} \label{lem:diamond} (The Diamond Lemma,
\cite{Newman:DiamondLemma}) If a Noetherian relation $\to$ on a set
$\calX$ satisfies the diamond condition then every connected subset
$\calY\subset\calX$ has a unique final element. Namely, there is a
unique $f\in \calY$ such that for every $y\in \calY$, $y\toto f$.
\end{lemma}

\noindent{\it Proof.} If $t\in\calZ\subset\calX$, we say that $t$ is
$\calZ$-terminal if there is no $z\in\calZ$ with $t\to z$. By
the Noetherian property, every non-empty $\calZ$ has a terminal element
(perhaps many). Set
\[ \calG\coloneqq
  \{x\in \calX\colon\text{there is a {\em unique} $\calX$-terminal $\tau(x)$ such that $x\toto \tau(x)$}\}.
\]
Clearly if $x\in\calG$ and $x\toto y$, then $y\in\calG$ and
$\tau(x)=\tau(y)$ (*). If $\calB\coloneqq\calX\setminus\calG$ is
non-empty, pick some $\calB$-terminal element $a\in\calB$. If $b,c\in\calX$ and $a\to b$
and $a\to c$, find $d$ such that $b\toto d$ and $c\toto d$. As $a$ is
$\calB$-terminal, $b,c,d\in\calG$ so by (*) $\tau(b)=\tau(d)=\tau(c)$.
Hence all the followers $b$ of $a$ have the same $\tau(b)$, and hence
$a\in\calG$ with $\tau(a)=\tau(\text{any follower})$ (if $a$ has no
followers take $\tau(a)=a$). But this contradicts $a\in\calB$, so $\calB$
is empty and $\calG=\calX$.

Now if $x,y\in\calX$ and $x\to y$ then $\tau(x)=\tau(y)$, so by connectivity
$\tau$ is constant on $\calY$. Call that constant $f$. \qed

\begin{definition} Let $\calX_n=\vcalPB_n\times\vcalROU_n$. We define a binary relation $\to$ on $\calX_n$ as follows
\begin{eqnarray*}
  (\beta_1,T_1)\to(\beta_2,T_2)
  & \Longleftrightarrow &
  \text{for some }g=\sigma_{ij}^{\pm 1}:\ g\mid T_1,\ T_2=g^{-1}T_1, \text{ and }\beta_2=\beta_1g \\
  & \Longleftrightarrow &
  \text{for some }g=\sigma_{ij}^{\pm 1}:\ \xi(T_2)<\xi(T_1),\  T_2=g^{-1}T_1, \text{ and }\beta_2=\beta_1g.
\end{eqnarray*}
\end{definition}

\begin{example} With a bit of thought, four examples of elements (A),
(B), (C), and (D) of $\calX_3$, in fact of $\calPB_3\times\calROU_3$, can
be seen in Figure~\ref{fig:stirring}. Precisely, the ``whisk'' part of
each of the figures is the braid part $\beta$, and the ``parsley'' part
becomes an OU tangle if the whisk is replaced by a straight ``identity''
whisk as in image (D). These elements are related in the opposite manner
to the figure: (D)$\to$(C)$\to$(B)$\to$(A).
\end{example}

\begin{discussion} \label{disc:to}
Note that if $(\beta_1,T_1)\to(\beta_2,T_2)$ then $\beta_1T_1=\beta_2T_2$
and $T_2$ is ``simpler'' than $T_1$. Thus ``flowing with $\to$''
agrees with our plan from Discussion~\ref{disc:plan}.

Note also that if $(\beta_1,T_1)\to(\beta_2,T_2)$ then $\beta_2$
and $T_2$ are determined by $\beta_1$ and $T_1$ and a single
generator $g$ of $\vcalPB_n$, which we can mark atop the $\to$ symbol as
$(\beta_1,T_1)\overset{g}{\longrightarrow}(\beta_2,T_2)$.  With this in
mind, a $\toto$-relation in $\calX_n$, meaning a $\to$-chain, is determined by a pair
\[ \left(
  \beta_0,
  \xymatrix{T_0 \ar[r]^{g_0} & T_1 \ar[r]^{g_1} & T_2 \ar[r]^{g_2} & \cdots \ar[r]^{g_{m-1}} & T_m}
\right) \]
where $\beta_0$ is a virtual braid, and where each $g_k$ is a generator of $\vcalPB_n$ and for every $k$,
$g_k\mid T_k$ and $T_{k+1}=g_k^{-1}T_k$. The $\to$-chain corresponding to such a pair is
\[ \xymatrix{
  (\beta_0,T_0) \ar[r]^<>(0.5){g_0} &
  (\beta_0g_0,T_1) \ar[r]^<>(0.5){g_1} &
  (\beta_0g_0g_1,T_2) \ar[r]^<>(0.5){g_2} &
  \cdots \ar[r]^<>(0.5){g_{m-1}}
  & (\beta_0\prod g_k,T_m)
} \]
An example with $\beta_0$ suppressed is in Example~\ref{exa:CinnamonRolls}. It can be completed by choosing
$\beta_0$ arbitrarily.

Finally, note that a diamond in $\calX_n$ is determined a single virtual
braid $\beta_0$ and two chains as above with a shared initial tangle,
\begin{equation} \label{eq:DiamondInX}
  \xymatrix@R=0mm@C=14mm{
    & T_1 \ar[r]^{g_1} & T_2 \ar[r]^{g_2} & \cdots \ar[r]^{g_{m-2}} & T_{m-1} \ar[rd]^<>(0.5){g_{m-1}} & \\
    T_0=T'_0 \ar[ur]^<>(0.5){g_0} \ar[dr]^<>(0.5){g'_0} & & & & & T_m=T'_{m'}, \\
    & T'_1 \ar[r]^{g'_1} & T'_2 \ar[r]^{g'_2} & \cdots \ar[r]^{g'_{m'-2}} & T'_{m'-1} \ar[ur]^<>(0.5){g'_{m'-1}} &
  }
\end{equation}
with the additional requirement that $\prod g_k=\prod g'_k$ in $\vcalPB_n$
(which also implies that the chains share their end tangles). An example
of such a diamond, with the initial $\beta_0$ suppressed, is in
Figure~\ref{fig:SCR}. \endpar{\ref{disc:to}}
\end{discussion}

\begin{lemma} The relation $\to$ satisfies the conditions of the Diamond Lemma.
\end{lemma}

\noindent{\it Proof.} As crossing numbers are always finite and $\to$
decreases the crossing number of the tangle part, $\to$ is Noetherian. To
verify the diamond condition we must start with a reduced OU tangle $T_0=T$
and two generators $g_0$ and $g'_0$ that divide it, and ``complete
a diamond'' as in Equation~\eqref{eq:DiamondInX}. Let us start with the
hardest case.

\Needspace{25mm} % 24mm is not enough.
\parpic[r]{\def\i{$i$} \def\j{$j$} \def\k{$k$}
  \input{figs/CaseHBase.pdf_t}
}
\noindent{\it Case 1. For some $i,j,k$, $\sigma_{ji}^{-1}\mid T$ and
$\sigma_{jk}\mid T$.} By (2) of the Division Lemma (\ref{lem:divquo}),
strand $j$ must be left-parallel to strand $k$ to $k$'s $\bowtie$ and
right-parallel to strand $i$ to $i$'s $\bowtie$. So the tangle $T$ must
contain a part as on the right, with the two grey bands representing any
number $w_1$ and $w_2$ of further strands. (Two options for $T$ are shown
and we will treat only the first, as the second is mirror image thereof).

In order to complete a diamond, we need to know the quotients
$\sigma_{ji}T$ and $\sigma_{jk}^{-1}T$. By (3) of the Division Lemma
(\ref{lem:divquo}), this gets complicated if $j$ continues as a right
parallel of $k$ and as a left parallel of $i$.

\Needspace{18mm} %17mm is not enough.
\parpic[r]{\def\i{$i$} \def\j{$j$} \def\k{$k$}
  \input{figs/pipk.pdf_t}
}
Sayeth you: ``That's impossible! One can't be to the left of $i$ and also to
the right of $k$!''. But unfortunately, it's the topological / combinatorial
``left'' and ``right'' that concern us here and the impossible is
actually possible. As indicated in Footnote~\ref{foot:parallel}, ``$j$
is right-parallel to $k$'' (to a point) just means that some number
$p_k\geq 0$ of strands that cross under $k$ then proceed to cross under
$j$, in the same order. As in the figure on the right, this can be drawn
while keeping $j$ straight and making the $p_k$ under-strands curve into
semi-circles. Similarly, ``$j$ is left-parallel to $i$'' (to a point)
means, as in the figure, that some number $p_i\geq 0$ of arcs cross
under both $i$ and $j$ in the manner shown.

Unfortunately, there are many cases to check, depending on the relative
sizes of the widths $w_1$ and $w_2$, of the ``push-back numbers''
$p_i$ and $p_k$, and on whether, at the end, $j$ crosses under $i$,
or under $k$, or goes elsewhere, as in options (ami) and (amo) of
Figure~\ref{fig:divquo}. We will try to make it as painless as possible.

The ``base cases'' occur when
\begin{enumerate}
\item $w_2=0$, 
\item $|p_i-p_k|\leq 1$, 
\item  $w_1$ is as small as it can be given $p_i$, $p_k$, and $w_2$
  (meaning, $w_1=p_k$ assuming the first two conditions hold).
\item strand $j$ continues outward relative to both $i$ and $k$,
  as in option (amo) of Figure~\ref{fig:divquo}.
\end{enumerate}
There are then three possibilities: If $p_k=p_i+1$, we are looking
at a slashed cinnamon roll as in Figure~\ref{fig:SCR}, that figure
also shows how to complete the diamond, and the required braid
relation is Equation~\eqref{eq:SCRBraids1}.  The cases $p_k=p_i$
and $p_k=p_i-1$ correspond to slashed cinnamon rolls rolled slightly
differently and are shown as (A) and (B) of Figure~\ref{fig:Cases23},
along with the corresponding diamonds and braids relations. Note
that in all of these cases the length of the ``twist sequence''
$\sigma_{ik}\sigma_{ki}\sigma_{ik}\cdots$ is $p_k+1$, so these diamonds
can be be arbitrarily long.

\begin{figure}
\[ \def\i{$i$} \def\j{$j$} \def\k{$k$}
  \def\s#1{$\sigma_{#1}$} \def\sb#1{$\sigma_{#1}^{-1}$}
  \input{figs/Cases23.pdf_t}
\]
\caption{Two other slashed cinnamon rolls.}
\label{fig:Cases23}
\end{figure}

What if $w_1$ is bigger than the least it can be given the other
parameters (which are otherwise unchanged)? That adds a band of strands at the bottom, as in (A) of
Figure~\ref{fig:WhatIfs}. This band gets added in the same way everywhere
else in Figures~\ref{fig:SCR} and~\ref{fig:Cases23}, with no change to
the resulting diamonds.

\begin{figure}
\[ \def\i{$i$} \def\j{$j$} \def\k{$k$}
  \input{figs/WhatIfs.pdf_t}
\]
\caption{The what ifs.}
\label{fig:WhatIfs}
\end{figure}

What if $p_i>p_k+1$ (yet respecting the other constraints)? This adds and extra band of strands as in (B)
of Figure~\ref{fig:WhatIfs}. These bands get tugged along through
the processes of Figure~\ref{fig:Cases23} with no changes to the end
results. A similar thing happens if $p_k>p_i+1$.

What if $w_2>0$ and $p_1=p_k$ are multiples of $w_2+1$? Then we are
in (C) of Figure~\ref{fig:WhatIfs}, and the slashed cinnamon roll has
a band of width $w_2$ of extra filling! One may check that the extra
filling unwinds along with the rest as in Figure~\ref{fig:Cases23}
with no change to the diamonds. There are similar ``filled'' versions
of the other base cases.

What if $w_2>0$ and $p_1=p_k$ are not round multiples of $w_2+1$? Then
we are in a situation like (D), which is a combination of previous cases,
and the same conclusions apply.

What if we are in an (ami) case instead of (amo)? We are in a situation
like in (E), and the same comments apply as for (C). We made $j$ dotted in
(E), to make the similarity with (C) easier to see.

What if several of the what ifs are combined? Then some combination of
(A)-(E) of Figure~\ref{fig:WhatIfs} applies, and we leave it to the reader
to verify that in all cases, diamonds complete as in Figures~\ref{fig:SCR}
and~\ref{fig:Cases23}.

\noindent{\it Case 2. For some $i,j,k$, $\sigma_{ij}\mid T$
and $\sigma_{jk}\mid T$.} By (2) of the Division Lemma (\ref{lem:divquo}),
strand $i$ must be a left-parallel of $j$ and then cross over it,
and $j$ must be a left-parallel of $k$ and then cross over it, as
shown in Figure~\ref{fig:CaseM}, along with the completion of the
wedge into a diamond. In that figure we took option (amo) for both
divisibilities. Option (ami) is possible only for the $\sigma_{ij}\mid T$
divisibility, and makes little difference to the resulting diamond.

\begin{figure}
\[ \def\i{$i$} \def\j{$j$} \def\k{$k$} \def\s#1{$\sigma_{#1}$}
  \input{figs/CaseM.pdf_t}
\]
\caption{Case 2 and the resulting diamond.} \label{fig:CaseM}
\end{figure}

\noindent{\it Case 3. For some $i,j,k$, $\sigma_{ij}^{-1}\mid T$
and $\sigma_{jk}^{-1}\mid T$.} That's the same as Case~2, with left interchanged with right.

\noindent{\it Case 4. For some distinct $i,j,k,l$, $\sigma_{ij}^{s_1}\mid
T$ and $\sigma_{kl}^{s_2}\mid T$, where $s_1,s_2\in\{\pm 1\}$.} In this
case division by $\sigma_{ij}^{s_1}$ commutes with division by $\sigma_{kl}^{s_2}$,
and the resulting diamond is a square, as in Figure~\ref{fig:Square}.

\begin{figure}
% This once was a parpic: \Needspace{27mm} % 26mm is not enough.
\[ \xymatrix@R=0mm@C=25mm{
  & \sigma_{ij}^{-s_1}T \ar[rd]^<>(0.5){\sigma_{kl}^{s_2}} & \\
  T \ar[ru]^<>(0.5){\sigma_{ij}^{s_1}} \ar[rd]_<>(0.5){\sigma_{kl}^{s_2}} & & \sigma_{kl}^{-s_2}\sigma_{ij}^{-s_1}T \\
  & \sigma_{kl}^{-s_2}T \ar[ru]_<>(0.5){\sigma_{ij}^{s_1}} &
} \]
\caption{The diamond for case 4.} \label{fig:Square}
\end{figure}

\noindent{\it There are no further cases to check.} If two generators
divide $T$, they involve at most 4 strands, and if they involve
exactly 4 strands, that's Case~4. The Division Lemma (\ref{lem:divquo}) excludes the
possibility that the two generators involve only two strands --- namely,
that they are two of $\{\sigma_{ij}^{\pm 1},\sigma_{ji}^{\pm 1}\}$. It
also excludes the remaining 3-strand cases: namely, that they are $\{\sigma_{ij},\sigma_{ik}\}$,
$\{\sigma_{ik},\sigma_{jk}\}$, $\{\sigma_{ij}^{-1},\sigma_{ik}^{-1}\}$, 
$\{\sigma_{ik}^{-1},\sigma_{jk}^{-1}\}$, $\{\sigma_{ij},\sigma_{jk}^{-1}\}$, $\{\sigma_{ij}^{-1},\sigma_{jk}\}$,
or $\{\sigma_{ij},\sigma_{kj}^{-1}\}$. Each of these exclusions requires a short argument, and we provide only the
argument for the first one. Indeed if both $\sigma_{ij}\mid T$ and $\sigma_{ik}\mid T$, then by
the Division Lemma strand $i$ is a
left parallel of both the O part of $j$ (call it $O_j$) and the O part
of $k$ (call it $O_k$), showing that at least one of $O_j$ and $O_k$ is
empty. Without loss of generality, it is $O_j$. But then the $i$ over $j$
crossing that the Division Lemma guarantees is the first crossing on
both $i$ and $j$, leaving no room for $O_k$ to be a right parallel of
a part of $i$, unless $O_k$ is also empty. But then the first crossing
on $i$ is both over $j$ and over $k$, which is impossible. \qed

\vskip 2mm
\noindent{\it Proof of Chterental's Theorem (\ref{thm:vinj}).} We have shown
that $\calX_n=\vcalPB_n\times\vcalROU_n$ with the relation $\to$
satisfies the conditions of the Diamond Lemma. Let
$f\colon\calX_n\to\calX_n$ be the function guaranteed by the Diamond
Lemma, mapping every element to the unique final element in its connected
component.

Let $I$ denote both the the 0-crossing pure virtual braid on $n$
strands (the identity element of $\vcalPB_n$) and the 0-crossing
OU tangle on $n$ strands. By (1) of the Division Lemma (\ref{lem:divquo}), if
$\beta',\beta''\in\vcalPB_n$ are virtual braids and $g=\sigma_{ij}^{\pm
1}$ is a generator of $\vcalPB_n$ then
\begin{align*}
  \text{either}\qquad &
  (\beta'g,\Ch(\beta'')) \to (\beta',g\Ch(\beta'')) = (\beta',\Ch(g\beta'')) &
  \qquad\text{if }g^{-1}\mid\Ch(\beta'') \\
  \text{or}\qquad &
  (\beta',\Ch(g\beta'')) = (\beta',g\Ch(\beta'')) \to (\beta'g,\Ch(\beta'')) &
  \qquad\text{if }g\mid g\Ch(\beta''),
\end{align*}
and so by induction on the length of a presentation of
$\beta\in\vcalPB_n$, $(\beta,I)$ and $(I,\Ch(\beta))$ are in the same
connected component of $\calX_n$. Hence $f(I,\Ch(\beta)) = f(\beta,I)
= (\beta,I)$, by the Diamond Lemma and as $\xi(I)=0$ implies that
$(\beta,I)$ is final.

Now if $\Ch(\beta_1)=\Ch(\beta_2)$ then
\[ (\beta_1,I) = f(\beta_1,I) = f(I,\Ch(\beta_1)) = f(I,\Ch(\beta_2)) = f(\beta_2,I) = (\beta_2,I), \]
so $\beta_1=\beta_2$, proving the injectivity of $\Ch$.

Note also that we learned that for every $\beta\in\vcalPB_n$,
$(I,\Ch(\beta))\toto(\beta,I)$, and in particular, $\Ch(\beta)$
must be divisible by at least one generator of $\vcalPB_n$. But
Example~\ref{exa:indivisible} exhibits a virtual OU tangle $T_2$ that
is not divisible by any generator, and hence $\Ch$ is not surjective. \qed