\documentclass[aspectratio=169]{beamer}
%\documentclass[11pt]{article} \usepackage{beamerarticle,hyperref}
\usepackage{pgfpages,wrapfig,mathtools}
\geometry{paperwidth=154.3mm,paperheight=90mm} % Best for PDF Annotator, full screen on 16x9.
%\pgfpagesuselayout{2 on 1}[letterpaper,border shrink=0mm]
%\pgfpagesuselayout{4 on 1}[letterpaper,border shrink=0mm,landscape]
\pgfpagesuselayout{8 on 1}[letterpaper,border shrink=0mm]

%\usepackage[breaklinks=true]{hyperref}
\hypersetup{colorlinks,
  linkcolor={green!50!black},
  citecolor={green!50!black},
  urlcolor=blue
}

\def\blue{\color{blue}}
\def\green{\color{green}}
\def\red{\color{red}}

\def\bbN{{\mathbb N}}
\def\bbZ{{\mathbb Z}}

\def\qed{{\linebreak[1]\null\hfill\text{$\Box$}}}

\title{Yarn-Ball Knots}

\author{Dror Bar-Natan}

\institute{\url{http://drorbn.net/fi20}}

\date{The Fields Institute, November 2020}

\begin{document} \beamertemplatenavigationsymbolsempty

\begin{frame}
  %\titlepage
  \begin{center}
  \vfill
  \Large Yarn-Ball Knots
  \vfill
  \par\normalsize Dror Bar-Natan, \url{http://drorbn.net/fi20}
  \vfill
  \par\large The Fields Institute, November 2020
  \end{center}

  \vfill\normalsize
  {\bf Agenda.} Modest, off-topic, light conversation.

  \vskip 2mm
  {\bf Abstract.} Let there be scones! Our view of knot theory is biased in favour of pancakes.
  Technically, if $K$ is a 3D knot that fits in volume $V$ (assuming fixed-width yarn), then its projection to 2D will have about $V^{4/3}$ crossings. You'd expect genuinely 3D quantities associated with $K$ to be computable straight from a 3D presentation of $K$. Yet we can hardly ever circumvent this $V^{4/3}\gg V$ ``projection fee''. Exceptions probably include the hyperbolic volume and certainly include finite type invariants (as we shall prove). But knot polynomials and knot homologies seem to always pay the fee.
  \vfill
  If you can, please turn your video on! (And mic, whenever needed).
\end{frame}

\begin{frame}
Thanks for inviting me to the Fields Institute! As most of you have never been there, here's a picture of the lecture room:
\[ \includegraphics[width=\textwidth]{LectureRoom.jpg} \]
\end{frame}

\begin{frame}
  A recurring question in knot theory is ``do we have a 3D understanding of our invariant?''
  
  \begin{itemize}
  \item See Witten and the Jones polynomial.
  \item See Khovanov homology.
  \end{itemize}
  
  I'll talk about my perspective on the matter\ldots
\end{frame}

\begin{frame}
  \parbox[b]{0.49\textwidth}{
    We often think of knots as planar diagrams. 3-dimensionally, they are embedded in ``pancakes''.
    
    This matters when
    \begin{itemize}
    \item We make statements about ``random knots''.
    \item We figure out computational complexity.
    \end{itemize}
  }
  \hfill\parbox[b]{0.49\textwidth}{
    \includegraphics[width=\linewidth]{KinP.jpg}
    \par Knot by Lisa Piccirillo, pancake by DBN
  }
\end{frame}

\begin{frame} \begin{center}
  \includegraphics[width=\textwidth]{../../2020-10/20201025_170730.jpg}
  \newline Yarn ball courtesy of Heather Young
\end{center}\end{frame}

\begin{frame} \begin{center}
  \includegraphics[width=3.5in]{../../Projects/Agenda/figs/IceBreakers.jpg}
  \par ‘Connector’ by Alexandra Griess and Jorel Heid (Hamburg, Germany). Image from \href{http://www.waterfrontbia.com/ice-breakers-2019-presented-by-ports/}{www.waterfrontbia.com/ice-breakers-2019-presented-by-ports/}.
\end{center} \end{frame}

\begin{frame}
  \parbox[b]{0.5\textwidth}{
    $\displaystyle V\sim L^3$
    \vskip 8mm
    \par $\displaystyle n = \text{xing number} \sim L^2L^2=L^4=V^{4/3}$
    \vskip 8mm
    \par (``$\sim$'' means ``equal up to constant terms and $\log$ terms'')
  }
  %\hfill\includegraphics[width=0.48\textwidth]{YarnBallMeasurements.jpg}
  \hfill\resizebox{0.48\textwidth}{!}{\input{YarnBallMeasurements.pdf_t}}
\end{frame}

\begin{frame} \null
  {\bf Conversation Starter 1.} A knot invariant $\zeta$ is said to be Computationally 3D, or C3D, if
  \[ C_\zeta(3D,V)\ll C_\zeta(2D,V^{4/3}). \]

  This isn't a rigorous definition! It is time- and na\"ivet\'e-dependent! But there's room for less-stringent rigour in mathematics, and on a philosophical level, our definition means something.
\end{frame}

\begin{frame} \null
  {\bf Theorem 1.} Let $lk$ denote the linking number of a 2-component link. Then $C_{lk}(2D, n)=n$ while $C_{lk}(3D,V)=V$, so $lk$ is C3D!

  {\bf Proof.} WLOG, we are looking at a link in a grid, which we project as on the right:

  \null\hfill\includegraphics[width=0.38\textwidth]{4x4x4_Box.png}
  \hfill\includegraphics[width=0.45\textwidth]{4x4x4_Grid.png}\hfill\null

\end{frame}

\begin{frame} Here's what it look like, in the case of a knot:
  
  \vskip 8mm
  \includegraphics[width=0.49\textwidth]{Knot_in_3x3x3.png}
  \includegraphics[width=0.49\textwidth]{Knot_in_3x3x3_with_Grid.png}
\end{frame}

\begin{frame}
  \parbox[b]{0.4\textwidth}{
    And here's a bigger knot.
    \par\vskip 8mm\par
    This may look like a lot of information, but if $V$ is big, it's less than the information in a planar diagram, and it is easily computable.
  }
  \includegraphics[width=0.59\textwidth]{Knot_in_5x5x5_with_Grid.png}
\end{frame}

\begin{frame}
  \parbox[b]{0.39\textwidth}{
    There are $2L^2$ triangular ``crossings fields'' $F_k$ in such a projection.
    \par\vskip 8mm\par
    WLOG, in each $F_k$ all over strands and all under strands are oriented in the same way and all green edges belong to one component and all red edges to the other.
  }
  \hfill\resizebox{0.59\textwidth}{!}{\input{CrossingFields.pdf_t}}
\end{frame}

\begin{frame}
  So $2L^2$ times we have to solve the problem ``given two sets $R$ and $G$ of integers in $[0,L]$, how many pairs $\{(r,g)\in R\times G\colon r<g\}$ are there?''. This takes time $\sim L$ (see below), so the overall computation takes time $\sim L^3$.

  \vskip 8mm
  {\bf Below.} Start with $rb=cf=0$ (``reds before'' and ``cases found'') and slide $\blue\triangledown$ from left to right, incrementing $rb$ by one each time you cross a $\red\bullet$ and incrementing $cf$ by $rb$ each time you cross a $\green\bullet$:

  \[ \includegraphics[width=\textwidth]{SlideBlue.png} \]

\end{frame}

\begin{frame} \null
  {\bf Great Embarrassment 1.} I don't know if any of the Alexander, Jones, HOMFLY-PT, and Kauffman polynomials is C3D. I don't know if any Reshetikhin-Turaev invariant is C3D. I don't know if any knot homology is C3D.
  
  \vskip 8mm
  Or maybe it's a cause for optimism --- there's still something very basic we don't know about (say) the Jones polynomial. Can we understand it well enough 3-dimensionally to compute it well? If not, why not?
\end{frame}

\begin{frame} \null
  {\bf Conversation Starter 2.} Similarly, if $\eta$ is a stingy quantity (a quantity we expect to be small for small knots), we will say that $\eta$ has Savings in 3D, or ``has S3D'' if $M_\eta(3D,V)\ll M_\eta(2D,V^{4/3})$.

  \vskip 8mm
  {\bf Example} (with van der Veen). It is probably true that the hyperbolic volume has $S3D$.

  \vskip 8mm
  {\bf Great Embarrassment 2.} I don't know if the genus of a knot has S3D! In other words, even if a knot is given in a 3-dimensional, the best way I know to find a Seifert surface for it is to first project it to 2D, at a great cost.
\end{frame}

\begin{frame} \null
  {\bf Theorem 2.} If $\zeta$ is a finite type invariant of type $d$ then $C_\zeta(3D,V)$ is at most $\sim V^d$.

  \vskip 3mm
  It is known that $C_\zeta(2D,n)$ is at most $\sim n^d$ (e.g., my {\em Polynomial Invariants are Polynomial}), and one may expect that for most $\zeta$, $C_\zeta(2D,n)$ is no better than $\sim n^d$ (exceptions: high coefficients of the Alexander polynomial and other poly-time knot polynomials).

  \vskip 3mm
  As $n^d\sim V^{\frac43d}\gg V^d$,  Theorem 2 says ``most finite type invariants are C3D; the ones in doubt are the lucky few that can be computed unusually quickly''.
\end{frame}

\begin{frame} A knot invariant is ``type $d=3$'' if it vanishes on all $(d+1=4)$-cubes like
\[ \includegraphics[width=0.3\textwidth]{FTDef.pdf} \]
All pre-categorification knot polynomials are power series whose coefficients are finite type invariants. (This is sometimes helpful for the computation of finite type invariants, but rarely helpful for the computation of knot polynomials).
\end{frame}

\begin{frame} Gauss diagrams and sub-Gauss-diagrams:
\[ \includegraphics[width=0.75\textwidth]{GaussDiagram.pdf} \]
\[ \includegraphics[width=0.6\textwidth]{SubGaussDiagrams.pdf} \]
Let $\varphi_d\colon\{\text{knot diagrams}\}\to\langle\text{Gauss diagrams}\rangle$ map every knot diagram to the sum of all the sub-diagrams of its Gauss diagram which have at most $d$ arrows.

\vskip 4mm
{\bf Under-Explained Theorem} (Goussarov-Polyak-Viro). A knot invariant $\zeta$ is of type $d$ iff there is a linear functional $\omega$ on $\langle\text{Gauss diagrams}\rangle$ such that $\zeta=\omega\circ\varphi_d$.
\end{frame}

\begin{frame}
  \resizebox{0.49\textwidth}{!}{\input{CrossingFields.pdf_t}}
  \hfill\parbox[b]{0.5\textwidth}{
    {\bf Strategy.} Count instances of \includegraphics[width=19mm]{GD2.pdf} by counting instances that fall into specific crossing fields as follows:
    \[ \scalebox{0.92}{\input{GD2Marked.pdf_t}} \]
    here each $B_i$ is the set of green/red strands within the relevant crossing field, having some specified orientations. There are two functions, $t\colon B_i\to\bbZ$ and $z\colon B_i\to[0..L]$ defined on each $B_i$.
  }
\end{frame}

\begin{frame}
Just picking the crossing fields costs $\sim L^{2d}$. The rest is handled by the following:

\vskip 4mm
{\bf Counting Problem.} Given $\alpha(j),\beta(j)\in[1..2d]$ for $j\in[1..d]$, given $2d$ ``buckets'' --- sets $B_i$ with $i\in[1..2d]$ --- and given functions $t\colon(B\coloneqq\cup B_i)\to\bbZ$ and $z\colon B\to[0..L]$ such that $z|_{B_i}$ is injective, compute $|A|$, where
\[
  A = \left\{b=(b_i)_{i=1}^{2d}\in\prod B_i\colon\begin{array}{c}
    t(b_1)<t(b_2)<\ldots<t(b_{2d}) \\
    \forall j\in[1..d],\ z(b_{\alpha(j)})<z(b_{\beta(j)})
  \end{array}\right\}.
\]

{\bf Proposition} (Itai Bar-Natan). This computation can be carried out in time $\sim L^d$.

\vskip 4mm
And hence the full computation of $\varphi_d$ takes time $\sim L^{2d}L^d = V^d$, as claimed.
\end{frame}

\begin{frame}\null
{\bf Lemma} (same thing, minus the $z$ data and conditions). Given $2d$ ``buckets'' --- sets $B_i$ with $i\in[1..2d]$ --- and given $t\colon(B\coloneqq\cup B_i)\to\bbZ$. Assuming $|B_i|\sim L$, the quantity
\[ N=\left|\left\{b=(b_i)_{i=1}^{2d}\in\prod B_i\colon t(b_1)<t(b_2)<\ldots<t(b_{2d}) \right\}\right| \]
can be computed in time $\sim L^2$ (in fact, $\sim L$, but we don't need that).

{\bf Proof of Lemma.} For $\iota\in[1..2d]$ and $\tau\in t(B)$ let
\[ N_{\iota,\tau} = \left|\left\{b=(b_i)_{i=1}^{\iota}\in\prod B_i\colon t(b_1)<t(b_2)<\ldots<t(b_{\iota})=\tau \right\}\right|. \]
Then each $N_{\iota,\tau}$ is computable from the $N_{\iota-1,\tau}$ in time $\sim L$, and there are $\sim L$ such computations to carry out. This done, $N=\sum_{\tau\in t(B)}N_{2d,\tau}$. \qed
\end{frame}

\begin{frame}\null
{\bf Re-inserting $z$ --- the idea.}
\vfill
{
  \def\a{{\red 0}}
  \def\b{{\red 1}}
  
  \def\aa{{\green 0\red 0}}
  \def\ab{{\green 0\red 1}}
  \def\ba{{\green 1\red 0}}
  \def\bb{{\green 1\red 1}}
  
  \def\aaa{{\green 00\red 0}}
  \def\aab{{\green 00\red 1}}
  \def\aba{{\green 01\red 0}}
  \def\abb{{\green 01\red 1}}
  \def\baa{{\green 10\red 0}}
  \def\bab{{\green 10\red 1}}
  \def\bba{{\green 11\red 0}}
  \def\bbb{{\green 11\red 1}}
  \input{DyadicTriangle.pdf_t}
}
\end{frame}

\begin{frame}\null
{\bf Proof of Bar-Natan's Proposition.} WLOG $L+1=2^p$ for some $p\in\bbN$. Let $S_q=\{0,1\}^q$ and let $S=\bigcup_{q=0}^{p-1}S_q$ be the set of binary sequences of any length $q\in[0..p-1]$. Let $\sigma=(\sigma_j)_{j=1}^d$ a $d$-tuple of such binary sequences, where the length of $\sigma_j$ is $|\sigma_j|=q_j\in[0..p-1]$. Then
\[ A = \bigcup_{q\in[0..p-1]^d} A_q
  \qquad\text{where}\qquad
  A_q = \bigcup_{\sigma\colon\forall j\,|\sigma_j|=q_j} A_\sigma
  \qquad\text{and}
\]
\[ A_\sigma = \left\{b=(b_i)_{i=1}^{2d}\in\prod B_i\colon\begin{array}{c}
    t(b_1)<t(b_2)<\ldots<t(b_{2d}) \\
    \forall j\in[1..d]\ \begin{array}{c}
      z(b_{\alpha(j)}) = \sigma_j0\ast \\
      z(b_{\beta(j)}) = \sigma_j1\ast
    \end{array} \text{ (in binary)}
  \end{array}\right\}.
\]

By the lemma, $|A_\sigma|$ can be computed in time $\sim\left(\frac{L}{2^{\min|\sigma_j|}}\right)^2$. There are $2^{\sum q_j}$ $A_\sigma$'s in $A_q$. so $A_q$ can be computed in time $\sim 2^{\sum q_j}\left(\frac{L}{2^{\min q_j}}\right)^2$. The number of choices for $q$ is $\sim 1$, so the only term that matters is the worst-case term, which is when for all $j$, $q_j=p-1$. In this case the computation time is $\sim \left(2^{p-1}\right)^d\left(\frac{L}{2^{p-1}}\right)^2\sim L^d\cdot 1^2=L^d$. \qed
\end{frame}

\begin{frame}
  If time --- a word about braids.
  
  \vskip 24mm
  Thank You!
\end{frame}

\end{document}