Alexander Fingerprints Separate Pairs Yet Collide in Databases

A knot invariant can certify that two diagrams represent different knots when its values disagree, but equality is weaker: many inequivalent knots can share a fingerprint. That distinction matters when invariants are used as filters in a large census rather than as one-off pairwise tests. The authors study this gap under two rooted random-diagram models and frame it through collision probability: the chance that two independent $n$-crossing diagrams receive the same discrete invariant value.

Their conclusion is deliberately mixed. The incomplete normalized Alexander polynomial is an effective random-pair separator, with collision probability $O(n^{-1/2})$, and every fixed normalized polynomial is exponentially rare. Yet a vanishing pair-collision probability does not imply a collision-free database. Once the number of sampled diagrams passes the birthday scale, repeated invariant values become likely.

Core Contribution

The paper connects random knot diagrams, database collisions, and collision entropy. For a discrete invariant $I$, it defines $\alpha_n(I)=\Pr\{I(D_n)=I(D_n')\}$ for independent diagrams and writes its collision entropy as $H_2(I(D_n))=-\log\alpha_n(I)$. A sample of size $M$ has $\binom{M}{2}\alpha_n(I)$ colliding pairs in expectation, so the relevant database threshold is $\alpha_n(I)^{-1/2}$ rather than the much weaker condition that $\alpha_n(I)$ merely tends to zero.

For the determinant, the paper proves an anti-concentration upper bound $\sup_{a\geq1}\Pr\{\det K(D_n)=a\}=O(n^{-1/2})$. This turns into a practical asymptotic statement: databases with $M=o(n^{1/4})$ are collision-free with high probability. The result does not establish the converse; the authors explicitly leave a matching lower bound open.

Technical Approach

The main mechanism is local and probabilistic. In the rooted random-diagram models, a high-probability “good-shadow” event contains linearly many disjoint opened-trefoil slots. After conditioning on the diagram shadow and exterior crossing signs, the internal signs of these slots remain independent. Each closure is a trefoil in two of its eight possible decorations, making the corresponding indicators independent Bernoulli variables with parameter $1/4$.

The paper also develops finite-population formulas instead of treating a fixed knot census as an independent sample. If a census of $T$ entries is partitioned into invariant fibers, the no-collision probability depends on the full fiber-size profile, not simply on the number of occupied values. Equal-sized fibers minimize collisions at fixed $T$ and number of fibers, while imbalanced fibers can trigger repeated values sooner.

Results and Analysis

The strongest quantitative result is the $O(n^{-1/2})$ pair-collision bound for the normalized Alexander polynomial and for the determinant’s maximum atom. This supports high balanced accuracy for a pair classifier that labels unequal normalized-Alexander values as inequivalent: the reported asymptotic balanced accuracy is $1-O(n^{-1/2})$. But the classifier has an irreducible blind spot inside each invariant fiber, where equal values cannot distinguish inequivalent pairs.

The database analysis is the more useful corrective to a common interpretation of such bounds. If $M_n^2\alpha_n(I)\to\infty$, a repeated value occurs with probability tending to one even when $\alpha_n(I)\to0$. Thus pairwise separation and census uniqueness answer different operational questions. For the determinant, the proven collision-free regime below $n^{1/4}$ is informative, but it is only a sufficient regime, not a sharp transition.

The authors further model adaptive invariant cascades. Their expected-work formula accounts for entries resolved at each stage, entries forwarded to later invariants, and unresolved pairs sent to a complete equivalence procedure. This makes ordering an economic decision: an additional invariant is worthwhile only when its evaluation cost is offset by expected savings in terminal calls. The framework does not assume independence among invariant coordinates, which is appropriate for related knot fingerprints.

Scope and Limits

The asymptotic proof is tied to Chapman’s rooted random-diagram ensembles and to the opened-trefoil construction. The authors note that other random-knot models, including lattice and off-lattice self-avoiding polygons, Petaluma diagrams, and random two-bridge knots, require separate analysis because their laws and asymptotics differ. The work is theoretical rather than an empirical benchmark: it supplies asymptotic rates and exact census formulas, but no measured finite-size transition for a real knot database.