Fox colorings and quandle invariants

Addition and multiplication of residue classes are well-defined because congruence modulo $p$ is preserved by sums and products. If $\bar{r}\mathrm{\ne }0$ in $\mathbb{Z}\mathrm{/}p\mathbb{Z}$, choose an integer representative $r$ not divisible by $p$. Since $p$ is prime, $\gcd (r,p)=1$; Bézout's identity gives integers $u,v$ with $ur+vp=1$, so $\bar{u}\bar{r}=1$. Hence the residue classes form a field. For fixed $b$, the right translation is $R_b(a)=2b-a$ and satisfies $R_b(R_b(a))=2b-(2b-a)=a$. It is therefore a bijection.

Idempotency holds because $a\ast a=2a-a=a$.

For all $a,b,c$, $(a\ast b)\ast c=2c-(2b-a)=a-2b+2c$, while $(a\ast c)\ast (b\ast c)=2(2c-b)-(2c-a)=a-2b+2c$. Thus right self-distributivity holds; together with step 1.1 and step 1.2, [F1] gives the quandle axioms.

An R1 kink adds one underarc color $y$ to the unchanged boundary arc color $x$. Depending on the local orientation, the crossing equation is $y=x\ast x$ or $x=y\ast x$. In the first case idempotency gives the unique extension $y=x$; in the second case $x=x\ast x$ and right invertibility give the unique solution $y=x$. Removing the kink is the inverse bijection.

At an R2 move, fix the color $y$ on the strand passing over the other strand. The understrand's color changes by $R_y$ at one crossing and by $R_y^{-1}$ at the other; these maps are inverse bijections by [F1]. Thus every boundary coloring extends uniquely across the two-crossing side, and the inverse R2 move gives the inverse map.

For the braid-like R3 orientation, the local crossing map is $B(x,y)=(y,x\ast y)$ and its inverse is . Starting from $(x,y,z)$, the two sides of R3 give respectively $(z,y\ast z,(x\ast y)\ast z)$ and $(z,y\ast z,(x\ast z)\ast (y\ast z))$; these are equal by right self-distributivity. For every $z$, $R_z(x\ast y)=(x\ast y)\ast z=(x\ast z)\ast (y\ast z)$, so $R_z$ preserves $\ast$. If , then $u\ast b=a$; applying the bijection $R_z$ gives $R_z(u)\ast R_z(b)=R_z(a)$, and uniqueness of right division yields . Hence $R_z$ preserves $\bar{\ast }$ too, and its inverse preserves both operations. Thus for either operation ${\star }_1,{\star }_2\in \{\ast ,\bar{\ast }\}$, $(x{\star }_{1}y){\star }_{2}z=(x{\star }_{2}z){\star }_1(y{\star }_{2}z)$. These four identities give the R3 relation for every choice of crossing direction, and the bijective crossing maps give the corresponding extension bijections. A planar isotopy simply transports each arc label.

For the converse, the R1 extension property gives $x\ast x=x$ for every $x$: on the kink side, the boundary color $x$ can extend only when this equality holds.

In an R2 tangle with over-color $y$, the under-color map is $R_y$. Unique extension for every incoming color makes $R_y$ a function defined everywhere; unique extension in the reverse direction means each target color has exactly one preimage. Hence $R_y$ is bijective for every $y$.

In the braid-like R3 tangle, arbitrary boundary colors $x,y,z$ yield the outputs $(x\ast y)\ast z$ and $(x\ast z)\ast (y\ast z)$. Unique extension to the same boundary coloring forces these outputs to agree for all triples, which is right self-distributivity.

Thus the local axioms are necessary and sufficient for the stated local extension property. Under ${\mathrm{A}\mathrm{C}}_{\omega }$, [F3] connects diagrams of the same oriented link by finitely many such moves; composing the local bijections gives a bijection of coloring sets. A finite quandle has finitely many assignments on a finite diagram, so the bijection preserves their counts. Countable choice is used only through [F3]; the move-by-move calculations in steps 1.1–1.6 are choice-free.

Self-distributivity gives $(w\ast x)\ast x=(w\ast x)\ast (x\ast x)$ for every $w,x$. Thus $R_x(R_x(w))=R_{x\ast x}(R_x(w))$. Since $R_x$ is surjective, the two permutations agree: $R_{x\ast x}=R_x$, or $R_{\pi (x)}=R_x$.

Fix $z\in R$ and put $x=R_z^{-1}(z)$, which exists by [F1]. Then $x\ast z=z$. Self-distributivity says $R_z\circ R_x=R_{x\ast z}\circ R_z=R_z\circ R_z$. Cancel the bijection $R_z$ on the left to obtain $R_x=R_z$. Therefore $\pi (x)=R_x(x)=R_z(x)=x\ast z=z$, so $\pi$ is surjective and the displayed formula gives a preimage of every $z$.

If $\pi (x)=\pi (y)$, then step 1.1 gives $R_x=R_{\pi (x)}=R_{\pi (y)}=R_y$. Hence $R_y(x)=R_x(x)=\pi (x)=\pi (y)=R_y(y)$. Since $R_y$ is injective, $x=y$. Thus $\pi$ is injective as well as surjective, and step 1.2's formula is its inverse. If $R$ is empty, the unique map $R\to R$ is bijective and the conclusion is vacuous.

Each crossing contributes one linear equation in the $a$ arc variables, so the algorithm forms a $c\times a$ matrix over ${\mathbb{F}}_p$. Addition and multiplication of residue classes are well-defined because congruence modulo $p$ is preserved by sums and products. If a residue $r$ is nonzero, then $\gcd (r,p)=1$, so integers $u,v$ satisfy $ur+vp=1$ and $u$ is the inverse of $r$ modulo $p$. The field hypothesis in [A1] therefore supplies every division used by the pivot instructions in [F1].

Every row operation in [F1] preserves the solution set of the homogeneous system. A row swap is reversible by the same swap; multiplying a row by a nonzero scalar is reversible by multiplying by its inverse; and adding a multiple of one row to another is reversible by subtracting the same multiple. Each transformed system is therefore equivalent to the preceding one.

The algorithm visits each of the $a$ columns once, and each pivot search inspects at most $c$ rows, for at most $ac$ pivot-search entry tests. There are at most $\min (a,c)$ pivots. If $c=0$, there are no pivots or row additions. If $c>0$, each pivot adds a multiple of its row to at most $c-1$ other rows, so at most $ac$ row additions occur; each addition updates at most $a$ coefficients, for at most $a^{2}c$ coefficient updates. Normalizing each pivot row divides at most $a$ entries, for at most $a^2$ divisions. The loops are finite and the chosen first nonzero entry makes the procedure deterministic.

At termination, each pivot column has a single $1$ in its pivot row and zeros in every other row; earlier pivot columns stay cleared because each later pivot row is zero in those columns. Each nonpivot column is free. The pivot equations uniquely determine the pivot variables from arbitrary free-variable values, and every such assignment satisfies the reduced system. By step 2.1 the reduced system has exactly the original solution set, so the returned assignments are exactly the Fox colorings.

There are exactly $p^f$ choices of the $f$ free variables, and each determines one distinct solution. If $a=0$, then $f=0$ and the empty diagram has its unique empty assignment; if $c=0$, every arc variable is free and all $p^a$ assignments are returned. The stated pivot, search, addition, update, and division bounds follow from step 2.2.

Let $s$ be the number of rows in the candidate. The shape check reads the row count and all $s$ row lengths, so it terminates after $s+1$ shape checks and returns that witness if the shape fails. If the shape is valid, then $s=m$; the entry-range check examines at most $m^2$ values, and the column-permutation checks examine at most $m^2$ entries. Thus shape and format validation use at most $m+1+2m^2$ checks on a shape-valid table, and a malformed shape stops before any entry or axiom checks.

The triple loop visits exactly $m^3$ ordered triples and checks the right self-distributive identity of [F2]. In quandle mode the diagonal loop visits $m$ entries and checks exactly $T[x,x]=x$. Thus the total check bound on a shape-valid table is at most $(m+1)+2m^2+m^3+m=m^3+2m^2+2m+1$. The algorithm accepts exactly the tables satisfying the selected rack axioms, with idempotency required precisely in quandle mode.

If a column passes its permutation check, it defines a bijective right translation and its inverse column is completely determined. The assignment loop enumerates every one of the $m^a$ functions from the ordered arc set to the table elements once. At each crossing it tests exactly the relation from [F2], using that inverse column if required; hence an assignment is retained if and only if it is a coloring.

Every loop has a finite range, so the procedure terminates; it returns the exact failure witness at the first failed check or the complete coloring set and count when all checks pass. For the empty diagram the unique empty assignment is tested once, and for a diagram with zero crossings every one of the $m^a$ assignments passes.

Under R1, the new underarc generator $y$ satisfies either $y=x\ast x$ or $x=y\ast x$ for the unchanged arc color $x$. In the first case idempotency gives $y=x$; in the second, $x=x\ast x$ and right invertibility give the unique solution $y=x$. Thus the new generator is eliminated. Under R2, each added underarc generator is uniquely solved from its neighboring arc and the overarc by $\ast$ or $\bar{\ast }$; the reverse move gives the inverse substitution. Thus these moves are quandle Tietze transformations.

Under R3, assigning boundary colors $x,y,z$ gives the two possible iterated labels $(x\ast y)\ast z$ and $(x\ast z)\ast (y\ast z)$; these agree by right self-distributivity. With the over-colors fixed, each under-color substitution is invertible by right invertibility, so the reverse replacements give inverse substitutions. The same calculation for reversed crossings follows by applying the inverse right translations, which preserve both operations by self-distributivity.

For the knot-group comparison assume $L=K$. Let $\mathrm{\Gamma }$ be the finite planar graph obtained by taking the crossings as vertices and the strand pieces between consecutive crossings as edges. Choose disjoint small disks about the crossing vertices, each meeting $D$ only in its two transverse branches, and disjoint tubular strips around the compact edge pieces outside those disks. At a crossing, oriented local coordinates straighten the branches to two transverse axes. Choose a nearby rational point and two rational direction vectors, still transverse and in the same cyclic order as the original branches; the four rational half-segments give the coded crossing and its over/under choice. Extend each edge strip a short distance into its endpoint disks through the corresponding disjoint branch sectors, and choose rational bend ports there. In each strip choose a simple rational polygonal path that is a graph in strip coordinates and joins its ports; choose it fine enough that rounding its bends gives a small normal graph over the original edge. If there are no crossings, choose a simple rational polygon in a tubular annulus of the projected circle. Since there are finitely many compact edge pieces, nonincident pieces have positive separation, and each crossing is transverse; density of ${\mathbb{Q}}^2$ and a sufficiently fine finite subdivision therefore let all vertices and bends be rational while preserving the one-circle tracing, crossing cyclic orders, orientations, and over/under data, with no other intersections. The resulting record is a valid code by [F4]; smoothing its bends in disjoint disks gives a smooth regular diagram with the same crossing data by [F6]. To compare it with $D$, move each crossing point to its nearby rational point by an isotopy supported in its disk and the short branch sectors, fixed at the outer ends of the strips, and interpolate its four half-branches, within their disjoint sectors, through transverse direction pairs to the rational branches. This is an isotopy preserving the cyclic order and over/under choice. After these local adjustments, each rounded edge replacement is a sufficiently small normal graph $r=f(s)$ over the original edge in its strip, with $f=0$ near the ports. Choose the approximation so $\mathrm{\mid }f\mathrm{\mid }\mathrm{\parallel }{\chi }^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}<1$ for a cutoff $\chi$ that is $1$ near the edge and $0$ near the strip boundary. Then $(s,r)\mapsto (s,r+t\chi (r)f(s))$, $0\le t\le 1$, is a diffeomorphism in each strip, fixed near its boundary, and gives an ambient isotopy of that edge. Compose the finitely many disk and strip isotopies, using smooth time reparameterizations constant near their endpoints, to obtain a smooth plane isotopy $h_t$ supported in a fixed compact set $B$. Realize $D$ by $K\subset {\mathbb{R}}^2\times \mathbb{R}$ and choose $M$ with $K\subset {\mathbb{R}}^2\times (-M,M)$. Choose a smooth compactly supported function $\rho :\mathbb{R}\to [0,1]$ equal to $1$ on $[-M,M]$, and set $H_t(x,z)=(h_{t\rho (z)}(x),z)$. Its smooth inverse is $(x,z)\mapsto (h_{t\rho (z)}^{-1}(x),z)$, and its support lies in the compact set $B\times \mathrm{supp}\rho$. Hence $H_t$ extends by the identity near $\mathrm{\infty }$ to a smooth ambient isotopy of $S^3$. On $K$ it agrees with $(x,z)\mapsto (h_t(x),z)$, so it preserves all crossing heights and carries $K$ to a realization of the smoothed code diagram. Thus the code represents the same oriented knot $K$. The induced bijection on under-arcs preserves source, target, and overarc at each crossing because the positive over-normal and branch orientations are preserved. This finite construction uses no choice axiom.

The conjugation operation on $W(D)$ is idempotent because $g\ast g=g^{-1}gg=g$. Its right translation by $h$ is conjugation by $h^{-1}$, with inverse conjugation by $h$. It is right self-distributive because both $(g\ast h)\ast k$ and $(g\ast k)\ast (h\ast k)$ reduce to $k^{-1}{h}^{-1}ghk$. Thus $\mathrm{Conj}(W(D))$ is a quandle. Its generators $g_a$ satisfy the crossing equations by the relators of $W(D)$, so recursive evaluation of terms gives a quandle homomorphism $f:Q(D)\to \mathrm{Conj}(W(D))$. Define $\psi$ on adjoint generators by $\psi (e_q)=f(q)$. Since $f(q\ast r)=f(r{)}^{-1}f(q)f(r)$, every adjoint relator maps to the identity; [F2] therefore makes $\psi$ a group homomorphism.

For the knot-group comparison define $\varphi :W(D)\to \mathrm{Adj}(Q(D))$ on generators by $\varphi (g_a)=e_{x_a}$. The code from step 1.3 has the same under-arcs and crossing relations as $D$, so the constructor's relators in [F5] are exactly those of $W(D)$. At each crossing, $x_v=x_u\ast x_o$ in $Q(D)$, and the adjoint relation gives $e_{x_v}=e_{x_o}^{-1}{e}_{x_u}{e}_{x_o}$. Thus every relator of $W(D)$ maps to the identity; [F2] makes the homomorphism from the free group on its arc generators descend to $W(D)$.

By [F3], diagrams of $L$ are related by a finite sequence of these moves, and step 1.1 and step 1.2 identify the corresponding quandle presentations at each move. Their composites give an isomorphism between the two diagram quandles. Countable choice is used only for [F3]; these local presentation transformations use no choice.

The composites $\psi \varphi$ fix each $g_a$. The other composite fixes each generator $e_q$: every $q\in Q(D)$ is represented by a term in the arc generators using $\ast$ and $\bar{\ast }$, and the adjoint relations give $e_{u\ast v}=e_v^{-1}{e}_u{e}_v$ and $e_{u\bar{\ast }v}=e_v{e}_u{e}_v^{-1}$, so induction on the term gives $\varphi \psi (e_q)=e_q$. Hence $\varphi$ and $\psi$ are inverse isomorphisms. By [F5] and step 1.3, $W(D)$ is the group of the Wirtinger constructor for a code of $K$, and is isomorphic to ${\pi }_1(S^3\setminus K)$.

At an R2 move, hold the overarc color $y$ fixed. The underarc label is changed by $R_y$ at one crossing and by $R_y^{-1}$ at the other, so the two boundary colorings determine one another uniquely. Reversing the move gives the inverse correspondence.

For a braid-like R3 move, use the crossing map $B(x,y)=(y,x\ast y)$. Its inverse is by right invertibility. The two sides send $(x,y,z)$ respectively to $(z,y\ast z,(x\ast y)\ast z)$ and $(z,y\ast z,(x\ast z)\ast (y\ast z))$; the last coordinates agree by rack self-distributivity. For every $z$, $R_z(x\ast y)=(x\ast y)\ast z=(x\ast z)\ast (y\ast z)$, so $R_z$ preserves $\ast$. If , then $u\ast b=a$; applying $R_z$ gives $R_z(u)\ast R_z(b)=R_z(a)$, and uniqueness of right division yields . Thus $R_z$ and its inverse preserve both operations. For either operation ${\star }_1,{\star }_2\in \{\ast ,\bar{\ast }\}$, this gives $(x{\star }_{1}y){\star }_{2}z=(x{\star }_{2}z){\star }_1(y{\star }_{2}z)$, the corresponding mixed R3 equation. The bijective crossing maps then give the extension bijection for every orientation variant. A planar isotopy transports arc labels.

Write the under-tangent as $a{v}_{\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}}+b{n}_o$. Its determinant sign is the sign of $b$, so at a positive crossing the oriented underpass goes from source to target. In a positive curl with incoming label $x$ and outgoing label $y$, either the overarc is the incoming arc and $y=x\ast x$, or it is the outgoing arc and $y=x\ast y$. In the latter case self-distributivity gives $R_y{R}_x=R_{x\ast y}{R}_y=R_y{R}_y$, hence $R_x=R_y$; therefore $y=x\ast y=x\ast x=\pi (x)$. Conversely $y=\pi (x)$ solves the equation since $R_{\pi (x)}=R_x$ by the kink-map proof. Thus both positive curl shapes have unique transport $y=\pi (x)$. In a negative curl the same equations are read backwards and give $y={\pi }^{-1}(x)$. This checks both choices of which boundary arc is the overarc, independently of a picture.

For a single unframed curl with boundary color $x$, extension requires $x=\pi (x)$; if $\pi$ is the identity, this condition holds uniquely for every $x$. Conversely, if every boundary color extends uniquely, every $x$ is fixed by $\pi$, so $x\ast x=x$ for all $x$ and the rack is a quandle.

The kink shift propagates through any crossing. Self-distributivity gives $\pi (x\ast y)=(x\ast y)\ast (x\ast y)=(x\ast x)\ast y$, hence $\pi R_y=R_y\pi$. It also gives $(x\ast y)\ast y=(x\ast y)\ast (y\ast y)$ for every $x$. Since $R_y$ is surjective, this implies $R_{\pi (y)}=R_y$. By [F2], $\pi$ is bijective, so these identities hold for its inverse as well: ${\pi }^k{R}_y^{\delta }=R_y^{\delta }{\pi }^k$ and $R_{{\pi }^{\mathrm{\ell }}(y)}^{\delta }=R_y^{\delta }$ for all $k,\mathrm{\ell }\in \mathbb{Z}$ and $\delta \in \{1,-1\}$. In particular, if a crossing obeys $x_t=R_y(x_s)$, independently shifting its two under-colors by the same ${\pi }^k$ and its over-color by ${\pi }^{\mathrm{\ell }}$ preserves it, because $R_{{\pi }^{\mathrm{\ell }}(y)}({\pi }^k{x}_s)={\pi }^k{R}_y(x_s)={\pi }^k{x}_t$. The reversed crossing relation is preserved by the same calculation with $R_y^{-1}$.

A compensated pair creates two curls on the same oriented component, or removes their inverse configuration. If its blackboard framing is preserved, [F4] forces the two created crossing signs to sum to zero; the same holds when opposite signed framing changes are specified directly. Choose either of the two component intervals between the sites and traverse it in the component orientation, writing $ϵ\in \{1,-1\}$ for the sign of its first curl; the second has sign $-ϵ$. Starting from an old coloring, retain every color off this interval and replace every old color on it by ${\pi }^{ϵ}$ of that color, splitting an old under-arc at the two sites if needed. Insert the unique local curl labels from step1.3. At the first site the transport changes the old incoming label to its ${\pi }^{ϵ}$-shift; at the second the transport ${\pi }^{-ϵ}$ restores the old outgoing label. Thus the prescribed labels agree along every new maximal under-arc.

At any old crossing, the selected component interval contains both local halves of the underpassing branch or neither, since its endpoints are away from crossings. Thus the source and target under-colors have the same shift exponent $k\in \{0,ϵ\}$. Independently the overpassing branch has shift exponent $\mathrm{\ell }\in \{0,ϵ\}$. Step1.5 preserves the crossing relation for all four possibilities, including a self-crossing at which the interval contains exactly one of the two visits. The old crossing relations therefore all hold after the recoloring. Conversely, start with any coloring of the twice-curled diagram, undo the ${\pi }^{ϵ}$ shift on that same marked component interval, and remove the two uniquely determined curl portions using step1.3; step1.5 again preserves every intervening relation. The endpoint transports now cancel in the inverse order. These constructions are inverse on every arc label, so give the required bijection for arbitrarily separated opposite curls, not only adjacent curls. The removal move uses the inverse bijection.

Steps 1.1–1.2 give the R2, R3 and planar-isotopy bijections; steps 2.1, 3.1 give the compensation bijection. A finite rack admits only finitely many assignments on a finite diagram, so the cardinalities are preserved. Step 1.4 proves exactly when the individual unframed R1 bijection is available. The algebraic assertions use no choice; only the smooth framing interpretation uses [A1].