11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ advantage as compared to what? $\endgroup$ – Will Sawin Jan 12 '18 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 '18 at 19:36
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.