Linking number and Fox coloring finite complexity

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.