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

gpt-6.2-sol high: aht-algorithms

Reviewer record, not the publication verdict. This preserves the model response, including proposed repairs and unadjudicated objections. The curated report rejects the unsupported Schubert scope objection. A later separate audit accepts the modified unweighted schedule under its stated scope; Sol's different amortization proposal remains unaccepted. Only expressly checked findings enter the decision graph.

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.

The elementary orbit invariants and compressed normal-to-pairing reductions survive the audit. The literal unweighted algorithm has an undefined truncation on a two-point input, and the printed close-interval and halving estimates have counterexamples even when the truncations are legal. A separate polynomial-cycle argument repairs the unweighted procedure after the suffix correction. The weighted extension has additional failures, including a direct wrong-weight example, but exact residue transport, corrected lists, and a change-position bound recover a bit-polynomial compressed result. These are new repairs, not validations of the printed proofs. The historical cutoff is 2002-05-06 on the recorded arXiv v1 fallback; the reviewed supplied source is v2, dated 2004-07-10 by the supplied record. No external theorem or later repair is imported. For the uninspected historical coordinate bound, available_from is recorded only at bibliography precision as 1999; date_evidence is AHT-TeX, HLP:99; date_basis is the cited JACM publication year; version is JACM 46 (1999), pp. 185–211, Lemma 6.1 as cited. Its attributed claim for a t-tetrahedron compact triangulated 3-manifold is the vertex-minimal bound 2^(7t−1) and integer Hilbert-basis coordinate bound <t·2^(7t+2); the original statement, hypotheses and publication record were not independently verified. Model training does not exclude later knowledge; the technical findings here are supported by the supplied source, explicit examples and self-contained replacement arguments, not by assuming later results were historically available.

A1

Checked statement: Section 4 definitions and Lemmas 7–11: legality and orbit effects of the elementary interval moves.

Returned assessment: repairable_gap

The elementary moves have the claimed orbit effects with their proper domains of application. A positive translation by t on the entire periodic interval joins precisely the congruence classes modulo t, including when the domain and range are adjacent rather than overlapping. In Lemma 8 the t1 consecutive test points represent every residue modulo t1, and their images give the shift by t2 on those residues. Even if paths leave R1 before returning, every edge preserves residues modulo gcd(t1,t2), so the asserted relation restricted to R1 is exact. This is not permission to discard portions of g2 outside R1. In Lemma 9, the overlap of width at least t1+t2 permits the test in both directions and meets every residue class for the merged period. In Lemma 10, the positive translations put the starts of J1, J, J2 in that order. Covering J forces J1 and J2 to overlap or be adjacent, giving width(J) ≥ t1+t2 as printed. Contraction deletes singleton orbits. Trimming retains one direction of each non-loop reflection edge. Transmission changes the endpoints of each edge along paths in the unchanged transmitting pairing. For truncation, after putting the leftmost of the two intervals first, excluding other ranges from the terminal suffix excludes their domains too. The removed points for a positive translation lie in chains along +t, each having exactly one attachment to the retained prefix; for a trimmed reflection they are leaves attached to the retained prefix. In either case every old orbit meets the prefix and its restricted equivalence relation is exactly the new one.

Premises used

  • Intervals consist of integers with inclusive endpoints except where explicitly indicated; width is cardinality.
  • Replacing a generator by its inverse leaves the generated equivalence relation unchanged.
  • In the move proofs, domains and ranges are ordered with a≤c, including after a transmission. A preserving map with a=c is an identity; a reversing one with a=c can be trimmed unless it too is an identity.

Missing inputs

Scope changes

Located concern

AHT-TeX: section 4, pairing conventions, Contraction, Trimming, and Truncation

The legality conventions should be explicit. In particular, the first sentence introducing truncation does not describe its actual hypothesis, and the proof of trimming overlooks a fixed midpoint.

For [1,2]→[3,4] by +2, peeling off [3,4] is legal although those points are not in the domain of the pairing. For the self-reflection of [1,3], the loop at 2 has no representative as an edge of the trimmed map or its inverse, but can simply be omitted from a path. A static interval must be disjoint from every domain and range, not merely fail to be contained in any one of them.

Normalize the two sides by inversion when necessary, delete identities, explicitly allow equal sides for a reflection before trimming, and omit fixed-point loops in the trimming proof. State truncation using the detailed terminal-suffix rule: the suffix is nonempty, contained in the chosen range, and misses all other ranges; a reversing chosen pairing must first have disjoint sides. Use the chain/leaf proof above.

No counterexample to the orbit-preservation statement under the detailed legal moves. The suffix-containment requirement matters to the algorithm in A2.

Located concern

AHT-TeX: Lemma orbit.same, final transmission paragraph

The written substitution for transmission uses the wrong generator on the right and an undefined exponent in place of the specified exponent.

For p:[1,4]→[3,6] by +2 and h:[1,1]→[5,5], the maximal inverse shift of the range of h is p^(-2); h'=[1,1]→[1,1]. The path for the old h edge uses p² after h', not p² after h (p² is not defined at 5).

For h'=p^(-r) h p^s use h=p^r h' p^(-s) on the original domain and h'=p^(-r) h p^s on the new domain. Substitute the inverted paths for inverse edges. Take s=0 when the domain is not shifted. Invert the result for storage if its sides are in the opposite order.

The elementary transmission operation is sound; the printed word substitution is not its proof.

A2

Checked statement: Theorem 12: correctness, termination, Claims 1–4, and polynomial bit complexity of the printed six-step orbit-counting algorithm.

Returned assessment: claim_false

As a specification of the printed algorithm on every input, the theorem fails: Step 6 can select an interval contained in no pairing range. With the containment correction below, the invariant is the counter plus the number of remaining orbits. After transmission all other normalized ranges start strictly left of the pivot's range start, so none ends at the current right endpoint. The corrected truncation deletes at least one point, and deletion of all pairings allows the remaining static points to be counted and the procedure to stop. Thus correctness and termination follow from A1. The bit bound needs a different progress proof. Claims 1 and 2 are valid: equal-width close intervals overlap or touch, and a subinterval of a non-close domain is non-close. Claims 3 and 4 are false in the exact six-step implementation, as is the stated 5k-cycle halving estimate. The loose bound N on cycles is not a bit-complexity bound. A new polynomial bound for the corrected six steps follows below. It does not validate the printed estimates.

Premises used

  • The repaired elementary-move conventions and invariants in A1.
  • A cycle means a pass through the six displayed steps. There is no seventh step in the unweighted algorithm.
  • Integer endpoints and the counter are stored in binary. The empty product in X=4^k times the product of widths is 1.

Missing inputs

Scope changes

  • The negative verdict concerns the literal algorithmic theorem, including its specified rule and progress estimates, not the existence of a polynomial orbit-counting algorithm.
  • The new bound uses strict closeness and a new amortization, and is stated polynomially in 1+k and log(2+N) to include empty generator lists and small N.

Located concern

AHT-TeX: Orbit counting algorithm, Steps (5)–(6)

Step 6 minimizes the suffix start without requiring it to lie in the pivot's range.

Take N=2 with the sole pairing [1,1]→[2,2]. No point is static and Steps 3–5 make no change. The smallest start whose suffix intersects exactly one range is 1, but no range contains [1,2].

For pivot range [c_i,N'], let B be the largest right endpoint of any other range, or 0 if there is none. Set the suffix start to max(c_i,B+1). Normalize transmitted pairings as in A1. Both normalized side starts of every nonpivot pairing after Step 5 are less than c_i: untranslated sides already started to its left, and a maximal inverse transmission moves each translated side to its left. Thus B<N' and the corrected truncation is legal, including in the one-pairing example.

The literal algorithm is not total. The corrected rule proves correctness and termination, not on its own polynomial time.

Located concern

AHT-TeX: Claim 3 (5pairs) and the final 5k-cycle estimate

Five cycles need not give five successive maximal pairings, nor any decrease in the number of close intervals. Trimming can restore a transmitted competitor to containment in the current pivot.

Take L=2^17, e=2^12, Z=N=2L+2e+1. Use the +1 pairing [L+1,N−1]→[L+2,N] and the reversing pairing [1,L+e]→[L+e+1,2L+2e]. There are no contractions or mergers in the first ten cycles. In cycle j=1,…,10, put E=e/2^(j−1) and w=L+E. Just after Step 5 the reverse pairing has domain [1,w] and range [L+1,L+w]. The preserving pivot truncates to end L+w and width w−1. In the next cycle the reflection trims to width L+E/2 and right start L+1+E/2, strictly to the right of the preserving range start L+2. Thus the preserving pairing stays maximal. Throughout the ten cycles its two sides and the right side of the reflection are Z-close; the reflection's left side is not (its width is at most L+e<Z/2). The close count is exactly three despite k=2. Moreover after cycle j the potential ratio is (w−1)w/[(L+2e)(L+e)]>1/2, including at j=10=5k. These truncations all satisfy the corrected and printed suffix condition. Separately, the printed assertion about all reversed inverse images being non-close fails at equality: on Z=4 the trimmed reflection [1,2]→[3,4] takes the whole range back to the Z-close interval [1,2].

Use strict closeness in a replacement proof; count repeated uses of the same pivot, not just switches. The new proof in the next two entries gives a polynomial bound without the five-cycle claim.

Claim 3 and the displayed halving schedule are false, not merely unproved. The family does not show superpolynomial running time.

Located concern

AHT-TeX: Claim 4 (div2) and the final proof of theorem orbitcount

Contraction between truncations invalidates the equality d_i'=d_(i+1) in the fixed Z coordinates. The claimed factor-two conclusion can fail.

Set Z=62. Use the reversing g:[1,30]→[33,62] and the +1 h:[31,50]→[32,51]. Cycle 1 truncates g to [12,30]→[33,51]. Cycle 2 contracts [1,11]; the surviving ranges of g and h are now [22,40] and [21,40]. The new pivot h transmits g's range to [20,38] by two backward steps and is truncated to [21,38]. The final widths are 19 and 18, and the final left sides are [1,19] and [20,37], respectively. None of the four sides is 62-close. Nonetheless X has ratio (19/30)(18/20)=0.57>1/2. There was no trim, merger or pairing deletion. The equality assumed for the first transition would identify 51 with 40.

New repair, part 1 (a close pivot while the potential barely falls). Consider a block of cycles with no drop in k. A truncation of length Δ removes at most Δ surviving points from the pivot's support. Charge static points which later get contracted as follows. Transmission itself loses no covered point, since every moved endpoint was covered by the pivot. An overlapping reflection trimmed in the next cycle was created by that transmission, and its only potentially uncovered point is its integer midpoint. That midpoint is in a transferred side, hence was covered by the preceding pivot. It can become static at the trim only if it lost that support at the preceding truncation. The static points from the truncation itself and these later midpoints are distinct and together charge at most Δ to that truncation. Any static points initially present or created by trimming overlaps already present at the first cycle have been dealt with by Step 2 of cycle 2. Mergers and identity deletion need not be charged in a block with no drop in k. Now set Z to the width just after Step 2 of cycle 3 of the block. All subsequent contractions can be charged to truncations in the block. Thus at the end of any subsequent cycle, Z−N'≤2ΣΔ_i, where the sum includes truncations from the beginning of the block. Write w_i for each pivot width before its truncation and w for the last retained pivot width. In constant k the next pivot has at least the width of the retained previous pivot: the latter still ends at the top, is already trimmed, and contractions preserve its width. If the current ratio of X to its value at the beginning of the block is r>3/4, then w≥r w_i for every preceding truncation, because the product of the truncation ratios from any such point is at least r. Also Σ(Δ_i/w_i)≤(1−r)/r, by expanding one minus the product of the truncation ratios, whose prefix products are at least r. Consequently Z−N'≤2w(1−r)/r²<w. The last pivot's range is therefore strictly Z-close: its width w exceeds (Z−c+1)/2=(w+Z−N')/2. This argument pays for contractions instead of identifying coordinates before and after them.

The printed telescoping proof is not valid for the algorithm. The replacement yields a different progress threshold and uses a charge for compressed-away static points.

Located concern

AHT-TeX: theorem orbitcount, polynomial-time conclusion

The printed bit-complexity conclusion uses the false progress estimates. The corrections need a universal cycle bound, not just legal and terminating moves.

The preceding examples invalidate the schedule used to multiply the per-cycle cost. The exact potential at termination, with no pairings, is 1 rather than 0. For one merger the valid width bound follows by writing the hull lengths as w_i+t_i: subtract the overlap of at least t1+t2 and then the new period to get new width at most w1+w2.

New repair, part 2 (a polynomial bound on stalls). Keep Z fixed as in part 1 and use strict closeness. With k constant, the close count is nonincreasing: each side is shortened or shifted left, possibly exchanging its label with the other side. Equal-width strictly close intervals overlap: if their starts are u≤v and width w, then 2w>Z−u+1≥v−u+w. No left side of a disjoint pairing is strictly close. Consider consecutive full cycles with no drop of close count or k, in a prefix where r>3/4. Each retained pivot range is close by part 1. On a switch, the next pivot contains and transmits the old pivot's close range. It must preserve orientation, since a reversing pivot moves a side into its non-close disjoint left side. Its own domain becomes known to be close because it contains the close transmitted interval. At a second switch, the outgoing preserving pivot consequently has both sides close. Let the new preserving transmitter have start a, range start c=a+t, and let the outgoing pairing's right side move from start v≥c to x in [a,c−1]. Let u<c be its other new side start, w its width, and s=|x−u|. An identity is deleted next cycle. Otherwise the outgoing pairing is periodic since its two close sides overlap. Also w>v−x≥t. If u≥a, its whole periodic hull overlaps the transmitter's hull, in width w+s≥t+s. If u<a, closeness of the width-w sides at u and v gives w>v−u≥c−u, so the overlap from a to x+w−1 again has width at least t+s. The transmitter is periodic, and remains so after truncation in a no-loss run: both its sides are close, and truncation retains the top of the transmitted hull. The overlap remains sufficient, and contraction cannot change the offsets inside the connected union of the two periodic intervals. Thus the next Step 4 merges them. Two switches in a no-loss run force a drop, allowing at most a final switch awaiting the next cycle. For a repeat of the same pivot, some competitor h ends at the truncated top and starts left of c after Step 5, so it would win next cycle unless it trims to a right start at least c. It must have been transmitted to become an overlapping reflection. Its post-transmission right side is close since it contains the retained pivot range. The previous right side of h was close too (among equal widths the farther-right side is at least as close). It was moved, so the transmitter preserves orientation, and the moved side must still be the right side: if both sides were close, trimming would lose one. In particular, the pivot's domain is close from this first repeat onward. Write u for h's left start, x≤c−1 for its right start just before the trim, and w_h for its width. For h to witness a repeat, e_h=u+w_h−c+1 must be at least 1, since the trimmed right start is floor((u+x+w_h−1)/2)+1. The new width floor((x+w_h−u)/2) gives e_h,new≤floor(e_h/2). Thereafter h's left start remains left of c and is never transmitted during this streak; its close right side cannot cross the non-close left side without loss. Contraction does not increase positive e_h: the retained pivot range covers the interval from c to any relevant left endpoint of h's right side or endpoint of its left side that lies to the right of c. More directly, e_h is the left-side right endpoint minus c plus 2; if that endpoint is ≥c−1, there is no gap between it and c, and otherwise it cannot reach c−1 under compression because the close pivot domain keeps point c−1 covered. Trimming only shortens the left side. Thus each h witnesses at most 1+floor(log2 N) repeats per streak. These switch and repeat bounds give O((1+k) log(2+N)) cycles per no-loss run. The at most 2k drops in close count give O((1+k)^2 log(2+N)) cycles before k drops or r≤3/4. Restart the block on either event. Each k drop decreases X by at least two, and the other event decreases it by at least 4/3. Since 1≤X≤4^k N^k initially, there are polynomially many cycles. In each cycle sort at most 2k support intervals, contract gaps arithmetically, and test merger pairs and update the candidates after each of at most k mergers. For a +t transmission of a side starting at x in the pivot's range, the maximum inverse exponent is 1+floor((x−c)/t), computed by binary division rather than iterating unit shifts. All endpoints, exponents, counts, and gcd computations have polynomial bit cost in log(2+N), with polynomially many operations in k. This proves a bit-polynomial bound for the corrected rules.

The replacement recovers the polynomial-time orbit-counting result with the legal suffix rule. It neither proves a literal execution of Step 6 nor recovers the claimed quantitative bound.

A3

Checked statement: Corollaries 13–14: compressed construction of interval pairings from normal curves and normal surfaces, and the resulting component-count bounds.

Returned assessment: no_issue_found

The compressed reductions work for admissible normal data in the stated triangulations. Orient the triangulation edges and label the intersection points on each by a consecutive block using prefix sums, without listing the points. On each face the arcs of each corner type occupy contiguous blocks on its two sides and match in order or reverse order, as in Figure 4. Counts for curves come directly from their face coordinates; for surfaces a face count is the sum of the contributing disk coordinates from one incident tetrahedron, with matching guaranteeing the same answer on the other side. Edge counts are read from a local incidence. There are at most 3t nonempty pairings for t triangles and 12t for t tetrahedra, with offsets obtained by polynomially many binary operations. Components of a normal curve are the components of this endpoint-and-arc graph. For a normal surface the same graph is the one-skeleton of its normal cell structure, and filling the elementary disks cannot join separate graph components because each disk has connected boundary. Nor is there a component without vertices. Thus the orbit equivalence is exact. The polynomial running times depend on a valid orbit counter, such as the one with the new repair in A2, not the literal Step 6.

Premises used

  • The input is a normal curve or an embedded normal surface, not arbitrary counts lacking matching or, for surfaces, quadrilateral admissibility.
  • The triangulations provide the incidences and orientations needed to put local arc and edge orders into common coordinates.

Missing inputs

Scope changes

  • The proofs reuse W for edge-intersection weight whereas the corollary statements use the sum of coordinates. If the coordinate sum is S, the endpoint interval has N≤2S for curves and N≤4S for surfaces, by counting all local arc endpoints or disk corners. No equality is needed. Use log(2+S), or treat the zero case separately.
  • The component-count time statements are conditional on a correct bit-polynomial orbit counter. No later theorem is used for that dependency.

A4

Checked statement: Section 6: Lemma 15, Theorem 16, and Corollaries 17–18, including exact weight transfer, list operations, topology and bit complexity.

Returned assessment: claim_false

There are independent weighted correctness failures even with a repaired unweighted orbit counter. The printed periodic formula changes orbit sums, and the contraction instructions do not correctly specify either weight reindexing or a disjoint output list. An explicit output record per orbit would also defeat the time bound; the interval multiplicity representation described elsewhere in the section is the viable reading. With the new repairs below, weight is only moved within its orbit and the number of constant blocks remains polynomial. The application to normal components then works: select one local edge met by each nonzero disk type and put a unit in its coordinate at the corresponding contiguous block of disk corners. The orbit sum of that coordinate counts the disks of that type in the component exactly once. The resulting weighted orbit list gives component normal vectors with multiplicities, from which one can compute the topological type without expanding the surface or the output. These repairs recover compressed versions of the results, not correctness of the printed formulas.

Premises used

  • A1's orbit moves and the conditional polynomial cycle and bit bound for the corrected algorithm in A2.
  • A3's arc and disk representation, including its validity hypotheses.
  • Total initial vector magnitude can be measured using the sum of coordinate absolute values on the input blocks. For signed weights this measures magnitude rather than allowing cancellations to bound storage.

Missing inputs

  • The cited original HLP:99 Lemma 6.1 is not supplied. The precise numerical normal-coordinate estimate in theorem bound was not externally checked. An elementary replacement sufficient for Corollary 18 is given below.

Scope changes

  • Corollaries 17–18 output types or normal vectors with multiplicities; a literal enumeration of all components is not asserted by the repaired complexity bound.
  • In the orientability test the ambient orientability assumption is the standing assumption of the paper. The intrinsic orientation-cover construction is a new repair if the corollary is read without that assumption.
  • The numerical HLP bound and its historical version remain external to this audit; only the weaker, independently proved bound is used.

Located concern

AHT-TeX: weighted transfer Case (2) and Lemma orbitweights.same

The printed extra-residue rule starts its residual interval at a+floor(w_j/t)t instead of at r_j+floor(w_j/t)t.

Use g:[1,4]→[3,6] by +2 and a scalar weight 1 on [3,6], zero on [1,2]. Each residue orbit has weight 2. The full-block contribution is 2 at each representative, but the printed residual interval is [5,6], so it adds another 1 to each. The computed orbit weights are 3 and 3. In this example even the interval used for the excess is nonempty when the true remainder is zero.

New repair: for a constant block [r_j,s_j] of width qt+rho, add q times its weight to every representative in [a,c−1] and add one copy to the residues of [r_j+qt,s_j], empty for rho=0. Its residues are one or two ordinary intervals in the representative block. This counts the exact preimages in each residue class, agrees with the last-remainder-points reasoning in the proof, and preserves each global orbit sum. For the two disjoint-side cases, transfer using the inverse isometry directly.

The literal Lemma 15 orbit-weight assertion and Theorem 16's correctness fail. The corrected transfer has the required invariant.

Located concern

AHT-TeX: Lemma orbitweights.same, distinct weights and constant-interval bound

Distinct vector values and maximal constant blocks are different quantities. The stated bound on growth of the former is false; naive separate endpoint accounting for each residual interval does not prove the latter.

Use the disjoint translation [1,12]→[13,24]. On the domain put 10,10,20,20,…,60,60 and on the range put six copies of the pair 0,1. Transfer produces 10,11,20,21,…,60,61 on the domain and zero on the range. The number of distinct weights increases from 8 to 13, by five. If the initial 4k-change restriction is imposed, adding four identity generators gives k=5 and accommodates the 17 changes without affecting the example.

New repair: count change positions between adjacent points instead. If there are b internal jumps in the range, resetting the range removes those b old positions. In a disjoint-side transfer the inverse image creates at most b internal jumps plus jumps at the ends of the destination; resetting adds at most two more boundary positions. In the periodic case extend the old range function by zero and fold by residues. The discrete difference of the folded sum is the sum of the old differences on each residue. The b internal jumps and the two endpoint jumps at c and d+1 are its only sources, and c has the residue of a, not an interior change position of [a,c−1]. Thus there are at most b+1 new internal changes on the representative interval and at most three further boundary positions, a, c and d+1. The corrected transfer increases the constant-block count by at most four. If there are 4k changes initially, allow 4k+1 blocks; the proof works for arbitrary input m as in Theorem 16.

The distinct-value claim is false even for sound nonperiodic transport. The constant-block bound needed for complexity does hold for the corrected transport.

Located concern

AHT-TeX: Weighted orbit counting algorithm, Steps (2), (5)–(7)

The weight function after contraction is not specified on the whole shifted suffix, and successive output intervals are indexed by a shrinking working length. The algorithm also lacks an early exit when Step 2 removes the remaining points.

Deleting [r,s] requires the shift formula starting at new position r, not only at x>s. Take length 7 with sole pairing [6,6]→[7,7], and with weights 1 on [1,2], 2 on [3,5], zero elsewhere. A left-to-right contraction must copy old position 3 to new position 1. Even correcting that copy, the printed append rule first gives output [8,9] at length 7 and then [6,8] at length 5, overlapping at 8. With all pairings gone, Step 2 contracts all remaining points but Step 5 still calls for a maximal pairing before Step 7 tests for the empty interval.

New repair: intersect the static set with the current constant-weight blocks; append one record (multiplicity, vector) per piece, or use a separate increasing output counter to give the records disjoint consecutive labels. For deletion of [r,s], copy old weight at x+s−r+1 to every surviving new x≥r, leaving x<r unchanged. Reindex pairing sides independently by the same order-preserving compression. Return after Step 2 if there are no points. Use the legal suffix of A2 at Step 6, transferring the weight of the entire pivot range first as intended. Points actually truncated have weight zero; A1 guarantees that no orbit is lost by this truncation.

The printed list invariant and control flow do not suffice, even after repairing the periodic formula. The replacement preserves orbit sums and multiplicities.

Located concern

AHT-TeX: theorem weightedcount, output and bit-cost paragraphs

Explicitly writing one record per orbit is incompatible with the compressed-input bound. Current weight integers need not fit in log D bits, and the work at a contraction is not bounded by the initial block count m alone.

On [1,N], one pairing [1,1]→[2,2] and constant weight 1 give N−1 orbits from constant-size lists of binary integers. Explicit orbit records cost Ω(N) writes. For weight magnitudes use g:[1,N−1]→[2,N] by +1 with constant weight 1. The defined input D is 1 on the one-block encoding, but the surviving orbit weight is N.

The output is a list of interval multiplicities and weights, not an enumerated orbit list. Every entry during computation has coordinate magnitude bounded by N D, using absolute values or nonnegativity, so use O(log(2+N)+log(2+D)) bits per coordinate. Process the current number m' of constant blocks, not the initial m, by sorting and scanning block endpoints, and implement each periodic contribution by binary division, multiplication and at most two residual intervals. A uniform sweep or even pairwise interval refinement is polynomial in m', d and these bit lengths. Contraction does not increase m'; transfer increases it by at most four. At most O(m'+k) records are needed in any single contraction step by intersecting the two ordered partitions. Together with the repaired polynomial cycle bound, both total work and compressed output length are polynomial in the input parameters.

The polynomial assertion is valid only for compressed output, with the corrected bookkeeping, bit bound, and unweighted dependency. The prose defining L' already supports this compressed interpretation.

Located concern

AHT-TeX: corollary eulercount and the following corollary on fundamental surfaces

The claimed D=W bound does not follow and can fail. The text also stops at computing normal vectors without detailing how to obtain each topological type.

For the magnitude measured by the sum of absolute coordinate values, triangulate the suspension of the octahedral sphere by the two cones on its eight triangles. The link of one cone apex is normal with 8 elementary triangles and edge-intersection weight W=6. Every triangle contributes a unit in its own coordinate at one chosen radial edge. Nonzero point vectors have disjoint supports, so dropping repetitions in the block encoding cannot reduce the total magnitude below 8. Thus D=W is not valid with this norm.

Use at most 5t chosen local edge blocks (one per nonzero disk type), so there are at most 10t+1 constant blocks, and use D≤Σv_j≤7tW since each chosen block has at most W points and each disk contributes once. For each resulting component vector, count vertices from edge intersections, edges by counting its face arcs once per global face (including boundary faces), and faces by summing disk counts; compute Euler characteristic from these three numbers. Count boundary curves using A3 on the boundary triangulation. In the paper's orientable ambient setting, double the normal vector: the two possible local parallel sheets form the normal-side cover, which has two components exactly when the connected surface is two-sided, equivalently orientable. Alternatively, for a nonorientable ambient manifold, form the intrinsic orientation cover using two orientation states per disk. Across each internal face match the stacks of equal arc type, subdividing at the endpoints of the disk-type blocks on either side; pair the orientation states for which the induced arc orientations are opposite. This uses only constantly many interval pairings per face. The graph of disk copies across these arcs counts components of the cover because paths can avoid the vertices of the surface cells. Euler characteristic, boundary count and orientability determine the surface type. Do this once per compressed record. For Corollary 18, a new elementary bound avoids importing the uninspected precise estimate: with n=7t coordinates, any support-minimal nonzero nonnegative kernel ray has one-dimensional kernel on its support (otherwise perturb in an independent kernel direction until a coordinate vanishes in a nonzero nonnegative solution). A primitive integer generator is bounded coordinatewise by the maximal minors of independent matching rows restricted to that support; this follows by taking the signed cofactor vector and dividing by its gcd. Entries of the matching matrix have absolute value at most 2, so the determinant expansion bounds the minors by (n−1)!2^(n−1). Repeatedly subtract a maximal nonnegative real multiple of such a generator supported in the positive coordinates of the remainder. Each subtraction drops a support index, giving at most n summands. For an indecomposable integer vector, a coefficient at least one forces the vector to equal that primitive generator, since subtracting the generator otherwise leaves a nonzero nonnegative integer kernel vector. In the other case every coefficient is less than one. This bounds coordinate bit lengths, and hence log(2+W), by O(t log(2+t)), sufficient for Corollary 18.

The compressed topology results can be recovered without the erroneous D=W substitution. The independently derived bit bound does not verify the exact constants of the cited HLP estimate.

Outside the audit

  • The precise text and proof of the cited HLP:99 Lemma 6.1 and other unsupplied external references.
  • The genus hardness and NP membership proofs, the spanning-area reduction, and the paper's other unassigned claims.
  • Journal receipt date, version history beyond the recorded fallback, priority, and subsequent literature.
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}
}