512 ARITHMETIC 4.7 We obtained the simple state (Adelphia web hosting)
512 ARITHMETIC 4.7 We obtained the simple state of affairs in (20) by starting with V and u, then defining U. But in practice we generally want to go the other way: Starting with some given function U, we want to find V and u such that (19) holds, i.e., such that V(U(z)) = uV(z). (21) Such a function V is called the Schriider function of U, because it was introduced by Ernst Schriider in Math. Annalen 3 (1871), 296-322. Let us now look at the problem of finding the Schrijder function V(z) = z + V2z2 +. . . of a given power series U = Ulz $ Uzz2 + a . . . Clearly u = VI if (21) is to hold. Expanding (21) with u = U1 and equating coefficients of z leads to a sequence of equations that begins u34 + u, = UIV2 up3 + 2u1uzvz + u, = UlV3 u; vi + 3u;u&s + 2ulusv2 + u;v2 + u, = ulb -, and so on. Clearly there is no solution when VI = 0 (unless trivially U2 = U, = . . . = 0); otherwise there is a unique solution unless VI is a root of unity. We might have expected that something funny would happen when Uy = 1, since Eq. (20) tells us that U (z) = z if the Schrijder function exists. For the moment let us assume that VI is nonzero and not a root of unity; then the Schrijder function does exist, and the next question is how to compute it without doing too much work. The Collowing procedure has been suggested by R. P. Brent and J. F. Traub. Equation (21) leads to subproblems of a similar but more complicated form, so we set ourselves a more general task whose subtasks have the same form: Let us try to find V(z) = V. + Viz + … + Vn-l~n-l such that V(W) = Wz)V(z) + S(z) + O(z L (22) W(z), SC z , and n, where n is a power of 2 and U(0) = 0. If n = 1 we simply let Vi = S(O)/(l -W(O)), with Vi = 1 if S(0) = 0 and W(0) = 1. Furthermore it is possible to go from n to 2n: First we find R(z) such that given u(z), ) V(U(z)) = W(z)V(z) + S(z) -z R(z) + O(z2 ). (23) Then we compute Wz) = W4(zlW)) , 3(z) = R(z)(z/U(z))n (24) and find P(z) = V, + Vntlz + . . . + V2n–1~n-1 such that P(U(z)) = vv(z)P(z) + 3(z) + O(P). (25) It follows that V*(U(z)) = W(z)V*(z) + S(Z) + O(z2 ) as desired, where V*(z) is equal to V(z) + z V(z).