17
$\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$
5
  • 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, 2012 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, 2012 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, 2012 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, 2012 at 0:23
  • 1
    $\begingroup$ I've now crossposted to MathOverflow. $\endgroup$
    – Joseph O'Rourke
    May 18, 2012 at 13:27

1 Answer 1

Reset to default
1
$\begingroup$

This has been answered on Mathoverflow.

$\endgroup$

You must log in to answer this question.

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