Newsgroups: sci.math.symbolic
Subject: Re: Do these polynomials have distinct roots?
From: rusin (but never sent, I think)
Date: Mar 30 1998 (Timestamp on file)

In article <351D8F25.2781@math.mcgill.ca>,
Thomas Mattman  <mattman@math.mcgill.ca> wrote:
>I would like to show that each polynomial in the following sequence
>has distinct roots in C.

[The polynomials were defined recursively as
	w[n] = p w[n-1] + q w[n-2]  
 where  w[1] = x^3 + 2x^2 + x + 1, w[2]= -(x^5 + 3x^4 + 4x^3 + 5x^2 + 4x +2),
	p= -(x^2 + x + 2)  and q=-x^2    -- djr]

I did not succeed in proving this. But you might be able to proceed further.
My angle was to observe (no repeated roots) <=> gcd(f, f')=1  <=> there
exist  h, k  with  h f + k f' = 1. If these  h, k  exist, they are not
unique, but there will be unique ones with deg(h) < deg(f'), deg(k)<deg(f).

So it seems natural to show the result by induction by actually producing
the  h  and  k  (also by induction, I guess). Well, I computed the first
20 pairs (h,k), and while there are some obvious patterns, I didn't 
succeed in finding an induction pattern. If you'd like to try this an
obvious thing to start with is to predict the denominators in the coefficients,
since the  w_i  themselves are integral. I couldn't even figure out
the pattern for the denominators. (If you do figure it out I'd like to know.)

If the  w_i  satisfy a linear recurrence corresponding to the quadratic
Q  (in the usual generating-series formulation), then both they and their
derivatives satisfy the recurrence corresponding to  Q^2. Unfortunately,
if the  h's  do, too, that recurrence doesn't kick in until past the 20th
term, according to my calculations. 

(On the other hand, note that it would suffice to find  h, k  to make
h f + k f'  _constant_, that is, we could scale arbitrarily. I didn't try
to hard to see if some non-uniform scaling of the  h's  would satisfy
this recurrence.)

It also seems to be true the the  h's  don't satisfy any 2-term recurrence
at all whose coefficients involve only  x  (not  i ).

Attached below oare the maple scripts I used.

Assuming the desired result is true, I'm sure there's a slick way to prove it!

dave

==============================================================================
#Maple script
w1:= x^3 + 2*x^2 + x + 1:
w2:= -(x^5 + 3*x^4 + 4*x^3 + 5*x^2 + 4*x +2):
p:= -(x^2 + x + 2):
q:=-x^2:

Mx:=20:
for n from 3 to Mx do
 j:=n-1:k:=n-2:
 w.n:=sort(expand(p*w.j+q*w.k));
od:

# w.i seems to have about i/4 real roots; numroots(w')=numroots(w)-1.
#you can get this number accurately with Sturm sequences. Use
readlib(realroot):
#But in fact there are functions  a, b, f, g  in a quadratic extension of 
#Q(x) with  w_i = a f^i + b g^i, so  w_i=0  iff  
#f(z)/g(z) = zeta * (-b(z)/a(z))^(1/i)  for any zeta with  zeta^i = 1.
#So we expect roots near  (f/g)^(-1) (1), etc.

#h_i = [the  h  above,  the  k  above]  :
for n from 1 to Mx do
 m:=2*n+1:
 h.n:=[seq(a.i,i=0..m-2),seq(b.i,i=0..m-1)]:
 i:='i':
 ex:=w.n*(sum(h.n[i+1]*x^i,i=0..m-2))+diff(w.n,x)*(sum(h.n[i+m]*x^i,'i'=0..m-1))-1:
 ex:=factor(taylor(ex,x,2*m-1)):
 co:=[]:for i from 0 to 2*m-2 do co:=[op(co),coeff(ex,x,i)]:od:
 solve({op(co)},{seq(a.i,i=0..m-2),seq(b.i,i=0..m-1)}):
 h.n:=subs(",h.n):
 i:='i':h.n:=[sum(h.n[i+1]*x^i,'i'=0..m-2),sum(h.n[i+m]*x^i,'i'=0..m-1)];
 print(n,'don'); #by n=20 this takes ~1 min per n.
od:

#check:
expand(h.Mx[1] * w.Mx + h.Mx[2]*diff(w.Mx,x) ); # should give  1.

#play with it a little
realroot(h.Mx[1]); #fsolves to ~ -1.97, -1.87, -1.68 for Mx=20
sort(h20[1]): #see that all coeffs are positive  !
z:=[seq(denom(content(h.i[1])),i=1..20)]; #numerators were all 1 !
#z seems to be  2^(2n-5) * (garbage);  garbage is prime e.g for n=20!
#or take  z=[seq(subs(x=0,h.i[1]),i=1..20)];
plot([seq(op([i,log(z[i])]),i=1..Mx)],style=point); #logz~11.1*i-28

eq:=[seq(h.i[1]-A*h.(i-1)[1]-B*h.(i-2)[1]-C*h.(i-3)[1]-d*h.(i-4)[1],i=5..Mx)]:
solve({eq[Mx-4],eq[Mx-5],eq[Mx-6],eq[Mx-7]},{A,B,C,d});
#Mx=10: nothing appropriate. 

eq:=[seq(h.i[1]-(A+B*i)*h.(i-1)[1]-(C+d*i)*h.(i-2)[1]-(e+f*i)*h.(i-3)[1],i=3..Mx)]:
#solve({eq[Mx-2],eq[Mx-3],eq[Mx-4],eq[Mx-5],eq[Mx-6],eq[Mx-7]},{A,B,C,d,e,f});
eq:=subs({e=0,f=0},eq): solve({eq[Mx-2],eq[Mx-3],eq[Mx-4],eq[Mx-5]},{A,B,C,d});
#nothing appropriate.

#quit !