16
$\begingroup$

I have two questions about the class of integer-coefficient polynomials all of whose roots are rational.

Q1. Is there some way to recognize such a polynomial from its coefficients $a_0, a_1, \ldots, a_n$?

I am aware of the rational-root theorem, which says that each rational root is of the form $\pm p/q$, where $p$ is a factor of $a_0$ and $q$ a factor of $a_n$.

Q2. Has this class of polynomials been studied in its own right?

In other words, is this class interesting? I can see it has at least a monoid structure, as the product of two such polynomials also has all rational roots.

These are naive questions, well out of my expertise. Thanks in advance for educating me!

Update. The discussion at MathOverflow (see here) concluded that Q1 can be answered in polynomial time, using methods in the famous Lenstra, Lenstra, Lovász paper, "Factoring polynomials with rational coefficients."

$\endgroup$
  • 2
    $\begingroup$ This class is bijective with the class of all pairs $(A,X)$ where $A$ is an integer and $X$ is a finite multiset of rational numbers. Whether that is a useful fact, I don't know. $\endgroup$ – user14972 May 17 '12 at 14:32
  • $\begingroup$ @Hurkyl: yes, but it doesn't appear to be particularly easy to compute this bijection in one direction. $\endgroup$ – Qiaochu Yuan May 17 '12 at 14:36
  • $\begingroup$ Sturm's Theorem gives you a way of telling how many distinct real roots there are without computing them and can be used to locate roots. So that can be done from the coefficients. en.wikipedia.org/wiki/Sturm's_theorem $\endgroup$ – Mark Bennet May 17 '12 at 16:23
  • 1
    $\begingroup$ @Mark: Thanks, yes. So one can view the question as seeking an equivalent of Sturm's Theorem for rational roots. $\endgroup$ – Joseph O'Rourke May 18 '12 at 0:23
  • 1
    $\begingroup$ I've now crossposted to MathOverflow. $\endgroup$ – Joseph O'Rourke May 18 '12 at 13:27
1
$\begingroup$

This has been answered on Mathoverflow.

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