Kuperberg's Knottedness is in $\mathsf{NP}$, modulo GRH provides a certificate that a knot $K$ given by a knot diagram on $c$ crossings is not trivial. The certificate is a prime $p$, along with a solution in $\mathbb{Z}/p$ to a system of $m$ polynomial equations on $n$ variables describing a representation of the knot group $\pi_1(S^3\setminus K)$ onto $\mathrm{SU(2)}$. Assuming the Generalized Riemann Hypothesis, the bit complexity $\log_2 p$ is polynomial in $m,n$, which are polynomial in $c$.

Letting each polynomial $f_i$ be of degree at most $d$, the problem is to find a solution to:


in $\mathbb{Z}/p$. Thought of as a $\mathsf{SAT}_p$ problem, for each $f_i$ we are asked to find a solution $f_i=0\mod p$.

However, we don't a-priori know $p$- the prime modulo which a solution is guaranteed to exist. We only know that there is at least one solution for at least one $p$ not bigger than some number that I'll call $B$.

Accordingly, is there any advantage to repeatedly guessing $n$ integers $\le B$, plugging these numbers in to the $m$ polynomials, and calculating the $\gcd$ of the resulting $f_i$, stopping when the $\gcd\ne1$?

If the $\gcd\ne 1$, we can think of it as a product of primes $p_1\times p_2\times\cdots$. Thus, there will be a solution in $\mathbb{Z}/p_1,\mathbb{Z}/p_2,\cdots$, and we know Kuperberg's certificate exists (although we might not know what the prime is unless we can factor the $\gcd$.)

There's an old adage that we can shoot an arrow at a wall and aim for a bulls-eye, but perhaps it's more efficient to shoot the arrow at the wall and draw a bulls-eye around wherever the arrow lands. But perhaps there are too few primes with solutions, or too few solutions modulo any given prime, to make such guessing worthwhile.

  • 1
    $\begingroup$ advantage as compared to what? $\endgroup$
    – Will Sawin
    Jan 12, 2018 at 17:04
  • $\begingroup$ Advantage of guessing $n$ variables and seeing if the $m$ equations are consistent over some $p$, as compared to trying various $p$'s and attempting to solve the $\mathsf{SAT}_p$ problem on $n$ variables. $\endgroup$
    – Mark S
    Jan 12, 2018 at 19:36

1 Answer 1


This question is probably very open if we want to be rigorous. With the roughest heuristics, the chance $p$ divides a polynomial value $f_i$ is $1/p$, and so the chance of recovering $p$ is $1/p^n$ where $n$ is the number of polynomials. Now if we sum over all primes and $n>2$ the expected number of solutions is less than $1$. While we know there is a solution, we won't find it by random search by this heuristic argument.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy