Normal-surface unknot recognition

Give $S^1$ its one-vertex, one-edge CW structure. By the oriented-knot convention [F1], the core circle has the specified positive orientation used for the section generator. The solid tube $S^1\times D^2$ retracts radially to the core circle, whose cellular boundary is zero, so $H_1(S^1\times D^2;\mathbb{Z})\cong \mathbb{Z}$. The product torus $T=S^1\times S^1$ has one $0$-cell, two $1$-cells and one $2$-cell; the two endpoint incidences cancel in degree $1$, and the attaching commutator of the $2$-cell has total signed incidence zero on each $1$-cell. Thus $H_1(T;\mathbb{Z})\cong {\mathbb{Z}}^2$, with basis the fibre class $[\mu ]$ and section class $[\sigma ]$. The projection to the first $S^1$ sends $[\mu ]$ to $0$ and $[\sigma ]$ to $1$.

Set $U=\mathrm{\Phi }(S^1\times \{\mathrm{\mid }z\mathrm{\mid }<3ϵ\mathrm{/}2\})$ and $V=S^3\setminus \mathrm{\Phi }(S^1\times D_{ϵ\mathrm{/}2}^2)$. They are open and cover $S^3$. Radial contraction in the disk coordinate retracts $U$ to the core circle and $U\cap V$ to $T$. The homotopy $r_t(r)=(1-t)r+tϵ$ for $ϵ\mathrm{/}2<r<ϵ$, fixed for $r\ge ϵ$, retracts $V$ onto $E$. The intersection map in the Mayer–Vietoris sequence is therefore the map $H_1(T)\to H_1(S^1)\oplus H_1(E)$ given by $x\mapsto (p_{\ast }x,-i_{\ast }x)$, where $p$ is product projection.

By exactness and [F3], this intersection map is an isomorphism. Its restriction to $\ker p_{\ast }=\mathbb{Z}[\mu ]$ is an isomorphism onto $0\oplus H_1(E)$: injectivity follows from the isomorphism, and any $(0,y)$ has a preimage $x$ with $p_{\ast }x=0$. Hence $H_1(E)\cong \mathbb{Z}$, generated up to sign by $i_{\ast }[\mu ]$.

Write $i_{\ast }[\sigma ]=c{i}_{\ast }[\mu ]$ for the unique integer $c$, and define $[\lambda ]=[\sigma ]-c[\mu ]$. Then $i_{\ast }[\lambda ]=0$ and its product projection is $1$. Every class in $\ker i_{\ast }$ has the form $a[\mu ]+b[\sigma ]$ and satisfies $a+bc=0$, so it is exactly $b[\lambda ]$; the projection condition forces $b=1$. The change-of-basis matrix from $([\mu ],[\sigma ])$ to $([\mu ],[\lambda ])$ has determinant $1$, so the latter pair is a basis. All choices were the supplied finite product data and integer operations; no choice axiom was used.

Give $T$ the one-vertex square cellulation with product generators $a=S^1\times \{1\}$ and $b=\{1\}\times S^1$. The cellular boundary of the square is the commutator $ab{a}^{-1}{b}^{-1}$, whose signed incidence on each 1-cell is zero; the 1-cell boundary is also zero. Thus $H_1(T;\mathbb{Z})=\mathbb{Z}[a]\oplus \mathbb{Z}[b]$, and the two product projections read the two coordinates. For a PL loop $c:S^1\to S^1$, lift its finitely many arcs successively to the covering line $\mathbb{R}\to S^1$; the endpoint displacement is an integer, its degree. A degree-zero lift closes and contracts linearly, so $c$ is null-homotopic; conversely a null-homotopy lifts over a finite subdivision and keeps the integer displacement zero. Applying this to both coordinate projections shows that if $C$ is not null-homotopic, at least one homology coordinate of $[C]$ is nonzero. If $C$ separated $T$, the closure of either complementary component would be an oriented PL surface with boundary $C$; its finite oriented triangulation gives a $2$-chain with boundary $C$, so $[C]=0$. Hence $C$ is nonseparating, and cutting along it leaves a connected compact surface with two boundary copies.

Choose a vertex $p$ of a triangulation of $C$, and let $p_{+}$ and $p_{-}$ be its two copies on the boundary of the cut surface. A shortest edge path joining these corresponding copies has no repeated vertices; push its interior off any intermediate boundary edges to obtain a properly embedded PL arc. After gluing the boundary copies back, its endpoints become the same point $p$ and the arc crosses $C$ transversely exactly once. Orient the resulting simple closed PL curve $D$ arbitrarily; its signed intersection with $C$ is $+1$ or $-1$.

For oriented transverse PL loops on an oriented torus, the signed crossing count is invariant under replacing either loop by a homologous cycle: across the boundary of each oriented triangle, the intersections with a closed transverse loop enter and leave with opposite signs. It is additive in each cycle. The product basis loops $a=S^1\times \{1\}$ and $b=\{1\}\times S^1$ meet once, while parallel copies of each are disjoint, so for classes $(p,q)$ and $(r,s)$ the pairing is $ps-qr$ up to the global orientation convention. Since $C\cdot D=\pm 1$, this determinant is $\pm 1$.

If an integer $k$ with $\mathrm{\mid }k\mathrm{\mid }>1$ divided both $p$ and $q$, it would divide $ps-qr$, contradicting its value $\pm 1$. Thus $\gcd (\mathrm{\mid }p\mathrm{\mid },\mathrm{\mid }q\mathrm{\mid })=1$, which says exactly that $[C]$ is primitive. Its nonzero status was established in step 1.1.

First restrict the nonsmooth locus to the complement of a protected open neighborhood of the given compact smooth set and a smaller boundary collar. Subdivide along the boundaries of finitely many smaller coordinate neighborhoods as necessary. Compactness and finiteness give positive separation between disjoint closed simplices away from their common stars, and between a sufficiently small replacement neighborhood and the closed complement of the prescribed neighborhood. Thus it suffices to smooth the finitely many unprotected vertices and edge portions inside these neighborhoods. All other points are already in smooth face interiors.

At an unprotected vertex use an ambient smooth chart centered at its image and affine coordinates on its finitely many incident triangles centered at the vertex. Write their common map as $f(x)=A(x)+R(x)$, where $A$ is the piecewise linear differential fan. On a sufficiently small star, $\mathrm{\mid }R(x)\mathrm{\mid }=o(\mathrm{\mid }x\mathrm{\mid })$ and $\mathrm{\parallel }DR(x)\mathrm{\parallel }=o(1)$, uniformly over those triangles. Let $\eta$ be a radial cutoff equal to one on a smaller star and zero outside a slightly larger star of radius $ϵ$, with derivative bounded by $C\mathrm{/}ϵ$. Replacing $f$ by $f-\eta R$ changes its derivative by $o(1)$, because $\mathrm{\mid }R\mathrm{\mid }\mathrm{\mid }D\eta \mathrm{\mid }=o(ϵ)\mathrm{/}ϵ=o(1)$. Apply [F1] to keep it an embedding. This makes the surface exactly its linear cone near the vertex, with the original map retained outside the larger star. The vertices have disjoint neighborhoods, so these finite replacements do not interfere. The link of the resulting cone on a small round sphere is a simple closed piecewise smooth curve: the surface vertex link is a circle and the differential fan is injective.

Smooth an open edge portion away from the vertex centers. Its two incident smooth half-surfaces have distinct tangent half-planes meeting along their common edge. In a small tubular coordinate box their union is a graph $z=h(s,u)$ over a plane, with the edge at $u=0$ and $h$ smooth for each sign of $u$. For unit transverse rays $v_{+}$ and $v_{-}$ pointing out from the edge into the two half-surfaces, whole-star injectivity gives $v_{+}\mathrm{\ne }{v}_{-}$. The linear functional $\mathrm{\ell }(w)=⟨v_{+}-v_{-},w⟩$ has $\mathrm{\ell }(v_{+})>0$ and $\mathrm{\ell }(v_{-})<0$. Projection onto the plane consisting of the edge direction and this signed transverse coordinate therefore gives the required graph, and remains regular on a smaller box by continuity. Replace $h$ near $u=0$ by convolution in $(s,u)$, using a cutoff supported in that box and equal to one near a smaller edge core. The new graph is smooth at its core, remains an embedded graph, and agrees with the old surface outside the box. Where the cutoff changes the old graph is already smooth, so the interpolation is smooth there. Use arbitrarily small value errors and the finite separation margins to prevent collisions with the rest of the surface. Covering each remaining compact edge portion by finitely many such boxes and retaining earlier smooth cores completes the open-edge smoothing.

In the linear conical neighborhoods of step 2.1 choose the edge rounding radially: round the finitely many corners of the link curve on the unit sphere in disjoint spherical graph charts, and take rays over this rounded link. A radial cutoff joins this choice to the open-edge graph choices farther out. On the overlap the chosen graph projection is still injective, so graph interpolation joins them without intersections. After this operation the only unsmoothed point in each vertex neighborhood is its center, and on an annulus about that center the surface is $r\gamma (s)$, where $\gamma :S^1\to S^2$ is a smooth embedded circle. These operations are fixed near the protected set.

By [F2], $\gamma$ bounds a smoothly parametrized disk region $e:D^2\to S^2$. The circles $s\mapsto e(\rho s)$, with $\rho$ decreasing from $1$ to a small positive number, give a smooth isotopy of embedded circles. In a small chart about $e(0)$, choose a fixed small $r>0$ and use the expression $E(trs)\mathrm{/}t$, continued at $t=0$ by $rd{E}_0(s)$; these circles remain inside that chart and are smooth and embedded for sufficiently small $r$: its derivative is uniformly close to the injective linear map, and projection onto its image plane gives injectivity by integration on segments. Deform the final linear ellipse to a round circle by its positive Gram square root, and carry it back through a spherical chart. This gives an isotopy ${\gamma }_t$ of smooth embedded spherical circles from $\gamma$ to a small latitude circle. Flatten its time parameter near both endpoints. No extension to a diffeomorphism of $S^2$ or of a three-ball is used.

In a smaller conical annulus replace $r\gamma (s)$ by $r{\gamma }_{\tau (r)}(s)$, where $\tau$ goes from zero on its outer collar to one on its inner collar. This is an embedded smooth annulus: different radial levels lie on disjoint round spheres, and at each fixed level the curve is embedded; its radial derivative has nonzero radial component, while its circle derivative is tangent to that sphere. Near the inner collar it is a circular cone. Close that cone by a surface of revolution lying inside the inner sphere: in coordinates around its axis, replace the conical graph $z=a\varrho$ near $\varrho =0$ by $z=a\psi (\varrho )$, where $\psi$ is smooth and even near zero, agrees with $\varrho$ near the outer radius and is positive at zero. Choose its modification supported in a much smaller radius so its graph lies strictly inside the inner sphere; a smooth convex rounding of the graph of $\mathrm{\mid }\varrho \mathrm{\mid }$ has these properties. This gives a smooth disk cap, unchanged on the annular seam. The cap replaces a conical disk by a disk with the same boundary, hence preserves the surface's homeomorphism type relative to everything outside the vertex neighborhood.

Apply step 6.1 in each of the disjoint vertex neighborhoods. The result is smooth on the face interiors, the edge cores, the connecting annuli and the caps, with identical maps on open seam collars. It is embedded by the graph, radial-level and separation arguments, and is unchanged on the protected smooth neighborhood. Replacing finitely many disks and edge strips by disks and strips with the same attaching collars gives a homeomorphism from the original surface to the result fixed there. All changes fit inside the prescribed neighborhood by step 1.1.

Finally, a surface PL in the specified compatible triangulation becomes a subcomplex after a common finite subdivision. Each restricted ambient simplex map is smooth and its differential fan is injective on the ambient star, hence on the surface's substar. Thus it has exactly the piecewise smooth whole-star data used in steps 1.1–4.1. The argument requires only this supplied compatibility and the stated countable choice, proving all clauses.

After a small smooth perturbation, keep $e$ proper and transverse to $\mathrm{\partial }M$ and make it transverse to the finite strata of $h(T)$, avoiding the vertices. Here the elementary finite parameter argument suffices: in each of finitely many ambient chart cores add small coordinate translations multiplied by a bump equal to one on the core. Evaluation on that core is a submersion in the translation parameters, so the regular values of the projection of the corresponding inverse-image stratum give transverse perturbations by [F2]. At boundary points use the tangential chart translations on $\mathrm{\partial }M$ and their product extensions in its collar. Choose the finitely many perturbations successively small enough to retain already obtained transversality and the disk's embedding and proper collar. Compact transverse intersections with the edge strata are finite; intersections with face interiors are compact regular arcs and circles after adding those edge endpoints, hence a finite embedded graph. There are no intersections with vertex strata.

Cut the disk along the finite inverse-image graph. Regard repeated slit sides as separate boundary copies before regluing. The pieces are compact smooth surfaces with corners: face-intersection arcs have nonzero differential; at an edge intersection their incident tangent directions are distinct, since the disk plane is transverse to that edge, so the two bounding equations in each sector give a corner chart by the inverse theorem. Supply each common boundary arc with one smooth regular parametrization, subdivided identically on its two copies. These are admissible boundary data in [F2], because the two corner rays are independent. Apply its finite relative whole-star construction to the pieces and reglue their identical boundary subdivisions. This gives a finite piecewise smooth whole-star triangulation of the disk with each simplex mapping into one ambient simplex. The inverse of $h$ on that simplex is smooth up to its indicated faces by the full-rank extension and inverse theorem. Consequently $g=h^{-1}e$ on this finite source complex is piecewise smooth. Its differential fan is injective: the ambient differential fan of $h$ is a homeomorphism onto the tangent half-space or space, and the disk differential is injective, so taking its inverse on the subdivided tangent sectors is injective. Thus $g$ is a whole-star embedding into a Euclidean realization of $\mathrm{\mid }T\mathrm{\mid }$.

Apply the shape-controlled secants of [F1] to $g$. Every refined simplex maps by affine interpolation of its vertex values into the same convex ambient simplex as its original carrier. Adjacent source simplices have identical interpolants on their common face. Thus these secants define a PL map into $\mathrm{\mid }T\mathrm{\mid }$, and sufficiently small strong error makes it an embedding by [F1]. They send boundary into the boundary subcomplex, since all the vertices of a boundary source simplex lie in its one boundary ambient face and the interpolant preserves that face.

Properness is retained as well. In a smooth disk collar the inward boundary defining coordinate of $M$ has strictly positive inward derivative, uniformly after a finite shrink, by the given transversality. Cellulate that collar as strips with its boundary as the only zero-coordinate face. In each ambient half-space simplex the corresponding affine boundary coordinate is nonnegative and positive on the vertices off that boundary face. Its affine interpolant is therefore zero precisely on the source boundary face. The derivative lower bound ensures these are precisely the collar sectors, even after a finer shape-controlled subdivision. Away from the collar the compact disk has a positive distance from $\mathrm{\partial }M$, and a sufficiently small value error retains that separation. Hence the PL disk meets $\mathrm{\partial }M$ exactly in its own boundary.

Along the original boundary, the secant curve lies in an arbitrarily small annular neighborhood and is transverse to its interval fibres: its tangential derivative is close to the nonzero derivative of the original parametrized curve in each of the finitely many sectors. Projection to the original circle is therefore a degree-one local homeomorphism, hence a homeomorphism. The new boundary is a graph in that annulus; interpolating its graph coordinate with zero gives an isotopy to the original boundary. Thus its nullhomotopy class, including its essentiality, is unchanged. The image under $h$ of the secant disk is the required properly embedded PL disk in the supplied compatible structure.

A transverse finite PL closed loop has a well-defined intersection count with $S$ modulo two, and this count is invariant under PL homotopy. Here is the finite representative argument needed for that assertion. Subdivide a homotopy annulus and the ambient finite PL charts until its pieces lie in charts straightening $S$. Put its interior vertices in general position, keeping its transverse boundary loops fixed. Such positions exist by avoiding finitely many affine equalities in each chart; a common finite subdivision makes the constructions agree on chart overlaps. In each chart, transverse intersection is the inverse image of one linear coordinate being zero. On the triangulated annulus these pieces paste to a compact PL one-manifold: interior points have two incident sides and boundary points have one. It consists of finitely many circles and arcs. Each arc has two boundary endpoints, so the total number of intersections on the two boundary loops is even. This proves the asserted invariance, with no orientation signs. The argument also permits an arbitrarily small generic perturbation of a loop or homotopy relative to already transverse boundary data.

Every finite PL closed loop is PL homotopic to an edge loop in $T$. For an explicit finite construction, realize the finite abstract complex in a Euclidean space by its barycentric coordinates. The inverse images of its finitely many open vertex stars cover the parameter circle. Subdivide the circle sufficiently finely that the image of each closed vertex star of that subdivision lies in one of these target stars, and assign that source vertex a witnessing target vertex. The vertices assigned to the ends of a source edge belong to the carrier simplex of every interior image point on that edge; consequently they span an edge or coincide. They define an edge loop. The original map and this edge map are carried by common original simplices, so they are homotopic within those simplices. Explicitly subdivide further where the original PL map changes its carrier, triangulate each homotopy prism, and extend linearly from the two boundary maps; each such extension stays in its convex carrier simplex. This gives the claimed PL homotopy. Since $S$ misses the target vertices and is transverse to the target edges, the resulting edge loop is transverse after harmless parametrization and a small perturbation at its vertices disjoint from $S$.

An edge loop crosses $S$ an even number of times. Indeed each traversal of an original edge contributes its even intersection number, with multiplicity; backtracking and repeated edges do not affect parity. By steps 1.1 and 1.2 every transverse finite PL closed loop has even intersection count with $S$. The argument allows boundary edges: $S$ is disjoint from the boundary of $M$, so any small inward displacement there is disjoint from $S$ and changes no count.

Suppose $M\setminus S$ were connected. Choose one straightening chart at a point of $S$ and a short interval crossing its coordinate plane once. Its endpoints lie in the complement and can be joined there by a finite PL path. To justify the path assertion without a selection principle, the set reachable from one endpoint by finite polygonal paths in PL charts is open and its complement is open; connectedness makes the reachable set the entire complement. Membership supplies just one finite chart chain and finitely many joining points. Concatenate that path with the transverse interval, then perturb away any extraneous tangencies while staying in the complement along the joining path. The resulting finite PL closed loop crosses $S$ exactly once. This contradicts step 2.1. Hence the complement is disconnected. All selections and subdivisions were finite; no orientability or ball bounded by $S$ was used.

Every $d\times d$ minor, $0\le d\le n$, has absolute determinant at most $d!\le (n+2{)}^n$ by [F1], interpreting the empty determinant as $1$. Put $B=(n+2{)}^n$, $M=16(n+2{)}^4$, $L_M=\mathrm{lcm}(1,\dots ,M)$ and $P_M={\prod }_{p\le M,p\text{ prime}}p$. All these are integers; only $B$ and the small bound $M$, not the complete integers $L_M,P_M$, will be stored.

The bound $L_M\ge 2^{M-1}\mathrm{/}M$ is elementary. For $N=M-1$ and any $0\le j\le N$, counting multiples of $p,p^2,\dots$ in factorials gives $v_p\left(\genfrac{}{}{0px}{}{N}{j}\right)={\sum }_{a\ge 1}(\lfloor \frac{N}{p^a}\rfloor -\lfloor \frac{j}{p^a}\rfloor -\lfloor \frac{N-j}{p^a}\rfloor )\mathrm{.}$ Each summand is zero or one and vanishes for $p^a>N$. Thus this valuation is at most $\lfloor {\log }_{p}N\rfloor$, at most the exponent of $p$ in $L_M$. Unique factorization makes every $\left(\genfrac{}{}{0px}{}{N}{j}\right)$ divide $L_M$. The sum of the $M$ binomial coefficients is $2^{M-1}$, so at least one is at least $2^{M-1}\mathrm{/}M$, proving the bound.

The exponent of every prime in $L_M$ is at most ${\log }_{2}M$. Consequently $L_M\le P_M^{{\log }_{2}M}$ and ${\log }_2{P}_M\ge \frac{M-1-{\log }_{2}M}{{\log }_{2}M}\mathrm{.}$ For the chosen $M$, ${\log }_{2}M=4+4{\log }_2(n+2)\le 4(n+2)$ and $M-1-{\log }_{2}M\ge M\mathrm{/}2$. The displayed lower bound is therefore at least $2(n+2{)}^3$, which is greater than $n{\log }_2(n+2)+3$. Hence $P_M>8B$. Enumerate integers $2,\dots ,M$, testing each for primality by trial division up to its square root. There are polynomially many trials on $O(\log (n+2))$-bit integers. Stop the prime stream as soon as its running product $Q$ exceeds $2B$; the bound just proved guarantees that this happens by $M$. Immediately before the last multiplication $Q\le 2B$, so the final product is at most $2BM$. The product accumulator thus has $O(n\log (n+2))$ bits.

For a specified square submatrix $D$, compute its determinant modulo each successive prime by [F2]. Every nonzero residue $h$ modulo a prime $p$ is a unit, with an explicit small-space inverse: apply Euclidean descent to $(p,h)$, maintaining $r_i=s_{i}p+t_{i}h$ with initial coefficient pairs $(1,0),(0,1)$ and updates $(s_{i+1},t_{i+1})=(s_{i-1},t_{i-1})-q_i(s_i,t_i)$. The last nonzero remainder is $1$, since a common divisor of $p$ and $0<h<p$ is $1$ by primality. Its coefficient $t_i$ is an inverse modulo $p$. This also constructs Bézout identities for arbitrary integer pairs, and induction gives one for any finite list and its gcd. Thus elimination is over a field; if a pivot cannot be found in a square trailing block, the determinant residue is zero. Row interchanges change its sign, and otherwise the product of the unscaled pivots gives the determinant. This uses one matrix of $O(n^2)$ residues, each with $O(\log (n+2))$ bits, and $O(n^3)$ modular operations per prime. Combine each residue $r$ with the previous representative $a$ modulo $Q$ by $a_{\mathrm{n}\mathrm{e}\mathrm{w}}=a+Q((r-a)Q^{-1}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p),Q_{\mathrm{n}\mathrm{e}\mathrm{w}}=Qp\mathrm{.}$ The inverse exists by [F3] and is computed from $Q<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p$, so its Euclidean inputs have only $O(\log (n+2))$ bits. After $Q>2B$, the unique representative in $[-B,B]$ is the integer determinant by step 1.1. Only the current residue matrix, the two reconstruction integers and small counters are retained; no list of primes, residues or previous matrices is stored.

For rank, perform prime-field elimination on the original rectangular matrix over the same prime stream, retaining the largest rank found and the original row indices of a basis attaining it. These indices can be selected during elimination without a transformation matrix: after the first $k$ pivots, the unselected rows have only had combinations of the $k$ selected original rows subtracted, so the next pivot row is independent of them exactly when its remainder is nonzero. The rank equals the largest order of a nonzero minor over either field. To see the needed direction directly, elimination selects $r$ original independent rows and $r$ pivot columns; their $r\times r$ submatrix becomes triangular with nonzero pivots after invertible row operations, so it has nonzero determinant. Conversely, $r+1$ rows are dependent and multilinearity makes every minor of that order zero. A nonzero modular minor is a nonzero integer minor, so every modular rank is at most the rational rank $r$. If $r>0$, choose any nonzero $r\times r$ integer minor $d$. If all sampled ranks were less than $r$, every sampled prime would divide $d$. Their product $Q>2B$ would divide $d$, contradicting $0<\mathrm{\mid }d\mathrm{\mid }\le B$. Therefore the maximum modular rank is exactly $r$, and its retained original rows form a rational row basis. For $r=0$ every entry and modular rank is zero.

If the number of columns is $b$ and the rank is $b-1$, let $R$ consist of the $b-1$ independent original rows from step 4.2. For $1\le j\le b$, compute $w_j=(-1{)}^{j+1}\det R_{\widehat{j}}$ by step 4.1, retaining the vector $w$. Some cofactor is nonzero because $R$ has full row rank. Expanding the determinant of the matrix obtained by adding any row of $R$ as a duplicate row gives $Rw=0$ by [F1]. Every row of $A$ lies in the rational row span of $R$, hence $Aw=0$. Divide $w$ by the positive gcd of its entries; the result is primitive. If a rational multiple $cu$ of a primitive integer vector $u$ is integral, a Bézout identity ${\sum }_j{a}_j{u}_j=1$ gives $c={\sum }_j{a}_j(c{u}_j)\in \mathbb{Z}$, so it generates all integer points on that line. Either overall sign may be selected. For $b=1$, $R$ is empty and its one empty cofactor is $1$, as required.

All counters bounded by $M$ have $O(\log (n+2))$ bits. The residue matrix uses $O(n^2\log (n+2))$ bits, the row-index list $O(n\log (n+2))$ bits, and each reconstructed determinant has $O(n\log (n+2))$ bits. The at most $n$ retained cofactors therefore also use $O(n^2\log (n+2))$ bits; the same residue matrix storage is reused for each one. Trial division, at most $M$ prime eliminations per determinant and at most $n$ cofactor determinants take polynomially many arithmetic operations on polynomial-length integers. Binary multiplication and long division take polynomial time; the Euclidean descent takes $O(\mathrm{\ell })$ divisions on $\mathrm{\ell }$-bit inputs because after two nonzero remainder steps the remainder is at most half its previous value. The coefficient-tracking algorithm is needed computationally only for inverses with inputs less than $p\le M$. It has $O(\log p)$ updates and quotients at most $p$, so even the crude coefficient bound obtained by multiplying $2p$ per update has $O((\log p{)}^2)$ bits. Thus these small inverses need only $O((\log (n+2){)}^2)$ extra workspace, which fits the asserted bound. Normalizing the cofactor vector needs only ordinary remainder gcds on $O(n\log (n+2))$-bit integers; the existential Bézout identity used to prove primitivity need not be computed or stored. All integer multiplications and divisions can be done by the digit-by-digit algorithms using a constant number of buffers of the operand/output lengths. Thus reconstruction, inversions, gcd normalization, rank and kernel calculations all have polynomial bit time and the asserted workspace. Empty matrices are handled directly by rank zero and empty determinant one. This proves all claims.

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 $j$th arc on one side to the $j$th arc on the other for each $j$. 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 $m=7t$. A one-dimensional face of the pointed cone $C(T)$ is cut out by the matching equalities together with active coordinate equations $x_i=0$ whose combined row rank is $m-1$. Choose $m-1$ independent active rows and form the integer matrix $R$ with those rows. Each matching row has four entries in $\{+1,-1\}$ and Euclidean norm $2$; each coordinate row has norm $1$. The cofactor vector $w\in {\mathbb{Z}}^m$, whose $j$th coordinate is the signed determinant of the matrix obtained by deleting column $j$, is nonzero and satisfies $Rw=0$ by Laplace expansion. Hadamard's inequality bounds each such determinant by the product of the row norms, hence $\mathrm{\mid }{w}_j\mathrm{\mid }\le 2^{m-1}$. Dividing by the gcd of the coordinates gives the primitive integer generator on that ray and cannot increase any coordinate.

The cone $C(T)$ is pointed because it lies in the nonnegative orthant. Intersect it with ${\sum }_i{x}_i=1$; 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 $C(T)$ into finitely many simplicial cones, each generated by at most $m$ extreme rays of $C(T)$.

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 $v$ be a fundamental admissible integer vector. If $v=x+y$ with nonzero integer vectors $x,y\in C(T)$, then $0\le x_i,y_i\le v_i$ for every coordinate. Since the support of the quadrilateral coordinates of $v$ uses at most one quad type per tetrahedron, the coordinatewise sub-vectors $x,y$ satisfy the same quadrilateral restriction. Step 2.1 realizes both as nonempty normal surfaces, contradicting fundamentalness. Thus $v$ is indecomposable in the integer semigroup $C(T)\cap {\mathbb{Z}}^m$.

Choose a simplicial cone from step 1.3 containing $v$, with primitive ray generators $r_1,\dots ,r_d$, where $d\le m$. Write $v={\sum }_{j=1}^d{\lambda }_j{r}_j$ with ${\lambda }_j\ge 0$. If some ${\lambda }_j>1$, then $v-r_j$ is a nonnegative integer vector in the same cone and is nonzero; hence $v=(v-r_j)+r_j$ contradicts indecomposability. Therefore every ${\lambda }_j\le 1$, including the case $v=r_j$. For every coordinate $i$, step 1.2 gives $v_i\le {\sum }_j(r_j{)}_i\le d{2}^{m-1}\le 7t{2}^{7t-1}\le t{2}^{7t+2}$. This proves the fundamental-vector bound.

Suppose $S$ is disconnected. Since $S$ is a finite normal surface, its connected components are finite in number; let $S_1$ be one component and let $S_2$ be the union of all remaining components. Both are nonempty properly embedded normal surfaces: each normal disk and each face-matched arc belongs to exactly one component. Disk counts add coordinatewise, so $v(S)=v(S_1)+v(S_2)$, and both summands are admissible nonzero integer vectors.

The decomposition in step 1.1 contradicts the defining indecomposability of the fundamental vector $v(S)$. Therefore $S$ is connected.

Form the finite dual graph with one vertex for each triangle, an additional outside vertex, an edge between two triangle vertices for each shared interior edge, and an edge from the outside vertex for each boundary edge. This graph is connected: a path in the connected surface between triangle interiors can be moved off the finitely many vertices and then crosses a finite sequence of edges; every triangle can also be joined to the outside vertex through a path to the nonempty boundary. Fix a spanning tree rooted at the outside vertex by choosing the first one in the finite lexicographic ordering of edge subsets.

Process the triangle vertices in increasing distance from the root. For a triangle whose parent is the outside vertex, use its corresponding boundary edge; otherwise use the edge shared with its parent triangle. The parent has already been removed, so the chosen edge is now incident to this triangle alone. Remove the open triangle and that free edge. This is an elementary collapse: it is a deformation retraction and removes one $2$-cell and one $1$-cell, preserving both connectedness and Euler characteristic. After all triangles are removed, the remaining finite connected complex is a graph $G$ with $\chi (G)=\chi (K)=1$.

A connected finite graph with $V$ vertices and $E$ edges has a spanning tree with $V-1$ edges. Since $V-E=\chi (G)=1$ by [F2], it has exactly $V-1$ edges, so every edge belongs to that spanning tree and $G$ itself is a tree.

Use small polygonal neighborhoods in the surface throughout, rather than attaching triangles along exposed edges of the remaining complex. For a free triangle-edge collapse $L\searrow L^{\mathrm{\prime }}$, choose the vertex disks and edge strips sufficiently small. Inside the removed triangle, a neighborhood of $L^{\mathrm{\prime }}$ is a narrow collar of the two retained sides, together with its corner sectors. Its boundary facing the empty triangle is one polygonal arc joining the two ends of the removed free edge. Other retained triangles may meet the retained sides on their opposite sides, but they do not meet this empty triangle interior. Move the facing boundary arc across that interior to a parallel arc just beyond the free edge, using the surface boundary collar if the edge lies on $\mathrm{\partial }S$. This expands a disk along one boundary interval; triangulating the intervening polygon gives a PL homeomorphism of the old and enlarged neighborhoods, fixed away from the triangle and its small corner sectors. The enlarged neighborhood is a neighborhood of $L$. Thus reversing each collapse preserves the neighborhood homeomorphism type without requiring any retained edge to be exposed. A neighborhood of the tree $G$ is a disk: absorb a leaf vertex disk and its rectangular edge strip successively into the neighboring vertex disk. Reversing all collapses and expanding the final boundary collar identifies this disk with $S$.

The boundary $\mathrm{\partial }D$ is an embedded PL simple closed curve in $T$. Since it bounds the disk $D$ in $E$, its image under inclusion $i:T\hookrightarrow E$ is zero. By [F1], the kernel is $\mathbb{Z}[\lambda ]$, so $[\mathrm{\partial }D]=k[\lambda ]$ for an integer $k$.

The hypothesis and [F2] say $[\mathrm{\partial }D]$ is nonzero and primitive. Since $[\lambda ]$ is a basis vector by [F1], the multiple $k[\lambda ]$ is primitive only if $k=1$ or $k=-1$. Hence $[\mathrm{\partial }D]=\pm [\lambda ]$.

Put the boundary curve in PL transverse position to the fibre $\mu =p^{-1}(s_0)$, where $p:T\to S^1$ is product projection. Its intersection points are exactly the preimages of $s_0$ under $p{\mathrm{\mid }}_{\mathrm{\partial }D}$. A lift of this PL circle map to $\mathbb{R}$ changes by its degree, which is the product-projection coefficient of $[\mathrm{\partial }D]$, namely $+1$ or $-1$ by step 2.1. For a regular value, the signed crossing count of the lift through the integer translates of that value equals this degree; reducing modulo $2$ removes the signs, so the number of preimages is odd. Thus $\mathrm{\partial }D$ has mod-two intersection $1$ with $\mu$.

Steps 2.1 and 3.1 give the longitude class and the asserted parity.

Reverse the parametrization of $C$ if necessary so its class is $(1,q)$. Round its finitely many corners in disjoint torus coordinate disks, using a coordinate in which the two incident arcs are graphs and replacing the graph corner by a smooth arc fixed near its endpoints. Each change is an isotopy of simple curves supported in that disk: interpolate graph values, which preserves the graph projection. Thus $C$ has an isotopy through finite piecewise smooth embedded curves to a smooth curve $C_0$ in the same class. Write $L_q(s)=(s,\exp (2\pi iqs))$. This is a simple smooth curve in that class.

Put $C_0$ transverse to $L_q$ by an arbitrarily small finite graph perturbation. The shear $(s,z)\mapsto (s,z\exp (-2\pi iqs))$ is a torus diffeomorphism carrying $L_q$ to a product section, so cutting the torus along $L_q$ gives an explicit annulus. The cut pieces of $C_0$ are finitely many properly embedded arcs. A returning arc, whose endpoints are on the same boundary circle, cuts off a disk with a subarc of that boundary. One elementary way to verify this familiar annulus fact is to cut the annulus to a rectangle along a spanning arc, lift the returning arc to its strip of translated rectangles, and choose an outermost lifted arc: its union with the interval between its endpoints on the same strip boundary bounds a polygonal disk. If a translate or another arc enters this disk, choose an innermost such arc instead. Finiteness of the intersections gives a disk with embedded interior in the annulus. Equivalently the finite disk-and-band reductions in [F2] give the same disk. Choose an innermost returning arc among the cut pieces; its disk interior misses the other cut pieces. Sliding it across that disk and a little beyond is an isotopy supported in the disk's collar and removes two intersections of $C_0$ with $L_q$. For smooth curves use smooth graph slides, stationary near the endpoints of the time interval.

Repeat the preceding removal while a returning arc remains. There are strictly fewer intersection points at each removal. If intersections remain when no returning arc is left, all cut arcs span the annulus. Traversing the connected oriented curve then meets $L_q$ always with the same crossing sign: after a spanning arc one arrives at the opposite copy of the cut circle, and gluing crosses it in the same direction as at the preceding crossing. Hence its algebraic intersection with $L_q$ is nonzero. This contradicts [F1], because both classes are $(1,q)$ and their determinant is zero. Thus the finite sequence ends with a smooth curve disjoint from $L_q$. The two curves bound an annulus: cutting along $L_q$ places the other essential circle in the interior of an annulus; cutting along it gives two annuli, as is seen by the same finite surface normal form [F2], or by lifting to a strip and taking the region between adjacent lifts. Sliding through that annulus supplies an isotopy to $L_q$. Concatenate with step 1.1 to obtain a finite piecewise smooth isotopy of simple curves from $C$ to $L_q$, smooth after the initial corner rounding.

Put the isotopy of step 3.1 into a radial collar of the tube. More precisely choose a strictly decreasing smooth radius $r(t)$ from $1$ to $1\mathrm{/}2$ and map $(s,t)$ to $(u_t(s),r(t)z_t(s))$, where $(u_t(s),z_t(s))$ parametrizes the curve isotopy on the boundary torus. Distinct $t$ give distinct radii, so this is an embedded annulus irrespective of overlaps between different curve images on the torus. On each smooth piece its circle derivative is nonzero and tangent to the radius torus, whereas its time derivative has nonzero radial component, so it is regular. Make the isotopy constant near its final time; its inner collar is then the product collar of the radius-$1\mathrm{/}2$ copy of $L_q$.

Continue inward by $(s,r)\mapsto (s,r\exp (2\pi iqs))$ for $0\le r\le 1\mathrm{/}2$. This is an embedded smooth annulus including its core boundary $r=0$: the first coordinate separates distinct $s$, and the $r$ derivative is a nonzero normal vector even at zero. Its outer collar agrees with the preceding annulus after the chosen radial reparametrization. The joined annulus meets the boundary torus only in $C$ and has the smooth core as its other boundary. Its interior lies on the tube side of that torus, while a proper exterior disk lies on the exterior side, so their union is an embedded disk, with a smooth product collar at the core. This proves the statement.

Put $D$ in finite PL general position: it misses vertices, meets edges transversely in finitely many points, and meets faces in finitely many arcs and circles. This is obtained by finite subdivision and small generic vertex displacements, choosing each displacement outside finitely many forbidden affine planes and lines. Preserve its proper boundary in the boundary faces. Every component $P$ of its intersection with a tetrahedron is a compact planar surface, because it is a subsurface of a disk. Components have nonempty boundary; an entire closed component in a tetrahedron would be a closed component of $D$. Put $w(D)=\mathrm{\mid }D\cap T^{(1)}\mathrm{\mid }$ and $\lambda (D)={\sum }_P(1-\chi (P))$. A connected planar piece with $b\ge 1$ boundary curves has $1-\chi (P)=b-1\ge 0$, as is seen by cutting it along $b-1$ disjoint connecting arcs to a disk and counting the cuts. Thus $(w,\lambda )$ is a pair of nonnegative integers.

We first record the permitted disk replacement inside a tetrahedron. Whenever a new cap is disjoint from the other pieces, a disk piece may be replaced, fixing its boundary and a smaller attaching collar, by that cap just inside its chosen boundary disk region. This preserves the topology of the entire surface: two disk parametrizations with the same boundary identification are homeomorphic relative to that boundary, extending the circle map radially. It is enough to choose the new cap disjoint from the other pieces. If all the pieces in question are disks, choose a point away from their boundary curves and take the disk side not containing that point for each curve. These disks are nested or disjoint by [F1]. Put the caps at successively deeper levels for successively larger nested regions, rounding their finite collar corners PL. This realizes all those disk pieces by disjoint caps. The same construction works in a boundary disk region containing only boundary curves of disk pieces, with other pieces kept outside its collar. The chosen depth intervals can be arbitrarily small. Boundary curves, edge intersections and the planar Euler deficits are unchanged. No assertion that the old disk is isotopic to the cap in the tetrahedron is needed.

If $\lambda >0$, select in some tetrahedron a boundary circle $c$ of a non-disk piece $P$ that is innermost among such boundary circles, using either fixed planar diagram of the boundary sphere. All boundary circles in its inner disk region are boundaries of disk pieces. Move those disk pieces to nested boundary-parallel caps as in step 2.1, at shallower collar depths. A copy of the inner boundary disk placed deeper than those caps, with boundary on a curve just inside the collar of $c$ in $P$, is then an embedded compressing disk disjoint from all other pieces. Its boundary is essential in $P$, since $P$ is planar with at least two boundary circles. Compress along it. Locally this splits off a disk and replaces $P$ by a planar piece with one fewer boundary circle, so $\lambda$ decreases by one, while $w$ is unchanged. Globally compression of a disk along an interior simple circle gives a disk with the original boundary and a sphere. Keep the disk and discard the sphere; discarding pieces cannot increase $w$ or $\lambda$. The boundary of the retained disk is still essential.

Repeat step 3.1 until $\lambda =0$ unless a preceding sphere discard has already decreased $w$; in that event restart with the smaller weight. At $\lambda =0$ every tetrahedral intersection piece is a disk. We may rearrange these disk pieces as boundary-parallel caps by step 2.1, without changing $w$ or $\lambda$. This rearrangement is only preparation for the next simplifying move, so it introduces no infinite sequence of equal-complexity moves.

Suppose some disk boundary meets a tetrahedral edge $e$ more than once. The finite disjoint boundary circles on the tetrahedral sphere then admit an edge-return interval $\beta \subset e$ with endpoints on the same boundary circle and interior disjoint from all the boundary circles. To verify this, the complementary regions of finitely many disjoint circles on a sphere have a tree as their incidence graph: each added circle separates one region into two, by [F1]. The edge $e$ traces a walk in that tree. Crossing one circle more than once repeats a tree edge; any such walk has an immediate backtrack. The two consecutive crossings of that backtrack are the required endpoints of $\beta$. Choose the cap side of its disk piece containing $\beta$ and use the compatible nested cap arrangement of step 2.1. The strip between $\beta$ and its parallel arc $\alpha$ on this cap is a disk $E$ with $E\cap D=\alpha$, $\mathrm{\partial }E=\alpha \cup \beta$, and interior disjoint from all pieces: inner caps miss $\beta$ and outer caps lie deeper. This is an actual embedded edge-compressing disk.

If $e$ is an interior edge of $M$, slide the strip of $D$ adjacent to $\alpha$ across $E$ and beyond $\beta$ into the other sectors of the edge star. In the local product of an edge interval and a normal disk this is the elementary removal of a bigon; it removes precisely the two intersections at the ends of $\beta$ and creates no new edge intersections. It is an isotopy supported in that edge star and preserves the global boundary. Hence $w$ decreases. The new disk may have a larger local Euler deficit, which does not matter because the first complexity coordinate has decreased.

If $e\subset \mathrm{\partial }M$, the same disk $E$ gives a boundary compression. Cutting the global disk along the proper arc $\alpha$ and adding the two parallel copies of $E$ gives two proper disks. At least one has essential boundary. Indeed, after choosing a base point and whiskers in $\mathrm{\partial }M$, the old boundary loop is the product of the two new boundary loops, with one conjugated by the connecting arc $\beta$. If both new loops were nullhomotopic, so would be the old one. Keep an essential-boundary disk. The total edge intersection number of the two new disks is smaller than the old one by two, so the retained disk has strictly smaller $w$. Again any increase of $\lambda$ is permitted.

Each compression macro-move of step 3.1 either decreases $w$ or leaves it fixed and decreases $\lambda$; each edge macro-move decreases $w$. The intervening cap preparations are finite. Lexicographic descent in ${\mathbb{N}}^2$ therefore terminates with an essential-boundary proper disk all of whose tetrahedral pieces are disks and all of whose boundary circles meet each tetrahedral edge at most once. A circle of intersection with an interior face would now be the entire boundary of a disk piece on either side, making a sphere component of the global disk. A circle on a boundary face would be the boundary of a disk lying entirely in one tetrahedron and would be nullhomotopic in that face. Both are impossible. Each face intersection is therefore an arc, and an arc returning to the same edge would violate the just established edge condition.

Each tetrahedral boundary circle meets an edge, since otherwise it would lie in one face and would have been excluded in step 7.1. It separates the four vertices into two subsets. An edge with endpoints on opposite sides must be crossed, and one with endpoints on the same side must be crossed an even number of times, hence not at all. The crossing set is consequently either the three edges separating one vertex from the other three, or the four edges separating two vertices from the other two. The boundary is thus a triangle or quadrilateral normal curve. Replace the finitely many disk pieces by standard parallel normal disks with those same boundary matchings; disjoint boundary curves permit only one quadrilateral type in a tetrahedron. Their finite gluing has exactly the same abstract surface topology and boundary essentiality as the retained disk. It is the required normal disk. This proof used only finite planar disk constructions and preserves essentiality at every retained-disk step.