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

Improve this question
$\endgroup$
3
  • 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
    Commented Nov 9, 2014 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
    Commented Nov 9, 2014 at 21:17
  • $\begingroup$ Well, yes, then binary search is your friend, as Timothy Chow explains :) $\endgroup$
    – Vladimir Dotsenko
    Commented Nov 10, 2014 at 9:47

2 Answers 2

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
7
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .