A Knotty situation

Question

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:

1. A sole loop without any crossings has polynomial 1.

2. 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})\$.

3. 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 prefer 0/1 or false/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:

• A paper on Knot Polynomials

• A paper on Dowker Notation

---

sandbox posts: 1, 2

thanks @ChasBrown and @H.Pwiz for catching a mistake in my definition of Dowker notation

Answer 1

K (ngn/k), 196 193 bytes

{!N::2*n:#x;{+/d,'x,'d:&:'-2!(|/n)-n:#:'x}(+/1-2*s){j::+,/y;,/(&0|2*x;(-1+#?{x[j]&:x@|j;x}/!N){-(d,x)+x,d:&4}/,1;&0|-2*x)}'(N!{(x,'|1+x;x+/:!2)}'((2*!n),'-1+x|-x)@'0 1=/:x>0)@'/:+~(y<0)=s:!n#2}

Try it online!

Answer 2

Brain-Flak, 1316 bytes

(({})<({()<(({}<>))><>}){(({})[()()]<{([{}]({})<>({}<>))}{}(([({}<>)]<<>({}<>)<>((({})<<>{({}<>)<>}<>>))>)){({}<>)<>}<>{}(({}<{}(({}<{({}<>)<>}>))>))<>{({}<>)<>}>)}<>>){(({}){}()<({}<>)>)<>{}(({}){}<>)<>}<>{}{}(()){(<({}<({}<>)>)>)<>((){[()](<(({})<>){({}[({})]<>({}<>))}{}({}<>({}<{}<>{({}<>)<>}>)[()])<>({}({})[()])(([()]{()(<({}[({})]())>)}{})<{(<{}{}>)}{}><>{()((<({}()[({}<>)])<>>))}{}<{}{}>)((){[()]<({}()<({}<({}<<>({()<({}<>)<>>}<>){({}[()]<(({})<({()<({}<>)<>>})<>>)<>{({}[()]<<>({}<>)>)}{}>)}<>>)<>>)>)((){[()](<{}(({})<<>(({})<(<<>({}<<>({}<(()()){({}[()]<([{}]()<>)<>({}<<>{({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>>)}{}>{})>)>)<>{}{({}<>)<>}<>([({}<>)]<((()))>)(())<>({}<>)<>{}({}[()]){<>({}<<>(()()){({}[()]<({}<<>{({}<>)<>}>){({}[({})]<>({}<>))}{}(({})<<>({}<>)<>([{}])>)>)}{}{}>)<>({}<(({})())>[()]<>)}{}({}<<>{}([{}]()<{({}<>)<>}>){({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>{}{}{}>{})>)>)}{}){(<{}(({})<<>(({}{})<<>(<({}<>)>)<>{}{({}<>)<>}<>>(({}){}){})>)>)}>}{}){(<{}([{}]<({}<<>([{}]()<>)<>({}<<>{({}({})<>[({}<>)])}{}{}>){({}<>)<>}<>>({})({}){})>)>)}{}>)}{}){{}(([{}]){}<>{}{}<<>({}<>{}){([{}]({}()()<{}({}<>)(())<>>))}{}{}{}>{})(())<>{{}({}<>)(())<>}(<>)<>}{}}{}{}<>{}{}({}<{{}({}<>)(())<>}<>{{}{((<(())>))}{}}{}{{}({}<>)(())<>}>)<>{{}({}<(<()>)<>([]){{}({}<>)(())<>([])}{}>)<>{{}({}<>)<>}{}{}({}<>)<>}<>

Try it online!

I regret nothing. Input is a flattened list of pairs.

# Part 1: extract edges
(({})<

({()<(({}<>))><>}){

(({})[()()]<

{([{}]({})<>({}<>))}{}(([({}<>)]<<>({}<>)<>((({})<<>{({}<>)<>}<>>))>)){({}<>)<>}

<>{}(({}<{}(({}<{({}<>)<>}>))>))<>{({}<>)<>}

>)}

<>>){(({}){}()<({}<>)>)<>{}(({}){}<>)<>}<>

{}{}(())

# Part 2: Compute bracket polynomial
{

  # Move degree/sign to other stack
  (<({}<({}<>)>)>)<>

  # If current shape has crossings:
  ((){[()](<

    # Consider first currently listed edge in set
    # Find the other edge leaving same crossing
    (({})<>){({}[({})]<>({}<>))}{}

    # Move to top of other stack
    # Also check for twist
    ({}<>({}<{}<>{({}<>)<>}>)[()])

    # Check for twist in current edge
    <>({}({})[()])

    (

      # Remove current edge if twist
      ([()]{()(<({}[({})]())>)}{})<{(<{}{}>)}{}>

      # Remove matching edge if twist
      <>{()((<({}()[({}<>)])<>>))}{}<{}{}>

    # Push 1 minus number of twists from current vertex.
    )

    # If number of twists is not 1:
    ((){[()]<

      # While testing whether number of twists is 2:
      ({}()<

        # Keep sign/degree on third stack:
        ({}<({}<

          # Duplicate current configuration
          <>({()<({}<>)<>>}<>){({}[()]<(({})<({()<({}<>)<>>})<>>)<>{({}[()]<<>({}<>)>)}{}>)}

        # Push sign and degree on separate stacks
        <>>)<>>)

      # If number of twists is not 2: (i.e., no twists)
      >)((){[()](<{}

        # Make first copy of sign/degree
        (({})<<>(({})<

          # Make second copy of sign/degree
          (<<>({}<<>({}<

            # Do twice:
            (()()){({}[()]<

              # Prepare search for vertex leading into crossing on other side
              ([{}]()<>)

              # While keeping destination on third stack:
              <>({}<

                # Search for matching edge
                <>{({}({})<>[({}<>)])}{}

              # Replace old destination
              {}>)

              # Move back to original stack
              {({}<>)<>}<>

            >)}{}

          # Add orientation to degree
          >{})>)>)

          # Move duplicate to left stack
          <>{}{({}<>)<>}<>

          # Create "fake" edges from current crossing as termination conditions
          ([({}<>)]<((()))>)(())<>

          # Create representation of "top" new edge
          ({}<>)<>{}({}[()])

          # While didn't reach initial crossing again:
          {

            # Keep destination of new edge on third stack
            <>({}<<>

              # Do twice:
              (()()){({}[()]<

                # Search for crossing
                ({}<<>{({}<>)<>}>){({}[({})]<>({}<>))}{}

                # Reverse orientation of crossing
                (({})<<>({}<>)<>([{}])>)

              >)}{}

              # Remove extraneous search term
              {}

            # Push new destination for edge
            >)

            # Set up next edge
            <>({}<(({})())>[()]<>)

          }

          # Get destination of last edge to link up
          {}({}<

            # Find edge headed toward original crossing
            <>{}([{}]()<{({}<>)<>}>){({}({})<>[({}<>)])}

          # Replace destination
          {}{}>)

          # Move everything to left stack
          {({}<>)<>}

          # Clean up temporary data
          <>{}{}{}

        # Push new sign/degree of negatively smoothed knot
        >{})>)

      # Else (two twists)
      # i.e., crossing is the twist in unknot with one half-twist
      >)}{}){(<{}

        # Copy sign and degree+orientation
        (({})<<>(({}{})<

          # Move sign to left stack
          <>(<({}<>)>)

          # Move copy of configuration to left stack
          <>{}{({}<>)<>}

        # Add an additional 4*orientation to degree
        <>>(({}){}){})>)

      >)}

    # Else (one twist)
    >}{}){(<

      # Invert sign and get degree
      {}([{}]<({}<

        # Search term for other edge leading to this crossing
        <>([{}]()<>)

        # With destination on third stack:
        <>({}<

          # Find matching edge
          <>{({}({})<>[({}<>)])}{}

        # Replace destination
        {}>)

        # Move stuff back to left stack
        {({}<>)<>}<>

      # Add 3*orientation to degree
      >({})({}){})>)

    >)}{}

  # Else (no crossings)
  >)}{}){{}

    # If this came from the 2-twist case, undo splitting.
    # If this came from an initial empty input, use implicit zeros to not join anything
    # New sign = sign - 2 * next entry sign
    (([{}]){}<>{}{}<

      # New degree = average of both degrees
      <>({}<>{})

      # Find coefficient corresponding to degree
      {([{}]({}()()<{}({}<>)(())<>>))}{}{}

    # Add sign to coefficient
    {}>{})

    # Move rest of polynomial back to right stack
    (())<>{{}({}<>)(())<>}

    # Set up next configuration
    (<>)<>

  }{}

}{}{}<>{}

# Step 3: Put polynomial in correct form

# Keeping constant term:
{}({}<

  # Move to other stack to get access to terms of highest absolute degree
  {{}({}<>)(())<>}<>

  # Remove outer zeros
  {{}{((<(())>))}{}}

  # Move back to right stack to get access to lower order terms
  {}{{}({}<>)(())<>}

>)<>

# While terms remain:
{

  # Move term with positive coefficient
  {}({}<(<()>)<>([]){{}({}<>)(())<>([])}{}>)<>{{}({}<>)<>}{}

  # Move term with negative coefficient
  {}({}<>)<>

}<>