\documentclass[10pt,notitlepage]{article}
\usepackage[english,greek]{babel}
\usepackage{amsmath,graphicx,amssymb,datetime,multicol,stmaryrd,amscd,dbnsymb}
\usepackage{tensor}
\usepackage{txfonts}	% for the likes of \coloneqq.
\usepackage[usenames,dvipsnames]{xcolor}
%\usepackage{layout,showframe}

% Following http://tex.stackexchange.com/a/847/22475:
\usepackage[setpagesize=false]{hyperref}
\hypersetup{colorlinks,
  linkcolor={blue!50!black},
  citecolor={blue!50!black},
  urlcolor=blue
}

\def\myurl{http://www.math.toronto.edu/~drorbn}
\def\navigator{{
  \href{\myurl}{Dror Bar-Natan}:
  \href{\myurl/Talks}{Talks}:
  \href{\myurl/Talks/Iowa-1603/}{Iowa-1603}:
}}
\def\webdef{{{\greektext web}$\coloneqq$\url{http://drorbn.net/Iowa-1603/}}}
\def\web#1{{\href{\myurl/Talks/Iowa-1603/#1}{{\greektext web}/#1}}}
\def\title{{Polynomial Time Knot Polynomials}}
\def\titleA{{\title, A}}
\def\titleB{{\title, B}}
\def\titleC{{\title, C}}

\def\blue{\color{blue}}
\def\red{\color{red}}
\def\cbox#1#2{{\setlength{\fboxsep}{0pt}\colorbox{#1}{#2}}}

\def\arXiv#1{{\href{http://front.math.ucdavis.edu/#1}{arXiv:\linebreak[0]#1}}}

\def\act{{\hspace{-1pt}\sslash\hspace{-0.75pt}}}
\def\Ad{\operatorname{Ad}}
\def\CW{\text{\it CW}}
\def\diag{\operatorname{diag}}
\def\FL{\text{\it FL}}
\def\lr{$\leftrightarrow$}
\def\ori{$\circlearrowleft$}
\def\PvT{{\mathit P\!v\!T}}
\def\remove{\!\setminus\!}
\def\tr{\operatorname{tr}}
\def\vT{{\mathit v\!T}}

\def\bbR{{\mathbb R}}
\def\bbZ{{\mathbb Z}}
\def\calA{{\mathcal A}}
\def\calD{{\mathcal D}}
\def\calG{{\mathcal G}}
\def\calI{{\mathcal I}}
\def\calK{{\mathcal K}}
\def\calO{{\mathcal O}}
\def\calS{{\mathcal S}}
\def\calT{{\mathcal T}}
\def\calU{{\mathcal U}}
\def\frakg{{\mathfrak g}}

%%%

\def\Abstract{{\raisebox{2mm}{\parbox[t]{3.95in}{
\parshape 5 0.65in 3.3in 0.65in 3.3in 0.65in 3.3in 0.65in 3.3in 0in 3.95in
{\red Abstrant.} \small The value of things is inversely correlated
with their computational complexity. ``Real time'' machines, such as
our brains, mostly run linear time algorithms, and there's still a lot
we don't know. Anything we learn about things doable in linear time
is truly valuable. Polynomial time we can in-practice run, even if we
have to wait; these things are still valuable. Exponential time we can
play with, but just a little, and exponential things must be beautiful
or philosophically compelling to deserve attention. Values further
diminish and the aesthetic-or-philosophical bar further rises as we go
further slower, or un-computable, or ZFC-style intrinsically infinite,
or large-cardinalish, or beyond.

I will explain some things I know about polynomial time knot polynomials
and explain where there's more, within reach.
}}}}

\def\MetaAssoc{{\parbox{1.2in}{
  (meta-associativity: $m^{ab}_x\act m^{xc}_y=m^{bc}_x\act m^{ax}_y$)
}}}

\def\WhyTangles{{\raisebox{2mm}{\parbox[t]{3.95in}{
\parshape 5 0in 1.25in 0in 1.25in 0in 3.95in 0in 3.95in 0in 1.8in
{\red Why Tangles?}
\newline $\bullet$ Finitely presented.
\newline $\bullet$ Divide and conquer computations.
\newline $\bullet$ ``Alg.\ Knot Theory'': If $K$ is ribbon,
\[ z(K)\in\{\kappa(\zeta)\colon \tau(\zeta)=1\}. \]
(Genus and crossing number are also definable properties).
}}}}

\def\Ta{$\calT_{2n}$}
\def\Tb{$U\in\calT_n$}
\def\Tc{ribbon $K\in\calT_1$}
\def\Aa{$\calA_{2n}$}
\def\Ab{$1\in\calA_n$}
\def\Ac{$z(K)\in\calA_1$}

\def\ThmOne{{\raisebox{2mm}{\parbox[t]{3.95in}{
{\red Theorem 1.} $\exists!$ an invariant $z_0\colon\{$pure framed
$S$-component tangles$\}\to\Gamma_0(S)\coloneqq R\times M_{S\times S}(R)$,
where $R=R_S=\bbZ((T_a)_{a\in S})$ is the ring of rational functions in
$S$ variables, intertwining
\newline
$\begin{CD}
  \left(
    \begin{array}{c|c} \omega_1&S_1\\ \hline S_1&A_1 \end{array},
    \begin{array}{c|c} \omega_2&S_2\\ \hline S_2&A_2 \end{array}
  \right)
  @>\displaystyle\sqcup>>
  \begin{array}{c|cc}
    \omega_1\omega_2 & S_1 & S_2 \\
    \hline
    S_1 & A_1 & 0 \\
    S_2 & 0 & A_2
  \end{array}
\end{CD}$,
\newline
$\begin{CD}
  \begin{array}{c|ccc}
    \omega & a & b & S \\
    \hline
    a & \alpha & \beta & \theta \\
    b & \gamma & \delta & \epsilon \\
    S & \phi & \psi & \Xi
  \end{array}
  @>{\displaystyle m^{ab}_c}>{\displaystyle T_a,T_b\to T_c\atop\displaystyle \mu\coloneqq 1-\beta}>
  \left(\!\begin{array}{c|cc}
    \mu\omega & c & S \\
    \hline
    c & \gamma+\alpha\delta/\mu & \epsilon+\delta\theta/\mu \\
    S & \phi+\alpha\psi/\mu & \Xi+\psi\theta/\mu
  \end{array}\!\right)
\end{CD}$,
\newline and satisfying
$\left(
  \mid_a;\,
  \tensor[_a]{\overcrossing}{_b},\tensor[_b]{\undercrossing}{_a}
  \right)
  \overset{\displaystyle z_0}{\longrightarrow}
  \left(
    \begin{array}{c|c} 1 & a \\ \hline a & 1 \\ \end{array};\,
    \begin{array}{c|cc}
      1 & a & b \\
      \hline
      a & 1 & 1-T_a^{\pm 1} \\
      b & 0 & T_a^{\pm 1}
    \end{array}
  \right)
$.
}}}}

\def\InAddition{{\raisebox{2mm}{\parbox[t]{3.95in}{
\parshape 8 0in 2.8in 0in 2.8in 0in 2.8in 0in 2.8in 0in 2.8in 0in 2.8in 0in 2.8in 0in 3.95in
{\red In Addition}
$\bullet$ The matrix part is just a stitching formula for Burau/Gassner
\cite{LeDimet:Gassner, KirkLivingstonWang:Gassner,
CimasoniTuraev:LagrangianRepresentation}.
\newline $\bullet$ $K\mapsto\omega$ is Alexander, mod units.
\newline $\bullet$ $L\mapsto(\omega,A) \mapsto \omega\det'(A-I)/(1-T')$ is
the MVA, mod units.
\newline $\bullet$ The fastest Alexander algorithm I know.
\newline $\bullet$ There are also formulas for strand deletion, reversal,
and doubling.
\newline $\bullet$ Every step along the computation is the invariant
of something.
\newline $\bullet$ Extends to and more naturally defined on v/w-tangles.
\newline $\bullet$ Fits in one column, including propaganda \& implementation.
}}}}

\def\Implementation{{\raisebox{2.5mm}{\parbox[t]{2in}{
\parshape 2 0in 2in 0.1in 1.5in
{\red Implementation} key idea:
\newline $\left(\omega,A=(\alpha_{ab})\right)\leftrightarrow$
\newline $\left(\omega,\lambda=\sum\alpha_{ab}t_ah_b\right)$
}}}}

\def\trace{{\raisebox{2mm}{\parbox[t]{3.95in}{
{\red Closed Components.} The Halacheva meta-trace $\tr_c$ satisfies
$m^{ab}_c\act\tr_c=m^{ba}_c\act\tr_c$ and computes the MVA for all links
in the atlas, but its domain is not understood:

\vskip 1mm
\ $\displaystyle \begin{CD}
  \begin{array}{c|ccc}
    \omega & c & S \\
    \hline
    c & \alpha & \theta \\
    S & \psi & \Xi
  \end{array}
  @>\displaystyle\tr_c>\displaystyle\mu\coloneqq 1-\alpha>
  \begin{array}{c|cc}
    \mu\omega & S \\
    \hline
    S & \Xi+\psi\theta/\mu
  \end{array}
\end{CD}$
}}}}

\def\Weaknesses{{\raisebox{2mm}{\parbox[t]{3.95in}{
{\red Weaknesses.} $\bullet$ $m^{ab}_c$ and $\tr_c$ are non-linear.
$\bullet$ The product $\omega A$ is always Laurent, but my current
proof takes induction with exponentially many conditions.
$\bullet$ I still don't understand $\tr_c$, ``unitarity'', the algebra
for ribbon knots.
}}}}

\def\vTPA{{$\vT\coloneqq$PA}}

\def\grI{{\raisebox{0mm}{\parbox[t]{3.95in}{
Let $\calI\coloneqq\langle\slashoverback-\crossing\rangle$. Then
$\calA^v\coloneqq\prod I^n/I^{n+1}=$``universal
$\calU(D\frakg)^{\otimes S}$''$=$

\vskip 0.8in

{\red Likely Theorem.} \cite{EtingofKazhdan:BialgebrasI, Enriquez:Quantization}
There exists a homomorphic expansion (universal finite type invariant)
$Z\colon\vT\to\calA^v$. \hfil{\footnotesize (issues~suppressed)}

{\red Too hard!} Let's look for ``meta-monoid'' quotients.
}}}}

\def\fineprint{{\raisebox{0mm}{\parbox[t]{3.9in}{
Fine print: No sources no sinks, AS vertices, internally acyclic,
$\deg=(\#\text{vertices})/2$.
}}}}

\def\Aw{$\calA^w\cong\calU(\FL(S)^S\ltimes\CW(S))$}

\def\ThmTwo{{\raisebox{2mm}{\parbox[t]{3.95in}{
{\red Theorem 2} \cite{WKO}.
$\exists!$ a homomorphic expansion, aka a homomorphic universal finite type
invariant $Z^w$ of pure w-tangles. $z^w\coloneqq\log Z^w$ takes
values in $\FL(S)^S\times\CW(S)$.
}}}}

\def\computable{{\raisebox{2.5mm}{\parbox[t]{3.95in}{
{\red $z$ is computable.} $z$ of the Borromean tangle, to degree 5 \cite{KBH}:
}}}}

\def\modbeta{{\raisebox{3.5mm}{\parbox[t]{2in}{
%\parshape 6 0pt 2.0in 0pt 2.0in 0pt 2.0in 0pt 2.0in 0pt 2.0in 0pt 3.95in
{\red Proposition} \cite{KBH}. Modulo all relations that universally hold
for the 2D non-Abelian Lie algebra and after some changes-of-variable,
$z^w$ reduces to $z_0$.
}}}}

\def\Lamb{$\Lambda$}

\def\ADOLink{{Likely related to~\cite{ADO}}}

\def\AbstractContext{{\raisebox{2mm}{\parbox[t]{3.95in}{
\parshape 3 0in 2.45in 0in 2.45in 0in 3.95in
{\red Definition.} (Compare~\cite{Bar-NatanSelmani:MetaMonoids, KBH})
A meta-monoid is a functor $M\colon$(finite sets,
injections)$\to$(sets) (think ``$M(S)$ is quantum $G^S$'', for $G$ a group)
along with natural operations $\ast\colon M(S_1)\times M(S_2)\to M(S_1\sqcup
S_2)$ whenever $S_1\cap S_2=\emptyset$ and $m^{ab}_c\colon
M(S)\to M((S\remove\{a,b\})\sqcup\{c\})$ whenever $a\neq b\in S$ and
$c\notin S\remove\{a,b\}$, such that
\[ \text{meta-associativity:}\quad
  m^{ab}_x\act m^{xc}_y = m^{bc}_x\act m^{ax}_y \]
\[ \text{meta-locality:}\quad
  m^{ab}_c\act m^{de}_f = m^{de}_f\act m^{ab}_c \]
and, with $\epsilon_b=M(S\hookrightarrow S\sqcup\{b\})$,
\[ \text{meta-unit:}\quad
  \epsilon_b\act m^{ab}_a = Id = \epsilon_b\act m^{ba}_a.
\]

{\red Claim.} Pure virtual tangles $\PvT$ form a meta-monoid.

{\red Theorem.} $S\mapsto\Gamma_0(S)$ is a meta-monoid and
$z_0\colon\PvT\to\Gamma_0$ is a morphism of meta-monoids.

{\red Theorem.} There exists an extension of $\Gamma_0$ to a
bigger meta-monoid $\Gamma_{01}(S) = \Gamma_0(S)\times\Gamma_1(S)$, along with
an extension of $z_0$ to $z_{01}\colon\PvT\to\Gamma_{01}$, with
\[ \Gamma_1(S) =
  R_S\oplus V\oplus V^{\otimes 2}\oplus V^{\otimes 3}\oplus \calS^2(V)^{\otimes 2}
  \qquad(\text{with }V\coloneqq R_S\langle S\rangle).
\]
{\red Furthermore,} upon reducing to a single variable everything is
polynomial size and polynomial time.

{\red Furthermore,} $\Gamma_{01}$ is given using a
``meta-2-cocycle $\rho^{ab}_c$ over $\Gamma_0$'': In
addition to $m^{ab}_c\to m^{ab}_{0c}$, there are $R_S$-linear
$m^{ab}_{1c}\colon\Gamma_1(S\sqcup\{a,b\})\to\Gamma_1(S\sqcup\{c\})$,
a meta-right-action
$\alpha^{ab}\colon\Gamma_1(S)\times\Gamma_0(S)\to\Gamma_1(S)$
$R_S$-linear in the first variable, and a
first order differential operator (over $R_S$)
$\rho^{ab}_c\colon\Gamma_0(S\sqcup\{a,b\})\to\Gamma_1(S\sqcup\{c\})$
such that
\[ (\zeta_0,\zeta_1)\act m^{ab}_c
  = \left(
    \zeta_0\act m^{ab}_{0c},
    (\zeta_1,\zeta_0)\act\alpha^{ab}\act m^{ab}_{1c}
      + \zeta_0\act\rho^{ab}_c
  \right)
\]

{\red What's done?} The braid part, with still-ugly formulas.

{\red What's missing?} A lot of concept- and detail-sensitive work towards
$m^{ab}_{1c}$, $\alpha^{ab}$, and $\rho^{ab}_c$. The ``ribbon element''.
}}}}

\def\Ribbon{{\raisebox{2mm}{\parbox[t]{3.95in}{
{\red A bit about ribbon knots.} A ``ribbon knot'' is a knot that can be
presented as the boundary of a disk that has ``ribbon singularities'', but
no ``clasp singularities''. A ``slice knot'' is a knot in $S^3=\partial
B^4$ which is the boundary of a non-singular disk in $B^4$. Every ribbon
knots is clearly slice, yet,

{\red Conjecture.} Some slice knots are not ribbon.

{\red Fox-Milnor.} The Alexander polynomial of a ribbon knot is always of
the form $A(t)=f(t)f(1/t)$.\hfill{(also~for~slice)}
}}}}

\def\GST{\parbox{1.8in}{\centering
\cite{GompfScharlemannThompson:Counterexample}: a slice knot that might
not be ribbon (48 crossings).}}

\def\refs{{\raisebox{2mm}{\parbox[t]{3.95in}{\small
{\red References.}
\par\vspace{-3mm}
\renewcommand{\section}[2]{}%
\begin{thebibliography}{}
\setlength{\parskip}{0pt}
\setlength{\itemsep}{0pt plus 0.3ex}

\bibitem[ADO]{ADO} Y.~Akutsu, T.~Deguchi, and T.~Ohtsuki,
  {\em Invariants of Colored Links,}
  J.\ of Knot Theory and its Ramifications {\bf 1-2} (1992) 161--184.

\bibitem[BN]{KBH} D.~Bar-Natan,
  {\em Balloons and Hoops and their Universal Finite Type Invariant, BF
    Theory, and an Ultimate Alexander Invariant,}
  \web{KBH}, \arXiv{1308.1721}.

\bibitem[BND]{WKO} D.~Bar-Natan and Z.~Dancso,
  {\em Finite Type Invariants of W-Knotted Objects I-II,}
  \web{WKO1}, \web{WKO2}, \arXiv{1405.1956}, \arXiv{1405.1955}.

\bibitem[BNS]{Bar-NatanSelmani:MetaMonoids} D.~Bar-Natan and S.~Selmani,
  {\em Meta-Monoids, Meta-Bicrossed Products, and the Alexander
    Polynomial,}
  J.\ of Knot Theory and its Ramifications {\bf 22-10} (2013),
  \arXiv{1302.5689}.

\bibitem[CT]{CimasoniTuraev:LagrangianRepresentation} D.~Cimasoni and V.~Turaev,
  {\em A Lagrangian Representation of Tangles,}
  Topology {\bf 44} (2005) 747--767, \arXiv{math.GT/0406269}.

\bibitem[En]{Enriquez:Quantization} B.~Enriquez,
  {\em A Cohomological Construction of Quantization Functors of Lie
    Bialgebras,}
  Adv.\ in Math.\ {\bf 197-2} (2005) 430–-479,
  \arXiv{math/0212325}.

\bibitem[EK]{EtingofKazhdan:BialgebrasI} P.~Etingof and D.~Kazhdan,
  {\em Quantization of Lie Bialgebras, I,}
  Selecta Mathematica {\bf 2} (1996) 1--41, \arXiv{q-alg/9506005}.

\bibitem[GST]{GompfScharlemannThompson:Counterexample} R.~E.~Gompf,
  M.~Scharlemann, and A.~Thompson,
  {\em Fibered Knots and Potential Counterexamples to the Property 2R and
    Slice-Ribbon Conjectures,}
  Geom.\ and Top.\ {\bf 14} (2010) 2305--2347, \arXiv{1103.1601}.

\bibitem[KLW]{KirkLivingstonWang:Gassner} P.~Kirk, C.~Livingston, and Z.~Wang,
  {\em The Gassner Representation for String Links,}
  Comm.\ Cont.\ Math.\ {\bf 3} (2001) 87--136, \arXiv{math/9806035}.

\bibitem[LD]{LeDimet:Gassner} J.~Y.~Le Dimet,
  {\em Enlacements d'Intervalles et Repr\'esentation de Gassner,}
  Comment.{} Math.{} Helv.{} {\bf 67} (1992) 306--315.

\end{thebibliography}
}}}}

\def\legalities{{\raisebox{0mm}{\parbox[t]{3.95in}{
It should be a {\red legal requirement} that the slides of slide-based
talks be linked from the conference web site {\em before} the actual talks.
}}}}

\paperwidth 8.5in
\paperheight 11in
\textwidth 8.5in
\textheight 11in
\oddsidemargin -1in
\evensidemargin \oddsidemargin
\topmargin -1in
\headheight 0in
\headsep 0in
\footskip 0in
\parindent 0in
\setlength{\topsep}{0pt}
\pagestyle{empty}

\begin{document} \latintext
\setlength{\jot}{0ex}
\setlength{\abovedisplayskip}{0.5ex}
\setlength{\belowdisplayskip}{0.5ex}
\setlength{\abovedisplayshortskip}{0ex}
\setlength{\belowdisplayshortskip}{0ex}

\begin{center}
%\layout{} \layout{}
\null\vfill \input{PP1.pstex_t} \vfill\null
\newpage \null\vfill \input{PP2.pstex_t} \vfill\null
\newpage \null\vfill \input{PP3.pstex_t} \vfill\null
\end{center}

\end{document}

\endinput