MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

464 ARITHMETIC 46.3 16. [HM15] Show that Theorem D is not trivially true just because of the binary method; if LB(n) denotes the length of the addition chain for n produced by the binary S-and-X method, lB(n)/X(n) does not approach a limit as n -+ co. 17. [M%] Explain how to find the intervals J1, . . , Jh that are required in the proof of Lemma P. 18. [HM24] Let ,0 be a positive constant. Show that there is a constant a: < 2 such that c(:+ :)( ;v)41Y((mits)2) < am for all large m, where the sum is over all s, t, v satisfying (30). 19. [M,8] A multiset is like a set, but it may contain identical elements repeated a finite number of times. If A and B are multisets, we define new multisets AN B, AU B, and An B in the following way: An element occurring exactly a times in A and b times in B occurs exactly a + b times in AN B, exactly max(a, b) times in AU B, and exactly min(a, b) times in A n B. (A set is a multiset that contains no elements more than once; if A and B are sets, so are A U B and A n B, and the definitions given in this exercise agree with the customary definitions of set union and intersection.) a) The prime factorization of an integer n > 0 is a multiset N whose elements are primes, where l&e,, = n. The fact that every positive integer can be uniquely factored into primes gives us a one-to-one correspondence between the positive integers and the finite multisets of prime numbers; for example, if n = 22 . 33 .17, the corresponding multiset is N = {2,2,3,3,3,17}. If M and N are the multisets corresponding respectively to m and n, what multisets correspond to gcd(m,n), lcm(m, n), and mn? b) Every manic polynomial f(z) over the complex numbers corresponds in a natural way to the multiset F of its roots ; we have f(z) = &,(z -0. If f(z) and g(z) are the polynomials corresponding to the finite multisets F and G of complex numbers, what polynomials correspond to F u G, F U G, and F n G? c) Find as many interesting identities as you can that hold between multisets, with respect to the three operations M, IJ, Il. 20. [M20] What are the sequences Si and Mij (0 2 i 2 r, 0 2 j 5 t) arising in Hansen s structural decomposition of star chains (a) of Type 3? (b) of Type 5? (The six types are defined in the proof of Theorem B.) b 21. [M25] (W. Hansen.) Let q be any positive integer. Find a value of n such that I(n) 2 l*(n) -4. 22. [MZ?O] Prove that the addition chain constructed in the proof of Theorem F is an lo-chain. 23. [MXI] Prove Brauer s inequality (50). b 24. [M.%?] Generalize the proof of Theorem G to show that l ((B -l)/(B -1)) 2 (n -1) 1 (B) + 1 (n), for any integer B > 1; and prove that 1(2 -1) 2 1(2m -1) + mn -m + l (n). 25. [ZVO] Let y be a fraction, 0 < y < 1, expressed in the binary number system as y = (.dr . . . c&)2. Design an algorithm to compute zy using the operations of multiplication and square-root extraction. b 26. [ML?41 Design an efficient algorithm that computes the nth Fibonacci number F,, modulo m, given large integers n and m.

4.6.3 EVALUATION OF POWERS 463 in 6. [A4.26] exercise If a slight 5, so that change is made the nodes below to the definition n are attached of the power tree in decreasing order that is given Tl+ak-1, . . . . 71.+%, n+al, n+l instead of increasing order, we get a tree whose first five levels are Show that this tree gives a method of computing x that requires exactly as many multiplications as the binary method; therefore it is not as good as the power tree, although it has been constructed in almost the same way. 7. [M.Z1] Prove that there are infinitely many values of n a) for which the factor method is better than the binary method; b) for which the binary method is better than the factor method; c) for which the power tree method is better than both the binary and factor methods. (Here the better method shows how to compute xn using fewer multiplications.) 8. [M.21] Prove that the power tree (exercise 5) never gives more multiplications for the computation of xn than the binary method. 9. [M.B] Design an exponentiation procedure that is analogous to Algorithm A, but based on a general radix m 2 2. Your method should perform approximately lgn + v + 2m multiplications, where v is the number of nonaero digits in the m-ary representation of n. 10. [JO] Figure 14 shows a tree that indicates one way to compute ZI? with the fewest possible multiplications, for all n 5 100. How can this tree be conveniently represented within a computer, in just 100 memory locations? k 11. [A4.26] The tree of Fig. 14 depicts addition chains ac, al, . . . , a, having l(u%) = i for all i in the chain. Find all addition chains for n that have this property, when n = 43 and when n = 77. Show that any tree such as Fig. 14 must include either the path 1, 2, 4, 8, 9, 1 7, 34, 43, 77 or the path 1, 2, 4, 8, 9, 17, 34, 68, 77. 12. [MM] Is it possible to extend the tree shown in Fig. 14 to an infinite tree that yields a minimum-multiplication rule for computing z?, for all positive integers n? 13. [MZ1] Find a star chain of length A + 2 for each of the four cases listed in Theorem C. (Consequently Theorem C holds also with 1 replaced by 1*.) 14. [M35] Complete the proof of Theorem C, by demonstrating that (a) step r -1 is not a small step; and (b) X(o,-k) cannot be less than m -1. 15. [M42] Write a computer program to extend Theorem C, characterizing all n such that 1(n) = 1(n) + 3 and characterizing all n such that l*(n) = x(n) + 3.

462 ARITHMETIC 4.6.3 sink exchange roles, and we obtain another directed graph corresponding to a set of addition chains for the same n; these addition chains have the same length (53) as the chain we started with. For example, if we make the arrows in (52) run from right to left, and if we relabel the vertices according to the number of paths from the right-hand vertex, we get (54) One of the star chains corresponding to this reduced directed graph is 1, 2, 4, 6, 12, 24, 26, 52, 78, 79; we may call this a dual of the original addition chain. Exercises 39 and 40 discuss important consequences of this graphical repre- sentation and the duality principle. EXERCISES 1. [IS] What is the value of 2 when Algorithm A terminates? 2. [%$I Write a MIX program for Algorithm A, to calculate xn mod w given integers n and x, where w is the word size. Assume that MIX has the binary operations SRB, JAE, etc., that are described in Section 4.5.2. Write another program that computes xn mod w in a serial manner (multiplying repeatedly by x), and compare the running times of these programs. b 3. [22] How is xg75 calculated by (a) the binary method? (b) the ternary method? (c) the quaternary method? (d) the factor method? 4. [M.%I] Find a number n for which the octal (23-ary) method gives ten fewer multiplications than the binary method. b 5. [24] Figure 13 shows the first eight levels of the power tree. The (Ic + 1)-st level of this tree is defined as follows, assuming that the first k levels have been constructed: Take each node n of the lath level, from left to right in turn, and attach below it the nodes n + 1, n + al, n + us, . . . , 72 + uk-1 = 2n (in this order), where 1, al, uz, . . . , ok-1 is the path from the root of the tree to n; but discard any node that duplicates a number that has already appeared in the tree. Design an efficient algorithm that constructs the first r + 1 levels of the power tree. [Hint: Make use of two sets of variables LINKU[j], LINKR[j] for 0 5 j 5 2 ; these point upwards and to the right, respectively, if j is a number in the tree.]

4.6.3 EVALUATION OF POWERS 461 If oi = oj + a,+ for more than one pair of indices (j, k), we choose a definite j and k for purposes of this construction. In general, all but the first vertex of such a directed graph will be at the head of exactly two arcs; however, this is not really an important property of the graph, because it conceals the fact that many different addition chains can be essentially equivalent. If a vertex has out-degree 1 (i.e., only one arc leading away), it is used in only one later step, hence the later step is essentially a sum of three inputs aj + ak + a, that might be computed either as (aj + ak) + a, or as aj + (ah + a,) or as ak + (ai + a,). These three choices are immaterial, but the addition-chain conventions force us to distinguish between them. We can avoid such redundancy by deleting any vertex whose out-degree is 1 and attaching the arcs from its predecessors to its successor. For example, the above graph would become (52) We can also delete any vertex whose out-degree is 0, except of course the final vertex a,., since such a vertex corresponds to a useless step in the addition chain. In this way every addition chain leads to a reduced directed graph that contains one source vertex (labeled 1) and one sink vertex (labeled n); every vertex but the source has in-degree 2 2 and every vertex but the sink has out-degree 2 2. Conversely, any such directed graph without oriented cycles corresponds to at least one addition chain, since we can topologically sort the vertices and write down d - 1 addition steps for each vertex of in-degree d > 0. The length of the addition chain, exclusive of useless steps, can be reconstructed by looking at the reduced graph; it is (number of arcs) - (number of vertices) + 1, (53) since deletion of a vertex of out-degree 1 also deletes one arc. We say that two addition chains are equivalent if they have the same reduced directed graph. For example, the addition chain 1, 2, 3, 6, 12, 15, 24, 39, 40, 79 is equivalent to the chain we began with, since it also leads to (52). This example shows that a non-star chain can be equivalent to a star chain. An addition chain is equivalent to a star chain if and only if its reduced directed graph can be topologically sorted in only one way. An important property of this graph representation has been pointed out by N. Pippenger: The label of each vertex is exactly equal to the number of oriented paths from the source to that vertex. Thus, the problem of finding an optimal addition chain for 72 is equivalent to minimizing the quantity (53) over all directed graphs that have one source vertex and one sink vertex and exactly n oriented paths from the source to the sink. This characterization has a surprising corollary, because of the symmetry of the directed graph. If we reverse the direction of all the arcs, the source and the

460 ARITHMETIC 4.6.3 As an example of an lo-chain (certainly not a minimum one), consider 1 2 4 5,&10,12,l8; -, -, -, (51) it is easy to verify that the difference between each element and the previous underlined element is in the chain. We let lo(n) denote the minimum length of an IO-chain for n. Clearly l(n) 5 1 (n) 5 l*(n). The chain constructed in Theorem F is an lo-chain (see exercise 22); hence we have lo(n) < 1*( n ) f or certain n. It is not known whether or not l(n) = 1 (n) in all cases; if this equation were true, the Scholz-Brauer conjecture would be settled, because of another theorem due to Hansen: Theorem G. 1 (2 -1) 2 n -1 + I (n). Proof. Let 1 = ao, al, . . , a, = n be an lo-chain of minimum length for n, andlet 1 =bo, bi, . . . . bt = n be the subsequence of underlined elements. (We may assume that n is underlined.) Then we can get an lo-chain for 2n -1 as follows: a) Include the 1 (n) + 1 numbers 2at - 1, for 0 2 i 5 T, underlined if and only if a, is underlined. b) Include the numbers 2i(2b J--l),forO -,6 -912 –f15 30 60 120 240 255 510 1020 1023 f-1 2 3 -, 31 ,-,~,~,~,~7~, 2040 ~,4095,8160,16320,32640,65280,130560,261120,262143. Graphical representation. An addition chain (1) corresponds in a natural way to a directed graph, where the vertices are labeled ai for 0 5 i 5 T, and where we draw arcs from a3 to a, and from ak to a, as a representation of each step a, = a? + ak in (2). For example, the addition chain 1, 2, 3, 6, 12, 15, 27, 39, 78, 79 that appears in Fig. 14 corresponds to the directed graph

4.6.3 EVALUATION OF POWERS 459 Table 1 VALUES OF n FOR SPECIAL ADDITION CHAINS 23 163 229 319 371 413 453 553 599 645 707 741 813 849 903 43 165 233 323 373 419 455 557 611 659 709 749 825 863 905 59 179 281 347 377 421 457 561 619 667 711 759 835 869 923 77 203 283 349 381 423 479 569 623 669 713 779 837 887 941 83 211 293 355 382 429 503 571 631 677 715 787 839 893 947 107 213 311 359 395 437 509 573 637 683 717 803 841 899 955 149 227 317 367 403 451 551 581 643 691 739 809 845 901 983 Let d(r) be the number of solutions n to the equation l(n) = T. The following table lists the first few values of this function: 1 1 6 15 11 246 2 2 7 26 12 432 3 3 8 44 13 772 4 5 9 78 14 1382 5 9 10 136 15 2481 Surely d(r) must be an increasing function of r, but there is no evident way to prove this seemingly simple assertion, much less to determine the asymptotic growth of d(r) for large r. The most famous problem about addition chains that is still outstanding is the Schola-Brauer conjecture, which states that l(2 -1) 2 n -1+ l(n). (49) Computer calculations show, in fact, that equality holds in (49) for 1 < n < 14; and hand calculations by E. G. Thurber [Discrete Math. 16 (1976), 279-2891 have shown that equality holds also for n = 15, 16, 17, 18, 20, 24, 32. Much of the research on addition chains has been devoted to attempts to prove (49); addition chains for the number 2n -1, which has so many ones in its binary representation, are of special interest, since this is the worst case for the binary method. Arnold Scholz coined the name addition chain (in German) and posed (49) as a problem in 1937 [Jahresbericht der deutschen Mathematiker- Vereinigung, class II, 47 (1937), 41-421; Alfred Brauer proved in 1939 that 1*(2n -1) 5 n -1 + l*(n). (50) Hansen s theorems show that l(n) can be less than l*(n), so more work is definitely necessary in order to prove or disprove (49). As a step in this direction, Hansen has defined the concept of an lo-chain, which lies between l-chains and l*-chains. In an lo-chain, certain of the elements are underlined; the condition is that ai = a? + uk, where a3 is the largest underlined element less t,han a,.

458 ARITHMETIC 4.6.3 Some conjectures. Although it was reasonable to guess at first glance that I(n) = l*(n), we have now seen that this is false. Another plausible conjecture [first made by A. Goulard, and supposedly proved by E. de JonquiBres in l lnterm. des Math. 2 (1895), 125-1261 is that 1(2n) = I(n) + 1; a doubling step is so efficient, it seems unlikely that there could be any shorter chain for 2n than to add a doubling step to the shortest chain for n. But computer calculations show that this conjecture also fails, since 1(191) = 1(382) = 11. (A star chain of length 11 for 382 is not hard to find; e.g., 1, 2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 382. The number 191 is minimal such that I(n) = 11, and it seems to be very difficult to prove by hand that 1(191) > 10; the computer s proof of this fact, using a backtrack method that will be sketched in Section 7.2.2, involved a detailed examination of 948 cases.) The smallest four values of n such that l(2n) = l(n) are n = 191, 701, 743, 1111; E. G. Thurber proved in Pacific J. Math. 49 (1973), 229-242, that the third of these is a member of an infinite family of such n, namely 23 . 2k + 7 for all k 2 5. It seems reasonable to conjecture that l(2n) 2 I(n), but even this may be false. Kevin R. Hebb has shown that l(n) -I(mn) can get arbitrarily large, for all fixed integers m not a power of 2 [Notices Amer. Math. Sot. 21 (1974), A-2941. The smallest case in which l(mn) < l(n) is 1((213 + 1)/3) = 15. Let C(T) be the smallest value of n such that l(n) = r. It seems to be most difficult to compute l(n) for these values of n. We have the following table: r c(r) r c(r) r c(r) 1 2 7 29 13 607 2 3 8 47 14 1087 3 5 9 71 15 1903 4 7 10 127 16 3583 5 11 11 191 17 6271 6 19 12 379 18 11231 For r 5 11, the value of c(r) is approximately equal to c(r -1) + c(r -2), and this fact led to speculation by several people that c(r) grows like the function @ ; but the result of Theorem D (with n = c(r)) implies that r/lgc(r) + 1 as n + co. [See E. G. Thurber, Duke Math. J. 40 (1973), 907-913, for more detailed information about the growth of c(r).] Several people had conjectured at one time that c(r) would always be a prime number; but ~(15) = 11.173 and ~(18) = 11 . 1021. Perhaps no conjecture about addition chains is safe! Tabulated values of l(n) show that this function is surprisingly smooth; for example, l(n) = 13 for all n in the range 1125 5 n 5 1148. The computer calculations show that a table of I(n) may be prepared for all n < 1000 by using the formula l(n) = min(l(n -1) + 1,1) -6, (48) where 1 = 0;) if n is prime, otherwise 1 = l(p) + l(n/p) if p is the smallest prime dividing n; and S = 1 for n in Table 1, S = 0 otherwise.

4.6.3 EVALUATION OF POWERS 457 Going back to our element x3 in MQ, we have x1 E Mu,; and we have proved that Y = 0. Therefore, by equation (40) again, eo -f d, -d 2 xj > eo + d, -d. (46) For all j = 1, 2, . . . , t we have determined a number x3 satisfying (46), and a small step i at which the term 2e 3 may be said to have entered into the addition chain. If j # j , the step i at which this occurs cannot be the same for both j and j ; for (46) would tell us that Ixj -xjll < m, while elements of M%, and Mi,, must differ by more than m, since e3 and ejj are so far apart. We are forced to conclude that the chain contains at least t small steps; but this is a contradiction. 1 Theorem F (W. Hansen). GA + XY) I A + 4x)+ 4~) -1, if X(x) + X(y) < A. (47) Proof. An addition chain (which is not a star chain in general) may be con- structed by combining the binary and factor methods. Let x = 251 +. . . + 2Xu and y = 2Y1 + ... + 2YV, where x1 > . . > x, 2 0 and y1 > . . . > yV 2 0. The first steps of the chain form successive powers of 2, until 2A-Yl is reached; in between these steps, the additional values 2sU-1 + 2xU, 25u-2 + 2x,-1 + 2xu, . . . , and x are inserted in the appropriate places. After a chain up to ~A-Y% + x(2Y~ –Y% + . . .+ 2Ya-l–YX) has been formed, we continue by adding x and doubling the resulting sum yi -yi+l times; this yields 2A–y,+l + x(2Y1–yt+1 + . . . + 2Yz–Yz+1). If this construction is done for i = 1, 2, . . . , V, assuming for convenience that yU+l = 0, we have an addition chain for 2A + xy as desired. 1 Theorem F enables us to find values of n for which l(n) < l*(n), since Theorem H gives an explicit value of l*(n) in certain cases. For example, let x = 21 16 + 1, y = 22032 + 1, and let n = 26103 + xy = 26103 + 23048 + 22032 + 2lOlS + 1. According to Theorem F, we have l(n) 5 6106. But Theorem H also applies, with m = 508, and this proves that l*(n) = 6107. Extensive computer calculations have shown that n = 12509 is the smallest value with l(n) < l*(n). No star chain for this value of n is as short as the sequence 1, 2, 4, 8, 16, 1 7, 32, 64, 128, 256, 512, 1024, 1041, 2082, 4164, 8328, 8345, 12509. The brute-force methods in the proof of Theorem C could be extended by computer program to determine all n such that l(n) = x(n) + 3; this approach would also characterize all n with v(n) = 5 and l(n) # l*(n). (The smallest such n is 16537 = 214 + 9.17.)

456 ARITHMETIC 4.6.3 and the multisets Mij and S,, reflect the structure of this chain, as defined above. By the corollary to Theorem A, we know that f < [3.27l(t -1)J; therefore the value of m is a bona fide upper bound for the number rnj of elements in each multiset Mj. In the summation no carries propagate from the term corresponding to Mij to the term correspond- ing to Mi(j-11, if we think of this sum as being carried out in the binary number system, since the e s are so far apart. (Cf. (40).) In particular, the sum of all the terms for j # 0 will not carry up to affect the terms for j = 0, so we must have ai 2 C 25 2 2x(at), 0 2 i 5 r. (44 In order to prove Theorem H, we would like to show that in some sense the t extra powers of n must be put in one at a time, so we want to find a way to tell at which step each of these terms essentially enters the addition chain. Let j be a number between 1 and t. Since Moj is empty and M,.j = Mj is nonempty, we can find the first step i for which Mi3 is not empty. From the way in which the Mi3 are defined, we know that step i is a non- doubling: ai = ai-+ aU for some u < i -1. We also know that all the elements of Mij are elements of S,. We will prove that a, must be relatively small compared to ai. Let x7 be an element of Jlij. Then since x3 E S,, there is some w for which xj E Mu,. It follows that d, -d, > m, (45) i.e., at least m + 1 doublings occur between steps u and i. For if di -d, < m, Lemma K tells us that lej -e,l < 2m; hence u = j. But this is impossible, because M,j is empty by our choice of step i. All elements of S, are less than or equal to el + d, -d. For if z E S, c S, and x > el + di -d, then x E Mu0 and x E Mto by (40); so Lemma K implies that Idi -d,[ < m, contradicting (45). In fact, this argument proves that MAO has no elements in common with S,, so M(2-l)o = Mio. From (44) we have ai-2 2X(aa), and therefore step i is a small step. We can now deduce what is probably the key fact in this entire proof: All elements of S, are in Muo. For if not, let x be an element of S, with z @ Muo. Since x 2 0, (40) implies that el 2 d - d,, hence eo = f + d - s 5 2.271s + d 2 2.271(t -1) + el + d,. By hypothesis (43), this implies d, > el. But d, E S, by (41), and it cannot be in MZO, hence d, 5 el + di -d < el, a contradiction.