Bounty: 500
Given the Dowker notation of a knot and its crossing signs, calculate its bracket polynomial.
Although there are more technical definitions, for this challenge it is enough to think of a knot as something made physically by attaching the two ends of a string together. Since knots exist in three dimensions, when we draw them on paper, we use knot diagrams – twodimensional projections in which the crossings are of exactly two lines, one over and one under.
Here (b) and (c) are different diagrams of the same knot.
How do we represent a knot diagram on paper? Most of us aren’t Rembrandt, so we rely on Dowker notation, which works as follows:
Pick an arbitrary starting point on the knot. Move in an arbitrary direction along the knot and number the crossings you encounter, starting from 1, with the following modification: if the crossing already has an assigned number and the new number is even and you’re currently going over the crossing, then negate that even number. Finally, pick the even numbers corresponding to 1, 3, 5, etc.
Let’s try an example:
On this knot, we chose “1” as our starting point and proceeded to move up and to the right. Every time we go over or under another piece of the rope, we assign the crossing point the next natural number. Thus, each crossing acquires a pair of natural numbers. If we’re going over and the crossing already has one number assigned and the second encounter corresponds to an even number, we negate it, for example [3,12]
in the diagram. So, this diagram would be represented by [[1,6],[2,5],[3,12],[4,9],[7,8],[10,11]]
. Listing the buddies of 1, 3, 5, 7, etc gives us [6,12,2,8,4,10]
.
There are a few things to note here. First, the Dowker notation is not unique for a given knot, as we can choose an arbitrary starting point and direction. But, given the notation, one can fully determine the structure of the knot (technically, up to reflection of its prime knot components). While not all Dowker notations can form possible knots, in this problem you can assume that the input represents an actual knot.
To avoid the ambiguity between a knot’s reflections, and to make the challenge easier to solve, you will also be given a list of crossing signs as input.
In a positive crossing the lower line goes to the left from the point of view of the upper line. In a negative crossing it goes to the right. Note that reversing the direction of going around the knot (i.e. reversing both the over line and under line) doesn’t change the crossing signs. In our example the crossing signs are [1,1,1,1,1,1]
. They are given in the same order as the Dowker notation, i.e. for crossings numbered 1, 3, 5, 7, etc.
In this challenge we will be calculating the bracket polynomial of a knot. It’s an object that is invariant across most transformation of the knot diagram – a concept which makes it supremely useful in knot theory analysis. (Again, most knot theorists compute the bracket polynomial as an intermediate product on their way to computing the Jones polynomial, which is invariant across all transformations, but we will not be doing that.) So how does it work? The bracket polynomial is a Laurent polynomial – one in which the variable (traditionally named $A$) can be raised to negative powers, as well as positive.
For a given knot diagram $D$, the three rules for the polynomial, represented as $langle Drangle$, are:
 A sole loop without any crossings has polynomial 1.
 If we have a diagram consisting of $D$ and a loop disconnected from $D$, the polynomial for both is the polynomial for $D$ times $(A^2A^{2})$.

This rule is the trickiest. It says that if you have a crossing in $D$ that looks like , then you can use this rule to simplify the knots in two different ways:
In the image above, the outlined crossing in the first diagram, which is of the form , can be transformed into as in the second figure (a.k.a. positive smoothing), or as in the third figure (negative smoothing).
So, the bracket polynomial of the first diagram is the bracket polynomial of the second times $A$ plus the third times $A^{1}$, i.e.,
Confused yet? Let’s do an example, trying to find the bracket polynomial of (Note: this is two knots linked together. This sort of diagram will not be a potential input in this challenge since the inputs will only be single knots, but it may appear as an intermediate result in the algorithm.)
We first use rule 3
We use rule 3 again on both of the new knots
We substitute these 4 new knots into the first equation.
Applying rules 1 and 2 to these 4 tell us
So, this tell us
Congrats on completing your brief intro to knot theory!
Input
Two lists:
 Dowker notation, e.g.
[6,12,2,8,4,10]
. Numbering of the crossings must start from 1. The corresponding odd numbers[1,3,5,7,...]
are implicit and must not be provided as input. 
Signs (
1
/1
or if you prefer0
/1
orfalse
/true
or'+'
/''
) for the crossings corresponding to the Dowker notation, e.g[1,1,1,1,1,1]
.
Instead of a pair of lists, you could have a list of pairs, e.g. [[6,1],[12,1],...
Output
Print or return the polynomial, for instance $A^{2}+5+AA^3$, as a list of coefficientexponent pairs (or exponentcoefficient pairs) in increasing order of the exponents and without any zero coefficients, e.g. [[1,2],[5,0],[1,1],[1,3]]
.
Alternatively, output an oddlength list of coefficients correspondings to exponents $kldots k$ for some $kin mathbb{N}$, e.g. [0,1,0,5,1,0,1]
. The central element is the constant term (coefficient before $A^0$). The leftmost and rightmost elements must not be both 0.
Rules
This is a codegolf challenge. None of the standard loopholes can be used, and libraries that have tools to calculate either Dowker notations, or Bracket polynomials, cannot be used. (A language that contains these libraries still can be used, just not the libraries/packages).
Tests
// 4tuples of [dowker_notation, crossing_signs, expected_result, description]
[
[[],[],[[1,0]],"unknot"],
[[2],[1],[[1,3]],"unknot with a halftwist (positive crossing)"],
[[2],[1],[[1,3]],"unknot with a halftwist (negative crossing)"],
[[4,2],[1,1],[[1,6]],"unknot with two halftwists (positive crossings)"],
[[4,6,2],[1,1,1],[[1,7],[1,3],[1,5]],"righthanded trefoil knot, 3_1"],
[[4,6,8,2],[1,1,1,1],[[1,8],[1,4],[1,0],[1,4],[1,8]],"figureeight knot, 4_1"],
[[6,8,10,2,4],[1,1,1,1,1],[[1,7],[1,1],[1,5],[1,9],[1,13]],"pentafoil knot, 5_1"],
[[6,8,10,4,2],[1,1,1,1,1],[[1,11],[1,7],[2,3],[1,1],[1,5],[1,9]],"threetwist knot, 5_2"],
[[4,8,10,2,12,6],[1,1,1,1,1,1],[[1,12],[2,8],[2,4],[3,0],[2,4],[2,8],[1,12]],"6_3"],
[[4,6,2,10,12,8],[1,1,1,1,1,1],[[1,10],[2,2],[2,2],[1,6],[2,10],[1,14]],"granny knot (sum of two trefoils)"],
[[6,12,2,8,4,10],[1,1,1,1,1,1],[[1,2],[1,6],[1,10]],"example knot"]
]
External resources
Not necessary for the challenge, but if you are interested: