2
$\begingroup$

The paper NEW NP-HARD AND NP-COMPLETE POLYNOMIAL AND INTEGER DIVISIBILITY PROBLEMS David A. PLAISTED

defines sparse polynomial as set $\{(a_i,i)\}$ and $f=\sum a_i x^i$.

On p.5:

Theorem 3.3. The followiug problem is NP-hard: Given a set $\{ p_1(x), p_2(x) \ldots , p_k(x)))\}$ of sparse polynomials with integer coefficients, to determine if they have a nontrivial greatest common divisor (the gcd has degree greater than zero).

At integers the gcd of two coprime polynomials $p_1,p_2$ is bounded by their resultant $res(p_1,p_2)$. For $k$ coprime polynomials $p_i$ the gcd at integers is bounded by the "total resultant" $res(res(res(p_1,p_2),p_3 \ldots p_k$). This means that if $p_i$ are coprime (not necessarily pairwise coprime) the $p_i$ vanish simultaneously modulo finitely many integers $q_i$. If $gcd(p_i)=g$ with $g$ non-constant, then for a root $r$ of $g$ modulo $n$ all $p_i(r)$ vanish modulo $n$.

This gives probabilistic algorithm: choose small prime power $p^k$, for $a \in \mathbb{Z}/p^k \mathbb{Z}$ check if $p_i(a)$ vanish simultaneously. If this happens, it increases the probability of non-constant gcd. Repeat with another prime power $p^k$.

Another possibility is to work modulo $p$ and try to do Hensel lifting of a common root $a$ for each $p_i$, since the derivative of sparse polynomial is efficiently computable. If the gcd is constant, we can't do too much Hensel lifting. If the gcd $g$ is non-constant and we he have found root $a$ of $g$ which is simple root modulo all $p_i$, we can do Hensel lifting forever.

If the total resultant is $1$, the $p_i$ will never vanish modulo $n$.

How good are these probabilistic algorithms? Any other special cases when they are deterministic?

Finding bound for the total resultant of the sparse polynomials in casea it is constant may help.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.