{ \def\face{\input{figs/face.pdf_t}} \def\human{\input{figs/human.pdf_t}} \def\machine{\input{figs/machine.pdf_t}} \def\cellscale{1} \newsavebox\pdfbox \newlength{\pdfheight} \def\nbpdfInput#1{{% \savebox{\pdfbox}{\includegraphics[scale=\cellscale]{#1}}% \settoheight{\pdfheight}{\usebox{\pdfbox}}% %\uselengthunit{mm}\printlength{\pdfheight}% \noindent\imagetop{\ifdim\pdfheight<10mm\face\else\human\fi}\ % \imagetop{\usebox{\pdfbox}}% \vskip 2mm% }} \def\nbpdfOutput#1{{\noindent{\imagetop{\machine}\ \imagetop{\includegraphics[scale=\cellscale]{#1}}\vskip 2mm}}} \def\m#1{\text{\tt #1}} \section{Some Computations} \label{sec:comp} We believe in implementing as much as possible. Actually, we hardly believe ourselves unless we implement. All code here is written in {\sl Mathematica}~\cite{Wolfram:Mathematica} and is available as the {\sl Mathematica} notebook {\sl SomeComputations.nb} at~\cite{Self}. \parpic[r]{\input{figs/VDExample.pdf_t}} \subsection{Implementing virtual OU tangles, virtual braids, and $\Ch$} To represent a virtual tangle diagram $D$ on the computer, we order its strands and traverse each of them in order, marking each ``O'' point, each ``U'' point, and each end of strand, with the integers $1,2,3,\ldots$, in the order in which they are encountered. See examples on the right. For each crossing $x$ of $D$ we form a {\sl Mathematica} expression $\m{X}_s[i,j]$, where $s$ is the sign of the crossing and $i$ and $j$ are the markings next to the O side and the U side of $x$, respectively. We also form an expression $\m{EOS}[k]$ for each end-of-strand marked $k$. We toss all this information into a container \m{VD}, and the result is our computer representation of $D$. Below, \m{vd1} and \m{vd2} are the results of this process for the two example tangles shown here. \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/1.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/2.pdf} Sometimes in a \m{VD} we allow to label O/U/\m{EOS} points by arbitrary real numbers, for in fact, only the ordering of these points matter. The routine \m{Tidy} takes a real-ordered \m{VD} and converts it to a sequentially ordered one. Thus it brings a \m{VD} to a ``canonical form'': \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/3.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/4.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/5.pdf} The routine \m{R12Reduce1} reduces a virtual diagram by performing one R2 or R1 move, if such a move is available, and otherwise it does nothing. The routine \m{R12Reduce} finds the fixed point of \m{R12Reduce1} --- in other words, it reduces a virtual diagram using all available R1 and R2 moves. \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/6.pdf} Here's a very minor example: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/7.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/8.pdf} \Needspace{30mm} % 29mm is not enough. \parpic[r]{ \def\Xa{$\m{X}_{s_1}[i_1,j_1]$} \def\Xb{$\m{X}_{s_2}[i_2,j_2]$} \def\Xc{$\m{X}_{s_2}[j_1,j_2]$} \def\Xd{$\m{X}_{s_1}[i_1,i_2]$} \def\Xe{$\m{X}_{s_1s_2}[i_1\!-\!s_1/3,j_2\!+\!s_2/3]$} \def\Xf{$\m{X}_{-s_1s_2}[i_1\!+\!s_1/3,j_2\!-\!s_2/3]$} \input{figs/Gamma1.pdf_t}} In a similar manner, \m{$\Gamma$1} performs one glide move if one is available, and \m{$\barGamma$} fully reduces under both glide moves and R1 and R2 moves. Here we bound the number of iterations by $2^{24}$, to artificially stop runaway reductions such as the one in Figure~\ref{fig:swirls}. \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/9.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/10.pdf} As expected, $\barGamma(\m{vd1})=\m{vd2}$: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/11.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/12.pdf} Next we define the composition operation \m{d1**d2} of virtual tangle diagrams. The implementation works by ``shrinking'' \m{d2} so that each of its strands would fit between the last crossing in the corresponding strand of \m{d1} and the \m{EOS} at the end of that strand of \m{d1}, then taking the union of \m{d1} and the shrank \m{d2}, and then applying \m{Tidy} to the result: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/13.pdf} For example, ``our'' \m{vd2} has $3$ crossings yet is equivalent to a 2-twist braid. So $\m{vd1}\cdot\m{vd2}$ ought to have $6$ crossings while its reduced OU form, $\barGamma(\m{vd1}\cdot\m{vd2})$ should be the Cinnamon Roll $\CR_4$, which has $7$ crossings. The computer agrees: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/14.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/15.pdf} Next we implement virtual pure braids, and it is best to start with an example. We represent the 3-strand virtual pure braid $\beta=\sigma_{21}^{-1}\sigma_{13}\sigma_{31}\sigma_{13}\sigma_{31}\sigma_{13}\sigma_{23}\sigma_{21}$ of Example~\ref{exa:SCR} by the {\sl Mathematica} expression below: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/16.pdf} The conversion of \m{VPB}s into \m{VD}s is quite easy. We just need to define it on the generators and then use the already-available composition of \m{VD}s to extend the definition to products of generators: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/17.pdf} We can compute $\Ch(\beta)=\barGamma_v(\bariota_v(\beta))$ (count that it has 18 \m{X} symbols, just as Figure~\ref{fig:SCR}~(A) has 18 crossings!): \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/18.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/19.pdf} We can even verify Equation~\eqref{eq:SCRBraids1}: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/20.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/21.pdf} \subsection{Tabulating Virtual Pure Braids} Our next task is to tabulate virtual pure braids with a given number of strands $n$ and a bound $m$ on the number of crossings. The first routine, \m{VPBGens}, outputs the list of all generators of $\vcalPB_n$: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/22.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/23.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/24.pdf} Next we'd like to generate all words in the generators we just computed, and separate them using $\Ch$ and Chterental's Theorem (\ref{thm:vinj}). To save some computer effort, we generate only ``proud'' words --- words that do not contain a letter followed by its inverse, or adjacent commuting letters that are not in lexicographic order. The ``Proud Followers'' \m{PF} of a generator are those generators that can follow it without ruining the pride of a word: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/25.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/26.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/27.pdf} And then $\m{PVPBDs}[n,m]$ computes all Proud Virtual Pure Braid Diagrams on $n$ strands and with $m$ crossings: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/28.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/29.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/30.pdf} These sets grow very rapidly: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/31.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/32.pdf} $\m {AllVPBs}[n, m] $ finds representatives for all virtual braids on $n$ strands with at most $m$ crossings, by using $\m{PVPBDs}[n,m]$ and then deleting duplicates by $\barGamma_v$: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/33.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/34.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/35.pdf} There are 15,156 virtual pure braids with 3 strands and precisely 4 crossings (meaning, braids in $\m {AllVPBs}[3,4] $ but excluding those in $\m {AllVPBs}[3,3]$). It took our computer about 86 seconds to figure that out: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/36.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/37.pdf} \Needspace{65mm} % 64mm is not enough. \parpic[r]{\setlength{\tabcolsep}{3pt}\begin{tabular}{|c|c|c|c|c|c|} \hline $m\backslash n$ & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 4 & 12 & 24 & 40 & 60 \\ 2 & 12 & 132 & 504 & 1,320 & 2,820 \\ 3 & 36 & 1,416 & 10,344 & 41,760 & 124,140 \\ 4 & 108 & 15,156 & 211,416 & 1,308,360 & 5,357,700 \\ 5 & 324 & 162,156 & 4,317,912 & & \\ 6 & 972 & 1,734,864 & & & \\ \hline \end{tabular}} In our spare time we have tabulated the numbers of $n$-strand pure virtual braids with precisely $m$ crossings for some small values of $n$ and $m$. The results are on the right, and data files containing the actual braids are at~\cite{Self}. As a test of the integrity of our programs we also computed most of the numbers in this table by generating all braid words and reducing modulo all relations\footnotemark. The numbers match. See the {\sl Mathematica} notebook {\sl VPBByGensAndRels.nb} at~\cite{Self}. % \footnotetext{Sometimes two braid words of length $m_1$ are related by a chain of relations that pass through words of length $m_2$, where $m_2>m_1$, and we do not know in advance a bound on $m_2$. Hence the computation using generators and relations is slow (as we have to raise $m_2$ and the number of words to consider grows very big) and unreliable (strictly speaking, we only get upper bounds on the braid counts).} \subsection{Tabulating Classical Braids} It is a bit odd that we have not seen a table such as the one above, but for classical braids. As the classical braid group is automatic~\cite{Epstein:WordProcessing} and hence the word problem in it is very easy, there are much better in-theory tools than ours to produce such a table. Yet our tools are implemented in practice, and we may as well use them. First, we need to be able to convert from a standard classical braid notation~\cite{Bar-NatanMorrison:KnotTheory} to the \m{VPB} notation used here. \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/38.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/39.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/40.pdf} After that, we repeat the same steps as in the virtual case: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/41.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/42.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/43.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/44.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/45.pdf} For example, here are all the distinct positive 3-strand braids: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/46.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/47.pdf} On our computer, it takes about 20 seconds to find that there are 1,110 classical braids with 4 strands and crossing number equal to 5: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/48.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/49.pdf} \parpic[r]{\setlength{\tabcolsep}{3pt}\begin{tabular}{|c|c|c|c|c|c|} \hline $m\backslash n$ & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 6 & 8 & 10 \\ 2 & 2 & 12 & 26 & 44 & 66 \\ 3 & 2 & 30 & 98 & 206 & 362 \\ 4 & 2 & 68 & 338 & 884 & 1,794 \\ 5 & 2 & 148 & 1,110 & 3,600 & 8,370 \\ 6 & 2 & 314 & 3,542 & 14,198 & 37,606 \\ 7 & 2 & 656 & 11,098 & 54,876 & 164,910 \\ 8 & 2 & 1,356 & 34,362 & 209,348 & 711,746 \\ 9 & 2 & 2,782 & 105,546 & 791,798 & 3,039,546 \\ \hline \end{tabular}} And here's a table of the numbers of $n$-strand pure virtual braids with precisely $m$ crossings, for small values of $n$ and $m$. The data files containing the actual braids are at~\cite{Self}. Note that the entries in the $n=3$ column of this table fit with the sequence $6\cdot 2^m-2F_{m+3}-2$, where $F_m$ is the $m$th Fibonacci number: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/50.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/51.pdf} \picskip{0} The fit persists at least up to $m=12$. We do not know why this is so. \subsection{Extraction Graphs} \label{ssec:EG} We can now write a short program \m{EG}, to compute and display Extraction Graphs as in Discussion~\ref{disc:EG}. \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/52.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/53.pdf} Note that the diamond in Figure~\ref{fig:SCR} is genuine, but it is not an extraction graph, because the full extraction graph of the initial OU tangle of that figure contains two further edges: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/54.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/55.pdf} The braid below, suggested to us by B.~Wiest, has a linear extraction graph and hence a unique ``special word'' (see Discussion~\ref{disc:EG}), but that word is of length 13, whereas the braid can be presented by a shorter word $\beta$, of length 11: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/56.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/57.pdf} It is easy to see that the extraction graph of the 4-crossing 8-strand braid $\overcrossing\ \overcrossing\ \overcrossing\ \overcrossing$ is the tesseract: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/58.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/59.pdf} The extraction graphs of Garside braids seem to be permutahedra (we did not attempt to prove this in general): \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/60.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/61.pdf} Sometimes extraction graphs can be amusing. In no particular order, here are a lifesaver, an impressionistic map of the US state of Iowa, a torch flame, a legless bird, a feather, a ladder, a tennis racket, and a mouse trap: \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/62.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/63.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/64.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/65.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/66.pdf} We don't know what, if any, can be learned about braids from these graphs, and we can only hope the referee will forgive us for having a bit of fun. \subsection{Computational Complexity} \label{ssec:CC} Looking again at Figure~\ref{fig:divquo}~(C), we see that in the worst case, if the crossing number $\xi(T)$ of an OU tangle $T$ is $p$, the crossing number of the OU version of $\sigma_{ij}^{\pm 1}T$ might be as big as $3p+1$, and hence the complexity of computing $\Ch$ grows exponentially. Here are the ``worst'' classical and virtual braids with 8 crossings. A bit more is in the {\sl Mathematica} notebook {\sl TheWorstBraids.nb} at~\cite{Self}. \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/67.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/68.pdf} \noindent\nbpdfInput{nb2tex_pdfs/SomeComputations/69.pdf} \noindent\nbpdfOutput{nb2tex_pdfs/SomeComputations/70.pdf} }