\documentclass[11pt]{article} \usepackage{amsmath, amssymb, amscd, dbnsymb, graphicx, stmaryrd, picins, fancyhdr, import, bbm, multicol} \usepackage{txfonts} % for the likes of \coloneqq. \usepackage[usenames,dvipsnames]{xcolor} % Following http://tex.stackexchange.com/a/847/22475: \usepackage[setpagesize=false]{hyperref} \hypersetup{colorlinks, linkcolor={blue!50!black}, citecolor={blue!50!black}, urlcolor=blue } % Following http://tex.stackexchange.com/questions/69901/how-to-typeset-greek-letters: \usepackage[LGR,T1]{fontenc} \newcommand{\textgreek}[1]{\begingroup\fontencoding{LGR}\selectfont#1\endgroup} \usepackage[all]{xy} \usepackage[textwidth=7in,textheight=9.5in,headsep=0.15in]{geometry} \usepackage{pdfpages} \def\myurl{http://www.math.toronto.edu/~drorbn} \def\pensieve{http://drorbn.net/AcademicPensieve} \def\bbe{\mathbbm{e}} \def\bbO{{\mathbb O}} \def\bbQ{{\mathbb Q}} \def\bbR{{\mathbb R}} \def\bbZ{{\mathbb Z}} \def\calA{{\mathcal A}} \def\calD{{\mathcal D}} \def\calF{{\mathcal F}} \def\calI{{\mathcal I}} \def\calK{{\mathcal K}} \def\calP{{\mathcal P}} \def\calR{{\mathcal R}} \def\calS{{\mathcal S}} \def\calT{{\mathcal T}} \def\calU{{\mathcal U}} \def\fraka{{\mathfrak a}} \def\frakb{{\mathfrak b}} \def\frakh{{\mathfrak h}} \def\frakg{{\mathfrak g}} \def\AS{\mathit{AS}} \def\gr{\operatorname{gr}} \def\IHX{\mathit{IHX}} \def\STU{\mathit{STU}} \def\TC{\mathit{TC}} \def\arXiv#1{{\href{http://front.math.ucdavis.edu/#1}{arXiv:#1}}} \def\web#1{{\href{http://drorbn.net/d17/#1}{\textgreek{web}/#1}}} \renewcommand{\headrulewidth}{0pt} \fancypagestyle{empty}{ \rhead{\footnotesize\href{\myurl}{Dror Bar-Natan}} \lhead{\footnotesize\textgreek{web}$\coloneqq$\url{http://drorbn.net/d17/}} \cfoot{} } \fancypagestyle{normal}{ \rhead{\footnotesize\href{\myurl}{Dror Bar-Natan}} \lhead{\footnotesize\textgreek{web}$\coloneqq$\url{http://drorbn.net/d17/}} \cfoot{\thepage} } \pagestyle{empty} \def\red{\color{red}} \catcode`\@=11 \long\def\@makecaption#1#2{% \vskip 10pt \setbox\@tempboxa\hbox{%\ifvoid\tinybox\else\box\tinybox\fi \small\sf{\bfcaptionfont #1. }\ignorespaces #2}% \ifdim \wd\@tempboxa >\captionwidth {% \rightskip=\@captionmargin\leftskip=\@captionmargin \unhbox\@tempboxa\par}% \else \hbox to\hsize{\hfil\box\@tempboxa\hfil}% \fi} \font\bfcaptionfont=cmssbx10 scaled \magstephalf \newdimen\@captionmargin\@captionmargin=2\parindent \newdimen\captionwidth\captionwidth=\hsize \catcode`\@=12 \begin{document} \par\noindent{\large\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Notice of Intent} \vskip 2mm {\small Totally by definition, once in a lifetime, a researcher is working on his personal best project. For me this is now, and I'm very excited about it. Let me explain. Here and there math has immense philosophical value or beauty to justify the effort. Yet everyday math is mostly about, or should be about, ``doing useful things''. Deciding if $A$ has property $B$, counting how many $C$'s satisfy $D$, computing $E$. When $A$ and $B$ and $C$ and $D$ and $E$ are small, we do the computations on the back of an envelope and write them as ``Example 3.14'' in some paper. But these are merely the demos, and sooner or later we worry (or ought to worry) about bigger inputs. I'm more aware then most mathematicians (though perhaps less than many computer scientists), how much the complexity of obtaining the solution as a function of the size of the inputs matters. Hence I firmly believe that incomputable mathematics is intrinsically less valuable than computable mathematics (allowing some exceptions for philosophical value and/or beauty), and that within computable mathematics, what can be computed in linear time is generally more valuable than what can be computed in polynomial (poly-) time, which in itself is more valuable than what can be computed in exponential (exp-) time, which in itself is more valuable than what can be computed just in theory. I've always been an exp-time mathematician. Almost everything I've worked on, finite-type invariants and invariants of certain 3-manifolds, categorification, matters related to associators and to free Lie algebras, etc., boils down to computable things, though they are computable in exp-time. My current project (joint with Roland van der Veen and continuing Lev Rozansky and Andrea Overbay) is poly-time, which puts it ahead of everything else I have done. IMHO it is also philosophically interesting and beautiful, but I'm biased. On to content: There is a standard construction that produces a knot invariant given a certain special element $R$ ("the $R$-matrix") in the second tensor power of some algebra $U$. Roughly speaking, one independent copy of $R$ is placed next to each crossing of a knot $K$, yielding an element in some high tensor power of $U$. Then the edges of $K$ provide ordering instructions for how to multiply together these tensor factors using the algebra structure of $U$ so as to get a $U$-valued knot invariant $Z$. Typically $U$ is the universal enveloping algebra of some semisimple Lie algebra $L$ (or some completed or quantized variant thereof). These algebras are infinite dimensional, and so $Z$ is not immediately computable. The standard resolution is to also choose a finite-dimensional representation $V$ of $L$ and to carry out all computations within $V$ and its tensor powers. This works incredibly well. In fact, almost all the ``knot polynomials'' that arose following the work of Jones and Witten, the Jones and coloured Jones polynomials, the HOMFLY-PT polynomial, the Kauffman polynomial, and more, arise in this way, and much if not all of ``quantum topology'' is derived from these seeds. Yet these polynomials take an exponential time to compute: within the computation high tensor powers of $V$ must be considered, the dimensions of such powers grow exponentially with the size of the input knot, and computations within exp-sized spaces take at least exp-time. The same criticism applies to almost everything else in quantum topology: whenever there is a ``braided monoidal category'' or a ``topological quantum field theory'' within some chain of reasoning, at some point high tensor powers of some vector spaces must be considered and the results become (at least) exp-time. (An alternative mean to extract computable information from $Z$ is to reduce modulo various ``powers of $h$'' filtrations on $U$. This yields the theory of finite type invariants. Individual finite type invariants are poly-time, but each single one is rather weak, and only when infinite sequences of finite type invariants are considered together, they become strong. Such sequences reproduce the aforementioned knot polynomials, but they are hard to compute). Our approach is different. We explain how one can ``fade out'' roughly a half of a given semisimple Lie algebra $L$ (namely its lower Borel subalgebra) by appropriately multiplying the structure constants that pertain to that half by some new coupling constant $b$. When $b=0$, the original $L$ collapses to a solvable Lie algebra inside which the computation of $Z$ is easy (as the name suggests, solvable algebras are easy to ``solve''). Alas at $b=0$ the result is always the same --- the classical (yet poly-time and very useful) Alexander polynomial. We find that in a formal neighborhood of $b=0$, namely in a ring in which $b^{k+1}=0$ for some natural number $k$, the invariant $Z$ remains poly-time to compute. By explicit experimentation with knots in the standard tables, the resulting poly-time invariants are very strong: with just $L=sl_2$ and $k=1$, the resulting invariant separates more knots than the exp-time HOMFLY-PT and Khovanov taken together. By both theory and experimentation, we know that our invariants give genus bounds for knots (hence they ``see'' some topology), and we have reasons to suspect that they may give a way to show that certain knots are not-ribbon, potentially assisting with the long-standing slice$=$ribbon conjecture. None of the above is written yet, though I have given many talks on the subject, and most are online with videos and handouts and running code. See \url{http://www.math.toronto.edu/drorbn/Talks/}. Within the time of the requested grant, I plan to complete my work on these poly-time invariants. Much remains to be done: writing from several perspectives, implementation for cases beyond $sl_2$ at $k=1$, a complete analysis of the relationship with genus and with the ribbon property, an analysis of the relationship with the Melvin-Morton-Rozansky expansion of the coloured Jones polynomial, and more. } \eject \par\noindent{\large\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Proposal Summary} \vskip 2mm One of the major triumphs of mathematics in the 1980s, which lead to at least 3 Fields medals (Jones, Drinfel'd, Witten) was the unexpected realization that low dimensional topology, and in particular knot theory, is closely related to quantum field theory and to the theory of quantum groups. Knot theory is mundane and ages-old; anything ``quantum'' seems hyper-modern. Why would the two have anything to do with each other? The answer is long and complicated and has a lot to do with the ``Yang-Baxter Equation'' (YBE). The YBE on the one hand can be interpreted in knot theory as ``the third Reidemeister move'', or as ``controlling the most basic interaction of 3 pieces of string'' (this turns out to be a very crucial part of knot theory). On the other hand solutions of the YBE arise from ``quantum'' machinery. Hence the quantum is useful to the knotted, and by similar ways, to the rest of low dimensional topology. But ``quantum'' has a caveat, which makes it super-exciting (to some) yet bounds its usefulness (to others). When quantum systems grow large (as they do when the knot or low-dimensional space we study grows complicated), their ``state space'' grows at an exponential rate. ``Quantum computers'' aim to exploit this fact and make large quantum systems performs overwhelmingly large computations by utilizing their vast state spaces. But quantum computers aren't here yet, may take many years to come, suffer from other limits on what they can do, and much of low-dimensional topology is anyway outside of these limits. So at least for now and likely forever, many things that have ``quantum'' in their description are exponentially-complex to compute, which in practice means that they cannot be computed beyond a few simple cases. Recently Van der Veen and myself, following Rozansky and Overbay, found a corner (figuratively speaking) of the vast state space of the quantum machinery used in knot theory, which can be described in just polynomial complexity, and which carries enough information to still speak to knot theory. The ``knot invariants'' constructed that way seem to be the strongest invariants we know that are computable even for very large knots. Our approach utilizes the fact that complicated symmetry groups often have much simpler ``contractions''. A well known example is the Lorentz group of relativity theory, which at small velocities contracts to the Galilean group of classical mechanics. In a similar manner we find that the symmetry algebras underlying the useful solutions of the Yang-Baxter equation, namely semi-simple algebras such as sl(n), have contractions that are ``solvable algebras'', and that the same operations that are exponentially complex for the original sl(n) symmetry become polynomially-complex (namely, much simpler) within and near these solvable contractions. Much remains to be done: implementation, documentation, application, generalization. I hope to achieve all that over this 5-year grant period. \eject \setcounter{page}{1} \pagestyle{normal} \par\noindent{\Large\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Proposal} \vskip 2mm \begin{multicols}{2} Recently, Roland van der Veen and myself, following Lev Rozansky and Andrea Overbay~\cite{Ro, Rozansky:Burau, Rozansky:U1RCC, Overbay:Thesis}, presented a methodology~\cite{PPSA} for the construction of poly-time computable knot polynomials and constructed~\cite{PP1} the first poly-time computable knot polynomial since the Alexander polynomial of 1928~\cite{Alexander:TopologicalInvariants}. {\bf Why is it exciting, even before the details?} Here and there mathematics has immense philosophical value or beauty to justify the effort. Yet everyday mathematics is mostly about, or should be about, ``doing useful things''. Deciding if $A$ has property $B$, counting how many $C$'s satisfy $D$, computing $E$. When $A$ and $B$ and $C$ and $D$ and $E$ are small, we do the computations on the back of an envelope and publish them as ``Example 3.14'' in some paper. But these are merely the demos, and sooner or later we worry (or ought to worry) about bigger inputs. I'm more aware then most mathematicians (though perhaps less than many computer scientists), how much the complexity of obtaining the solution as a function of the size of the inputs matters. Hence I firmly believe that incomputable mathematics is intrinsically less valuable than computable mathematics (allowing some exceptions for philosophical value and/or beauty), and that within computable mathematics, what can be computed in linear time is generally more valuable than what can be computed in polynomial (poly-) time, which in itself is more valuable than what can be computed in exponential \text{(exp-)} time, which in itself is more valuable than what can be computed just in theory. With the exception of the Alexander polynomial, which has been thoroughly mined\footnote{Though newer and better still arises. For example, the techniques of~\cite{Bar-NatanSelmani:MetaMonoids} lead to the fastest known algorithm for the computation of the Alexander polynomial.}, and with the exception of the first few finite-type invariants~\cite{Bar-Natan:OnVassiliev, Bar-Natan:Polynomial}, which are rather weak, until recently~\cite{Bar-Natan:LesDiablerets-1608} all known knot invariants were harder-than-poly-time to compute\footnote{\label{foot:DivideAndConquer}Though divide-and-conquer methods reduce the computation time for the Jones and HOMFLY-PT polynomials~\cite{Jones:New, HOMFLY, PrzytyckiTraczyk:PT} and possibly even for Khovanov homology~\cite{Bar-Natan:FastKh} to around $C\bbe^{c\sqrt{n}}$ where $n$ is the crossing number, and so these invariants can be computed for surprisingly large knots.}. So clearly, what we have in~\cite{PP1, PPSA} --- a rather strong poly-time-computable knot polynomial\footnote{How strong? As detailed in~\cite{Bar-Natan:Indiana-1611}, stronger than HOMFLY-PT and Khovanov taken together, at least for knots up to with 12 crossings.} and a methodology for further such --- is a priori exciting. Furthermore, our invariants extend to tangles, and are well-behaved under the basic tangle-theoretic operations of ``strand stitching'' and ``strand doubling'', and hence they carry topological information: a bound on the genus of a knot~\cite{Bar-Natan:Indiana-1611}, and what may be the best chance we have of showing that certain slice knots are not ribbon~\cite{K17}, hence resolving (negatively) the long-standing ``slice$=$ribbon'' conjecture~\cite{FoxMilnor:Singularities}. Finally, merely our suggestion (starting~\cite{Bar-Natan:Qinhuangdao-1507}) that some poly-time knot polynomials beyond the Alexander polynomial ought to exist is already generating both interest~\cite{Fiedler:1Cocycle} and competition~\cite{Przytycki:Vertigan} (both authors do not cite us explicitly, but were present in our talks~\cite{Bar-Natan:Toulouse-1705, Bar-Natan:GWU-1612} and were clearly influenced). {\bf Our methodology.} Since already the 1980s, there is a standard ``quantum algebra'' methodology that associates a framed knot invariant to certain triples $(U,R,C)$, where $U$ is a unital algebra and $R\in U\otimes U$ and $C\in U$ are invertible (see e.g.~\cite{Ohtsuki:QuantumInvariants}). Let us briefly recall the standard methodology here. \parpic[r]{\parbox[t]{1.5in}{\begin{center} \input{URCMethod.pdf_t} \newline $\displaystyle z(K) = \sum_{i,j,k} b_ia_jb_kCa_ib_ja_k$ \end{center}}} Draw a given (framed, oriented) knot $K$ as a long knot in the plane so that at each crossing the two crossing strands are oriented upward, and so that the orientation at two ends of $K$ is up. Put a copy of $R=\sum a_i\otimes b_i$ on every positive crossing of $K$ with the ``$a$'' side on the over-strand and the ``$b$'' side on the under-strand, labeling these $a$'s and $b$'s with distinct indices $i,j,k,\ldots$ (similarly put copies of $R^{-1}=\sum a'_i\otimes b'_i$ on the negative crossings; these are absent in our example). Put a copy of $C^{\pm 1}$ on every cuap where the tangent to the knot is pointing to the right (meaning, a $C$ on every such cup and a $C^{-1}$ on every such cap). Form an expression $z(K)$ in $U$ by multiplying all the $a$, $b$, $C$ letters as they are seen when traveling along $K$ and then summing over all the indices, as shown. If $R$ and $C$ satisfy some conditions dictated by the standard Reidemeister moves of knot theory, especially the Yang-Baxter Equation (YBE), the resulting $z(K)$ is a knot invariant. %\picskip{1} Abstractly, $z(K)$ is obtained by tensoring together several copies of $R^{\pm 1}\in U^{\otimes 2}$ and $C^{\pm 1}\in U$ to get an intermediate result $z_0\in U^{\otimes S}$, where $S$ is a finite set with two elements for each crossing of $K$ and one element for each right-pointing cuap. We then multiply the different tensor factors in $z_0$ in an order dictated by $K$ to get an output in a single copy of $U$. The best algebras with which to apply the standard methodology, at least as of 2017, are certain completions $\calU(\frakg)$ of the universal enveloping algebras of semi-simple Lie algebras $\frakg$ (or their quantizations). But these algebras are infinite dimensional and the sum in $z(K)$ is infinite and not immediately computable. The dogma solution is to pick a finite dimensional representation of $\frakg$ and use it to represent all the elements appearing in $z(K)$, effectively replacing the algebra by the algebra of endomorphisms of some finite dimensional vector space. This turns the sum finite; yet if the knot $K$ has $n$ crossings, our sum becomes a sum over $n$ indices $i_1,\ldots,i_n$. Thus there are exponentially-many summands to consider and it takes an exponential amount of time to compute $z(K)$.\textsuperscript{\ref{foot:DivideAndConquer},}\footnote{Note that almost any time the phrases ``braided monoidal category'' or ``TQFT'' are used within low dimensional topology, some tensor powers of some vector spaces need to be considered at some point, and dimensions grow exponentially. Thus our criticism applies in these cases too~\cite{Bar-Natan:Toulouse-1705}.} Alternatively, one may extract finite-type~\cite{Bar-Natan:OnVassiliev} information out of $z(K)$ by reducing modulo appropriate filtrations of $U$ and its tensor powers. As already mentioned, the results are computable but weak. Our approach to the computation of $z(K)$ is different. Instead of working directly in $U^{\otimes S}$, we work in relatively small\footnote{Ranks grow polynomially in $|S|$.} spaces $\calF(S)$ of ``closed-form formulas for elements of $U^{\otimes S}$''. For this to work, we need to ensure that the fundamentals $R$ and $C$ would be described by ``closed-form formulas'', and that the most basic operations necessary for the computation of $z$, namely multiplication of factors in $U^{\otimes S}$, would be implemented ``in closed form'' in $\calF(S)$. In practice, the kind of terms that appear within formulas for $R$ and $C$ are exponentials of the form $\bbe^{\xi x}$, where $x$ is a generator of $U$ and $\xi$ is a formal scalar variable, their iterated derivatives $(\partial_\xi)^k\bbe^{\xi x}=x^k\bbe^{\xi x}$, and exponentials of quadratics like $\bbe^{\lambda xy}$ or $\bbe^{\lambda x\otimes y}$, with scalar $\lambda$ and $x,y\in U$. We then need to multiply several such exponentials and differentiated exponentials, and we need to learn how to bring such products into some pre-chosen ``canonical order''. In the standard $U\sim\calU(\frakg)$ case, where $\frakg$ is semi-simple, this is complicated. Yet if $\frakg$ is solvable, this is often easy. Wouldn't it be nice if it was possible to approximate semi-simple Lie algebras with solvable ones? In our work we exploit the little-known fact that this is (nearly) possible. Precisely, given a semisimple $\frakg$, there exists a Lie algebra $\frakg^\epsilon$ defined over the ring $\bbQ[\epsilon]$ of polynomials in a formal variable $\epsilon$ (in other words, $\frakg^\epsilon$ is a ``one-parameter family of Lie algebras''), so that \begin{enumerate} \item If $\epsilon$ is fixed to be some constant not equal to zero, then $\frakg^\epsilon$ is isomorphic to $\frakg^+\coloneqq\frakg\oplus\frakh$, which is the original $\frakg$ with an extra copy of its own (Abelian) Cartan subalgebra $\frakh$ added. \item At $\epsilon=0$, $\frakg^0$ is solvable. Furthermore, $\frakg^\epsilon$ is solvable in a formal neighborhood of $\epsilon=0$: for any natural number $k\geq 0$ the reduction $\frakg^{\leq k}$ of $\frakg^\epsilon$ to the ring $\bbQ[\epsilon]/(\epsilon^{k+1}=0)$ is solvable as a Lie algebra over $\bbQ$ (whose dimension is $(k+1)\dim\frakg$). \end{enumerate} As $k$ gets larger, the solvable $\frakg^{\leq k}$ is closer and closer to $\frakg^\epsilon$, as the reduction modulo $\epsilon^{k+1}=0$ means less and less, and so at least informally, $\frakg^{\leq k}\xrightarrow[k\to\infty]{}\frakg^+\sim\frakg$. We sketch why $\frakg^\epsilon$ exists. Let $\frakg$ be a semisimple Lie algebra and let $\frakb^+$ and $\frakb^-$ be its upper and lower Borel subalgebras, respectively. Then $(\frakb^+)^\ast$ is $\frakb^-$, and as the latter has a Lie bracket, it follows that $\frakb^+$ has a co-bracket $\delta$. In fact, $\frakb^+$ along with its bracket $[\cdot,\cdot]$ and co-bracket $\delta$ is a ``Lie bialgebra'', and one may recover $\frakg^+=\frakg\oplus\frakh=\frakb^-\oplus\frakb^+$ as the ``Drinfel'd double'' $\calD(\frakb^+,[\cdot,\cdot],\delta)$ of $\frakb^+$ (see e.g.~\cite{EtingofSchiffman:QuantumGroups}). The axioms of a Lie bialgebra are homogeneous in $\delta$, meaning that $(\frakb^+,[\cdot,\cdot],\epsilon\delta)$ is again a Lie bialgebra for any scalar $\epsilon$, and one may set $\frakg^\epsilon\coloneqq\calD(\frakb^+,[\cdot,\cdot],\epsilon\delta)$. The required properties are easy to check. Perhaps the most interesting is the solvability of $\frakg^0$: indeed $\frakg^0=I\frakb^+\coloneqq(\frakb^+)^\ast\rtimes\frakb^+$ with $(\frakb^+)^\ast$ regarded as an Abelian Lie algebra and $\frakb^+$ acting on $(\frakb^+)^\ast$ using the co-adjoint action, and then the solvability of $I\frakb^+$ easily follows from the solvability of $\frakb^+$. We studied the knot-theoretic significance of $\frakb^\ast\rtimes\frakb$ for a general Lie algebra $\frakb$ extensively in the context of ``w-knots'' in \cite{WKO1,WKO2,WKO3,WKO4,KBH} (supported by our previous NSERC discovery grant), and these studies along with the observations in this paragraph were in some sense the starting points for our current study. {\bf A model result.} Let us state the $\frakg=sl_2$ version of our main result; one of our future directions will be to extend beyond that case. Let $k$ be a natural number. One may check that the Lie algebra $sl_2^{\geq k}$ is generated by generators $\{t,y,a,x\}$ such that $t$ is central and $[a,x]=x$, $[a,y]=-y$, and $[x,y]=2\epsilon a-t$; here $\epsilon$ is a scalar for which $\epsilon^{k+1}=0$. Let $\calU$ be the universal enveloping algebra of $sl_2^{\leq k}$ (completed, details elsewhere), and likewise let $\calS$ be the (similarly completed) symmetric algebra of $sl_2^{\leq k}$. We write ``$v_i$'' for ``$v$ placed in an $i$'th tensor factor'', so e.g., $y_1x_2=y\otimes x$ is an element of either $\calU^{\otimes 2}$ or $\calS^{\otimes 2}$, according to context. We let $\bbO\colon\calS\to\calU$ be the ``normal ordering map'' which plants the non-commuting generators $\{y,a,x\}$ in the ``$y$ then $a$ then $x$'' order. For example, for a scalar $\lambda$, $\bbO(\bbe^{\lambda xy})=\sum\frac{\lambda^jy^jx^j}{j!}$ (and not $\sum\frac{\lambda^j(yx)^j}{j!}$). It turns out that there are suitable $R$ and $C$ elements for $\calU$, constructed using the standard quantum algebra methodology, and hence there is a corresponding knot invariant $z$, which easily extends to some general class of tangles which we do not specify here other than to say that it includes all knots. {\bf Model Theorem.} {\em If $K$ is an $n$-crossing $S$-component tangle (where $S$ is a finite set) then $z(K)\in\calU^{\otimes S}$ and \[ z(K) = \bbO\left(\omega\exp\left( \sum_{i,j\in S}\lambda_{ij}t_ia_j + \sum_{i,j\in S}q_{ij}y_ix_j + \sum_{d=1}^k P_d\epsilon^d \right)\right), \] where $\lambda_{ij}\in\bbZ$, where $\omega$ and $q_{ij}$ are rational functions in $T_i\coloneqq\bbe^{t_i}$ with numerators and denominators of degrees bounded by $n$, and where the $P_d$'s are ``perturbations'' which are polynomials in variables $\{y_i,a_i,x_i\}$ of degree at most $4d$, with coefficients rational functions in the $T_i$'s with numerators and denominators of degrees bounded by $n$.\footnote{The actual degree bounds we have are stronger than indicated here, though a bit harder to state. Stronger degree bounds imply faster computations.} } The formula for $z(K)$ appears complicated, but in some technical sense, it is in fact simple. Indeed if all the $T_i$ are identified (setting $T_i=T_j$ for all $i,j\in S$), then the space $\calF(S)$ of all formulas as in the theorem is of ``poly-size'' --- such a formula is determined by a finite number of integer coefficients and the number of coefficients required is a polynomial in $n$ and in $|S|$. The fact that $\calF(S)$ is poly-size suggests that the operations one needs to perform on $\calF(S)$ to compute $z(K)$ (mostly, multiplication of different tensor factors) would take poly-time. We show that this is indeed the case, and hence $z(K)$ is poly-time computable. {\bf What goes in the proof?} Some ``classical algebra'' PBW-reordering techniques to carry out the required operations on $\calF(S)$, some ``quantum algebra'' techniques to find $R$ and $C$ in a certain quantization of $\calU$, and a little bit of extra work to pull $R$ and $C$ from the quantized world to the classical one, in which our model theorem is written. In the case where $k=1$, this isn't just ``theory'' --- the programs are written and are quite short, and the results are tabulated and are quite strong; see e.g.~\cite{Bar-Natan:GWU-1612, PP1}. For $k>1$ we are very near a complete implementation. It is not much more complicated, and the results should be more powerful. The generalization to $\frakg$ other than $sl_2$ is in sight, yet will require more work. \vskip 5mm \noindent{\bf Frequently Asked Questions.} \begin{itemize} \item {\em What is the relationship between this proposal and the work of Rozansky and Overbay?} Our invariants are the Rozansky-Overbay~\cite{Ro, Rozansky:Burau, Rozansky:U1RCC, Overbay:Thesis} invariants, and in many ways our work is a continuation of theirs, though we believe our techniques are cleaner and more easily susceptible to generalization. Rozansky and Overbay did not note that their invariants are computable in polynomial time, and did not explain how to generalize them to the case of tangles. The latter generalization allows for divide-and-conquer computations which lead to a significant speedup, and is crucial if one attmpts to relate invariants to topological properties such as the genus and the ribbon property (e.g.~\cite{K17}). \item {\em What is the relationship between these invariants and the coloured Jones polynomial?} The totality of all $sl_2^{\leq k}$ invariants is most likely equivalent to the coloured Jones polynomial; incrementing $k$ by one should correspond to the consideration of one further diagonal in the Melvin-Morton-Rozansky expansion of the coloured Jones polynomial~\cite{MelvinMorton:Coloured, Bar-NatanGaroufalidis:MMR}. In some sense, as indicated already in the ``summary'' section of this proposal, we merely find a computable ``corner'' of a known and very-difficult-to-compute theory. We believe computability makes a huge difference! Note also that there isn't a good Melvin-Morton-Rozansky expansion for tangles, and tangles are crucial from our perspective. \item {\em What is the relationship between this proposal and the ``loop expansion'' of the Kontsevich integral?} The ``loop expansion''~\cite{GaroufalidisRozansky:LoopExpansion} of the Kontsevich integral is an all-Lie-algebra universal version of the Melvin-Morton-Rozansky expansion, and it should relate to the invariants we discuss in accordance with that --- for any semi-simple $\frakg$, the $\frakg^{\leq k}$ should be ``$k$-loop invariants''. Yet again, the ``loop expansion'' is nearly impossible to compute and its generalization to tangles depends on a choice of a Drinfel'd associator, which is another hard-to-compute object. \end{itemize} \vskip 5mm \noindent{\bf Our proposed research.} Much remains to be done, and I plan to do it over the grant period: \begin{itemize} \item Our present implementation of the algorithm for the $sl_2^{\leq 1}$ invariant is pathetic; it has the right asymptotic behavior, but the constants are all wrong, by factors of thousands. This should be improved. \item The implementation work in the case of $k>1$ has to be completed. \item An excellent exposition for the case $\frakg=sl_2$ and for general $k$ should be written. \item Everything should be generalized and implemented for Lie algebras beyond $sl_2$. If $\frakg$ is of rank $r$, meaning its Cartan subalgebra $\frakh$ is $r$-dimensional, then our invariants should become a (computable) polynomials in $r$ variables! \item Our tabulations so far (e.g.~\cite{Bar-Natan:GWU-1612}) show that the $k=1$ invariant for $sl_2$, $\rho_1(K)$, yields a bound on the genus $g(K)$ of $K$: it seems that always $\deg\rho_1(K)\leq 2g(K)-1$, and that that bound is independent of the bound obtained from the Alexander polynomial. I think I know why this is so, and why there should be a ``Seifert surface formula'' for $\rho_1(K)$, but this has to be rigorously confirmed. \item As indicated in~\cite{K17}, there is a potential for a relationship between these invariants, in particular $\rho_1$, and ribbon knots and the ribbon$=$slice conjecture. This should be pursued. \item There is some tension within our work between classical universal enveloping algebras and quantized ones: operations of $\calF(S)$ are easier to describe in classical language, yet the crucial elements $R$ and $C$ are easier to describe in the quantum language. Our current solution is to use an isomorphism between the two languages (an analog of the non-canonical algebra-structure-only isomorphism $\calU(\frakg)\llbracket\hbar\rrbracket\simeq\calU_\hbar(\frakg)$) to push/pull structures from one side to the other. We expect that a better understanding of this tension will eventually arise, and with it a better understanding of quantum groups as they appear in knot theory.\footnote{Perhaps a footnote isn't the right place to raise a major issue, yet I believe we don't genuinely understand the relationship between quantum groups and knot theory: if we know quantum groups we know how to make knot invariants, but the relationship should also go the other way. One has to be able to start with ``we want knot invariants'' and be lead to the specific formulas appearing in the quantizations of semi-simple Lie algebras. The narrative for the latter direction, as it stands now, is far from complete. It is hard to expect that our work in itself will change this situation. Yet we must hover around these issues if we ever want to fully understand them, and this we do.} \item The relationship between the story presented here and the ``loop expansion'' of the Kontsevich integral (e.g.~\cite{GaroufalidisRozansky:LoopExpansion}) should be studied. \item More generally, there may be more to say about poly-time computations in knot theory (e.g.~\cite{Przytycki:Vertigan, Fiedler:1Cocycle}). I intend to contribute in these directions as well. \item While these topics are largely untouched within this proposal, I intend to continue working as time will allow on the topics of my previous NSERC research proposal, ``Knot Theory, Algebra, and Higher Algebra'', \cite{Bar-Natan:Discovery-12, Bar-NatanSelmani:MetaMonoids, KBH, WKO1, WKO2, WKO3, WKO4}. \end{itemize} \end{multicols} \eject \pagestyle{empty} \par\noindent{\large\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Proposal Budget Justification} \vskip 2mm \begin{multicols}{2} {\bf Salaries and Benefits.} Since 2011 I have graduated 5 PhD students (Peter Lee, Karene Chu, Zsuzsanna Dancso, Oleg Chterental, and Iva Halacheva). I am presently working with three more (Huan Vo, Travis Ens, and Robin Gaudreau). I plan to support each of those at around \$8,000 per year. In addition I've had a number of master's students, I expect to have about two more per year, and to support each at about \$4,000 per year. Likewise I've taken a number of undergraduate ``summer project'' students, and I hope to support about two such students per year, at about \$2,000 each. I hope to be able to support a postdoctoral fellow throughout the grant period, at about \$40,000 per year. {\bf Equipment or Facility.} Many of my past projects required massive computations, often running for months at a time (e.g., the calculation of all the invariants appearing on the Knot Atlas, \url{http://katlas.org}), and many of the results are made available by means of a dedicated web server, \url{http://drorbn.net}, especially \url{http://drorbn.net/ap}. My current proposal will clearly lead me to continue using computers in a similar way. This will be a lot more effective if I would be able to purchase and maintain current hardware. Hence the \$2,500 allocated per year for purchase or rental of computers and peripherals, and the \$500 allocated per year for the maintenance of those. Also, I will have to pay user fees for some of the programs I will be using (Mathematica, for example) and also to some shared facilities to be provided by my university --- internet connection, backup services, etc. I am requesting an amount of \$1,500 per year for these purposes. {\bf Materials and Supplies.} This amount of \$500 per year will be used primarily to purchase office supplies and printer paper and ink. {\bf Travel.} In the past I have traveled extensively and gave presentations on my work in a large number of domestic and foreign universities and in many international conferences. I presume this will continue throughout the years of my contract. In addition I hope to support some travel by my graduate students and postdoctoral fellows, and to support visits by my scientific collaborators to Toronto. I am requesting an amount of \$8,000 per year for these purposes. {\bf Books.} Needs no explain. \end{multicols} \eject \setcounter{page}{1} \pagestyle{normal} \par\noindent{\large\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Proposal References} \vskip 2mm \begin{multicols}{2} {\renewcommand{\section}[2]{}% \begin{thebibliography}{} \bibitem[Al]{Alexander:TopologicalInvariants} J.~W.~Alexander, {\em Topological invariants of knots and links,} Trans.\ Amer.\ Math.\ Soc.\ {\bf 30} (1928) 275--306. \bibitem[BN1]{Bar-Natan:OnVassiliev} D.~Bar-Natan, \href{\myurl/papers/OnVassiliev/}{{\em On the Vassiliev Knot Invariants,}} Topology {\bf 34} (1995) 423--472. (Reported at the prestigious S\'eminaire Bourbaki. See P.~Vogel, {\em Invariants de Vassiliev des n\oe uds [d'apr\`es D.~Bar-Natan, M.~Kontsevich et V.~A.Vassiliev],} S\'eminaire Bourbaki {\bf 761} (1993) 1--17 \& Asterisque {\bf 216} (1993) 213--232). \bibitem[BN2]{Bar-Natan:Polynomial} D.~Bar-Natan, \href{\myurl/LOP.html#Polynomial}{{\em Polynomial Invariants are Polynomial,}} Mathematical Research Letters {\bf 2} (1995) 239--246. \bibitem[BN3]{Bar-Natan:FastKh} D.~Bar-Natan, \href{\myurl/papers/FastKh/}{{\em Fast Khovanov Homology Computations,}} Journal of Knot Theory and its Ramifications {\bf 16-3} (2007) 243--255. \bibitem[BN4]{Bar-Natan:Discovery-12} D.~Bar-Natan, {\em Knot Theory, Algebra, and Higher Algebra,} NSERC Discovery grant proposal, 2012, \web{d12}. \bibitem[BN5]{KBH} D.~Bar-Natan, {\em \href{http://www.math.toronto.edu/~drorbn/papers/KBH/}{Balloons and Hoops and their Universal Finite Type Invariant, BF Theory, and an Ultimate Alexander Invariant,} } Acta Mathematica Vietnamica {\bf 40-2} (2015) 271--329, \arXiv{1308.1721}. \bibitem[BN6]{WKO4} D.~Bar-Natan, {\em Finite Type Invariants of W-Knotted Objects IV: Some Computations,} in preparation, \web{wko4}, \arXiv{1511.05624}. \bibitem[BN7]{Bar-Natan:Qinhuangdao-1507} D.~Bar-Natan, {\em Polynomial Time Knot Polynomials,} conference talks in Qinhuangdao and Aarhus, July 2015. Handouts and video at \web{q15} and \web{a15}. \bibitem[BN8]{Bar-Natan:LesDiablerets-1608} D.~Bar-Natan, {\em The Brute and the Hidden Paradise,} conference talk at Les Diablerets, August 2016. Handout and video at \web{ld16}. \bibitem[BN9]{Bar-Natan:Indiana-1611} D.~Bar-Natan, {\em A Poly-Time Knot Polynomial Via Solvable Approximation,} talk at Indiana University, November 2016. Handout and video at \web{ind}. \bibitem[BN10]{Bar-Natan:GWU-1612} D.~Bar-Natan, {\em On Elves and Invariants,} Conference talk at George Washington University, December 2016. Handout and video at \web{gwu}. \bibitem[BN11]{K17} D.~Bar-Natan, {\em Polynomial Time Knot Polynomial,} research proposal for the 2017 Killam Fellowship, \web{k17}. \bibitem[BN12]{Bar-Natan:Toulouse-1705} D.~Bar-Natan, {\em The Dogma is Wrong,} Conference talk in Toulouse, May 2017. Handout and video at \web{Toulouse}. \bibitem[BND1]{WKO1} D.~Bar-Natan and Z.~Dancso, \href {http://drorbn.net/AcademicPensieve/Projects/WKO1} {{\em Finite Type Invariants of W-Knotted Objects I: W-Knots and the Alexander Polynomial,}} Alg.\ and Geom.\ Top.\ {\bf 16-2} (2016) 1063--1133, \arXiv{1405.1956}. \bibitem[BND2]{WKO2} D.~Bar-Natan and Z.~Dancso, \href {http://drorbn.net/AcademicPensieve/Projects/WKO2} {{\em Finite Type Invariants of W-Knotted Objects II: Tangles and the Kashiwara-Vergne Problem,}} Math.\ Ann.\ {\bf 367} (2017) 1517--1586, \arXiv{1405.1955}. \bibitem[BND3]{WKO3} D.~Bar-Natan and Z.~Dancso, {\em Finite Type Invariants of W-Knotted Objects III: Double Tree Construction,} in preparation, \web{wko3}. \bibitem[BNG]{Bar-NatanGaroufalidis:MMR} D.~Bar-Natan and S.~Garoufalidis, {\em On the Melvin-Morton-Rozansky Conjecture,} Inventiones Mathematicae {\bf 125} (1996) 103--133, \web{mmr}. \bibitem[BNS]{Bar-NatanSelmani:MetaMonoids} D.~Bar-Natan and S.~Selmani, {\em Meta-Monoids, Meta-Bicrossed Products, and the Alexander Polynomial,} Journal of Knot Theory and Its Ramifications {\bf 22-10} (2013), \web{BNS}. \bibitem[BV1]{PP1} D.~Bar-Natan and R.~van~der~Veen, {\em A Polynomial Time Knot Polynomial,} \arXiv{1708.04853}. \bibitem[BV2]{PPSA} D.~Bar-Natan and R.~van~der~Veen, {\em Poly-Time Knot Polynomials Via Solvable Approximations,} in preparation, \web{BV2}. \bibitem[ES]{EtingofSchiffman:QuantumGroups} P.~Etingof and O.~Schiffman, {\em Lectures on Quantum Groups,} International Press, Boston, 1998. \bibitem[Fi]{Fiedler:1Cocycle} T.~Fiedler, {\em Knot Polynomials from 1-Cocycles,} \arXiv{1709.10332}. \bibitem[FM]{FoxMilnor:Singularities} R.~H.~Fox and J.~W.~Milnor, {\em Singularities of 2-Spheres in 4-Space and Cobordism of Knots,} Osaka J.\ Math.\ {\bf 3} (1966) 257--267. \bibitem[GR]{GaroufalidisRozansky:LoopExpansion} S. Garoufalidis and L. Rozansky, {\em The Loop Expansion of the Kontsevich Integral, the Null Move and $S$-Equivalence,} Topology {\bf 43} (2004) 1183--1210, \arXiv{math.GT/0003187}. \bibitem[HOMFLY]{HOMFLY} J.~Hoste, A.~Ocneanu, K.~Millett, P.~Freyd, W.~B.~R.~Lickorish, and D.~Yetter, {\em A new polynomial invariant of knots and links,} Bull.\ Amer.\ Math.\ Soc.\ {\bf 12} (1985) 239--246. \bibitem[Jo]{Jones:New} V.~F.~R. Jones, {\em A polynomial invariant for knots via von Neumann algebras,} Bull.\ Amer.\ Math.\ Soc.\ {\bf 12} (1985) 103--111. \bibitem[MM]{MelvinMorton:Coloured} P.~M.~Melvin and H.~R.~Morton, {\em The coloured Jones function,} Comm.\ Math.\ Phys.\ {\bf 169} (1995) 501--520. \bibitem[Oh]{Ohtsuki:QuantumInvariants} T.~Ohtsuki, {\em Quantum Invariants,} Series on Knots and Everything {\bf 29}, World Scientific 2002. \bibitem[Ov]{Overbay:Thesis} A.~Overbay, {\em Perturbative Expansion of the Colored Jones Polynomial,} University of North Carolina PhD thesis, \web{Ov}. \bibitem[Pr]{Przytycki:Vertigan} J.~H.~Przytycki, {\em The First Coefficient of Homflypt and Kauffman Polynomials: Vertigan Proof of Polynomial Complexity using Dynamic Programming,} \arXiv{1707.07733}. \bibitem[PT]{PrzytyckiTraczyk:PT} J.~H.~Przytycki and P.~Traczyk, {\em Conway Algebras and Skein Equivalence of Links,} Proc.\ Amer.\ Math.\ Soc.\ {\bf 100} (1987) 744--748. \bibitem[Ro1]{Ro} L.~Rozansky, {\em A contribution of the trivial flat connection to the Jones polynomial and Witten's invariant of 3d manifolds, I,} Comm.\ Math.\ Phys.\ {\bf 175-2} (1996) 275--296, \arXiv{hep-th/9401061}. \bibitem[Ro2]{Rozansky:Burau} L.~Rozansky, {\em The Universal $R$-Matrix, Burau Representation and the Melvin-Morton Expansion of the Colored Jones Polynomial,} Adv.\ Math.\ {\bf 134-1} (1998) 1--31, \arXiv{q-alg/9604005}. \bibitem[Ro3]{Rozansky:U1RCC} L.~Rozansky, {\em A Universal $U(1)$-RCC Invariant of Links and Rationality Conjecture,} \arXiv{math/0201139}. \end{thebibliography}} \end{multicols} \eject \pagestyle{empty} \par\noindent{\large\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Proposal HQP Training Plan} \vskip 2mm My project can be naturally broken into several parts, and there are many offshoot directions starting from my main proposal. This means that there is ample room for advanced undergraduate students, for graduate students, and for postdoctoral fellows to take part in the research outlined in my proposal and/or in closely related research. This allowed me to participate in the training of many students and fellows in the past, and will continue to allow me to do the same in the future. I share my significant use of computers as a tool for research, presentation and dissemination of knowledge with my students and postdoctoral fellows. I believe this adds major further quality to the training they receive. Though frankly, I still don't know how to do the thing I'd really want to do. For me, the best mathematics is the math that can be implemented on a computer. This ranges from the simplest, say Gaussian elimination or the Fibonacci sequence, and continues all the way to the fanciest and most abstract, be it a planar-algebra category-theory ultra-fast computation of Khovanov homology or a free-Lie-algebra meta-group-action-based computation of a non-commutative generalization of the Alexander polynomial. I've implemented these, as well as a dozen other versions of the Alexander polynomial, and a dozen other knot invariants, and a very large number of other little things within knot theory, and a computer solution of the Rubik's cube, and a hyperbolic-geometry based algorithm for optimal camera motion, and I made computer generated pictures of various fancy links and surfaces and of steps within Arnold's resolution of Hilbert's 13th problem, and very many other things, big and small. (And most are on my web site). For me, that's what keeps mathematics alive and sincere and believable (and when it comes to the graphics, sometimes also visually beautiful). I wish I knew how to teach my students to actually compute (and draw!) what they are talking about, and gain the benefit that that entails, and pass it on to their students later on. I wish they would do it routinely and often, and with joy. I think I've contributed some, and I hope to contribute further, to my students by sharing with them my love of the implementable (and teaching a bit of the how-to). In 5-10 years I will know how many have become truly passionate. \vfill \par\noindent{\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Relationship to Other Research Support} \vskip 2mm I currently receive no other research support. Along with Thomas Fiedler of the University of Toulouse I am applying for a small France-Canada Research Fund (FCRF) grant (\$14,800 over two years, split between the two of us). If approved the money will mostly be used for travel between Toulouse and Toronto for Fiedler and myself and our students, to collaborate on a computer implementation of Fiedler's theory of ``1-cocycle invariants'' (\arXiv{1709:1033}). It is not known if his invariants are related to the ones outlined in this proposal. \vfill \eject \par\noindent{\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Most Significant Contributions} \vskip 2mm My paper {\bf Balloons and Hoops and their Universal Finite Type Invariant, BF Theory, and an Ultimate Alexander Invariant} (attached and Acta Mathematica Vietnamica 40-2 (2015) 271--329, \arXiv{1308.1721}) explains how to turn knotted objects in 3 dimensions, namely ordinary knots and tangles, into knotted objects in 4 dimensions, namely knotted 2-spheres (``balloons'') with 1-dimensional circles (``hoops'') knotted among them. The paper then constructs a universal invariant $Z$ (in the finite type sense) of such ``knotted balloons and hoops'' and finds that it is valued in a certain space whose components are free Lie algebras and spaces of cyclic words. The paper gives complete computational techniques for the computation of $Z$, along with the sophisticated mathematics that leads there and along with a complete implementation. As explained in the paper, the resulting invariant $Z$ is related to the 4-dimensional BF topological quantum field theory, and it has a reduction which in itself is a generalization of the Alexander polynomial to tangles which, as explained in the paper, yields the ``best'' formulas we have for the Alexander polynomial. My paper {\bf Finite Type Invariants of W-Knotted Objects II: Tangles and the Kashiwara-Vergne Problem} (joint with my former student Zsuzsanna Dancso, attached and Mathematische Annalen 367 (2017) 1517--1586, \arXiv{1405.1955}) explains how the construction of a universal finite type invariant of certain ``knotted foams in 4-dimensional space'' is equivalent to the solution of the Kashiwara-Vergne conjecture, which in itself is about the relationship between the convolution algebra of functions on a Lie group and the convolution algebra of functions on its Le algebra. This equivalence, along with the Satoh ``tube map'' from 3-dimensional knot theory to 4-dimensional knot theory, gives a topological explanation for the relationship between Drinfel'd associators and solutions of the Kashiwara-Vergne equations, as discovered earlier by Alekseev-Torossian and Alekseev-Enriquez-Torossian. My preprint {\bf Finite Type Invariants of w-Knotted Objects IV: Some Computations} (attached and \arXiv{1511.05624} presents a complete framework for computations in free Lie algebras and related algebraic spaces, leading in particular to a computation of the BCH formula to the highest degree known, of a Drinfel'd associator to the highest degree known, and of a solution of the Kashiwara-Vergne problem to the highest degree known. I see lecturing and the assimilation of mathematical knowledge and the exposition of its beauty as one of my primary goals. I aim to polish my lectures to perfection; almost every lecture I give comes with a colourful handout summarizing the information in it, and with a web space with links to said handout, to relevant papers and programs, and almost always, with a link to a video recording of the talk itself. My 4th attached contribution is merely a reminder of that --- an abridged version of my {\bf Handout Portfolio} (the full version is at \url{http://drorbn.net/hp}). \vfill \par\noindent{\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant 4 Samples of Research Contributions} \vskip 2mm See \web{kbh}, \web{wko2}, \web{wko4}, and \web{hp}. \vfill \eject \par\noindent{\large\bf Poly-Time Knot Theory and Quantum Algebra \hfill Discovery Grant Proposal To Do List} \vskip 2mm \begin{itemize} \item Clear this list and remove this page. \item Is there some big-name-quote along the lines of ``computable better than not''? \item Additional Information on Contributions (2500 characters, TXT). \item Attach CCV. \item Reread instructions pages. \end{itemize} \end{document}