# How hard is it to guess Kuperberg's certificate of knottedness?

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:

$$f_1[x_1,x_2,\cdots,x_n]=f_2[x_1,x_2,\cdots,x_n]=\cdots=f_m[x_1,x_2,\cdots,x_n]=0$$

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.

• advantage as compared to what? Jan 12, 2018 at 17:04
• 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. Jan 12, 2018 at 19:36

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.