gpt-6.2-astra high: aht-dependency-challenges
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 conditional defect propagates to claims of polynomial running time exactly where a proof imports the general cycle bound or a counting interface built on it. It does not propagate simply by citation. The certification work proves input-size and geometric reconstruction bounds but imports weighted orbit computations; genus 8.6 reuses the bundle result. The pants proof, by contrast, gives an amortised bound for its own track moves. The knot-genus verifier needs scalar counts, while the link verifier needs componentwise information. Expanded weighted output has a separate output-size obstruction that scalar counts, marked queries, or batched results need not have. No supplied example proves that unweighted AHT runs in superpolynomial time or that any of the downstream complexity-class decisions is false.
D1
Checked statement: Whether the certification and fixed-manifold genus excerpts independently justify the polynomial-time weighted computations they use.
Returned assessment: unresolved
The dependency is identifiable; the missing general time estimate is not supplied by these applications. In AHT the weighted proof preserves orbit sums by transferring weight off points before truncation and recording sums at contraction. Its time argument has two factors: the number of underlying steps, taken from unweighted orbit counting, and the extra cost per step. In particular, growth of the number m' of constant pieces by at most four per step is useful because the number of steps is supposed to be polynomial; it does not prove that number is polynomial. For a normal surface, AHT labels edge intersections, pairs endpoints of face arcs, and counts each disk of type j once at a chosen incident edge in coordinate j. Paths along the arcs detect components because each normal disk has connected boundary. Thus an orbit sum is a component vector, not just a component count. The reduction gives N=W, k≤12t, d=7t and O(t) initial weight pieces. Even if D denotes a total norm rather than a bound per coordinate, each disk count is at most W and their sum is at most 7tW, enough for the logarithmic estimate. The last corollary additionally uses the fundamental-coordinate bound to bound log W; this is not a new orbit algorithm.
Certification Theorem 9.1 is explicitly attributed to AHT. Here D is the maximum pointwise ℓ1 norm, not the total norm: ND bounds the sum of pointwise norms, so orbit sums still have polynomial bit length. Theorem 9.2 does substantial work of its own. It first constructs the complement of B− (the parallelity handles under consideration between parallel discs). Uniform handle type bounds the disc types per handle; boundary regulation limits incoherently oriented adjacencies. This leaves O(h) non-parallelity handles with bounded local incidence. The complement, vertical interface pieces, and boundary signs can be found without constructing all the cut handles. For type i with x_i discs, max(0,2(x_i−1)) counts the horizontal disc faces in its stacks, with boundary orientations distinguished as in the proof. Incidences of types across attached handles give O(h²) interval bijections. Their orbits are components of the horizontal boundary of B−. The first three orbit sums count surface handles, giving χ by the alternating sum; a fourth detects meeting ∂M, and the remaining coordinates label incidences with the complement. For a vertical interface, knowing whether its two horizontal sides belong to the same horizontal component distinguishes twisted from product in the incident connected bundle. Entire components without such an interface require separate treatment; in the closed case p. 76 also invokes AHT for normal vectors of components of S and tests by cutting along closed components. A second interval system on [1,N′] follows portions of the vertical/horizontal boundary away from the complement. Its weights identify the incident ends on the complement; with the local square data this yields the required order around vertical boundary, not just the number of squares. Finally the boundedly many complementary handles lying in the full bundle can be attached to B−. These are reductions to orbit computations and geometric deductions from their answers. The first system has d and pointwise D bounded linearly in h, polynomially many weight changes, and N bounded in terms of h and w(S) as on p. 76. Substitution in Theorem 9.1 explains the claimed polynomial in h and log w(S); it gives no independent bound on transmissions or cycles on these inputs.
Theorem 9.2 excludes bundles between normally parallel closed components from its per-component request and uses transverse orientation data for its sutured conclusions. The pair version, 9.3, takes a triangulation and an orientable normal vector; it requests the complement, base genus and boundary count, product/twisted bit, and vertical attaching data, without the sutured product test. Its proof is referred to minor modifications of 9.2. Theorem 9.4, cutting a surface along a normal 1-manifold, requests complementary topology, locations at the old boundary and vectors of new boundary curves; its proof is omitted as an easier variant. In §13.2 the directly named AHT calls are (1) testing a union of tori, (7) determining components and their Euler characteristics and testing their signs (used in (8)), and (9) testing normal parallelism to a unique component with a preassigned disc orientation. These are tests of types, component data and marked classes; it is not stated that every call must print all general weighted orbits. Step (6) uses 9.4 to test for disc-bounding boundary curves. Other steps have their own named prerequisites, e.g. (2) uses 11.4 and 10.3, (10)–(11) use orientation/intersection theorems and (13)–(14) use Corollary 9.5. The verifier list is not a proof of those subroutines.
Lackenby–Yazdi 8.6 is the pair theorem 9.3 of [21] (identified on p. 42), not a reanalysis of AHT. In the sphere/disc cutting sketch it provides a small complement and the bundle type and attaching locations, including the order of squares when part of the vertical boundary runs along ∂X. The sketch uses planarity of the horizontal pieces, a bound on the non-bundle handles and a stated bound on the total number of base boundary curves to budget triangulations (100t plus 100t). It separately describes the cocycle extension, its 1200t size factor, and why a possible vertical difference class is trivial in this application. Those are different estimates from the time to obtain the bundle information. Neither 8.6 nor this substitution is an independent general weighted counting proof. Nor is the whole proof of the fixed-manifold co-NP result on these pages.
Premises used
- Conditional premise: the polynomial cycle bound for the general unweighted algorithm is not taken as established by its printed progress argument.
- An orbit sum is the sum of point weights, not a description of all original points in the orbit.
- Time polynomial in log N is measured on a succinct input, including binary interval endpoints and weights.
Missing inputs
- An independently justified polynomial subroutine for the required weighted or marked queries on the induced systems, or a valid general bound with suitable output semantics.
- Full weighted list/transfer definitions before AHT line 1953; a representation and cost analysis for repeated components and all required incidence queries.
- Separate details for certification 9.3, 9.4 and the other verifier subroutines whose proofs are not on the supplied pages; the full route to the fixed-manifold co-NP theorems.
Scope changes
- The unresolved part is the polynomial implementation with the needed interface, not the identification of the dependencies.
- The fixed closed (or fixed toroidal-boundary) manifold with a fixed surgery diagram in Lackenby–Yazdi is not AHT's variable-manifold NP-hard language.
Located concern
AHT-dependency-excerpts 1953–1965, 1981–2001; Lackenby-certification pp. 72–73, Theorem 9.1
In addition to the conditional cycle-count issue there is a representation issue. An explicitly expanded 'list with one point for each orbit' cannot have the stated uniform time bound.
Take even N=2^s, one translation [1,N/2]→[N/2+1,N], and constant scalar weight 2. All points are covered, the pairing is nontrivial, and there are N/2 two-point orbits of weight 4. The parameters other than the logarithms are constant, log(total weight)=O(s), and log(maximum point weight) is constant. Merely writing N/2 records takes Ω(N) time. This is an output lower bound even with a perfect cycle bound.
Distinguish batched output, marked queries, and output-sensitive expansion. For example, at contraction a static constant-weight run of length q represents exactly q singleton current orbits with that accumulated weight; a run and a binary multiplicity suffice for that batch. A marker coordinate equal to 1 only at a specified original point singles out its orbit sum even among otherwise identical weights. Such observations explain possible succinct interfaces; they do not prove a polynomial implementation of all transfers, representative lookups, or later topological queries under the conditional premise.
The literal expanded general output specification fails, not the scalar unweighted count. An interval list representing many points at once escapes this example. The application must say what can be recovered from its compressed answer.
Located concern
Lackenby-certification pp. 74–77; Lackenby-Yazdi-genus pp. 32–33
Small complement and few marked attachments are not a bound on the number of all unmarked components. Conversely, an application that only needs types, multiplicities and marked incidences need not enumerate every parallel copy.
A binary multiple q of a two-sided normal vertex-linking sphere gives q parallel spheres at fixed triangulation size and q−1 intervening product layers. Closed product layers have no vertical attaching squares. Bounds on the squares or on the total number of base boundary circles do not charge one item for each such layer. The 9.2 exclusion matters and is not stated in the same form in 9.3/8.6.
For a succinct interpretation specify multiplicities for parallel unmarked data and retain component vectors and labels sufficient to locate the marked sides and recover attachment order. For explicit constructions justify a restriction bounding the components actually materialized or account for their output size. A full repair for the stated range of applications is not established here.
One cannot discharge 9.1 by substituting a scalar count, or discharge all output costs by bounding h, d, m and log N. This does not exhibit a false certification decision or a counterexample to co-NP membership.
D2
Checked statement: The pants-distance proof has a restricted progress estimate; its citation of general AHT does not import the general reflection/trimming progress argument into that estimate.
Returned assessment: no_issue_found
The background quotes AHT for arbitrary interval systems, and the moves and orbit interpretation are taken from that algorithm. The proof used for distance is about the systems of based integrally weighted train tracks on a compact orientable surface, with an initial tie-interval identification and an active part having a non-base vertex. Base tie intervals are put first; the active right endpoint occurs at a non-base tie with two incident widths. The authors use at-most-two coverage to exclude mergers and orientability of this track construction to exclude overlapping reversing pairings requiring trimming. This is not the assertion that all arbitrary pairings on an ordered set preserve orientation. A shifted processing cycle transmits and truncates, then cleans up by steps (1)–(4); deleted circle data are kept in the stationary part. The key closure assertion proved by the split/twirl description is that another track instance results: disjoint ends of the maximal branch give splits along that branch, overlapping ends give a twirl (batching repeated traversals). Thus the hypotheses for the next active move are geometric invariants, not assumptions about five arbitrary AHT cycles.
The amortisation, following Dynnikov–Wiest, is displayed in the paper. With positive integer active widths z_i and narrower right-end width u, set C=r+Σlog₂(z_i)−½log₂(u). Let z≥u be the maximal width and let u′ be the new narrower width. In the branch-loss case the charged decrease is at least 1+log₂(z)−½log₂(u)+½log₂(u′)≥1 for a nonempty successor. In the continuing case the split geometry on p. 35 gives z≥u+u′: the residual is obtained after subtracting a positive multiple of a segment of length at least u. Other retained widths do not offset this loss. The decrease is at least log₂(z)−½log₂(u)−½log₂(u′)≥1 since z²≥(u+u′)²≥4uu′. This is a one-move potential and does not use counting of Z-close intervals. C is nonnegative (u is itself a branch width) and initially at most E+E log₂|μ|. This bounds the number of effective shifted moves, treating the empty active part as terminal and the initial (1)–(4) cleanup as setup, not charging a unit decrease for an idle setup. Lemma 4.17 gives the stated train-track sequence bound 1+E+E log |μ| with its no-complementary-bigon hypothesis. Splits are batched in O(E) size groups, or one has an encoded twirl; 4.13 supplies a polynomial construction per move, not an iteration over every strand.
In Theorem 1.2 the input tracks satisfy E≤3|χ(S)| and |μ|=i(P,P′). The move-distance costs use other geometric lemmas: they sum O((k_i+1)|χ(S)|) with Σk_i=O(|χ(S)|), and the initial distance costs O(|χ(S)|²). Substitution of the track bound gives O(|χ(S)|² log i(P,P′)) for i≥2. What matters is the sequence of moves, not just the answer to an orbit-count query. There is no step in this progress calculation that needs a right-to-left reflection of a general overlapping band to make a Z-close interval non-close.
Premises used
- Train-track incidence and split/twirl width relations in Proposition 4.13; the log decrease is checked on those relations.
- The orbit algorithm and the special train-track construction are distinct from a general algorithm for weighted orbit lists. Here the branch weights specify widths.
Missing inputs
- Some train-track definitions, figures and earlier geometric lemmas invoked on pp. 33–37 are not in the packet; this is an audit of the progress dependency, not a verification of every track or pants-move construction.
Scope changes
- No transfer of a general trimming objection to these track moves is justified without an example obeying the track, orientation, incidence and cycle hypotheses.
- Conversely the two-end width inequality and preservation of the track form have not been proved for general AHT inputs. The restricted proof is not a general repair.
D3
Checked statement: The independent alternatives in the packet have different inputs and outputs; none of the inspected proofs supplies a general weighted AHT theorem.
Returned assessment: no_issue_found
SSS states deterministic polynomial normal-curve algorithms including the vector of the component through a marked crossing, a component count, and non-isotopic curves with occurrence counts. Its word-equation/straight-line-program approach is presented as different from orbit simplification. The Las Vegas statements in Theorem 2 are not the component-count statement in Theorem 1(b). Importantly, p. 4 expressly extends part (b) to counting components of a normal surface and says that the proof is omitted. This is evidence for a possible alternative even for a 3-dimensional application; it is not an inspected proof, and it does not extend all the curve outputs to surfaces. Conditional substitution is quite specific: given a polynomial normal-surface counter, count components of F and, for connected F in an orientable ambient manifold, of the surface with vector 2v(F). The latter is the transverse double, two components in the two-sided case, one in the one-sided case. This checks connectedness and orientability. The boundary curve count is a 2-dimensional normal-curve problem. These operations replace the orbit-count calls in the AHT genus verifier without producing a single weighted list.
Erickson–Nayyeri describe a different mechanism on compact orientable triangulated surfaces: trace into a small street complex, skip redundant decisions and batch long spirals. For example tracing one component and comparing its crossings with the total tests connectedness; untracing that component gives its coordinates. Their stated tracing scale is O(min{X,n² log X}), in the integer RAM model for normal coordinates with words holding crossing counts (bit costs matter when comparing precise bounds). Their discussion of reduced curves and classes must not be read as printing arbitrarily many parallel copies in polylogarithmic time. They quote AHT and compare running times; that comparison is not the derivation of their tracing algorithm. This is pertinent to boundary curves, not a reduction from branched incidence systems of normal discs in a 3-manifold or from arbitrary weighted interval pairings.
HLP concerns in particular a diagram of a knot in S³ and an essential normal disc in its exterior. Page 20 supplies a polynomial-size triangulation and a marked meridian. Pages 21–24 describe admissibility, nonempty boundary, χ=1 for a connected surface, and a nontrivial mod-two boundary class tested at the meridian. These are small calculations on the vector once connectedness is secured. A special way to secure it is a primitive minimal vertex solution: a one-dimensional face can be certified by the rank of the matching equations with the active zero coordinates, and primitivity by a gcd. In a nonnegative decomposition both summands must stay on that ray and be integral multiples of the primitive generator. Thus no decomposition into two nonempty surface vectors exists; a disconnected surface would give just such a decomposition. HLP invokes existence of a suitable vertex disc in this setting. It also describes exhaustive, not polynomial, testing for fundamentality in a different search. Guessing an arbitrary vector and calling it fundamental is not this vertex argument. Inspection stops on p. 24 during the proof of Theorem 1.1. Neither the disc existence theorem nor this special certificate shows that every low-genus spanning surface problem admits a suitable vertex certificate. HLP's PSPACE result mentioned in the abstract is not a polynomial verifier for the general genus problem.
Premises used
- Use SSS's stated surface extension as a conditional black box only, distinct from having its proof.
- A component of a disconnected embedded normal surface contributes a nonzero admissible summand of its vector.
- Boundary component counting on the triangulated peripheral torus has normal-curve input.
Missing inputs
- SSS pp. 5–9 are not supplied; the conference version explicitly omits the surface-count proof. References and abstracts do not fill that omission.
- Erickson-Nayyeri's detailed tracing, time analysis, untracing and application sections after the introductory material are not supplied.
- HLP coverage is exactly pp. 1, 20, 21, 22, 23, 24; earlier normal-surface lemmas and the continuation of the NP proof after p. 24 were not inspected.
Scope changes
- There is evidence of independent curve methods and an announced independent scalar surface method. There is no verified extension here from these results to all the marked, weighted, bundle-incidence and attachment-order computations of D1.
- The HLP verifier is an alternative in its unknot setting, not an AHT-dependent casualty and not a general component oracle.
D4
Checked statement: What remains justified about the AHT genus proof, the survey account, and the classical-link NP proof if the original general progress estimate is not justified?
Returned assessment: unresolved
The AHT proof separates orbit preservation/correct accounting and termination (including a decrease of the current length yielding a bound in N) from polynomial time in the bit length of N. Its general time proof charges a halving of X=4^k∏w_i over O(k) cycles, using the five-cycle Z-close claim, the truncation estimate and the decrease at pairing loss. A polynomial cost per cycle and log₂ X_initial≤k(2+log₂ N) do not do this without progress. Even a counterexample to a progress assertion would not by itself be a family requiring superpolynomial running time, much less wrong orbit counts. For example, the local statement at lines 1311–1313 that disjointness forces every transmitted interval to be non-close is too strong with the printed weak inequality: take Z=2w and reflection [1,w]→[w+1,2w]. The inverse of the full range has width w=(Z−1+1)/2. But this is an equality case: for disjoint ordered ends of width w starting at a on the left, Z≥a+2w−1, and closeness of the left end forces equality and adjacency. A proper subinterval of that left end is then non-close. A transmission after the ambient size has already fallen strictly below the fixed Z cannot attain that equality. This observation distinguishes a false local implication from a counterexample to the sequence actually needed; it neither settles all the progress claims nor proves Theorem 12 false.
For AHT's variable-manifold problem the certificate is a short normal spanning-surface vector, with admissibility, peripheral boundary/essentiality, connectedness, orientability and genus tests. Lines 1671–1694 call for the surface count, the boundary count (also discussing an alternative), and the doubled-surface count. Euler characteristic can be computed by counting cells with binary multiplicities; it does not require listing orbits. Lines 1712–1718 give W≤28t²2^(7t+2) in the working triangulation, hence log W=O(t+log t); subdivision changes t by only a constant factor. This bounds certificate and arithmetic sizes, not the time of an O(W)-cycle verifier. The dependence is on unweighted counting, not AHT's later explicit weighted-output specification. NP-hardness is separately ascribed to a polynomial reduction from ONE-IN-THREE SAT, not to verification of the certificate. The reduction proof is not in the excerpts. Under the premise of this audit, it is the exhibited polynomial verification route, hence that route to combining membership with hardness, that needs justification.
The survey accurately separates a scalar number of equivalence classes from enhanced weights. Tagging two points with unit weights tests whether some orbit has weight two; edge tags give per-component edge counts for recovering normal vectors. Orientability by doubling and boundary counts are scalar applications. The band picture explains the moves and the survey repeats the 5k-cycle halving bound, expressly referring the delicate proof back to AHT. It gives no replacement cycle estimate. Its genus discussion does give geometric certificate information: a normal spanning surface meeting a meridian once, a least-weight/fundamental summand argument, bounded weight, a single winding-one boundary and the Euler characteristic test. Those steps do not prove fast component checks. Page 27 separates the hardness direction and turns to a related link problem; it is not an independent proof of AHT's time bound.
The link paper treats an unoriented classical link in S³ and an upper bound on the sum of max(0,−χ) over components of an orientable Seifert surface. It does more than quote the knot-genus result. It uses a triangulation of size linear in the diagram complexity and prescribed boundary curves intersecting each edge at most once. In a fundamental decomposition the boundary curves cannot be split among summands along an edge. If there are more summands than link components, one summand is closed. The least-weight argument on pp. 4–5 rules this out for the chosen minimizer: in the orientable remainder case the closed summand has nonpositive χ and removal does not increase χ−; the other case uses orientation-respecting regluing and a cited weight reduction. Thus at most b summands for a b-component link and a coordinate bound b times the fundamental bound suffice. This bounds binary certificate length by adding only O(log b) bits per coordinate. The certificate includes the induced link orientation and the vector. Page 5 still invokes AHT to obtain components and their Euler characteristics, to check the sum of negative parts along with the required boundary. For a disconnected surface total χ alone need not determine χ− (a disc can offset a negative component in total χ). The short-vector argument does not perform that computation. The link paper starts a separate link-specific 1-in-3-sat reduction with sentence satellites and bands; an objection to the component verifier is not an objection to that reduction.
Premises used
- The question is conditional on a gap in the general progress proof; no lower bound for the actual running time is assumed.
- Normal-form existence, fundamental-size estimates and the cited geometric minimizer results are distinguished from verification algorithms, not independently reproved in this dependency audit.
Missing inputs
- A complete progress proof, a substitute normal-surface algorithm with the requisite proved time bound, or a different verifier for whichever membership result is at issue.
- Full AHT hardness and normal-count reductions and full classical-link hardness proof; the cited normal-surface existence and weight-reduction proofs.
Scope changes
- The survey's scalar and enhanced general claims, AHT's variable-manifold genus verifier, and the link paper's componentwise Thurston-complexity verifier require different interfaces.
- The dependency criticism concerns these proofs as supplied, not the truth or novelty of the later decisions, and not all possible proofs in the literature.
Located concern
Lackenby-survey pp. 24–27; AHT-dependency-excerpts 1426–1443, 1671–1694
Rephrasing the progress estimate or bounding the witness size does not supply the missing time bound.
N may be exponential in t on the very coordinate bound used by the verifier; the elementary termination bound polynomial in N is insufficient.
For this use it suffices to prove polynomial normal-surface connectedness/count and boundary-curve count on the indicated inputs, including 2v(F); the substitution in D3 proves sufficiency. One need not repair an expanded weighted-list theorem. Unconditional completion by the alternative surface method is not verified in this packet.
Conditional gap in support for the printed NP upper bound, not disproof of NP membership or of the separately argued hardness.
Located concern
Lackenby-links pp. 4–5
The bound on the number of fundamental summands is a certificate-existence estimate, not a polynomial per-component algorithm.
The proof invokes the component/χ list after bounding the digits of [S]. It does not use the summand bound to identify the components of [S]. A normal sum is not in general a disjoint union of its summands.
A polynomial computation of χ− together with verification of the orientable spanning and prescribed-boundary conditions suffices. Alternatively, a proved output-sensitive component/type algorithm would suffice on the chosen witnesses: after discarding closed components, each component uses a distinct nonempty subset of the b boundary curves, so at most b records need be output. A verifier using such a bound could time-limit the computation and reject excessive outputs on other guesses. The algorithm furnishing that bound is still needed.
This restricted need avoids the unrestricted explicit-list lower bound on honest witnesses, but the link paper's special certificate bound alone does not discharge the AHT invocation. No negative complexity-class conclusion follows.
Outside the audit
- Only the four numbered AHT line ranges were inspected; in particular the preceding move/weighted-list definitions and lemmas, hardness reduction and omitted normal-surface proofs were not inspected.
- Only the selected pages of the certification, genus, survey, pants and link works were inspected, not complete proofs of their main theorems or of all cited special-case geometric estimates.
- The missing SSS surface proof, omitted curve proofs, later Erickson-Nayyeri analysis, and the HLP material outside pp. 1 and 20–24 were not inspected.
- No external search, code execution, exhaustive test of algorithm trajectories or exhaustive assessment of possible repairs was performed.
Additional supporting archive items are identified in the original report. View the manuscript hashes and repository snapshot.