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 - two-dimensional 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 it's an even number and you're currently going over the crossing, negate that even number. Finally, pick the even numbers corresponding to 1, 3, 5, etc.
Let's try an example:
Taken with permission from wikimedia user Czupirek
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. We negate the even numbers corresponding to strands that go over a crossing, 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 D\rangle\$, 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^2-A^{-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+A-A^3\$, as a list of coefficient-exponent pairs (or exponent-coefficient 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 odd-length list of coefficients correspondings to exponents \$-k\ldots k\$ for some \$k\in \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 code-golf 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
// 4-tuples of [dowker_notation, crossing_signs, expected_result, description]
[
[[],[],[[1,0]],"unknot"],
[[2],[1],[[-1,3]],"unknot with a half-twist (positive crossing)"],
[[2],[-1],[[-1,-3]],"unknot with a half-twist (negative crossing)"],
[[2,4],[1,1],[[1,6]],"unknot with two half-twists (positive crossings)"],
[[4,6,2],[1,1,1],[[1,-7],[-1,-3],[-1,5]],"right-handed trefoil knot, 3_1"],
[[4,6,2,8],[-1,1,-1,1],[[1,-8],[-1,-4],[1,0],[-1,4],[1,8]],"figure-eight 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]],"three-twist 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 identical trefoils)"],
[[4,6,2,-10,-12,-8],[1,1,1,1,1,1],[[1,-14],[-2,-10],[1,-6],[-2,-2],[2,2],[1,10]],"square knot (sum of two mirrored 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:
thanks @ChasBrown and @H.Pwiz for catching a mistake in my definition of Dowker notation