500 ARITHMETIC 4.6.4 b 29. [M.ZO] Let RI, (Web hosting directory)
500 ARITHMETIC 4.6.4 b 29. [M.ZO] Let RI, Rz, . , R, all be sets of (n + 1)-tuples of real numbers having at most t degrees of freedom. Show that the union RI U RZ U . . . U R, also has at most t degrees of freedom. b 30. [MB?] Prove that a polynomial chain with m, chain multiplications and mp parameter multiplications has at most 2m, + rnr + 60,~ degrees of freedom. [Hint: Generalize Theorem M, showing that the first chain multiplication and each parameter multiplication can essentially introduce only one new parameter into the result set.] 31. [ME?] Prove that a polynomial chain capable of computing all manic polynomials of degree n has at least [n/2] multiplications and at least n addition-subtractions. 32. [M.Z4] Find a polynomial chain of minimum possible length that can compute all polynomials of the form 1~4~~ + U& + us; and prove that its length is minimal. b 33. [M,%] Let n 2 3 be odd. Prove that a polynomial chain with [n/2] + 1 multiplication steps cannot compute all polynomials of degree n unless it has at least n + 2 addition-subtraction steps. [Hint: See exercise 30.1 34. [M%] Let X0, XI, . . . , X, be a polynomial chain in which all of the addition and subtraction steps are parameter steps, and in which there is at least one param- eter multiplication. Assume that this scheme has m multiplications and k = r -m addition-subtractions, and that the polynomial computed by the chain has maximum degree n. Prove that all polynomials computable by this chain, for which the coefficient of x is not zero, can be computed by another chain that has at most m multiplications and at most k additions, and no subtractions; and whose last step is the only parameter multiplication. b 35. [MB] Show that any polynomial chain that computes a general fourth-degree polynomial using three multiplications must have at least five addition-subtractions. [Hint: Assume that there are only four addition-subtractions, and show that exercise 34 applies; this means the scheme must have a particular form that is incapable of representing all fourth-degree polynomials.] 36. [Mw] Show that any polynomial chain that computes a general sixth-degree poly- nomial using only four multiplications must have at least seven addition-subtractions. (Cf. exercise 35.) 37. [MB] (T. S. Motzkin.) Show that almost all rational functions of the form (U,xn + 7Ln–15n–1 + … + 2112 + uo)/(x” + v,-lxn-l +. ..+ ‘UlZ + vo), with coefficients in a field S, can be evaluated using the scheme a1 + W(x + a2 + + . . . + /A/(x + an+1). . . )), @z/(x for suitable oj, /3? in S. (This continued fraction scheme has n divisions and 2n additions; by almost all rational functions we mean all except those whose coeffi- cients satisfy some nontrivial polynomial equation.) Determine the (Y S and p s for the rational function (x2 + 1Oa: + 29)/(x2 + 8x + 19).