1
$\begingroup$

If $P(x)$ and $R(x)$ have integer coefficients and are irreducible over $\mathbb{Q}$, is there any way to tell if any of their non-real roots share a real part in common, i.e. that a root of one is $a + ib$ and the root of the other is $a + ic$ where $a \ne 0$?

One anecdotal observation that I made while constructing such polynomials was that if $a$ was rational then a factor of the $P'(x)$ and $R'(x)$ was $(x - a)$. But the existence of such a rational factor in the derivative doesn't guarantee that the polynomial has a root with that real part, e.g. $4x^4 - 4x^3 + 8x + 44$ has a factor of 1 in its derivative but has no complex root with a real part of 1. (So could it be that if there is no factor in common between the derivatives that there is no common real part among the non-real roots of the two polynomials?)

It seems like one way we could answer in the negative is to align the two polynomials in some way, e.g. on the values of the roots of their respective $(n-1)$st derivatives, $d_1$ and $d_2$, find the radius of the circles, $C_1(x)$ and $C_2(x)$, which contain the roots of $P(x-d_1)$ and $R(x - d_2)$. If these circles do not overlap when moved to $C_1(x + d_1)$ and $C_2(x + d_2)$ then the roots can't share a common real part. Why this choice of alignment? Because we know that the roots of all higher order derivatives of a polynomial lie within the convex hull that contains the roots of the polynomial (if I read Lemma 2 of Hubbard, Schleicher and Sutherland's 2001 paper correctly). And we know that the $(n-1)$st derivative will always exist and be real so it is a convenient reference point. The root of the $(n-1)$st derivative is $x = -b/(n a)$ where $n$ is the degree of the polynomial, $a$ is the coefficient of $x^n$ and $b$ is the coefficient of $x^{n-1}$ (which might be 0).

The motivation for this question is the desire to sort complex roots by real and imaginary part, e.g. $[a - iA, a + iA, a - iB, a + iB, b - iB, b + iB]$ where $a < b$ and $A < B$. All that is known are polynomial(s) and the rectangles in the complex plane that contains the roots for each polynomial (as generated by the Collins-Krandick algorithm of 2000). If two rectangles are not disjoint then refinement might lead to them being distinguishable in real component (as when the roots have real parts $a$ and $b$)...or may not (as when they share a common real part). It would be nice to know whether the real parts are distinct before attempting iterative refinement.


Here is an implementation of the solution suggested by @dxiv using SymPy

def samere(p, r):
  def res(p):
    a, b = var('a b', real=True)
    p1a, p1b = p.subs(x, a + I*b).as_real_imag()
    return Poly(p1a, b).resultant(Poly(p1b, b))
  g = Poly(res(p)).gcd(Poly(res(r)))
  if g.degree() > 0:
    return set(g.real_roots())


>>> p
x**4 - 8*x**3 + 26*x**2 - 40*x + 13
>>> r
x**4 - 8*x**3 + 30*x**2 - 56*x + 29
>>> samere(p, r)
{2}
>>> [i.n(2) for i in Poly(p).all_roots()]
[0.43, 3.6, 2.0 - 2.1*I, 2.0 + 2.1*I]
>>> [i.n(2) for i in Poly(r).all_roots()]
[0.79, 3.2, 2.0 - 2.7*I, 2.0 + 2.7*I]
$\endgroup$
1
$\begingroup$

The following outlines the steps to determine whether roots with the same real part exist, but it is computationally intensive and would require a CAS to work out in all but the most trivial cases.

Let $\,P(a+ib)=p_1(a,b) \,+\, i \,p_2(a,b)\,$ where $\,p_1,p_2\,$ are bivariate polynomials in $\,a,b\,$ with real (in fact, integer) coefficients. Then $\,P(a+ib) = 0 \iff p_1(a,b) = p_2(a,b) = 0\,$. Eliminating $\,b\,$ between the latter using polynomial resultants gives the polynomial $\,P_1(a) = \operatorname{res}_b (p_1,p_2)\,$ that $\,a\,$ must satisfy $\,P_1(a)=0\,$. Repeating the procedure for $\,R(a+ib)\,$ gives in the end a similar equation $\,R_1(a)=0\,$. Those two equations have a common real root $\,a\,$ iff $\,\gcd(P_1,R_1)\,$ has degree at least $\,1\,$ and has real roots. What still remains to be verified is that any such common root $\,a\,$ corresponds to $\,b \ne 0\,$ non-real complex roots of $\,P,R\,$.

$\endgroup$
  • 1
    $\begingroup$ In fact, this question arises from a CAS context (SymPy) and your approach was easy to implement using existing tools. Thanks! $\endgroup$ – smichr Mar 19 '18 at 20:40
  • $\begingroup$ Nicely done, thank you for the followup. $\endgroup$ – dxiv Mar 19 '18 at 21:42

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.