Knots & counting
Easy pieces can have a hard total.
Fix the coarse colouring of a knot, and the remaining choices are easy to count. Change that colouring, and the number of choices changes too.
John Cullen · · A companion to Counting what emerges
Six labels, in three pairs
The group S₄ consists of the 24 ways to rearrange four objects. Here we use six of them: the swaps of two objects, called transpositions. The label (12), for example, means “swap 1 and 2.”
We put these labels on a knot diagram. At each crossing, the over-strand keeps its label and changes the under-strand’s label by a fixed rule. A valid colouring obeys that rule everywhere and joins up consistently around the knot.
The six swaps fall into three pairs. Think of a label as a coarse colour plus one binary choice.
Colour A
(12)or(34)
Colour B
(13)or(24)
Colour C
(14)or(23)
The group theory behind the pairs
The quotient map S₄ → S₃ forgets the Klein four subgroup V₄. The six transpositions map two-to-one onto the three transpositions of S₃. The two swaps in each pair commute. The colours A, B and C are names for those three quotient labels.
With left input x passing over right input y, one crossing sends (x, y) to (xyx⁻¹, x). For swaps, x⁻¹ = x. The example below applies this rule three times and checks that the output labels match the inputs.
Try a knot with three crossings
Three consecutive crossings have a useful effect: they return the coarse colours to their starting positions. The fine choices behave differently depending on whether the coarse colours match.
Close the two strands into a trefoil, the simplest nontrivial knot. Choose a coarse colour for each input, then choose one of the allowed lifts. A lift fills in the actual swaps inside those colour families.
Explore all nine cases
Same knot. Different numbers of choices.
The gap at each crossing marks the under-strand. The labels at the top and bottom match, so this colouring closes.
1. Choose the two input colours
Rows choose the left colour; columns choose the right. Each number counts its lifts.
| Left colour / right colour | A | B | C |
|---|---|---|---|
| A | |||
| B | |||
| C |
Matching colours: 2 lifts
The three crossings exchange the two fine choices. Closing the braid forces those choices to agree: two possibilities.
3 × 2 + 6 × 4 = 30 colourings
Three matching pairs, six different pairs. Add the entries in the table to count every transposition colouring of this trefoil.
The diagram is computed from the swaps themselves: all 36 possible starting pairs are checked against the three crossing rules and closure. Thirty work. This is the count with transposition labels; S₄ has other types of elements as well.
The difficulty is in adding the layers together
The example shows the essential dependence. There are nine coarse colourings, but they do not contribute equally. Some contribute two lifts; others contribute four.
For the larger diagrams in my note, a plane graph supplies the layout. Every edge becomes a twist of three crossings. Coarse colours can be chosen freely on its vertices. Once those colours are fixed, the remaining binary choices travel along loops determined by which neighbouring colours agree. Each independent loop contributes a factor of two.
01
Choose coarse colours
Assign one of three colours to each vertex of the graph.
02
Count the lifts
For this assignment, count the free binary choices using linear algebra.
03
Add every contribution
The loop pattern changes with the colours, so each assignment can have a different weight.
Each individual lifting calculation is easy. The total combines exponentially many of them, with weights that depend on the colouring. That explains where difficulty can enter, but an exponential number of terms alone does not prove hardness: some large sums have shortcuts.
The bicycle law, in one formula
total = ∑φ 2c(Hφ) + dim B(Hφ)
For each assignment φ of the three coarse colours, Hφ keeps only graph edges whose endpoints have the same colour. The exponent counts its components, including isolated vertices, plus the dimension of its binary bicycle space: edge sets that are both cycles and cuts. Together these count the loops carrying independent bits.
The equivalent 12-state model uses extra variables to express the parity constraints. Its twelve states are bookkeeping states, not twelve transpositions of S₄.
How the proof rules out a general shortcut
The note connects this weighted sum to a known hard problem: counting proper colourings of a planar graph with twelve colours, where neighbouring vertices must differ.
- Keep one knot. The simplest conversion gives a link with many components. Special pieces of diagram let us change the interaction weights while preserving a single closed component.
- Make several related knots. Varying those pieces produces a family whose exact colouring counts reveal different mixtures of the graph’s colourings.
- Recover the graph count. Combining polynomially many knot counts by interpolation recovers the number of proper twelve-colourings.
A general fast algorithm for these knot counts would therefore give a fast algorithm for that #P-hard counting problem. The full S₄ homomorphism count can also be used: the note shows how to extract the transposition count from it using an efficiently computable correction.
“Solvable” describes the group’s algebraic layers. It does not guarantee that all the ways those layers interact can be counted efficiently. Nor does hardness mean that a small knot like this trefoil is difficult to count.
How this differs from the earlier knot construction
Kuperberg and Samperton make braids simulate reversible computations. Their theorem applies to nonabelian simple groups, using rich braid actions to build the necessary gates. My S₄ argument encodes a weighted graph-colouring count instead.
Kuperberg–Samperton
A computation becomes a braid.
Braid pieces act as reversible gates. Closing the braid imposes the input and output conditions. The resulting colouring count tracks successful computations very directly.
Read their proof outline ↗The S₄ construction
A graph count becomes a sum of lifts.
Triple crossings separate coarse colours from binary choices. The number of lifts supplies graph-dependent weights. Several exact knot counts recover the answer by interpolation.
Read §4 of my note ↗This proves hardness of exact counting under polynomial-time Turing reductions. It does not by itself prove hardness of approximation. The Heisenberg and Borromean-surgery arguments elsewhere in the note use a different mechanism.
From the example to the proof
The trefoil checks the local mechanism. The general claim rests on the bicycle law, the pieces that preserve one knot, and the interpolation argument in the note.
- Counting homomorphisms from knot groups to solvable groups can be #P-hard — the note, especially §4.
- Source, checks, and research record — the accompanying material in knotlab.
- The original intuition — the two layers and the bicycle law.
- Kuperberg–Samperton: Coloring invariants of knots and links are often intractable — the earlier construction for nonabelian simple groups.
The note and this explainer were prepared with AI assistance. The note’s proofs and computational checks are public; its mathematical claims have not been reviewed by a human expert.