Are there any good tools to understand the movement of roots of polynomials in single variable with real or rational coefficients? That is say the coefficients are of the form $a_{i} + M b_{i}$ where $i$ coefficient index and the sets of numbers $a_{i}$ and $b_{i}$ for all $i$ need not be distinct but are fixed and $M$ is the parameter that varies. Is there a good tool to study when some of the roots turn positive for some $M \in \mathbb{Z}_{+}$ and $M$ bounded by some number $K$ and in an efficient way preferably in time $O(\log^{k}(K))$ for some $k > 0 \in \mathbb{R}$)?

  • $\begingroup$ A real root hits $0$ when the $0$'th coefficient $a_0 + M b_0 = 0$. Or are you talking about the real parts of complex roots? $\endgroup$ – Robert Israel Jun 27 '12 at 2:31
  • 1
    $\begingroup$ Maybe I misunderstand the question, but if you have fixed polynomials $f(x),g(x)$ and want to know where are the positive roots of $f+Mg$, then you need $M = -f(x)/g(x)$ and you just want to see the values of $-f(x)/g(x)$ for $x>0$. This is just calculus. $\endgroup$ – Felipe Voloch Jun 27 '12 at 3:07
  • $\begingroup$ I think you are talking about the root locus technique in control theory. en.wikipedia.org/wiki/Root_locus $\endgroup$ – Dan Petersen Jun 27 '12 at 3:20
  • $\begingroup$ corrected the question $\endgroup$ – T.... Jun 27 '12 at 17:27
  • $\begingroup$ To expand on Felipe Voloch's "just calculus", you just need find which of the critical points of $-f/g$ are in the positive real axis, and the value at $f=0$ as well as the limit as $f\to \infty$. The number of positive roots of the polynomial cannot change unless $M$ moves through one of these values, so by counting positive roots in each interval between two values you divide $[-K,K]$ into $O(1)$ intervals and can count the roots on each interval. $\endgroup$ – Will Sawin Jun 28 '12 at 15:19

If Robert Israel is correct that you are talking about real parts of complex roots, then you can do the following, to test for an imaginary root:

If $z$ is an imaginary root, then so is $-z$, so $x^2-z^2$ divides the polynomial. This means that $z^2$ is a root of two different polynomials: the "even" polynomial $a_0+Mb_0+(a_2+Mb_2)x+(a_4+Mb_4)x^2\dots $ and the "odd" polynomial $a_1+Mb_1+(a_3+Mb_3)x+(a_5+Mb_5)x^2+\dots$

So, a necessary condition is that the resultant of these two polynomials be $0$. This will be a polynomial in $M$, which you can solve explicitly. For each real root of $M$ you then have to check that the root shared by the even and odd polynomials is a negative real number, or, equivalently, check that the original polynomial has an imaginary root. But you only have to check that for finitely many values of $M$, the roots of the resultant, so it's not too bad.

The resultant could be identically $0$. This implies that there are always two roots that sum to $0$, so some polynomial in $\mathbb C[M]$ with no odd coefficients divides the original polynomial. This can only happen if the polynomial reduces in $C[M]$ into one constant factor and one factor with linear coefficients, in which case you just repeat for the factor with linear coefficients, or if all the odd coefficients are $0$, in which case you can write the polynomial as $f_M(x^2)$ and imaginary roots are just negative real roots of $f_M$.

So the resultant gives a method to solve the problem. This may or may not be the best way to go about it.


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.