Re: polynomials with real roots

On Thu, 07 Feb 2008 03:33:44 -0500, quasi <quasi@xxxxxxxx> wrote:

On Thu, 7 Feb 2008 00:23:43 -0800 (PST), robin <robinsuri@xxxxxxxxx>
wrote:

On Feb 7, 12:37 pm, quasi <qu...@xxxxxxxx> wrote:
On Wed, 6 Feb 2008 23:07:18 -0800 (PST), robin <robins...@xxxxxxxxx>
wrote:

I am stuck with the following problem:

How to characterize all polynomials with real roots which has
coefficients 1 or -1?

Firstly, what do you mean by "with real roots"? Do you mean at least
one real root or do you mean that all the roots must be real?

Secondly, are missing terms allowed (i.e. possible coefficients of 0
as well as 1 or -1)?

Missing terms are not allowed.
All roots should be real.

There's no loss of generality in assuming the leading coefficient is
1.

By exhaustive search, there are 2 such polynomials of in each of the
degrees 1,2,3. Thus, 6 polynomials in all (or 12 if you count the ones
with leading coefficient -1).

There appear to be no others. In other words, for degree greater than
3, it appears that no such polynomial exists, but off hand, I don't
see how to prove that.

I /think/ I have a proof. It uses an inequality of Newton's to
reduce the number of cases to be considered to 1 for each n, and
then it has to use separate trickery for each value of n mod 4
to mutate the equation into a form in which Descartes's rule of
signs can be applied. This eliminates all cases except:

x^4 + x^3 - x^2 - x + 1 = 0

for which I just threw up my hands and drew a graph for x in
(0, 1), to 'show' that it has no real roots, not having yet
got anywhere with the equivalent form 1/(1-x) = x(x+1)^2.
(It surely ought to be simple to prove LHS > RHS, but I have
to go out to the shops now ...)

Never having learned Descartes's rule of signs, I had to crib
it from my old secondary school algebra book. (Oh, the rust!)
I stole the reference to Newton's inequality from this paper:

David C. Kurtz, "A sufficient condition for all the roots of
a polynomial to be real", AMM 99, 3 (Mar. 1992), pp. 259-263.

That is not an error, by the way, because he first considers
Newton's /necessary/ condition, which is that if n >= 2, and
the equation a_nx^n + ... + a_ix^i + ... + a_0 = 0 has all
real roots, then, for i = 1, 2, ..., n - 1:

a_i^2 >= a_{i-1}a_{i+1}(n - i + 1)(i + 1)/((n - i)i)

It's a thoroughly ugly proof (even assuming there are no errors
in it), so I won't type it out until we've seen if anyone can
come up with something that is either prettier or more direct.

--
Angus Rodgers
(twirlip@ eats spam; reply to angusrod@)
Contains mild peril
.

Relevant Pages