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.

Unknot recognition has a polynomial-bit normal-surface certificate

Statement

Assume countable choice. For a valid finite $n$ -crossing one-component knot code $D$ , let $T_{D}$ be the fixed deterministic good exterior triangulation with $t \leq C (n + 1)$ tetrahedra and the marked original meridian path, recomputed from $D$ by the stated finite construction. The smooth knot represented by $D$ is the unknot if and only if it has a certificate consisting of a nonnegative $7 t$ -coordinate normal vector $v$ , active matching and zero-coordinate constraints, and a nonzero $(7 t - 1)$ -minor witnessing their rank, all relative to $T_{D}$ . A deterministic verifier reconstructs $T_{D}$ and its meridian path from $D$ and checks the certificate in time polynomial in its bit length, without expanding the represented normal surface.

Statement references

Haken–Jaco–Tollefson normal-surface unknot search — the fixed finite exterior and JT primitive-ray interface.

Polynomial verification of a primitive normal vertex-disk certificate — polynomial-time sound verification of a primitive normal vertex-disk vector.

Jaco–Tollefson normal essential-disk vertex theorem — completeness of primitive vertex-disk certificates.

Meridian-disk criterion for unknot recognition — the proved conversion between unknotting and compatible PL exterior disks.

Linear-size good exterior triangulation from a planar knot code — deterministic $O (n)$ exterior construction.

Facts & Assumptions

Given: Countable choice, a valid finite one-component knot code $D$ , and the certificate format in the statement.

[A1]

${A C}_{ω}$ is inherited through the smooth isotopy-extension and code-to-exterior interfaces.

[F1]

Smooth knots have compatible piecewise-linear exterior models: $D$ has a smooth representative in its diagram type and a deterministic good exterior triangulation of size $t \leq C (n + 1)$ with a marked original meridian.

[F2]

Polynomial verification of a primitive normal vertex-disk certificate: an accepted certificate gives a properly embedded disk with non-null-homotopic boundary, and verification is polynomial in its encoded length.

[F3]

Jaco–Tollefson normal essential-disk vertex theorem: if an essential disk exists, one is represented by a primitive normal vector on an extreme ray.

[F4]

Meridian-disk criterion for unknot recognition: unknotting is equivalent to an essential disk in the compatible PL exterior, by finite relative rounding and the smooth disk-boundary isotopy.

[F5]

Matching equations and finite bounds for normal coordinates: each primitive vertex coordinate is at most $2^{7 t - 1}$ .

Proof

1.1givenA1F1construct

The given countable-choice hypothesis [A1] is the choice assumption used by [F1]'s exterior model. Reconstruct $T_{D}$ and the marked path using its fixed code order and local templates. The verifier does not accept a triangulation supplied by the certificate, so the certificate cannot substitute an unrelated manifold.

2.1F2F4step 1.1construct

If the verifier accepts, [F2] gives an essential disk in the exterior of the represented smooth knot. By [F4], the knot is the unknot. The relative rounding and disk-boundary isotopy in [F4] apply to exactly this compatible exterior model.

2.2F2F3F4F5step 1.1constructalgebra

Conversely, suppose the knot is the unknot. By [F4], its exterior contains an essential disk. By [F3], there is such a disk represented by a primitive vertex vector $v$ . By [F5], each coordinate is at most $2^{7 t - 1}$ and therefore has $O (t)$ bits; the full vector has $O (t^{2})$ bits. The active matching and zero-coordinate rows at this extreme ray have rank $7 t - 1$ , so choose $7 t - 1$ independent rows and a nonzero square minor. Such a minor exists by the rank definition and has polynomial encoded length. The resulting certificate is accepted by the polynomial verifier [F2]. The primitive vertex-disk theorem [F3] supplies completeness, and the disk criterion [F4] supplies both conversion directions.

3.1F1F2step 2.2algebra∎

Since $t = O (n + 1)$ by [F1], the vector, row indices and determinant witness all have polynomial bit length in $n$ . The verifier reconstructs $T_{D}$ in polynomial time and checks matching equations, gcd, rank, boundary, Euler characteristic and meridian parity through compressed arithmetic as in [F2]; it never lists the exponentially many normal disks.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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