Terminating computations for classical knot invariants

For fixed $b\in {\mathbb{F}}_p$, define $R_b(a)=a\ast b=2b-a$. Then $R_b(R_b(a))=2b-(2b-a)=a$, so $R_b^{-1}=R_b$. Also $a\ast a=2a-a=a$. Thus both the forward and reverse crossing rules use the same involution, and an arc's color is uniquely recoverable across one underpass.

In an R1 disk, the coloring relation on the kinked side is either $y=x\ast x$ or $x=y\ast x$, where $x$ is the unchanged boundary color and $y$ is the color of the new interior underarc. In the first case $y=x$ by idempotency; in the second, $R_x(y)=x$ has the unique solution $y=R_x(x)=x$ because $R_x$ is bijective. Deleting the kink is the inverse restriction map. The two formulas cover both strand directions because the inverse operation equals the operation by step 1.1.

In an R2 disk, fix the color $b$ of the strand passing over the other strand and the incoming underarc color $a$. The first crossing changes the underarc color to $R_b(a)$, and the second changes it by $R_b^{-1}$; their composition is $R_b^{-1}(R_b(a))=a$. Therefore every boundary coloring extends uniquely across the two-crossing side, and the reverse R2 move gives the inverse bijection. Other orientation variants replace one of these maps by its inverse, which is the same map by step 1.1.

For a braid-like R3 orientation, start with boundary colors $a,b,c$. Propagating through the two sides gives respectively $(c,b\ast c,(a\ast b)\ast c)$ and $(c,b\ast c,(a\ast c)\ast (b\ast c))$. The last coordinates agree by right self-distributivity in [F2], so every boundary coloring on either side has a unique matching extension on the other. Reversing a crossing replaces a right translation by its inverse; step 1.1 makes that the same map, and relabeling the three strands gives every height-order and orientation variant in [F3].

If $D$ is empty, its unique empty coloring is carried to itself by planar isotopy, and no Reidemeister move is supported on the empty diagram. If $D$ is nonempty, planar isotopy carries every arc and local crossing relation bijectively to its image, while steps 2.1, 2.2, and 2.3 give explicit coloring bijections for every local move. Composing the finitely many bijections along any finite move sequence preserves the coloring count. These constructions act on finite arc labels and use no choice principle.

The state set has exactly $2^c$ elements by [F3]. A complete smoothing starts with $m$ circles. At each crossing the four local endpoints lie on one or two current circles, and either smoothing reconnects them into one or two circles. Thus the circle count increases by at most one at each of the $c$ smoothings. Every state has $1\le \mathrm{\mid }S\mathrm{\mid }\le m+c$.

For a fixed state, put $r=\mathrm{\mid }S\mathrm{\mid }-1$, so $0\le r\le m+c-1$. The binomial theorem gives ${\delta }^r=(-1{)}^r{\sum }_{k=0}^r\left(\genfrac{}{}{0px}{}{r}{k}\right)A^{2r-4k}$. These exponents are distinct, so its coefficient l1 norm is ${\sum }_{k=0}^r\left(\genfrac{}{}{0px}{}{r}{k}\right)=2^r$; multiplication by the monomial $A^{a(S)-b(S)}$ only shifts the exponents.

Since $a(S)+b(S)=c$, one has $\mathrm{\mid }a(S)-b(S)\mathrm{\mid }\le c$. The exponents in ${\delta }^r$ lie between $-2r$ and $2r$. Using $r\le m+c-1$, every exponent in every state term, and thus in the sum, has absolute value at most $c+2(m+c-1)=3c+2m-2$.

Put $q=c+m+1\ge 2$. Represent a crossing endpoint by an integer from $1$ to $4c$, grouped into four successive ports at each crossing, and write $\alpha$ for the supplied edge-pairing involution. For a state, let $\beta$ pair the two left and two right ports for A, or the two top and two bottom ports for B. The multigraph on the $4c$ endpoints with one $\alpha$-edge and one $\beta$-edge at every vertex is two-regular, allowing parallel edges. Each connected component follows one smoothed circle, and the $u$ supplied crossingless components add $u$ further circles. Thus a traversal marking a vertex when first queued computes $\mathrm{\mid }S\mathrm{\mid }$ exactly. The same traversal, with the opposite ports paired instead of smoothing ports, computes the original component count $m$; perform it once initially and then compute $q$ for allocation. Use binary counters and linear scans for all table and mark lookups: there are $O(q)$ endpoint visits, each using a bounded number of scans of $O(q)$ records with $O(\log q)$ index bits. Even with a work-tape queue or stack scanned linearly, each visit costs $O(q^2)$ bit steps, so tracing costs $O(q^3)$. Computing $a(S)-b(S)$ and adding $u$ use counters of $O(\log q)$ bits and fit this bound. Enumerate the states with a $c$-bit binary counter, making exactly $2^c$ visits; the $c=0$ case is one empty mask with $\mathrm{\mid }S\mathrm{\mid }=u=m$. Reading the stated input takes $O(q\log q)$ steps and is included.

Summing over all $2^c$ states, the l1 norm of the final coefficient sequence is at most the sum of the state-term l1 norms, hence at most $2^c{2}^{m+c-1}=2^{m+2c-1}$. Every individual coefficient therefore has absolute value at most $2^{m+2c-1}$.

Let $M=m+2c\ge 1$. By step 3.1, a nonzero coefficient $z_j$ satisfies $\mathrm{\mid }{z}_j\mathrm{\mid }\le 2^{M-1}$, so $\mathrm{\mid }{z}_j\mathrm{\mid }+1\le 2^M$ and ${\mathrm{\ell }}_{\mathbb{Z}}(z_j)=1+\lceil {\log }_2(\mathrm{\mid }{z}_j\mathrm{\mid }+1)\rceil \le M+1=m+2c+1$. The support lies in at most $6c+4m-3$ integer exponents by step 2.2, so storing the exact polynomial as a dense coefficient array takes $O((c+m{)}^2)$ bits. For a knot, $m=1$, giving degree at most $3c$ and coefficient-bit size at most $2c+2$, both linear in $c+1$.

Use coefficient slots for every exponent from $-3q$ to $3q$, padded with zeros, and use $2q+3$ bits per signed-magnitude slot, plus $O(\log q)$-bit position counters. These arrays have $O(q^2)$ tape cells. Every partial accumulator, not just the final sum, has coefficient l1 norm at most $2^c{2}^{m+c-1}$: apply the triangle inequality in step 3.1 to the subset of states already processed. Hence its coefficients fit the chosen width, since $m+2c-1<2q$. For one state compute $r=\mathrm{\mid }S\mathrm{\mid }-1$ and start with the array for $P_0=1$. For $k=0,\dots ,r-1$, form a new array by the exact recurrence $(P_{k+1}{)}_j=-(P_k{)}_{j-2}-(P_k{)}_{j+2}$, reading absent coefficients as zero. This is multiplication by $\delta$, so $P_r={\delta }^r$. All intermediate powers have degree at most $2r<2q$ and l1 norm at most $2^r\le 2^{m+c-1}$, so they too fit the arrays and widths.

Here is a direct tape bound without unit-cost access or integer arithmetic. To retrieve or write a coefficient, scan an entire array of $O(q)$ slots of $O(q)$ bits, advancing a binary slot counter and comparing it with the desired index. The counter work is $O(q\log q)$ and the scanned data have $O(q^2)$ bits, so one lookup or write costs $O(q^2)$ bit steps. Addition or subtraction of two signed integers in these slots is performed by sign comparison, a linear magnitude comparison, and the usual binary carry or borrow scan, costing $O(q)$ steps; the extra carry bit fits the reserved width. For each of the $O(q)$ destination coefficients in the recurrence of step 4.2, make at most two source lookups, one such addition, and one destination write. A multiplication by $\delta$ therefore costs $O(q^3)$ steps. There are $r<q$ repetitions, giving $O(q^4)$ work. Shift this state polynomial by $a(S)-b(S)$ and add it to the accumulator coefficient by coefficient using the same linear scans; the state shift has magnitude at most $c$, its support stays inside the slots by step 2.2, and this accumulation costs $O(q^3)$. Clearing arrays, moving the state counter, and loop-index bookkeeping are bounded by the same charges.

Summing the per-state bounds in steps 2.3, 4.2, and 5.1 over exactly $2^c$ visits gives $O(2^c{q}^4)$ bit steps. The initial component-count traversal costs $O(q^3)$ by step 2.3; coefficient-array initialization and writing the dense exact output cost $O(q^2)$. These are absorbed because $2^c\ge 1$ and $q\ge 2$. The loop tracing and arithmetic realize exactly the state terms in [F2], so [F3] identifies the result with the bracket. When $c=0$, the single state computes ${\delta }^{m-1}$ with the same bound; when $m=1$, $q=c+2$ gives $O(2^c(c+1{)}^4)$. All choices and operations are finite. The bit-cost argument concerns only the specified indexed table and elementary binary operations, so it makes no claim about parsing arbitrary code strings of length $L$ or the cost of an unspecified arithmetic library.

The linking scan performs one visit per element of the finite crossing list by [F2]. On a two-component input each visit makes at most one component-membership test and, for a mixed crossing, one integer addition, so there are at most $c$ tests and $c$ additions after the constant-size component-count check. Each added term is $+1$ or $-1$, hence the absolute value of the sum is at most $c$ and the returned half-sum has absolute value at most $c\mathrm{/}2$. The result is an integer and is the diagram's linking number by [F3] and [F4].

For each of the $c$ crossings, [F5] contributes three coefficients to a row. If arc labels repeat, combining at most three contributions requires at most two field additions for that row, so setup uses at most $2c$ additions; initializing the dense $c\times a$ matrix writes $ca$ zeros. There are $a$ columns, and each pivot search checks at most $c$ rows, for at most $ca$ entry tests.

Let $r$ be the number of pivots, so $r\le \min (c,a)$ and $f=a-r$. Normalizing each pivot row divides at most $a$ entries by its nonzero pivot, for at most $ra$ divisions. Clearing a pivot column from each of at most $c-1$ other rows updates at most $a$ entries, with at most one multiplication and one addition per entry. The row-reduction arithmetic count is therefore at most $ra+2r(c-1)a$. These loops are finite because there are at most $a$ columns and $c$ rows.

There are exactly $p^f$ assignments to the $f$ free variables by [F6]. For each assignment, each of the $a-f$ pivot variables is a linear combination of at most $f$ free variables; computing it uses at most $f$ multiplications and $f$ additions/subtractions, including the final negation. Writing the full solution uses $a$ output entries. Thus listing every coloring uses at most $p^f(2f(a-f)+a)$ field arithmetic and output-write operations. The loop is finite, including $f=0$, when there is one solution and only the $a$ entries are written.

For $f=0$, the count is $1$ without multiplication. For $f\ge 1$, binary repeated squaring computes $p^f$ with at most $2\lceil {\log }_2(f+1)\rceil$ integer multiplications. Since $f\le a$, the magnitude bit length is at most $f\lceil {\log }_{2}p\rceil +1$. This count-only postprocessing does not enumerate the solution set and does not change the full-list cost in step 3.1.

The diagram-by-diagram scan, matrix construction, row reduction, and finite solution enumeration above use no choice principle. By [F7], the Fox coloring count is preserved along every finite sequence of planar isotopies and oriented Reidemeister moves; by [A1] and [F8], ambient-isotopic oriented links admit such a sequence. By [F4], the linking-number half-sum has the same move invariance. Thus ACω is used only for the ambient-isotopy interpretations, not for any finite operation count.

By [F3], the state-sum procedure visits every map from the $c$-element crossing set to $\{A,B\}$ exactly once, so it makes exactly $2^c$ state visits. The writhe is the sum of one sign from each of the $c$ crossings by [F5], so a direct scan computes it in one pass. These finite operations use no choice principle.

Each crossing sign is $+1$ or $-1$, so $\mathrm{\mid }\mathrm{wr}(D)\mathrm{\mid }\le c$. Multiplication by $(-A^3{)}^{-\mathrm{wr}(D)}$ shifts every Laurent exponent of the raw bracket by $-3\mathrm{wr}(D)$ and multiplies coefficients only by a sign. Thus the absolute degree increases by at most $3c$, giving $6c+2m-2$ by [F4], while coefficient-bit size is unchanged and remains at most $m+2c+1$. For $m=1$ both bounds are linear in $c+1$.

Put $q=c+m+1$. By [F4], compute the raw bracket in $O(2^c{q}^4)$ bit steps in the specified representation. Summing the supplied sign bits uses an $O(\log (q+1))$-bit signed counter and $O(c\log (q+1))$ bit steps, rather than unit-cost unbounded arithmetic. The factor $(-A^3{)}^{-\mathrm{wr}(D)}$ has sign $(-1{)}^{\mathrm{wr}(D)}$ and exponent $-3\mathrm{wr}(D)$. Allocate a dense output array with exponents from $-6q$ to $6q$ and the same $O(q)$-bit signed coefficient slots as in [F4]. For each raw slot, copy its value to the position shifted by $-3\mathrm{wr}(D)$ and toggle the sign when necessary. There are $O(q)$ slots. Linear lookup or writing scans at most $O(q^2)$ tape cells per slot, including binary index counters, so even this naive normalization costs $O(q^3)$ bit steps. Step 1.2 ensures every shifted exponent and coefficient fits the array. This cost is absorbed in $O(2^c{q}^4)$, and for $m=1$ it is $O(2^c(c+1{)}^4)$. No arbitrary code parser or black-box arithmetic operation is assigned a false constant bit cost.

Under [A1], [F5] identifies the normalized output with an invariant of the ambient-isotopy class of the oriented link. The state count, writhe pass, degree shift, coefficient estimate, and specified bit implementation in steps 1.1, 1.2, and 2.1 remain choice-free. The running-time estimate is exponential in the crossing count, and makes no polynomial-time Jones evaluation claim.

Fix a code $C$ with $c$ crossings. The neighbor procedure uses bound $c+2$. By [F2] and [F3], this yields a finite candidate list containing every normalized connected one-component code with at most $c+2$ crossings. Each candidate has finitely many crossing labels, edge labels, and local edge intervals; the number of relabelings, subsets of at most three local crossings, boundary orders, and move variants is finite. Each candidate validation terminates by [F4]. Thus the neighbor list is finite and its local comparisons terminate.

If the neighbor procedure returns $(E,\mu )$, its certificate $\mu$ records either a code relabeling or a local code replacement matching one of the oriented Reidemeister variants, so [F4] and [F5] identify the represented diagrams up to planar isotopy and that one local move. Conversely, any single R1, R2, or R3 move changes the crossing count by at most two. Its result therefore appears among the candidates bounded by $c+2$ by [F3]. The move disk has two, four, or six boundary endpoints and at most three local crossing records; these are among the finite sites and variants checked by [F1]. Relabeling its finite code data is also among the finite bijections tested. Hence every one-move neighbor is returned.

The initial breadth frontier is a singleton. If a frontier is finite, [F1] and step 1.1 give a finite neighbor list for each of its members; a finite union of finite lists is finite. By induction every layer is finite and is processed in finite time, including an empty layer, which the algorithm repeats without returning a negative answer.

If the search returns a path, every adjacent pair has a certificate from [F1]. By step 2.1 each such pair differs by planar isotopy or one oriented Reidemeister move; concatenating the finitely many certificates gives a finite move sequence between the input diagrams. The easy direction of [F7] therefore gives ambient isotopy.

If the represented oriented knots are ambient-isotopic, [A1] and [F7] give a finite sequence of planar isotopies and oriented Reidemeister moves. By [F5], each intermediate diagram has a valid normalized code class. By step 2.1, the code class after each move appears in the corresponding neighbor list. Induction on the finite path length therefore places the target code class in a finite breadth layer; by step 2.2 that layer finishes, and [F6] returns the path.

The algorithm has no negative-output branch by [F6]. If no finite move path exists, it never returns Found(path); any finite-depth run that has not found the target establishes only that no path of that bounded length was found. The finite enumeration proves no decision or complexity-class conclusion. Finite neighbor generation and breadth-layer processing are choice-free; ${\mathrm{A}\mathrm{C}}_{\omega }$ is used only in [F5] and [F7] to interpret code and ambient-isotopy equivalence.