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-complexity

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 parts (2)-(3) or in the part-(1) facts they rely on. The telescope, closeness monotonicity, both-side closeness of consecutive increasing transmitters, the merger overlap inequality (including multi-power transmissions), the loss and block accounting, and the bit bound all check by direct local argument. The result is a bound of O(k^3 (1+log N)^2) transmissions and trims, plus polynomial bookkeeping, for the modified schedule. The only defects are presentational: X is not defined and the telescope is cited rather than shown. Nothing here bounds the printed algorithm's cycles. Orbit-count correctness and the application claim are treated conditionally.

R2

Checked statement: Parts (2)-(3) of candidate R, together with the part-(1) facts they use, give a polynomial bit-complexity bound in k and log N for the modified fixed-Q schedule on arbitrary signed interval pairings.

Returned assessment: no_issue_found

I checked each transition by hand and found no failing step. Two items are unstated in the candidate and are filled in here (see issues). The bound is for the modified schedule only.

Part-(1) facts used later. (a) After a transmission both side starts of P are <c. For increasing Q with shift t and domain start a=c-t, maximality of r puts a shifted start in [a,c-1]. An unshifted domain is not contained in [c,n] and ends before n, so it starts <c. For a trimmed reversing Q, images lie in Q's domain, which ends before c. (b) Repeats. For reversing Q, a retrimmed reflection has only its range moved, becomes a translation, and stops. For increasing Q, write the reflection as x->H-x with trimmed range start u=floor(H/2)+1>=c. Only the range moves, by m>=u-c+1, so H'=H-m. With e=H-2c+2>=0 and floor(H/2)=c-1+floor(e/2), this gives e'<=ceil(e/2)-1. Hence O(1+log N) transmissions per pairing. (c) Pairings whose range is not inside [c,n] start <c and are never altered. One ending at n would be wider than Q, contradicting maximality. Eligible pairings keep width <=w_Q and end with start <c, so they end before n. Other domains end before their ranges. So truncation removes at least one point. If Q survives, the new endpoint n' is the end of another range starting <c. Therefore the next maximal pairing is different, the endpoint is unchanged between selections, and c_{i+1}<c_i.

Part (2). I take X to be the product of 4w over pairings. This is the only reading consistent with X<=(4N)^k, the deletion factor 4, and the merger remark. Telescope: let n_0=Z and n_i be the endpoint after truncation i. The step-i ratio is (n_i-c_i+1)/(n_{i-1}-c_i+1). Since n_i<n_{i-1} and c_r<=c_i, this is at most (n_i-c_r+1)/(n_{i-1}-c_r+1). The product telescopes to w_r'/(Z-c_r+1). Transmissions keep widths and trims shrink them. No contraction occurs inside a constant-k block, because the endpoint stays covered. Halving: if the truncated range fails strict closeness, then 2w_r'<=Z-c_r+1 and X has halved. k drops: a deletion or vanishing pairing loses a factor 4w>=4. A merged pairing has width at most w1+w2-gcd, because the union of spans is at most (w1+t1)+(w2+t2)-(t1+t2). Then 4(w1+w2)<=8w1w2, which is half of 16w1w2.

Part (3). Monotonicity: a side is strictly close when its width exceeds Z minus its right end. I checked every constant-k move. A left shift keeps the width and lowers the right end. Both trimmed halves have smaller width and no larger right end. Truncating Q's range lowers width and right end equally. Q's domain under truncation is either cut on the right (increasing) or cut on the left with the same right end (reversing). In no case does a non-close side become close. Reversing transmitter: Q's domain has width v>=w(J) and right end b with Z-b>=v, so the image of J is not close. That is a count loss. Increasing transmitter: J'=Q^{-r}(J) lies in Q's domain. If J' is close, the domain is close, since its width is >=w and its right end is >= that of J'. Q's range contains J with the same right end, so it is close too.

Merger check. P is the step-2 transmitter and Q the step-3 transmitter. Both are increasing, with both sides close after truncation unless there is a loss or block end.

  • After transmission P is increasing, of width w, with starts L<=R<c and j' in {L,R}. There is no trim.
  • L=R is an identity, hence a k drop.
  • Otherwise closeness of the L-side and R+w-1<=Z give R-L<w, so P is periodic with period R-L.
  • Q after truncation has both sides close, so t=c-a<w_Q' and Q is periodic.
  • J ends at most at Z and the L-side is close, so w>j-L.
  • With L<=j'=j-rt and j>c=a+t, this gives w>t and w>t+a-L. So w>=t+max(0,a-L), in fact with one unit to spare.
  • The truncated Q ends at the largest other range end, which is >=R+w-1. The spans [L,R+w-1] and [a,n_3] therefore overlap in width R+w-max(L,a)>=(R-L)+t. This is exactly the hypothesis of Lemma merge2. It uses only the period t, so r>1 does no harm. Nothing alters P or Q before the next step starts, so the merger is available there.

Counting. Three consecutive macro steps with no close-count loss and no block end force a merger at the start of the fourth. Close count is at most 2k and nonincreasing, so there are O(k+1) macro steps per block. Each block ends with X halved, and 1<=X<=(4N)^k, so there are O(k(1+log N)) blocks. Each macro step has O(k(1+log N)) transmissions and trims. Each is O(1) arithmetic operations (one division for the maximal power) on integers bounded by 2N. Merger search is O(k^2) comparisons. The total is polynomial in k and log N.

Scope. This bounds the modified schedule only. It gives no bound for the printed cycle schedule and does not rely on one.

Premises used

  • Source definitions of pairing, width, range/domain normalization, periodic pairing, trimming, truncation, transmission
  • Lemma merge2 (overlap >= t1+t2 allows periodic merger) as stated in the source
  • Candidate schedule conventions: normalized/trimmed/identity-free system, merger checked at step start, fixed-Q stabilization, maximal exclusive-suffix truncation, block ends at k drop or halving of X
  • Inferred definition X = product over pairings of 4*width
  • Conditional: orbit-count correctness of the schedule (orbit preservation of the moves, deferred counting of static points) is assumed, not audited here

Missing inputs

  • Explicit definition of X in the candidate text
  • The statement of the telescope 'proved under P2'

Scope changes

  • The bound applies to the modified fixed-Q schedule, not to the printed algorithm's cycles
  • The merger inequality holds with slack: w>=t+max(0,a-L)+1

Located concern

candidate-R part (2), 'Apply the telescope proved under P2'

The telescope is cited, not proved in the supplied text, and the potential X is never defined.

Not a counterexample. With X=prod(4w), the inequality follows from (n_i-c_i+1)/(n_{i-1}-c_i+1)<=(n_i-c_r+1)/(n_{i-1}-c_r+1) for c_r<=c_i and n_i<n_{i-1}, then exact telescoping.

State X=prod_i 4w_i explicitly and include the two-line monotonicity argument in part (2).

None; presentational only.

Located concern

candidate-R part (3), 'four consecutive macro steps ... are impossible'

The no-loss hypothesis is stated loosely. It must cover the transmitted image staying close and the transmitter's domain staying close through truncation, in both steps two and three. A trim that annihilates a width-1 fixed-point reflection should be listed as a k drop.

Each of these events is either a close-count loss, a halving, or a k drop, so all are already charged. No schedule-conforming configuration escapes the trichotomy.

List the charged events explicitly: loss of J', loss of Q's domain on truncation, loss of a P side, identity or vanishing pairing.

None; constants only (roughly 3(2k+1)+1 macro steps per block).

Outside the audit

  • Orbit-count correctness of the modified schedule (deferred static points, orbit preservation)
  • Candidate application claim (Corollaries 13/14 input sizes, the bound on N, NP certificate, NP-hardness section)
  • Any running-time statement about the original printed algorithm
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}
}