Knot genus: a proof gap and a checked repair

A compressed algorithm connects knot genus to NP. Explicit counterexamples expose a gap in its running-time proof; a separately audited schedule repairs the unweighted component counter.

Math Referee editorial

An algorithm can return the right answer on every example and still lack a valid proof that it runs fast enough. In computational topology, that distinction can separate a plausible procedure from a theorem about NP.

Agol, Hass and Thurston's The Computational Complexity of Knot Genus and Spanning Area is a particularly consequential example. Its compressed orbit-counting algorithm became an input to later work on knottedness, Thurston norm and knot genus. Our review finds explicit counterexamples to two steps in the printed running-time argument. A subsequent repair audit supports a modified algorithm with a polynomial-time proof.

The outcome has three parts: a demonstrated proof gap, a checked replacement for unweighted orbit counting, and a precise boundary around the applications that replacement repairs. The knot-genus theorem has not been disproved.

Why counting components is difficult

The genus of a knot is the smallest number of handles of an orientable surface spanning it. Finding such a surface can be difficult. The NP question asks something different: can a short description of a proposed surface be checked in polynomial time?

A normal surface meets each tetrahedron in standard triangle and quadrilateral pieces. Instead of writing down every piece, one records their multiplicities in binary. This is powerful compression: an integer with 101 binary digits can describe more than a trillion trillion pieces.

But compression creates an obligation. A verifier cannot expand all those pieces and still claim polynomial time in the description length.

AHT encodes connectivity by pairings between intervals of integers. For example, a pairing can identify every point of $[a,b]$ with its translate in $[c,d]$, or reverse their order. The task is to count the equivalence classes generated by all these identifications. With $k$ pairings on $[1,N]$, the required bound is polynomial in $k$ and $\log N$. A bound proportional to $N$ will not do.

The paper's NP-completeness result concerns knots in varying triangulated orientable three-manifolds. It should not be restated as NP-hardness for knots in the fixed three-sphere. Original manuscript, arXiv v2.

Where the printed progress proof breaks

The algorithm simplifies its interval pairings through transmissions, trimming, mergers and truncations. To show that it finishes quickly, the proof tracks a potential

$$X=4^k\prod_i w_i,$$

where $w_i$ is the inclusive width of pairing $i$. The proposed argument requires this potential to halve within a constant multiple of $k$ cycles.

One exact family has only two pairings but keeps the potential above half its initial value for arbitrarily many complete cycles. A reflection is trimmed at the start of each cycle, allowing the same translation to remain the chosen pairing. The asserted transition to a different pairing fails.

A second example fits on just 29 points. It starts with

$$[14,24]\longrightarrow[15,25],\qquad [1,13]\longrightarrow[17,29].$$

The relevant sequence removes an interior static interval. That changes the coordinates between two truncations, so the product of ratios no longer telescopes as claimed. At the point where the halving argument is applied,

$$X_{\mathrm{final}}=1152>\frac{2288}{2}=1144.$$

These examples contradict the stated progress estimates. They do not give a superpolynomial running-time lower bound: the first family's long phase is itself only logarithmic in its parameter. Nor do they show that the unweighted orbit counts are wrong. The full review gives the exact states and source locations.

Repair the schedule, then prove its cost

The checked reconstruction retains AHT's interval operations but changes when they occur.

First, it leaves interior static gaps in place. Isolated points are counted and removed only when they form a terminal suffix. The coordinate system needed for the telescoping estimate is therefore preserved.

Second, it holds the chosen maximal pairing fixed while stabilizing each transmission: normalize, trim immediately, and retransmit if trimming makes the pairing eligible again. Only after stabilization does it truncate.

This is not a way to hide many old cycles inside one supposedly cheap step. The proof explicitly bounds the internal work. An integer excess associated with a repeating reflection satisfies

$$e_{\mathrm{new}}\le\lceil e/2\rceil-1,$$

so stabilization takes $O(\log N)$ transmissions per competing pairing. A separate potential argument bounds the number of stabilized steps. Together with orbit preservation and binary arithmetic bounds, this proves polynomial bit complexity for the modified unweighted counter.

Read the complete reconstruction, or download the proof PDF and exact-check bundle.

What this repairs—and what it leaves to check

The NP verifier needs three unweighted component counts: for the proposed surface, its boundary, and the surface represented by twice its normal coordinates. These test connectedness and, with the ambient orientability condition, orientability. The modified counter supplies all three calls.

There is also a local correction to the genus calculation. For vertex, triangle and quadrilateral counts $V,T,Q$, and $b$ boundary arcs, the appropriate Euler characteristic is

$$\chi=V-\frac{T}{2}-Q-\frac{b}{2}.$$

The boundary term cannot be omitted in a knot exterior.

With that correction, the reconstruction repairs the audited computational bottleneck in NP membership. It still imports the existence and size bounds for normal-surface witnesses and the topological certificate premises. Those foundations, the independent NP-hardness reduction, and the entire spanning-area argument have not been freshly certified by this audit.

The weighted extension presents a separate task. Its printed transfer formula has a six-point counterexample, and later applications can need more than a component count. The present repair does not yet supply all that weighted information.

Follow the mathematical dependency

The influence is visible in specific theorem calls. Lackenby's The efficient certification of knottedness and Thurston norm imports weighted AHT in Theorem 9.1 and uses it in compressed cutting constructions. Lackenby and Yazdi's later The computational complexity of knot genus in a fixed 3-manifold, Theorem 8.6, imports the resulting cutting theorem. Lackenby's algorithmic survey also repeats the original cycle estimate.

This establishes particular proof dependencies, not false downstream theorems. It also does not establish that every subsequent use has the same problem. In their pants-distance work, Lackenby and Yazdi work with restricted systems excluding the problematic trimming and supply their own progress argument.

Nor can a scoped search establish that nobody previously noticed or repaired the issue. Schaefer, Sedgwick and Štefankovič state an alternative polynomial component counter for normal surfaces, although its proof is omitted from the conference paper we inspected. It remains relevant prior work. We make no priority claim for the repair.

Evidence a reader can inspect

The reconstruction grew from Astra 6.2's proposal. Sol 6.2 and Fable 5.2 then independently read three separate obligations: preservation of orbits, polynomial complexity, and the NP-verifier interface. The final exposition incorporates the required definitions, local derivations and boundary correction, checked by the coordinating assistant.

The accompanying implementation checks the entire equivalence relation after every move on 53,667 exhaustive small systems and 10,000 seeded random systems, plus large exact families. Those tests check the implementation; the written argument establishes the universal bound. This is an AI-assisted, scoped review, not formal verification or human peer review.

Our source is the July 2004 arXiv revision. The journal version appeared in 2006, but we have not completed a line-by-line collation of that edition. The review and decision graph keep original proof defects separate from the replacement argument.

The value of this example is the complete chain: locate the failed inference, give a reproducible witness, construct a replacement, and check which applications it actually supports. An influential result deserves that level of scrutiny—and a repair deserves it too.

Cite this spotlight

If this spotlight informs your work, please cite it.

Igor Rivin. Knot genus: a proof gap and a checked repair. Math Referee, .

Download .bib
View BibTeX
@misc{rivin2026spotlight-knot-genus-proof-repair,
  author = {Rivin, Igor},
  title = {{Knot genus: a proof gap and a checked repair}},
  year = {2026},
  month = {November},
  date = {2026-11-20},
  howpublished = {Math Referee},
  url = {https://mathreferee.dimensionreducers.ai/spotlight/knot-genus-proof-repair/},
  note = {Paper Spotlight}
}

Take a closer look at your paper.

Explore the public reports, then join the waitlist for our invitation-only research preview. Joining is free; reviews are paid.

Join the preview waitlist