From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.symbolic
Subject: Re: Evaluation of Polynomials
Date: 27 Feb 1996 17:43:08 GMT

In article <1996Feb22.153704.10923@pat.uwe.ac.uk>,
Simon Langley <S.Langley@csm.uwe.ac.uk> wrote:
>Every polynomial p(x) has a (unique-ish) decomposition of the form:
>
>	p(x) = p0(p1(p2(...pk(x))))
>
>Where the pi are all polynomials (of course the decomposition may be trivial).  Suppose p 
>has degree m*n is there necessarily a decomposition of the form:
>
>	p(x) = q(s(x)) + r(x)
>
>Where degree(q) = m, degree(q) = n and degree(r) <= anything sensible?
                             ^  (should be  deg(s)=n)

>Since the lower bound for polynomial evaluation is m*n/2 multiplications presumably 
>degree(r) <= (m*n - m - n)/2?

You can't do that well in general. If you stay above the degree of  r,
you need to make the remaining coefficients of  q o s  agree with those
of  p. Treat the leading  k  coefficients of  q  as unknowns, as well
as all  n+1  coefficients of  s. These  (n+1)+k  coefficients are the
only ones which will affect the coefficients of  q o s  above degree
x^[(m-k)n]. If you expect all those coefficients to match the corresponding
coefficients of  p, then you'll have  mn - (m-k)n = kn  equations in
only  k+(n+1) unknowns, which is in general insoluble as soon as 
k > (n+1)/(n-1). Indeed, you can't even have  k=2 unless n = 1, 2, or 3. 
That is, you need to have a remainder r affecting powers of x greater
than x^( mn - 2n ) except possibly for those small n.

dave