11
$\begingroup$

I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite exact representation of these polynomials). If needed, we may suppose that the degree of both polynomials is equal. Let us denote by $x_p$ (resp. $x_q$) the greatest absolute value of some (real or complex) root of the polynomial $p$ (resp. $q$). Is the property $x_p = x_q$ decidable?

If not, does this property hold for some restricted families of polynomials? In the context from which this problem arises, the polynomials are characteristic polynomials of matrices, and their roots are eigenvalues.

I am aware of some numerical algorithms for computing roots of polynomials / eigenvalues, however these seem to be of no use here, since the output of these algorithms is only approximate. It seems to me that computer algebra might be useful here, however, unfortunately, I do not have almost any knowledge in that field.

I am not searching for a detailed solution to this problem, however any intuition and ideas where to search for the solution would be helpful.

Thank you in advance.

$\endgroup$
  • $\begingroup$ If you can compute the splitting field then you could just write them both in the form $(x-x_0)(x-x_1)\dots$ and compare; for some fields the splitting field isn't computable but I'm not sure if this holds for extensions of $\mathbb{Q}$? $\endgroup$ – Xodarap Oct 15 '12 at 15:45
5
$\begingroup$

I'm not knowledgeable in that field either, but I think I can provide a non-constructive answer.

The first-order theory of real closed fields is decidable. Your problem can be stated as a system of algebraic equations and inequations over the real algebraic numbers. Consider $2 (\deg P + \deg Q)$ variables $x_1,\ldots,x_{\deg P}, y_1,\ldots,y_{\deg P}, x'_1,\ldots,x'_{\deg P}, y'_1,\ldots,y'_{\deg P}$. You want to know whether the following system is satisfiable: $$\begin{align*} P(x_j+i\,y_j) &= 0 & \text{for \(1 \le j \le \deg P\)} \\ Q(x'_k+i\,y'_k) &= 0 & \text{for \(1 \le k \le \deg Q\)} \\ x_j^2 + y_j^k &\le x_1^2 + x_2^2 & \text{for \(2 \le j \le \deg P\)} \\ x'_j^2 + y'_j^k &\le x'_1^2 + x'_2^2 & \text{for \(2 \le k \le \deg Q\)} \\ x_1^2 + y_1^2 = x'_1^2 + y'_1^2 \\ \end{align*}$$

The first two equation families express that the $x_j+i\,y_j$ and $x'_k+i\,y'_k$ are roots of the polynomials, the next two inequation families express that $x_1+i\,y_1$ and $x'_1+i\,y'_1$ have the largest absolute value, and the last inequation compares these largest absolute values.

It is decidable whether this system is satisfiable: your problem is decidable. However, this statement is probably not the most efficient way to go about it.

A more useful answer probably involves the theory of Gröbner bases. If you're trying to solve that problem for yourself, I think reading the first few chapters of any computational algebra book will give you the requisite background. If you're just aiming to solve your underlying problem, there is probably an off-the-shelf algorithm you can implement.

$\endgroup$
1
$\begingroup$

I may be wrong about this: I am also not very knowledgeable in this field (where are the experts!?), but I believe I have a reasonably fast algorithm for what you are asking.

I am going to suppose, for simplicity, that all the roots are real. Find an interval bound on the root of $P$ with highest absolute value (i.e. an interval $I$ such that $x_P\in I$ and $x_P'\notin I$ for all other roots of $P$). Such an interval can be found by the combined use of dichotomy and Sturm's theorem. Now compute the polynomial GCD $R$ of $P$ and $Q$. Verify that $R$ has a root in $I$ (again with Sturm's theorem).

If I am not mistaken, $R$ has such a root if and only if $P$ and $Q$ have a common root in $I$, which in turn is only possible if $x_P$ is a root of $Q$. Both the application of Sturm's theorem and the GCD are rather fast (not more than quadratic in the size of the polynomials in fact).

This is just a sketch, but it doesn't take much to turn this into a bona fide algorithm, in fact I suspect that the use of Maple or Mathematica would make this trivial.

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