Knots, black holes, databases, and birthdays: Collision entropy of knot invariants

Source abstract

A knot invariant is a fingerprint shared by equivalent knots: unequal values certify inequivalence, while equal values may conceal different knots. Under two rooted random-diagram models, we prove that the incomplete normalized Alexander polynomial separates random pairs but collides in a growing database. If $D_n$ and $D_n'$ are independent $n$-crossing diagrams, then $\Pr\{Δ_{K(D_n)}=Δ_{K(D_n')}\}=O(n^{-1/2})$, and every fixed normalized Alexander polynomial is exponentially rare. With exponentially high probability, the diagram shadow contains linearly many disjoint opened-trefoil slots. Conditional on the shadow and exterior crossing signs, their indicators are independent Bernoulli$(1/4)$ variables whose sum is a binomial coordinate in the $3$-adic determinant valuation. Consequently, $\sup_{a\geq 1}\Pr\{\det K(D_n)=a\}=O(n^{-1/2})$. For a discrete invariant $I$, let $α_n(I)=\Pr\{I(D_n)=I(D_n')\}$. Its collision entropy is $H_2(I(D_n))=-\logα_n(I)$. An independent sample of size $M$ has $\binom{M}{2}α_n(I)$ colliding pairs on average and birthday scale $α_n(I)^{-1/2}$. If $M_n^2α_n(I)\to\infty$, a repeated value occurs with probability tending to one even when $α_n(I)\to0$. For the determinant, $M=o(n^{1/4})$ suffices for collision freedom with high probability; a matching lower bound is open. We also give exact finite-population formulas for fixed censuses, calculate the expected cost of invariant cascades, and relate collision probability to the frequency of calls to a complete equivalence procedure. On a balanced pair-classification benchmark, the normalized-Alexander rule has balanced accuracy $1-O(n^{-1/2})$ but cannot distinguish inequivalent pairs in one fiber.