\documentclass[aspectratio=169]{beamer}
%\documentclass[11pt]{article} \usepackage{beamerarticle,hyperref}
\usepackage{pgfpages,wrapfig,mathtools,import}
\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\gray{\color{gray}}
\def\green{\color{green}}
\def\red{\color{red}}

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

\def\arXiv#1{{\href{http://arxiv.org/abs/#1}{{arXiv:}\linebreak[0]{#1}}}}
\def\qed{{\linebreak[1]\null\hfill\text{$\Box$}}}

% Following http://tex.stackexchange.com/questions/23521/tabular-vertical-alignment-to-top:
\def\imagetop#1{\vtop{\null\hbox{#1}}}

\title{Yarn-Ball Knots}

\author{Dror Bar-Natan}

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

%\date{The Fields Institute, October 2021}

\begin{document} \beamertemplatenavigationsymbolsempty

\begin{frame} {\red {\bf Warning.} The second formula on page $(-2)$ ``{\bf Conclusion}'' is silly-wrong. A fix will be posted here soon: some of the numbers written in this handout are a bit off, yet the qualitative results remain exactly the same (namely, for finite type, 3D seems to beat 2D, with the same algorithms).}
\end{frame}

\begin{frame}
  %\titlepage
  \begin{center}
  \vfill
  \LARGE{\bf Yarn-Ball Knots}
  \vfill
  \par\Large [\href{https://lrobert.perso.math.cnrs.fr/kos.html}{K-OS}] on October 21, 2021
  \vfill
  \par\normalsize Dror Bar-Natan with Itai Bar-Natan, Iva Halacheva, and Nancy Scherich
  \end{center}

  \vfill\normalsize
  {\bf Agenda.} A modest light conversation on how knots should be measured.

  \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 include linking numbers (as we shall prove), the hyperbolic volume, and likely finite type invariants (as we shall discuss in detail). But knot polynomials and knot homologies seem to always pay the fee. Can we exempt them?

  \vskip 2mm More at \url{http://drorbn.net/kos21}
\end{frame}

\begin{frame}
Thanks for inviting me to speak at [\href{https://lrobert.perso.math.cnrs.fr/kos.html}{K-OS}]!
\vfill Most important: \url{http://drorbn.net/kos21}
\vfill See also \arXiv{2108.10923}.
\vfill If you can, please turn your video on! (And mic, whenever needed).
\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''.
  }
  \hfill\parbox[b]{0.49\textwidth}{
    \includegraphics[width=\linewidth]{../Fields-2011/KinP.jpg}
    \par Knot by Lisa Piccirillo, pancake by DBN
  }
\end{frame}

\begin{frame}
  \parbox[b]{0.49\textwidth}{
    But real life knots are 3D!
  }
  \hfill\parbox[b]{0.49\textwidth}{
    \includegraphics[width=\linewidth]{../../Projects/YarnBallKnots/iStock-120538554-Cropped.jpg}
    \par \null\hfill A Yarn Ball \hfill\null
  }
\end{frame}

%\begin{frame} \begin{center}
%  \includegraphics[width=0.6\textwidth]{../../Projects/YarnBallKnots/iStock-120538554-Cropped.jpg}
%  \newline A Yarn Ball
%\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}
\includegraphics[width=0.45\linewidth]{../Fields-2011/KinP.jpg}
\hfill \includegraphics[width=0.45\linewidth]{../../Projects/YarnBallKnots/iStock-120538554-Cropped.jpg}

\null\hfill\parbox{0.6\linewidth}{
  The difference matters when
  \begin{itemize}
  \item We make statements about ``random knots''.
  \item We figure out computational complexity.
  \end{itemize}
  Let's try to make it quantitative\ldots
}\hfill\null
\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}{!}{\import{../Fields-2011/}{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) \sim n$ while $C_{lk}(3D,V) \sim 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]{../Fields-2011/4x4x4_Box.png}
  \hfill\includegraphics[width=0.45\textwidth]{../Fields-2011/4x4x4_Grid.png}\hfill\null

  \vskip -5mm
  \null\hfill {\red$\backslash$red} \hfill {\green$/$green} \hfill {\blue --blue} \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]{../Fields-2011/Knot_in_3x3x3.png}
  \includegraphics[width=0.49\textwidth]{../Fields-2011/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]{../Fields-2011/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}{!}{\import{../Fields-2011/}{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]{../Fields-2011/SlideBlue.png} \]

\end{frame}

\begin{frame}
  \parbox[t]{0.4\textwidth}{
    In general, with our limited tools, speedup arises because appropriately projected 3D knots have many uniform ``red over green'' regions:
  }
  \imagetop{\includegraphics[width=0.59\textwidth]{Logs.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} (R.~van der Veen, D.~Thurston, private communications). 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 Next we argue that most finite type invariants are probably C3D\ldots
\vskip 20mm
{\footnotesize (What a weak statement!)}
\vskip 20mm
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} \null
  {\bf Theorem FT2D.} If $\zeta$ is a finite type invariant of type $d$ then $C_\zeta(2D,n)$ is at most $\sim n^{\lfloor 3d/4\rfloor}$. \hfill{\gray With more effort, $C_\zeta(2D,n)\lesssim n^{(\frac{2}{3}+\epsilon)d}$.}

  \vskip 3mm
  Note that there are some exceptional finite type invariants, e.g. high coefficients of the Alexander polynomial and other poly-time knot polynomials, which can be computed much faster!

  \vskip 3mm
  {\bf Theorem FT3D.} If $\zeta$ is a finite type invariant of type $d$ then $C_\zeta(3D,V)$ is at most $\sim V^{6d/7+1/7}$. \hfill{\gray With more effort, $C_\zeta(2D,V)\lesssim V^{(\frac{4}{5}+\epsilon)d}$.}

  \vskip 3mm
  {\bf Tentative Conclusion.} As

  $\displaystyle n^{3d/4} \sim (V^{4/3})^{3d/4} = V \gg V^{6d/7+1/7}$
  \hfill {\gray $n^{2d/3} \sim (V^{4/3})^{2d/3} = V^{8d/9} \gg V^{4d/5}$}

  these theorems say ``most finite type invariants are probably C3D; the ones in greater 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]{../Fields-2011/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]{../Fields-2011/GaussDiagram.pdf} \]
\[ \includegraphics[width=0.6\textwidth]{../Fields-2011/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} \null
  {\bf Theorem FT2D.} If $\zeta$ is a finite type invariant of type $d$ then $C_\zeta(2D,n)$ is at most $\sim n^{\lfloor 3d/4\rfloor}$. \hfill{\gray With more effort, $C_\zeta(2D,n)\lesssim n^{(\frac{2}{3}+\epsilon)d}$.}
\end{frame}

\begin{frame} \null
  {\it Proof of Theorem FT2D.}
  \[ \includegraphics[width=\textwidth]{GD1.png} \]
  We need to count how many times a diagram such as the red appears within a bigger diagram, having $n$ arrows. Clearly this can be done in time $\sim n^3$, and in general, in time $\sim n^d$.
\end{frame}

\begin{frame}
  \[ \includegraphics[width=\textwidth]{GD2.png} \]
  With an appropriate look-up table, it can also be done in time $\sim n^2$ (in general, $\sim n^{d-1}$). That look-up table $(T^{p_1,p_2}_{q_1,q_2})$ is of size (and production cost) $\sim n^4$ if you are naive, and $\sim n^2$ if you are just a bit smarter. Indeed
  \[ T^{p_1,p_2}_{q_1,q_2} =
    T^{0,p_2}_{0,q_2} - T^{0,p_1}_{0,q_2}- T^{0,p_2}_{0,q_1} + T^{0,p_1}_{0,q_1},
  \]
  and $(T^{0,p}_{0,q})$ is easy to compute.
\end{frame}

\begin{frame}
  \[ \includegraphics[width=\textwidth]{GD3.png} \]
  With multiple uses of the same lookup table, what naively takes $\sim n^5$ can be reduced to $\sim n^3$.

  \vskip 2mm In general within a big $d$-arrow diagram we need to find an as-large-as possible collection of arrows to delay. These must be non-adjacent to each other. As the adjacency graph for the arrows is at worst quadrivalent, we can always find $\lceil\frac{d}{4}\rceil$ non-adjacent arrows, and hence solve the counting problem in time $\sim n^{d-\lceil\frac{d}{4}\rceil} = n^{\lfloor 3d/4\rfloor}$.
\end{frame}

\begin{frame} \null
  Note that this counting argument works equally well if each of the $d$ arrows is pulled from a different set!

  \vskip 2mm It follows that we can compute $\varphi_d$ in time $\sim n^{\lfloor 3d/4\rfloor}$. \qed

  \vskip 2mm {\gray With bigger look-up tables that allow looking up ``clusters'' of $G$ arrows, we can reduce this to $\sim n^{(\frac{2}{3}+\epsilon)d}$. \qed}
\end{frame}

\begin{frame} \null
  On to
  \vskip 10mm
  {\bf Theorem FT3D.} If $\zeta$ is a finite type invariant of type $d$ then $C_\zeta(3D,V)$ is at most $\sim V^{6d/7+1/7}$. \hfill{\gray With more effort, $C_\zeta(2D,V)\lesssim V^{(\frac{4}{5}+\epsilon)d}$.}
\end{frame}

\begin{frame}
An image editing problem:
\[ \includegraphics[width=0.75\textwidth]{20201025_170730.jpg} \]
(Yarn ball and background coutesy of Heather Young)
\end{frame}

\begin{frame}
The line/feather method:
\[ \includegraphics[width=0.65\textwidth]{Feather.jpg} \]
Accurate but takes forever.
\end{frame}

\begin{frame}
The rectangle/shark method:
\[ \includegraphics[width=0.65\textwidth]{Shark.jpg} \]
Coarse but fast.
\end{frame}

\begin{frame}
In reality, you take a few shark bites and feather the rest \ldots
\[ \includegraphics[width=0.65\textwidth]{SharkAndFeather.jpg} \]
\ldots and then there's an optimization problem to solve: when to stop biting and start feathering.
\end{frame}

\begin{frame}\null {\bf The structure of a crossing field.}
  \[ \scalebox{1.6}{\input{DyadicTriangle.pdf_t}} \]
  There are about $\log_2 L$ ``generations''. There are $2^g$ bites in generation $g$, and the total number of crossings in them is $\sim L^2/2^g$. \hfill{\blue Let's go hunt!}
\end{frame}

\begin{frame}\null {\bf Multi-feathers and multi-sharks.}
  \newline\parbox[b]{0.49\textwidth}{
    For a type $d$ invariant we need to count $d$-tuples of crossings, and each has its own ``generation'' $g_i$. So we have the ``multi-generation''
    \[ \bar{g}=(g_1,\ldots,g_d). \]
    Let $G\coloneqq\sum g_i$ be the ``overall generation''. We will choose between a ``multi-feather'' method and a ``multi-shark'' method based on the size of $G$.
  }
  \hfill\parbox[b]{0.49\textwidth}{\scalebox{1}{
    \begin{picture}(120,150)
      \put(0,0){\includegraphics[width=2.15in]{squares_and_diagonals.png}}
      \put(155,80){\textcolor{purple}{\large{$g_1$}}}
      \put(120,90){\textcolor{purple}{\large{$g_2$}}}
      \put(85,120){\textcolor{purple}{\large{$g_3$}}}
      \put(52,140){\textcolor{purple}{\large{$g_4$}}}
    \end{picture}
  }}
\end{frame}

%\begin{frame}\null {\bf Multi-feathers and multi-sharks.}
%  \newline\parbox[b]{0.49\textwidth}{
%    For a type $d$ invariant we need to count $d$-tuples of crossings, and each has its own ``generation'' $g_i$. So we have the ``multi-generation''
%    \[ \bar{g}=(g_1,\ldots,g_d). \]
%    Let $G\coloneqq\sum g_i$.
%  }
%  \hfill\parbox[b]{0.49\textwidth}{
%    \resizebox{\linewidth}{!}{\input{MultiBites.pdf_t}}
%  }
%\end{frame}

\begin{frame}
  \parbox[b]{0.75\textwidth}{
    The effort to take a single multi-bite is tiny. Indeed,

    \vskip 2mm{\bf Lemma} Given $2d$ finite sets $B_i=\{t_{i1},t_{i2},\ldots\}\subset[1..L^3]$ and a permutation $\pi\in S_{2n}$ the quantity
    \[ N = \left|\left\{
        (b_i)\in\prod_{i=1}^{2d}B_i\colon \text{the $b_i$'s are ordered as $\pi$}
      \right\}\right|
    \]
    can be computed in time $\sim\sum|B_i|\sim\max{|B_i|}$.

    \vskip 2mm{\it Proof.} WLOG $\pi=Id$. For $\iota\in[1..2d]$ and $\beta\in B\coloneqq\cup B_i$ let
    \[
      N_{\iota,\beta} = \left|\left\{(b_i)\in\prod_{i=1}^{\iota} B_i\colon b_1<b_2<\ldots<b_{\iota}\leq\beta \right\}\right|.
    \]
    We need to know $N_{2d,\max{B}}$; compute it inductively using $N_{\iota,\beta} = N_{\iota,\beta'} + N_{\iota-1,\beta'}$, where $\beta'$ is the predecessor of $\beta$ in $B$. \qed
  }
  \quad\parbox[b]{0.18\textwidth}{
    \resizebox{0.18\textwidth}{!}{\input{MultiBite.pdf_t}}
  }
\end{frame}

\begin{frame} \null {\bf Conclusion.} We wish to compute the contribution to $\varphi_d$ coming from $d$-tuples of crossings of multi-generation $\bar{g}$.
\begin{itemize}
\item The multi-shark method does it in time
\[ \sim (\text{no.\ of bites})\cdot(\text{time per bite})
  = L^{2d}2^G\cdot \frac{L}{2^{\min \bar{g}}} < L^{2d+1}2^G
\]
(increases with $G$).
\item The multi-feather method (project and use the 2D algorithm) does it in time
\[ \sim (\text{no.\ of crossings})^{\lfloor\frac34 d\rfloor}
  = \left(\prod_{i=1}^d L^2\frac{L^2}{2^{g_i}}\right)^{\lfloor\frac34 d\rfloor}
  < \frac{L^{3d}}{(2^G)^{3/4}}
\]
(decreases with $G$).
\end{itemize}
Of course, for any specific $G$ we are free to choose whichever is better, shark or feather.
\end{frame}

\begin{frame} \null
The two methods agree (and therefore are at their worst) if $2^G=L^{\frac47(d-1)}$, and in that case, they both take time $\sim L^{\frac{18}{7}d+\frac37} = V^{\frac67 d+\frac17}$.

\vskip 3mm {\gray The same reasoning, with the $n^{(\frac23+\epsilon)d}$ feather, gives $V^{(\frac45+\epsilon)d}$.} \qed
\end{frame}

%\begin{frame} I am reminded of a scene from The Princess Bride (1987). Inigo Montoya (2D) is having a sword fight with the Man in Black (3D); Inigo is with his back to the abyss: \\
%%Inigo Montoya: You are wonderful! \\
%%Man in Black: Thank you. I've worked hard to become so. \\
%Inigo Montoya: I admit it. You are better than I am. \\
%Man in Black: Then why are you smiling? \\
%Inigo Montoya: Because I know something you don't know. \\
%Man in Black: And what is that? \\
%Inigo Montoya: I am not left-handed! \\
%\[ \includegraphics[width=0.4\textwidth]{InigoSwitch.jpg} \]
%\end{frame}
%
%\begin{frame}
%And now the Man in Black is against the abyss\ldots \\
%%Man in Black: You're amazing! \\
%%Inigo Montoya: I ought to be, after twenty years. \\
%Man in Black: There's something I ought to tell you. \\
%Inigo Montoya: Tell me. \\
%Man in Black: I'm not left-handed either. \\
%\[ \includegraphics[width=0.4\textwidth]{WestleySwitch.jpg} \]
%\end{frame}

\begin{frame}
  If time --- a word about braids.

  \vskip 24mm
  Thank You!
\end{frame}

\end{document}


