8
$\begingroup$

Does there exist a polynomial-time algorithm to determine whether a given polynomial $p(n)$ with integer coefficients is positive on $\mathbb{N}$, in the sense that $p(n) \geq 0$ for all $n\in\mathbb{N}$?

This question seems to be related, but it involves multivariable polynomials and asks about positivity on all of $\mathbb{R}^n$, and the answer doesn't seem to apply to single-variable polynomials.

Edit: Just to clarify, the input for the algorithm should be a string that encodes the polynomial $p$ in a reasonably compact fashion, e.g. the digits of the degree of $p$ followed by the digits of the coefficients.

$\endgroup$
  • 1
    $\begingroup$ It would help if you give some context, and explain what you tried. For instance, what prevents you from bounding the roots in the usual way (like you do when proving the fundamental theorem of algebra) by (roughly) the sum of absolute values of coefficients, and then compute values at points within that range? $\endgroup$ – Vladimir Dotsenko Nov 9 '14 at 21:04
  • $\begingroup$ @VladimirDotsenko I've editied my post to clarify what "input length" means in this context. The problem is that the sum of the coefficients is an exponential function of the input length (since each coefficient is exponential in its number of digits), so there's not enough time to test all points within that range. $\endgroup$ – Magritte Nov 9 '14 at 21:17
  • $\begingroup$ Well, yes, then binary search is your friend, as Timothy Chow explains :) $\endgroup$ – Vladimir Dotsenko Nov 10 '14 at 9:47
11
$\begingroup$

Yes. Compute a Sturm sequence and use binary search to locate the real roots.

$\endgroup$
6
$\begingroup$

Yes, sure, this can be done.

You can "find" all the roots of $f$ on the real axis in polynomial time. More precisely, you can find intervals $[a_i,b_i]$ ($i=1,\dots, d$) with rational endpoints $a_i$, $b_i$, so that $f$ is monotonic on $[a_i,b_i]$ and $f(a_i)f(b_i)<0$, and so $x_i\in [a_i,b_i]$ is a real root of $f$. Assuming these intervals are ordered from left to right, you easily test whether there is a positive integer between $x_{2j-1}$ and $x_{2_j}$ (this is for the case of even degree $f$; for the odd degree the first $x_i$ can be ignored).

This will pin the finitely many (at most the degree of $f$) positive integers of which $f$ might be negative.

$\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.