644 ANSWERS TO EXERCISES 4.6.4 30. (Web site developers) Starting with
644 ANSWERS TO EXERCISES 4.6.4 30. Starting with the construction in Theorem M, we will prove that mp+(l-~~om,) of the /3 s may effectively be eliminated: If pi corresponds to a parameter multiplication, we have pLz = PZG-1 x (Tz + Pz~); add P -P c 2% 1 2%t o each pj for which cpi occurs in Tj, and replace ,& by zero. This removes one parameter for each parameter multiplication. If pLz is the first chain multiplication, then /-lZ is the first chain multiplication, then pZ = (ylz + 81-k ,&-1) X (7~~ + 02 $ &), where 71, 72, 01, 02 are polynomials in pi, . . . , pzZ-z with integer coefficients. Here 6 1 and 6 2 can be absorbed into ,&-I and &, respectively, so we may assume that 01 = 82 = 0. Now add c&i-1pzi to each & for which cpL2 occurs in Tj; add &–172/71 to &; and set &-I to zero. The result set is unchanged by this elimination of &i-1, except for the values of CQ, . . . , cr, such that y1 is zero. [This proof is essentially due to V. I^a. Pan, Russian Mathematical Surveys 21,l (1966), 105-136.1 The latter case can be handled as in the proof of Theorem A, since the polynomials with yl = 0 can be evaluated by eliminating p2i (as in the first construction, where pLz corresponds to a parameter multiplication). 31. Otherwise we could add one parameter multiplication as a final step, and violate Theorem C. (The exercise is an improvement over Theorem A, in this special case, since there are only n degrees of freedom in the coefficients of a manic polynomial of degree n.) 32. XI = X0 X X0, X2 = cyl X XI, X3 = (~2 +X2, X4 = X3 x X1, X5 = ct3 +X4. We need at least three multiplications to compute 2~4~~ (see Section 4.6.3), and at least two additions by Theorem A. 33. We must have n+l 2 2m,+m,+&,,, and mc+mp = (n+l)/2; so there are no parameter multiplications. Now the first X, whose leading coefficient (as a polynomial in Z) is not an integer must be obtained by a chain addition; and there must be at least n + 1 parameters, so there are at least n + 1 parameter additions. 34. Transform the given chain step by step, and also define the content ci of Xi, as follows: (Intuitively, cz is the leading coefficient of Xi.) Define CO = 1. (a) If the step has the form A, = cyj + xk, replace it by A, = @, + &, where pj = &j/ck; and define cz = ck. (b) If the step has the form Xi = aj -xk, replace it by Xi = pj + Xk, where p, = -cr,/ck; and define ci = -ck. (c) If the step has the form 1, = Yj X xk, replace it by X, = xk (the step will be deleted later); and define cz = (d) If the ajck. step has the form A, = 1, X xk, leave it unchanged; and define ci = cjck. After this process is finished, delete all steps of the form Xi = &, replacing Xi by xk in each future step that uses Xj. Then add a final step X,+1 = p X X,, where p = CT. This is the desired scheme, since it is easy to verify that the new Xi are just the old ones divided by the factor ct. The p s are given functions of the CY S; division by zero is no problem, because if any ck = 0 we must have cr = 0 (hence the coefficient of xn is zero), or else xk never contributes to the final result. 35. Since there are at least five parameter steps, the result is trivial unless there is at least one parameter multiplication; considering the ways in which three multiplications can form u4z4, we see that there must be one parameter multiplication and two chain multiplications. Therefore the four addition-subtractions must each be parameter steps, and exercise 34 applies. We can now assume that only additions are used, and that we have a chain to compute a general manic fourth-degree polynomial with two chain multiplications and four parameter additions. The only possible scheme of this type