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 of the Haken finite-box disk search

Statement

For a valid one-component knot code, the Haken finite-box search accepts if and only if the triangulated exterior contains a properly embedded disk with non-null-homotopic boundary. On acceptance it returns a normal-coordinate vector for such a disk; after exhaustive rejection, no such disk exists.

Statement references

Haken–Jaco–Tollefson normal-surface unknot search — Haken finite-box search and its acceptance tests.

Matching equations and finite bounds for normal coordinates — matching characterization and fundamental-vector bound.

Haken normal essential-disk existence theorem — existence of a fundamental normal essential disk, with its no-projective-plane hypothesis.

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

No closed nonorientable piecewise-linear surface embeds in the three-sphere — the knot exterior contains no embedded projective plane.

Linear-size good exterior triangulation from a planar knot code — triangulated knot exterior used by the search.

Facts & Assumptions

Given: A valid one-component knot code, its good triangulated exterior $E$ , and the marked original meridian.

[F1]

Haken–Jaco–Tollefson normal-surface unknot search: the Haken branch enumerates every admissible fundamental vector in the coordinate box and accepts exactly when the boundary, Euler-characteristic and meridian tests pass.

[F2]

Matching equations and finite bounds for normal coordinates: every fundamental normal vector for a triangulation with $t$ tetrahedra has each coordinate at most $t 2^{7 t + 2}$ .

[F3]

Haken normal essential-disk existence theorem: if a compact triangulated PL $3$ -manifold with nonempty boundary has no embedded projective plane and contains an essential disk, it contains a fundamental normal essential disk.

[F4]

Finite normal-coordinate tests characterize essential disk candidates: an admissible normal vector passes the nonempty-boundary, Euler-characteristic-one and odd-meridian tests exactly when its surface is a disk with essential boundary; fundamentalness supplies connectedness.

[F5]

No closed nonorientable piecewise-linear surface embeds in the three-sphere: no closed nonorientable PL surface embeds in $S^{3}$ .

Proof

1.1givenF1F4construct

If the Haken search accepts, [F1] says the vector is admissible and passes the candidate tests. By [F4], its normal surface is a properly embedded disk with non-null-homotopic boundary.

1.2givenF2F3F4F5construct

Conversely, suppose $E$ contains such a disk. Any embedded projective plane in $E$ would also be a closed nonorientable PL surface in $S^{3}$ , contradicting [F5]. The exterior has nonempty boundary by its construction. Thus the hypotheses of [F3] hold, and [F3] gives a fundamental normal disk $S$ with essential boundary. Let $v (S)$ be its normal-coordinate vector. By [F2], each coordinate is at most $t 2^{7 t + 2}$ , so the Haken box enumerates $v (S)$ . Its boundary is nonempty, it is connected by fundamentalness, its Euler characteristic is one, and its boundary has odd meridian intersection by [F4]. Therefore the algorithm accepts no later than when it reaches $v (S)$ .

2.1F1F3step 1.1step 1.2algebra∎

Steps 1.1 and 1.2 prove that acceptance is equivalent to existence of an essential disk. If the finite search exhausts without acceptance, step 1.2 shows no such disk can exist.

Depends on

Used by

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

Dependency tree · two levels

27 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)