Three-dimensional topology and computational complexity

The Computational Complexity of Knot Genus and Spanning Area

Ian Agol, Joel Hass and William Thurston

29 pages23 claims indexed27 referencesManuscript 2004-07-10

claude-fable-5-2 medium: aht-repair-operations

Completed visible assessment, preserved as a readable check record. It is a model assessment, not a formal certificate. This document contains no private reasoning stream.

I found no error in the schedule or in part (1). The schedule is well defined: a pivot always exists after terminal cleanup, every transmission and truncation meets the source hypotheses, and static points are counted exactly once. With Q fixed, a reversing pivot needs at most two transmissions per pairing. For an increasing pivot the excess e = H-2c+2 obeys e' <= ceil(e/2)-1, which gives O(1+log N). After stabilization the endpoint n belongs only to Q, so truncation removes at least one point. If Q survives at constant k without a merger, the new endpoint is the end of another range starting left of c, so the next pivot is different, has a strictly smaller range start, and transmits Q. Termination follows unconditionally (at most N macro steps plus k restarts). This is not a polynomial bound; that rests entirely on parts (2)-(3), which I did not audit. The three listed issues are clarifications and do not affect the conclusion.

R1

Checked statement: The modified fixed-pivot schedule is well defined, uses only orbit-preserving moves or counted deletions of singleton orbits, and terminates. Part (1) holds: O(1+log N) transmissions per other pairing with Q fixed; truncation then removes at least one point; if Q survives with k unchanged and no merger, the next pivot is a different pairing whose range starts strictly left of c and contains Q's shortened range.

Returned assessment: no_issue_found

Conventions. Normalized means domain start < range start, so domain end <= range end. Trimmed means reversing pairings have disjoint sides. Q has range [c,n].

Pivot exists. After terminal cleanup n lies in some side, which must end at n. If that side is a domain, the range also ends at n, giving a fixed-point-free... rather, giving domain = range: an identity (increasing) or an untrimmed reflection (reversing). Both are excluded, so some range ends at n. Any choice among equal widest ranges works below.

Transmission is legal. An eligible P has range inside [c,n], which is the source hypothesis. Exponents r and s come from one integer division. A duplicate of Q becomes an identity and is deleted.

Starts fall below c. For increasing Q, maximality of r means Q^{-r}(range) is not inside [c,n], so its start is < c. The same holds for the domain if it is shifted. An unshifted domain is not inside [c,n] and ends at most at n, so it starts < c. For trimmed reversing Q, shifted sides land in Q's domain, which ends before c. So immediately after a transmission both side starts are < c. Without a trim, the normalized range starts < c and P is ineligible. Only a trim can cause a repeat.

Reversing Q. A trim keeps the minimum start, so the trimmed domain starts < c and is not shifted on the repeat. Only the range moves, by one application of Q^{-1}. P becomes increasing with both starts < c, so no trim and no further repeat. At most two transmissions per P.

Increasing Q. Orientation is preserved, so repeats occur only for a reflection x -> H-x. The trimmed sides are [a, ceil(H/2)-1] and [floor(H/2)+1, d], with a < c and H = a+d (minimum start plus maximum end, which I checked survives each retrim). A repeat needs u = floor(H/2)+1 >= c, so e = H-2c+2 >= 0. The domain is unshifted. The range moves left by m = rt to a start below c, so m >= u-c+1 and the constant becomes H-m. Since floor(H/2) = floor(e/2)+c-1, the new excess is at most e - floor(e/2) - 1 = ceil(e/2)-1. From e=0 this is -1, so no repeat follows. With H <= 2n <= 2N there are O(1+log N) transmissions per P. Other pairings are untouched while P is processed, so earlier stabilized pairings stay stabilized.

Truncation removes at least one point. Width is preserved by transmission and not increased by trimming. A stabilized eligible P has width <= n-c+1 and both starts < c, so both sides end < n. An ineligible pairing has range start < c; ending at n would make it wider than Q. Its domain ends no later than its range. So n lies in no side of any other pairing. For normalized pairings a suffix free of other ranges is also free of other domains, so both the increasing and the reversing truncation hypotheses of the source hold. Q's own domain ends below n.

Next pivot. Let N' >= c be the new endpoint with Q surviving. By maximality of the exclusive suffix, N' lies in a side of another pairing and no other side goes beyond N'. That pairing's range therefore ends exactly at N' and, by stabilization, starts at some s < c. So N' is covered, there is no static suffix, and no trim is pending. Every widest range ending at N' starts <= s < c, so the new pivot is not Q and its range strictly contains [c,N']. Q is eligible and gets transmitted. This gives c_(i+1) < c_i with unchanged endpoint when k is constant and no merger intervenes.

Static bookkeeping. No operation enlarges the covered set: transmission moves sides into Q's domain, a merger covers R1 union R2, and trimming and truncation restrict. So static points stay static, are singleton orbits by orbit preservation, and are counted exactly once when they become terminal. Points newly uncovered by trimming (the midpoint) or by reversing truncation (the left part of Q's domain) are singleton orbits of the current system and are also counted correctly later.

Termination. Each completed macro step lowers n by at least 1. Each merger, identity deletion or elimination lowers k, and k never rises. Hence at most N macro steps plus at most k restarts. This is termination only; a polynomial bound depends on parts (2)-(3).

Cost. Endpoints stay in [1,N]. A macro step uses O(k(1+log N)) transmissions and trims, plus O(k^2) merger tests.

Premises used

  • Source definitions of normalization, trimming, truncation, transmission and periodic merger (lines 904-1003)
  • Source Lemma orbit.same and Lemma merge2 (orbit preservation of the elementary moves), taken as given and not re-derived
  • Candidate invariant: system normalized, trimmed and identity-free at every selection
  • Merger test read as overlap width >= t1+t2 for two periodic pairings, as in Lemma merge2

Missing inputs

Scope changes

  • Orbit preservation of the elementary moves (source Lemmas merge2 and orbit.same) is used as a premise, not audited.
  • The halving telescope, close-side counting and forced-merger argument in parts (2)-(3) are treated conditionally. Only the termination bound of at most N macro steps is established here, not a polynomial bound.

Located concern

candidate-R schedule; AHT-operations lines 757-761

A width-1 pairing a -> c with a != c is both orientation preserving and orientation reversing. The candidate fixes no convention for it.

Take [3,3] -> [4,4]. Read as increasing it is periodic with t=1 and can take part in mergers. Read as reversing it is a trimmed reflection and is never periodic. Correctness, termination and all of part (1) hold under either reading, since the arguments above never depend on which is chosen.

Declare width-1 non-identity pairings orientation preserving, or fix any other single convention, and use it in the merger search.

None for R1. Part (3) relies on a merger being available for increasing or periodic pairings, so its audit should confirm the convention it needs.

Located concern

candidate-R schedule ('maximal exclusive suffix'); AHT-operations lines 943-968

The source states the increasing truncation hypothesis for other ranges only and the reversing one for other domains and ranges. The candidate does not say which sense of 'exclusive' it uses.

Under normalization domain end <= range end, so a suffix [N'+1,n] meeting another pairing's domain would also contain that pairing's range end. After stabilization every other side ends at or below N'. The two senses therefore coincide here.

State that exclusive means disjoint from every side of every other pairing, with the one-line normalization argument.

Presentation only.

Located concern

candidate-R part (1), final sentences

The different-pivot claim is stated 'without a merger', and the schedule allows identity-deletion restarts. The claim c_(i+1) < c_i is therefore proved only between consecutive selections with k constant and no merger.

If a merger fires at the start of the next step, the merged pairing may absorb Q and its range start is unrelated to c. This always comes with a drop in k.

None needed if part (2) invokes the telescope only at constant k, as it says it does.

None for R1. It limits how part (2) may use the claim.

Outside the audit

  • Candidate part (2): X potential, telescope inequality, factor-4 and merger estimates
  • Candidate part (3): close-side monotonicity, forced merger, O(k+1) macro steps per block
  • Candidate application claim: N bounds, Corollaries 13/14, verifier and NP-hardness statements
  • Internal proofs of the source lemmas (merge1-3, orbit.same)
Source record

Additional supporting archive items are identified in the original report. View the manuscript hashes and repository snapshot.

Cite this review

If this review or its supporting reports inform your work, please cite it.

Igor Rivin. Review of The Computational Complexity of Knot Genus and Spanning Area. Math Referee, .

Download .bib
View BibTeX
@misc{rivin2026review-human-agol-hass-thurston-knot-genus,
  author = {Rivin, Igor},
  title = {{Review of The Computational Complexity of Knot Genus and Spanning Area}},
  year = {2026},
  month = {November},
  date = {2026-11-19},
  howpublished = {Math Referee},
  url = {https://mathreferee.dimensionreducers.ai/papers/human-agol-hass-thurston-knot-genus/panel/},
  note = {Review report}
}