TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)verified 2026-10-22 (gpt-6.1-sol)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Correctness and finite bounds of the Jaco–Tollefson vertex search

Statement

For a valid one-component knot code, the JT primitive extreme-ray search accepts if and only if the triangulated exterior contains a properly embedded disk with non-null-homotopic boundary. It examines at most $2^{7 t}$ support subsets for a $t$ -tetrahedron exterior, each candidate coordinate has $O (t)$ bits, and its sequential Turing space is $O (t^{2} \log (t + 2))$ bits.

Statement references

Haken–Jaco–Tollefson normal-surface unknot search — JT support enumeration and its candidate tests.

Matching equations and finite bounds for normal coordinates — primitive-ray coordinate bound.

Jaco–Tollefson normal essential-disk vertex theorem — existence of an essential disk on a primitive vertex ray.

Finite normal-coordinate tests characterize essential disk candidates — soundness of the disk tests.

Facts & Assumptions

Given: A valid one-component knot code, its $t$ -tetrahedron good exterior, and its marked original meridian.

[F1]

Haken–Jaco–Tollefson normal-surface unknot search: the JT branch enumerates zero-coordinate supports, computes each one-dimensional nonnegative kernel ray, and accepts exactly when an admissible primitive generator passes the boundary, Euler-characteristic and meridian tests.

[F2]

Matching equations and finite bounds for normal coordinates: each primitive integer generator on an extreme ray has coordinates at most $2^{7 t - 1}$ .

[F3]

Jaco–Tollefson normal essential-disk vertex theorem: if a triangulated compact PL $3$ -manifold with nonempty boundary contains an essential disk, it contains such a disk represented by a primitive normal vector on an extreme ray.

[F4]

Finite normal-coordinate tests characterize essential disk candidates: an admissible normal vector passing nonempty-boundary, Euler-characteristic-one and odd-meridian tests represents a properly embedded disk with essential boundary; a fundamental vector is connected.

[F5]

Exact small-entry matrix algebra in quadratic logarithmic workspace: an $O (t)$ -by- $O (t)$ matrix with entries in ${- 1, 0, 1}$ admits exact rational rank, independent-row selection and primitive nullity-one kernel computation in polynomial time and $O (t^{2} \log (t + 2))$ sequential Turing workspace, by streamed prime-field elimination and bounded Chinese remaindering.

Proof

1.1givenF1F4algebra

If the JT search accepts, its vector is an admissible normal vector passing the candidate tests by [F1]. The vector is primitive on an extreme ray, hence fundamental: a sum of two nonzero cone vectors on an extreme ray would have each summand on that ray, and the primitive integer generator cannot split into two positive integer multiples. By [F4], the associated surface is a properly embedded disk with essential boundary.

1.2givenF1F2F3F4construct

If $E$ contains an essential disk, [F3] supplies such a disk whose vector lies on a primitive extreme ray. By [F2], each coordinate is at most $2^{7 t - 1}$ and therefore has at most $7 t$ bits. Let $Z$ be exactly the set of zero coordinates of this vector. The support loop in [F1] examines this subset, the combined matrix has nullity one, and its kernel generator is the stated vector. The vector is admissible and its normal disk passes the remaining tests by [F4], so the JT search accepts.

2.1F1F2F5step 1.2algebra

There are $2^{7 t}$ coordinate supports, so [F1] examines at most that many candidates and stores no list of prior rays because each ray is found at its unique exact zero support. Each candidate has $7 t$ coordinates of $O (t)$ bits by [F2]. The matching and active-coordinate matrix has $O (t)$ rows and columns with entries in ${0, 1, - 1}$ . Implement its rank, independent-row and cofactor-kernel calculations by [F5]. That supplier stores one prime-field residue matrix with $O (\log (t + 2))$ -bit entries, streams its primes and determinant residues, stops reconstruction as soon as the modulus exceeds twice the integer determinant bound, and reuses the matrix space for successive cofactors. Thus these exact calculations take polynomial bit time and $O (t^{2} \log (t + 2))$ workspace without retaining a matrix of large exact elimination fractions. The candidate, support counter and finite boundary linear-form tests fit within the same bound.

3.1step 1.1step 1.2step 2.1algebra∎

Steps 1.1 and 1.2 prove acceptance exactly when an essential disk exists. Step 2.1 proves the stated candidate, bit-length and space bounds.

Depends on

Used by

Termination, correctness, and bounds of normal-surface unknot recognition Theorem

Dependency tree · two levels

21 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger, The Computational Complexity of Knot and Link Problems, Journal of the ACM 46 (1999) (standard reference, not scraped)
Jeff Erickson, Normal Surfaces and Knots, Computational Topology lecture notes (2009) (standard reference, not scraped)