Polynomial verification of a primitive normal vertex-disk certificate

The verifier first checks the vector length, nonnegativity, matching equations, and the at-most-one-quadrilateral condition by scanning $7t$ coordinates and the finite face-matching rows. It computes the gcd of the coordinates by Euclid's algorithm and checks that it is $1$. These operations use polynomially many integer operations on integers whose bit lengths are bounded by the certificate length.

For Euler characteristic, let $F(v)={\sum }_i{v}_i$ count normal disks and let $A(v)={\sum }_i{q}_i{v}_i$ count their normal-arc sides, where $q_i$ is $3$ for a triangle type and $4$ for a quadrilateral type. Let $B(v)$ count arcs on boundary faces; this is a fixed linear form in the coordinates. The number of surface edges is $(A(v)+B(v))\mathrm{/}2$, since each interior-face arc side is paired and each boundary arc is unpaired. For each edge $e$ of the triangulation, choose one incident tetrahedron and let $N_e(v)$ be its local linear count of normal disk intersections with $e$; matching makes this count independent of the incident tetrahedron. Then $V(v)={\sum }_e{N}_e(v)$ counts surface vertices and $\chi (v)=V(v)-(A(v)+B(v))\mathrm{/}2+F(v)$. The boundary is nonempty exactly when $B(v)>0$. Put the marked meridian in transverse position to the finite list of boundary arc types; each type has a fixed intersection count, so parity of total intersections is another linear form modulo $2$. These local coefficients are computed once from constant-size face and tetrahedron templates; arithmetic on their compressed coordinate sums is polynomial in $t$ and the certificate bit length.

The certificate lists active zero-coordinate rows and matching rows. The verifier checks every listed zero coordinate is actually zero, chooses the stated $(7t-1)$ square minor, and computes its determinant by the explicit prime-field/CRT algorithm [F5]. The minor has dimension $7t-1$ and entries in $\{-1,0,1\}$, so that algorithm takes polynomial time in $t$, hence in the certificate length. Its determinant is reconstructed as an integer, not accepted from a claimed numerical value in the witness. A nonzero determinant certifies that the listed rows have rank at least $7t-1$; because the nonzero vector $v$ lies in their common kernel, the rank is at most $7t-1$, hence exactly that value. The face of the nonnegative matching cone containing $v$ therefore has dimension one, so $v$ lies on an extreme ray. The gcd check makes it the primitive integer generator of that ray.

A primitive integer vector on an extreme ray is fundamental among admissible integer vectors. If $v=x+y$ with nonzero admissible integer vectors, then $x,y$ lie in the cone and their sum lies on an extreme ray. By extremality each summand lies on that same ray; since $v$ is the primitive integer generator, each nonzero integral summand is a positive integer multiple of $v$, which cannot sum to $v$. Thus $v$ is fundamental and [F3] makes its normal surface connected without expanding it.

If the boundary is nonempty, the Euler characteristic is $1$, and the meridian intersection is odd, [F4] identifies the surface as a properly embedded disk with non-null-homotopic boundary. Conversely, acceptance has checked admissibility, a primitive extreme ray, connectedness from step 3.1, and these three disk tests, so it certifies exactly such a disk.

The certificate has $7t$ coordinates with their binary expansions, at most $O(t)$ constraint indices, and one determinant minor of dimension $7t-1$. Determinants have the polynomial bit-time implementation [F5]. Ordinary binary gcd descent has at most a constant times the input bit length many divisions (two remainder steps at least halve the positive remainder); each division is polynomial in the input bit length. Thus determinant and gcd computations, coordinate checks, and local linear-form evaluations all take polynomial time in the total encoded length. At no point is a disk copy expanded; arithmetic acts directly on its coordinate multiplicity.