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.
Matching equations and finite bounds for normal coordinates
Statement
Let be a finite tetrahedral triangulation of a compact piecewise-linear -manifold with tetrahedra. A nonzero nonnegative integer vector in is the normal-coordinate vector of a normal surface exactly when it satisfies every face-matching equation and at most one quadrilateral type is nonzero in each tetrahedron. Every primitive integer generator of an extreme ray of the Haken cone has each coordinate at most . Every fundamental normal-surface vector has each coordinate at most .
Statement references
Normal-surface coordinates and the Haken cone — seven disk types per tetrahedron, face matching, quadrilateral admissibility, fundamental vectors and the Haken cone.
Hass–Lagarias–Pippenger, Theorem 5.1 and Lemma 6.1 — matching characterization and coordinate bounds.
Erickson, “Normal Surfaces and Knots,” §§14.1–14.3 — independent normal-coordinate conventions.
Facts & Assumptions
Given: A finite tetrahedral triangulation with tetrahedra and the seven normal disk types per tetrahedron.
Normal-surface coordinates and the Haken cone: normal vectors have nonnegative integer coordinates; matching equations equate the counts of each normal-arc type across an interior face; the quadrilateral condition allows at most one quad type per tetrahedron.
Normal-surface coordinates and the Haken cone: a vector is fundamental exactly when it is not a sum of two nonzero admissible integer vectors, and the Haken cone is the nonnegative real solution set of the matching equations.
Proof
For an existing normal surface, the arcs on the two sides of every interior face are the same finite set, so their type counts agree. Distinct quadrilateral types in one tetrahedron separate different opposite vertex pairs and intersect, so a disjoint normal surface can use at most one of them. Conversely, for a vector satisfying these conditions, place the prescribed parallel copies of each triangle type and the single permitted quadrilateral type in every tetrahedron. In each triangular face, arcs of a fixed type are nested parallel copies; put the endpoint blocks in the same order on its three edges on both incident tetrahedra. The matching equations give equal counts for every type, so pair the th arc on one side to the th arc on the other for each . These gluings identify disk sides in pairs and do not identify interior points, producing a properly embedded normal surface with precisely the given counts.
Put . A one-dimensional face of the pointed cone is cut out by the matching equalities together with active coordinate equations whose combined row rank is . Choose independent active rows and form the integer matrix with those rows. Each matching row has four entries in and Euclidean norm ; each coordinate row has norm . The cofactor vector , whose th coordinate is the signed determinant of the matrix obtained by deleting column , is nonzero and satisfies by Laplace expansion. Hadamard's inequality bounds each such determinant by the product of the row norms, hence . Dividing by the gcd of the coordinates gives the primitive integer generator on that ray and cannot increase any coordinate.
The cone is pointed because it lies in the nonnegative orthant. Intersect it with ; this is a bounded rational polytope. Triangulate that finite polytope by coning a triangulation of each face from its first vertex in a fixed finite vertex order. Coning the simplices back to the origin decomposes into finitely many simplicial cones, each generated by at most extreme rays of .
Any nonzero vector satisfying the equations and quadrilateral condition is realized by step 1.1; counting its disk pieces returns the original vector. The zero vector has no disk pieces and represents the empty surface, which is admitted for coordinate addition. This proves the claimed characterization.
Let be a fundamental admissible integer vector. If with nonzero integer vectors , then for every coordinate. Since the support of the quadrilateral coordinates of uses at most one quad type per tetrahedron, the coordinatewise sub-vectors satisfy the same quadrilateral restriction. Step 2.1 realizes both as nonempty normal surfaces, contradicting fundamentalness. Thus is indecomposable in the integer semigroup .
Choose a simplicial cone from step 1.3 containing , with primitive ray generators , where . Write with . If some , then is a nonnegative integer vector in the same cone and is nonzero; hence contradicts indecomposability. Therefore every , including the case . For every coordinate , step 1.2 gives . This proves the fundamental-vector bound.
Depends on
Used by
- Haken–Jaco–Tollefson normal-surface unknot search Algorithm
- Compatible normal vectors admit regular sum diagrams in the original triangulation Lemma
- Finite normal-coordinate tests characterize essential disk candidates Lemma
- Polynomial verification of a primitive normal vertex-disk certificate Lemma
- Correctness and finite bounds of the Jaco–Tollefson vertex search Theorem
- Correctness of the Haken finite-box disk search Theorem
- Termination, correctness, and bounds of normal-surface unknot recognition Theorem
- Unknot recognition has a polynomial-bit normal-surface certificate Theorem
Dependency tree · one level
1 result within one dependency step 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)