POLYNOMIAL INVARIANTS ARE POLYNOMIAL

DROR BAR-NATAN

This edition: June 20, 1995; First edition: December 30, 1994.

Abstract. We show that (as conjectured by Lin and Wang) when a Vassiliev invariant of type m is evaluated on a knot projection having n crossings, the result is bounded by a constant times n^{m}. Thus the well known analogy between Vassiliev invariants and polynomials justifies (well, at least explains) the odd title of this note.

Contents

1. Introduction 1 1.1. Acknowledgement

2. The method of proof 2

3. Proof of Lemma 1 3 3.1. A reduction to SubLemmas. 3.2. Proofs of the SubLemmas.

References 7

1. Introduction

Let V be a fixed Vassiliev knot invariant of type m with values in some normed vector space (see e.g. [1, 2, 3, 4, 5, 6, 8, 9]). The purpose of this note is to prove the following three theorems:

Theorem 1. If K is a knot with a large number n of crossings (in some planar projection), then V (K) can be computed (in terms of V of finitely many fixed knots) in O(n^{m}) computational steps.

This work was supported by NSF grant DMS-92-03382. Published in Mathematical Research Letters, 2 (1995) 239–246, and is available via anony-

mous file transfer from ftp.math.harvard.edu, user name ftp, subdirectory dror. Read the file README first. For easier access, point your WWW browser at http://www.math.harvard.edu/

HTML/Individuals/Dror Bar-Natan.html.

Theorem 2. If K is a knot with a large number n of crossings (in some planar projection), then V (K) is bounded by Cn^{m} for some fixed constant C.

Theorem 3. If K is a (singular) knot with k double points and a large number n of crossings (in some planar projection), then V (K) is bounded by C_{k}n^{m−k} for some fixed constants C_{k}.

We will only prove theorem 3. Theorem 2 follows from theorem 3 by setting k = 0, and theorem 1 can be proven by making all the steps of our proof effective.

Theorem 2 was stated as a conjecture in [7], where Lin and Wang commented that it can be interpreted as saying that polynomial invariants grow polynomially. Simply recall that in [1] an analogy was made between Vassiliev invariants and polynomials.

Remark 1.1. With little additional effort one can generalize the results of this note to links, tangles, etc.

Remark 1.2. It is rather easy to show that V (K) is bounded by a polynomial of degree 2m or 3m in the number of crossings n, and that it is computable in a (highdegree) polynomial time, as stated in [6]. For example, one can use the combinatorial formulas for a universal Vassiliev invariant in terms of a Drinfel’d associator to find such bounds, or one may argue along the same lines of this paper but with a little less care about the bounds in Lemma 1. I found the proof of the much more pleasing degree m bound for a type m invariant to be somewhat trickier than expected, as presented in this note.

1.1. Acknowledgement. I would like to thank P. Etingof, Y. Karshon, X-S. Lin, A. Referee, and J. Wunsch for their comments and suggestions, X-S. Lin and Z. Wang for suggesting the problem in their paper [7], and D. Zeilberger for his contributions to the theory of SubSubLemmas ([10]). I am the littlest of his disciples.

2. The method of proof

For a technical reason (see remark 3.3), we prefer to work with knots parametrized by a parameter s ∈ R (rather than s ∈ S^{1}) and extending from the point (−∞, 0, −∞) to the point (∞, 0, ∞) (in some appropriate compactification of R^{3}). If no double points are allowed, this theory of knots is equivalent to the usual theory of knots parametrized by a circle.

For any chord diagram D of degree at most m choose a singular knot K_{D} representing it (see e.g. [1]), and fix these representatives once and for all. It is well known (see e.g. [2, 3, 8, 9]) that V is determined by its type m and its values on all the K_{D}’s. This is proven for singular knots with k double points (“k-singular knots”) by downward induction on k: If K is a singular knot with k > m double points then V (K) = 0 by the defining property of Vassiliev invariants. And if we know V (L) for every (k + 1)-singular knot L (for k <= m), we can compute V (K) for a k-singular knot K whose underlying chord diagram is D in terms of the V (L)’s and V (K_{D}).

Simply connect K to K_{D} via a path K(t) of singular knots that have exactly k double points at all times, with the exception of finitely many times where k+1 double points may occur. The usual rule for knots with double points (V ( ) = V ( ) − V ( )) and telescopic summation now show that V (K) − V (K_{D}) is a signed sum of the values of V on the (k + 1)-singular knots seen at the exceptional times.

As theorem 3 is trivial for k > m, the above paragraph suggests that theorem 3 can be proven for arbitrary k by downward induction on k. Clearly, the induction step (going from k + 1 to k) follows from the following Lemma:

Lemma 1. Let K_{0} and K_{1} be two k-singular knot projections with at most n crossings, having the same underlying degree k chord diagram. Then there exists a path of singular knot projections connecting K_{0} and K_{1}, along which there are only finitely many times in which the number of singular points grows to k + 1, and so that if you denote the (k + 1)-singular knot projections that you see along the way by L_{1}, …, L_{p}, then:

(1) p is bounded by a linear function of n, whose slope a_{k} depends only on k.

(2) The number of crossings in each of the L_{i}’s is bounded by a linear function of n, whose slope b_{k} depends only on k.

Indeed, let K be a k-singular knot projection with (a large number) n of crossings and D be its underlying chord diagram, and set K_{0} = K and K_{1} = K_{D}. There is no loss of generality in assuming that n is larger than the number of crossings in the fixed knot K_{D}. Pick a path as in the Lemma, and then by the induction hypothesis

|V (L_{i})| < C_{k+1}(b_{k}n)^{m−k−1}, (1 ≤ i ≤ p).

Thus by the discussion in the proceeding paragraph and the bound on p,

|V (K)| ≤ |V (K_{D})| + ∑_{i=1}^{p} |V (L_{i})| ≤ |V (K_{D})| + a_{k}b_{k}^{m−k−1}C_{k+1}n^{m−k},

and as there are only finitely many fixed K_{D}’s to consider, we find that there is a single constant C_{k} for which

|V (K)| < C_{k}n^{m−k}

for all k-singular knots K with (a large number) n of crossings.

3. Proof of Lemma 1

3.1. A reduction to SubLemmas. Let us start with some relevant definitions and SubLemmas.

Definition 3.1. We will say that a presentation of a singular knot K (that is, an appropriate immersion K = (K_{x}, K_{y}, K_{z}) : R → R^{3}) is almost monotone if it satisfies K_{z}(s) = s for all s ∈ R except in small neighborhoods of the double points. Notice that K visits each double point twice, once for a small value of the parameter s and once for a larger value of s. We also require that K_{z}(s) = s near those smaller s’s, and that near the larger values of s the knot simply makes a ‘vertical dive’ to meet the lower strand at the double point, and then climbs vertically up. Finally, we require that the projection of K to the xy-plane will fall entirely in the upper half plane {y > 0}, except perhaps the projections of small neighborhoods of some of the double points, which are allowed to extend just a bit into the lower half plane {y ≤ 0}. We say that the double points whose projections are in the lower half plane are exposed, and if all double points are exposed, we say that the (almost monotone) presentation K is fully exposed. See e.g. figures 1 and 2.

upper half plane lower half plane

Figure 1. The vertical projection of some almost monotone immersion having 3 double points, two of which exposed, and 3 additional crossings. On the right is the corresponding chord diagram.

z  s

Figure 2. K_{z} as a function of s for the immersion in figure 1.

Remark 3.2. The notion of “a fully exposed presentation” is the key to the proof of Lemma 1. Indeed, within the proof of SubLemma 1.3 below, we show that if two fully exposed presentations have the same underlying chord diagram and their (exposed) double points (which are in a 1 − 1 correspondence) are embedded in the same way, then the corresponding two singular knots are the same. In the three SubLemmas below we simply show that any singular knot presentation can be connected to a fully exposed one by a path which satisfies the conditions of Lemma 1.

SubLemma 1.1. If a k-singular knot K has n ≫ k crossings (in some projection), it can be transformed to an almost monotone knot (having the same chord diagram, of course) by a path of singular knots satisfying conditions (1) and (2) of Lemma 1.

SubLemma 1.2. If a k-singular knot presentation K has n ≫ k crossings and is almost monotone, it can be transformed to a fully exposed presentation (having the same chord diagram, of course) by a path of singular knots satisfying conditions (1) and (2) of Lemma 1.

SubLemma 1.3. If K_{0} and K_{1} of Lemma 1 have fully exposed presentations, the conclusion of that Lemma holds.

Clearly, SubLemmas 1.1–1.3 imply Lemma 1. Simply start from K_{0} and K_{1}, transform them to be fully exposed using SubLemma 1.1 and then SubLemma 1.2, and then use SubLemma 1.3 to connect the resulting two fully exposed presentations.

Remark 3.3. The equality K_{z}(s) = s in the definition of almost monotone knots is the reason why it is technically slightly easier to work with knots parametrized by an infinite line. On a circle, we’d have to choose some special point where K_{z} can dive down so as it can then rise back in a gradual way. Such a point will have to be given a special treatment, similar to that of the double points in SubLemma 1.2, creating some extra mess that we happily avoid. When dealing with links (as we don’t), this extra mess seems to be unavoidable.

3.2. Proofs of the SubLemmas.

Proof of SubLemma 1.1. Simply deform K_{z} to satisfy K_{z}(s) = s away from the double points while keeping the projection of K to the xy-plane in place. Along the way you pick some extra double points for crossings that originally were ‘the wrong way’ (and there are at most n of these), but you never increase the total number of crossings, so (1) and (2) of Lemma 1 hold. Then (if you’re not too tired), do some cosmetics near the double points to have the strands bounce down and up as they should.

To prove SubLemma 1.2, we first need

SubSubLemma 1.2.1. Let πK be the planar projection of a k-singular knot presentation as in SubLemma 1.2 (it is a planar graph with k + n vertices and 2(k + n) + 1 edges). There exists disjoint simple paths γ_{i} (called ‘exposing paths’) connecting the projections of the un-exposed double points of K to points in the lower half plane, so that:

• The γ_{i}’s miss all the vertices of πK.

• The total number of intersection points between the γ_{i}’s and the edges of πK is at most k(2(k + n) + 1).

Check figure 3 for an example.

Figure 3. A (somewhat odd) choice for an exposing path for the only un-exposed double point in the knot projection of figure 1.

Proof. Start with arbitrary paths that miss the vertices of πK and connect the projections of the un-exposed double points of K to points in the lower half plane. If any of these paths intersects any of the edges of πK more than once, at least one of these intersection points can be eliminated by traveling from one to the other along a ‘shorter’ path that follows the relevant edge:

The original γ_{i} A short cut with fewer intersections A part of πK

Doing as much as we can of that, we get a collection of paths, each of which intersecting each edge of πK at most once, to a total of at most k(2(k + n) + 1) intersections. But we may have created lots of intersections between the different paths and lots of self intersections. Eliminate these by moves like

,

and by throwing out closed loops when these are created as a move like above is applied to a self-intersection.

Proof of SubLemma 1.2. Choose exposing paths γ_{i} as in SubSubLemma 1.2.1, and pull the un-exposed double points (and small neighborhoods thereof) along them:

The bound supplied by SubSubLemma 1.2.1 on the number of intersections between the γ_{i}’s and the projection of K shows that conditions (1) and (2) of Lemma 1 hold.

Proof of SubLemma 1.3. The fact that K_{0} and K_{1} have the same underlying chord diagram implies that there is a natural correspondence between their k double points, and between the 4k strands emanating from these k double points in each of them. Ensure that these 4k strands on K_{1} enter the upper half plane in the same places as the corresponding ones for K_{0}. This can be done by permuting and rotating the k double points of K_{1}, at a cost (in the sense of conditions (1) and (2) of Lemma 1) proportional to k^{2}, not even linear in n. The new K_{1} is now the same knot as K_{0}. Indeed, we’ve just arranged things so that the restrictions πK′_{0} and πK′_{1} of their projections to the upper half plane are homotopically equivalent modulo the boundary. But both knots are almost monotone, and thus we can lift any homotopy that takes πK′_{0} to πK′_{1} to an isotopy taking K_{0} to K_{1}.

References

1. D. Bar-Natan, On the Vassiliev knot invariants, Topology 34 423–472 (1995).

2. J. S. Birman, New points of view in knot theory, Bull. Amer. Math. Soc. 28 (1993) 253–287.

3. & X-S. Lin, Knot polynomials and Vassiliev’s invariants, Inv. Math. 111 (1993) 225–270.

4. M. Gusarov, A new form of the Conway-Jones polynomial of oriented links, in Topology of manifolds and varieties (O. Viro, editor), Amer. Math. Soc., Providence 1994, 167–172.

5. , On n-equivalence of knots and invariants of finite degree, in Topology of manifolds and varieties (O. Viro, editor), Amer. Math. Soc., Providence 1994, 173–192.

6. M. Kontsevich, Vassiliev’s knot invariants, Adv. in Sov. Math., 16(2) (1993), 137–150.

7. X-S. Lin and Z. Wang, Integral geometry of plane curves and knot invariants, Columbia Univ. preprint, December 1994.

8. V. A. Vassiliev, Cohomology of knot spaces, Theory of Singularities and its Applications (Providence) (V. I. Arnold, ed.), Amer. Math. Soc., Providence, 1990.

9. , Complements of discriminants of smooth maps: topology and applications, Trans. of Math. Mono. 98, Amer. Math. Soc., Providence, 1992.

10. D. Zeilberger, Proof of the alternating sign matrix conjecture, Temple Univ. preprint, December Department of Mathematics, Harvard University, Cambridge, MA 02138 Current address: Institute of Mathematics, The Hebrew University, Giv’at-Ram, Jerusalem

91904, Israel E-mail address: dror@math.harvard.edu