MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.6.3 EVALUATION OF POWERS 455 From this definition it follows that ej+di–d 2 x > ej+di-d-mmj, for all X E Mij. (40) As an example of this detailed construction, let us consider the star chain 1, 2, 3, 5, 10, 20, 23, for which t = 3, r = 6, d = 3, f = 3. We obtain the following array of multisets: (do,dl,…,dG): 0 1 1 1 1 1 j 2 1 3 3 (ao,al,…,a6): 1 2 20 23 (MO3, Ml3,. . . , M63): M3 e3 = 0, m3 = 1 (Mo2, Ml2,. . . , Ms2): 111: Ad2 e2 = 1, m2 = 1 (MOl,Mll,…,MSl): ., / 0 2 2 MI el = 2, ml = 1 (Moo, MIO,. . .,MGo): 3 3 MO eo = 4, mo = 2 3 3 I SO sl 82 s3 s4 SE, 496 Thus M40 = {2,2}, etc. From the construction we can see that di is the largest element of St; hence 4 E Mio. (41) The most important part of this structure comes from Eq. (40); one of its immediate consequences is Lemma K. If Mz3 and Mu, both contain a common integer x, then -mu < (e3 -e,)-(d,-dd,) < mj. 1 (42) Although Lemma K may not look extremely powerful, it says (when Mij contains an element in common with Mu, and when mj, m, are reasonably small) that the number of doublings between steps u and i is approximately equal to the difference between the exponents k, and ej. This imposes a certain amount of regularity on the addition chain; and it suggests that we might be able to prove a result analogous to Theorem B above, that I*(n) = eo + t, provided that the ej are far enough apart. The next theorem shows how this can be done. Theorem H (W. Hansen, J. fiir die reine und angew. Math. 202 (1959), 129-136). Let n = 2e0 + 2e + ... + 2et, eo > el > .+. > et 2 0. If eo > 2el + 2.271(t -1) and ei-1 2 ei + 2m for 1 5 i 2 t, (43) where m = 2L3.271(t-1)l -t, then l*(n) = eo + t. Proof. We may assume that t > 2, since the result of the theorem is true without restriction on the e s when t 5 2. Suppose that we have a star chain 1 = a0 < a1 < … < a, = n for n with r < eo + t -1. Let the integers d, f, do, . . . , d,,

454 ARITHMETIC 4.6.3 where d, is the number of doublings among steps 1, 2, . . . , i. We also define a sequence of multisets So, &, . . . , S,, which keep track of the powers of 2 present in the chain. (A multiset is a mathematical entity that is like a set, but it is allowed to contain repeated elements; an object may be an element of a multiset several times, and its multiplicity of occurrences is relevant. See exercise 19 for familiar examples of multisets.) The multisets S, are defined by the rules a) SO = (0); b) If ai+l = 2az, then &+i = 5 i + 1 = {z + 1 1 z E Si }; C) If ai+l = oi + ok, /C < i, then Si+r = S, &J Sk. (The symbol H means that the multisets are combined, adding the multi- plicities.) From this definition it follows that Ui = c 2=, (36) XES, where the terms in this sum are not necessarily distinct. In particular, n = y0 + y + . . . + 2Q = c 2x. (37) XES, The number of elements in the latter sum is at most 2f, where f = r -d is the number of nondoublings. Since n has two different binary representations in (37), we can partition the multiset S,. into multisets MO, Ml, . . . , Mt such that 2Q = c 2=, o ej -mj, for all x E Mj. (39) Our examination of the star chain s structure is completed by forming the multisets MQ that record the ancestral history of My. The multiset Si is partitioned into t + 1 multisets as follows: a) MTj = Mj; b) If oi+i = 2oi, then Mij = M(i+l)j -1 = { 2 -1 1 X E M(~+I)~ }; C) If ~i+i = Ui + ok, k < i, then (Since Si+i = Si u Sk) we let Mtj = M(i+ljJ minus Sk, that is, we remove the elements of Sk from M(i+l)j. If some element of Sk appears in two or more different IdthtS M(i+l)j, we remove it from the set with the largest possible value of j; this rule uniquely defines Mij for each j, when i is fixed.

4.6.3 EVALUATION OF POWERS 453 Finally, once the j and k have been selected for each of the non- ministeps, there are fewer than r2 (33) 0 t ways to choose the j and the k for the ministeps: We select t distinct pairs (jl, kl), . . . , (jt, kt) of indices in the range 0 < kh < j, < r, in fewer than (33) ways. Then for each ministep i, in turn, we use a pair of indices (jh, kh) such that a) jh < i; b) aj, f ok,, is as small as possible among the pairs not already used for smaller ministeps i; c) ai = a$, + ak,, satisfies the definition of ministep. If no such pair (jh, kh) exists, we get no addition chain; on the other hand, any addition chain with ministeps in the designated places must be selected in one of these ways, so (33) is an upper bound on the possibilities. Thus the total number of possible addition chains satisfying (26) is bounded by (31) times (32) times (33), summed over all relevant s, t, U, and U. The proof of Theorem E can now be completed by means of a rather standard estimation of these functions (exercise 18). 1 Corollary. The value of l(n) is asymptotically A(n) + A(n)l for almost all 72. More precisely, there is a function f(n) such that f(n) --+ 0 as n --+ oo, and Pr( (l(n) -A(n) -A(n)/U(n)( 2 f(n)A(n)/AA(n)) = 0. (34) (See Section 3.5 for the definition of this probability Pr .) Proof. The upper bound (25) shows that (34) holds without the absolute value signs. The lower bound comes from Theorem E, if we let f(n) decrease to zero slowly enough so that, when f(n) 2 E, the value N is so large that at most EN values n 5 N have l(n) 5 A(n) + (1 -e)A(n)/AA(n). 1 Star chains. Optimistic people find it reasonable to suppose that I(n) = l*(n); given an addition chain of minimal length l(n), it appears hard to believe that we cannot find one of the same length that satisfies the (apparently mild) star condition. But in 1958 Walter Hansen proved the remarkable theorem that, for certain large values of n, the value of I(n) is definitely less than l*(n), and he also proved several related theorems that we shall now investigate. Hansen s theorems begin with an investigation of the detailed structure of a star chain. This structure is given in terms of other sequences and sets constructed from the given chain. Let n = 2e0 + 2e1 + . . . + 2et, eo > el > . .. > et 2 0, and let 1 = a0 < al < … < a, = n be a star chain for n. If there are d doublings in this chain, we define the auxiliary sequence (35)

452 ARITHMETIC 4.6.3 Lemma P. Let b < & -1 be a fixed positive real number. Call step i of an addition chain a ministep if it is not a doubling and if a, < a?(1 + ~5)~--1 for some j, where 0 < j < i. If the addition chain contains s small steps and t ministeps, then t F s/(1 -Q where (1 + 6)2 = 2e. (27) Proof. For each ministep ik, 1 5 k 5 t, we have aik < ~(1 +S)ik-jk for some jk < ik. Let 11, . . . . It be the intervals (j,, iI], . . . , (j,, it], where the notation (j,i] stands for th e set of all integers k such that j < k 5 i. It is possible (see exercise 17) to find nonoverlapping intervals J1, . . . , Jh = (j:, i], . . . , (jk, ii ] such that I, u . . . u4 = 51 U...UJh, a,; < q(l + q2(G-j2, for 1 5 k 5 h. (28) Now for all steps i outside of the intervals 51, . . , Jh we have ui 5 2ui-1; hence if we let we have 2X@) 5 n 5 2r-9(1 + 6) a -- 2x(n)+s-(l--ekl < p(n)+s-(l-w. , Returning to the proof of Theorem E, let us choose S = 2 14 -1, and let us divide the r steps of each addition chain into three classes: t ministeps, u doublings, w other steps, t+u+v=r. (29) Counting another way, we have s small steps, where s + m = r. By the hypoth- eses, Theorem A, and Lemma P, we obtain the relations t I s/(1 -+% t + v < 3.271s, s 2 (1 -e)m/x(m). (30) Given s, t, u, v satisfying these conditions, there are at most (31) ways to assign the steps to the specified classes. Given such a distribution of the steps, let us consider how the non-ministeps can be selected: If step i is one of the other steps in (29), ai > (1 + @u,-~, so ui = u3 + uk, where bat-l 5 ak 5 uj 2 azpl. Also a3 5 uZ/(l + S)%-j 5 2azp1/(1 +6)2–j, so S < 2/(1 + S)i-i. This gives at most p choices for j, where /3 is a constant that depends only on 6. There are also at most /3 choices for k, so the number of ways to assign j and k for each of the non-ministeps is at most 2v P . (32)

4.6.3 EVALUATION OF POWERS 451 E. C,. Thurber [Pacific J. Math. 49 (1973), 229-2421 has extended Theorem C to show that I(n) > x(n) + 4 when v(n) > 8. It seems reasonable to conjecture that l(n) > x(n) + lg v(n) in general, since A. Schijnhage has come very close to proving this (see exercise 29). Asymptotic values. Theorem C indicates that it is probably quite difficult to get exact values of l(n) for large n, when v(n) > 4; however, we can determine the approximate behavior in the limit as n -+ 00. Theorem D (A. Brauer, Bull. Amer. Math. Sot. 45 (1939), 736-739). lim l*(n)/x(n) = lim l(n)/x(n) = 1. (23) Tl-CC 7X-00 Proof. The addition chain (4) for the 2k-ary method is a star chain if we delete the second occurrence of any element that appears twice in the chain; for if a, is the first element among 2do, 4do, . . . of the second line that is not present in the first line, we have ai 5 2(m -1); hence ai = (m -1) + a3 for some a3 in the first line. By totaling up the length of the chain, we have A(n) 5 l(n) 5 l*(n) < 1 + ; lgn + 2k ( > for all k 2 1. The theorem follows if we choose, say, k = [f lgX(n)J. I If we let k = U(n) -2XXX(n) in (24) for large n, where U(n) denotes x(x(n)), we obtain the stronger asymptotic bound l(n) 5 l (n) < A(n) + X(?z)/XX(?z) + o(x(n)xxx(?z)/xx(n)2). (25) The second term Y(n)/U( n ) is essentially the best that can be obtained from (24). A much deeper analysis of lower bounds can be carried out, to show that this term X(n)/XX( 72 is, in ) . fact, essential in (25). In order to see why this is so, let us consider the following fact: Theorem E (Paul Erdiis, Acta Arithmetica 6 (1960), 77-81). Let t be a positive real number. The number of addition chains (11) such that A(n) = m, r 5 m + (1 -t)m/x(m) (26) is less than aim, for some CY < 2, for all suitably large m. (In other words, the number of addition chains so short that (26) is satisfied is substantially less than the number of values of n such that x(n) = m, when m is large.) Proof. We want to estimate the number of possible addition chains, and for this purpose our first goal is to get an improvement of Theorem A that enables us to deal more satisfactorily with nondoublings.

450 ARITHMETIC 4.6.3 cases listed in the theorem. We can obtain addition chains of the required form for each special n, as shown in exercise 13; therefore it remains for us to prove that no chain with exactly two small steps contains any elements with V(Q) 2 4 except when a, is special. Let a counterexample chain be an addition chain with two small steps such that V(a,) 2 4, but a, is not special. If counterexample chains exist, let 1 = a0 < al < ... < a7 = n be a counterexample chain of shortest possible length. Then step T is not a small step, since none of the six types in the proof of Theorem B can be followed by a small step with v(n) > 4 except when n is special. Furthermore, step r is not a doubling, otherwise ao, . . . , a7-l would be a shorter counterexample chain; and step T is a star step, otherwise ao, . . . , arP2, a, would be a shorter counterexample chain. Thus ar = a7-1 + (h–k, k 2 2; and x(a,) = x(a,-,) + 1. (21) Let c be the number of carries that occur when aTPl is added to ar-k in the binary number system by Algorithm 4.3.1A. Using the fundamental relation V(&) = v(a,-l) + v(hk) -c, (22) we can prove that step r -1 is not a small step (see exercise 14). Let m = x(a,-1). Since neither r nor r -1 is a small step, c 2 2; and c = 2 can hold only when a,-l 2 2m + 2m-1. Now let us suppose that T - 1 is not a star step. Then r -2 is a small step, and ao, . . . , ar-s, a,-1 is a chain with only one small step; hence v(a,-l) 2 2 and v(a,-2) 5 4. The relation (22) can now hold only if V(a,) = 4, v(a,-1) = 2, k = 2, c = 2, v(a,-2) = 4. From c = 2 we conclude that aTAl = 2m + 2m-1; hence ao, al, . . . , arP3 = 2m-1 + 2m-2 is an addition chain with only one small step, and it must be of Type 1, so a, belongs to Case 3. Thus r -1 is a star step. Now assume that aTPl = 2ta,-k for some t. If v(a,-l) 5 3, then by (22), c = 2, k = 2, and we see that a, must belong to Case 3. On the other hand, if v(a,-1) = 4 then aTYl is special, and it is easy to see by considering each case that a, also belongs to one of the four cases. (Case 4 arises, for example, when a,-1 = 90, ar-k = 45; or aTAl = 120, ar-k = 15.) Therefore we may conclude that a,-l # 2ta,-k for any t. We have proved that aTPl = arP2 + arYq for some q > 2. If k = 2, then q > 2, and ao, al, . . . , ar–2, 2a,-2, 2a7-2 + arPq = a, is a counterexample sequence in which k > 2; therefore we may assume that k > 2. Let us now suppose that x(&-k) = m -1; the case X(&-k) < m -1 may be ruled out by similar arguments, as shown in exercise 14. If k = 4, both T - 2 and T - 3 are small steps; hence aTF4 = 2m-1, and (22) is impossible. Therefore k = 3; step T - 2 is small, v(a,-3) = 2, c = 2, a,-l 2 2m + 2m-1, and v(a,-1) = 4. There must be at least two carries when a+2 is added to a7-l -arms; hence v(a,-2) = 4, and ar-z (being special and 2 farPI) has the form 2m-1 + 2m-2 + 2d+1 + 2d for some d. Now arPl is either 2m + 2m+1 + 2d+ + 2d or 2m + 2m- + 2d+2 + Zd+ , and in both cases arP3 must be 2m-1 + 2m-2, so a7 belongs to Case 3. I

4.6.3 EVALUATION OF POWERS 449 Theorem B. 1(2A+2B+2C)=A+2, ifA > B > C. (20) Proof. We can, in fact, prove a stronger result that will be of use to us later in this section: A/l addition chains with exactly one small step have one of the following six types (where all steps indicated by . . . represent doublings): Type 1. 1, . . . , 2A, 2A + 2B, . . . , 2A+C+2B+C;A>B>0,C>0. Type 2. 1, . . . , 2A, 2A + 2B, ZA+l + 2B, . . . , 2A+C+1 + ZB-tC; A > B 2 0, c 2 0. Type 3. 1, . . . , 2A, 2A + 2A-1, ZAfl + 2A-1, 2A+2, . . . . 2A+c; A > 0, c 2 2. Type 4. 1, . . . , 2A, 2A +2A-1, 2A+1 +2A, 2A+2, . . . , 2A+C; A > 0, C 2 2. Type 5. 1, . . . , 2A, 2A + 2A-1, . . . , ZAfC + 2A+C-1, 2A+C+1 + 2A+C-2, , 2A+C+D+1 + 2A+C+D–2; A > 0, C > 0, D 2 0. Type 6. 1, . . . , 2A, 2A + 2B, 2A+l, ) _ , C>l . . . , 2A+C.A>B>0 _ . A straightforward hand calculation shows that these six types exhaust all possibilities. (Note that, by the corollary to Theorem A, there are at most three nondoublings when there is one small step; this maximum of three is attained only in sequences of Type 3. All of the above are star chains, except Type 6 whenB 2. 1 (E. de Jonquieres stated without proof in 1894 that I(n) 2 x(n) + 2 when u(n) > 2. The first published demonstration of Theorem B was by A. A. Gioia, M. V. Subbarao, and M. Sugunamma in Duke Math. J. 29 (1962), 481-487.) The calculation of 1(2A + 2B + 2c + aD), when A > B > C > D, is more involved; by the binary method it is at most A + 3, and by the proof of Theorem B it is at least A + 2. The value A + 2 is possible, since we know that the binary method is not optimal when n = 15 or n = 23. The complete behavior when u(n) = 4 can be determined, as we shall now see. Theorem C. If v(n) 2 4 then l(n) 2 x(n) + 3, except in the following cir- cumstances when A > B > C > D and 1(2A + 2B + 2c + 2 ) equals A + 2: Case 1. A-B = C -D. (Example: n = 15.) Case 2. A -B = C -D + 1. (Example: n = 23.) Case 3. A-B = 3, C -D = 1. (Example: n = 39.) Case 4. A-B = 5, B -C = C -D = 1. (Example: n = 135.) Proof. When l(n) = x(n) + 2, there is an addition chain for n having just two small steps; such an addition chain starts out as one of the six types in the proof of Theorem B, followed by a small step, followed by a sequence of nonsmall steps. Let us say that n is special if n = 2A + 2B + 2c + 2O for one of the four

448 ARITHMETIC 4.6.3 Theorem A. If the addition chain (11) includes d doublings and f = r -d nondoublings, then n 2 2*- Ff+s. (14) Proof. By induction on r = d + f, we see that (14) is certainly true when r = 1. When r > 1, there are three cases: If step r is a doubling, then $n = a,-1 5 2d-2F f+s; hence (14) follows. If steps r and T -1 are both nondoublings, then a,-1 5 2*-lFf+2 and arP2 5 2d-1Ff+l; hence n = a,. 2 a,.-1 + a7-s 2 2*- (Ff-t2 + Fffl) = 2d-1Ff+3 by the definition of the Fibonacci sequence. Finally, if step r is a nondoubling but step r -1 is a doubling, then arP2 2 2*- Ff+z and n = a,. 5 a,_l + a7-2 = 3a7-2. Now 2Ff+s -3Ff+2 = Fftl -Ff 2 0; hence n 5 2d-1Ff+3 in all cases. 1 The method of proof we have used shows that inequality (14) is best possible under the stated assumptions; the addition chain 1,2,. . . ,2*–1, 2*–lF3, 2*-lF 4,*.., 2*–lFf+s (15) has d doublings and f nondoublings. Corollary. If the addition chain (11) includes f nondoublings and s small steps, then s 5 f 2 3.271s. (16) Proof. Obviously s 6 f. We have ZXcn) 2 n 5 2d-1Ff+3 5 2*4f = 2X(n)+s(+/2)f, since d + f = A(n) + s, and since Ff+s < 24f when f > 0. Hence 0 5 s In 2 + f ln(#/2), and (16) follows from the fact that In 2/ ln(2/@) M 3.2706. 1 Values of l(n) for special 12. It is easy to show by induction that ai 5 2i, and therefore lgn 5 r in any addition chain (11). Hence l(n) 2 knl. (17) This lower bound, together with the upper bound (10) given by the binary method, gives us the values 1(2A) = A; (18) 1(2A+2B)=A+1, ifA> B. (19) In other words, the binary method is optimum when u(n) 2 2. With some further calculation we can extend these formulas to the case v(n) = 3:

4.6.3 EVALUATION OF POWERS 447 In terms of these functions, the binary addition chain for n requires exactly x(n) + u(n) -1 steps, and (5) becomes l(n) 5 x(n) + v(n) -1. (10) Special classes of chains. We may assume without any loss of generality that an addition chain is ascending, 1 = %I < Ul < a2 < .. < a, = n. (11) For if any two a s are equal, one of them may be dropped; and we can also rearrange the sequence (1) into ascending order and remove terms > n without destroying the addition chain property (2). from now on we shall consider only ascending chains, without explicitly mentioning this assumption. It is convenient at this point to define a few special terms relating to addition chains. By definition we have, for 1 5 i 2 T, Ui = aj + ak (14 for some j and k, 0 < k 2 j < i. Let us say that step i of (11) is a doubling, if j=k=i-1; then ai has the maximum possible value 2ai-1 that can follow the ascending chain 1, al, . . . , CJ-~. If j (but not necessarily k) equals i -1, let us say that step i is a star step. The importance of star steps is explained below. Finally let us say that step i is a small step if x(ai) = X(ai.-1). Since ai-< ai 5 2ai-1, the quantity x(ai) is always equal to either X(ai-1) or X(ai-1) + 1; it follows that, in any chain (ll), the length r is equal to A(n) plus the number of small steps. Several elementary relations hold between these types of steps: Step 1 is always a doubling. A doubling obviously is a star step, but never a small step. A doubling must be followed by a star step. Furthermore if step i is not a small step, then step i + 1 is either a small step or a star step, or both; putting this another way, if step i + 1 is neither small nor star, step i must be small. A star chain is an addition chain that involves only star steps. This means that each term ai is the sum of ai- and a previous ak; the simple computer discussed above after Eq. (2) makes use only of the two operations STA and ADD (not LDA) in a star chain, since each new term of the sequence utilizes the pre- ceding result in the accumulator. Most of the addition chains we have discussed so far are star chains. The minimum length of a star chain for n is denoted by l*(n); clearly l(n) 5 l*(n). (13) We are now ready to derive some nontrivial facts about addition chains. First we can show that there must be fairly many doublings if r is not far from x(n).

446 ARITHMETIC 4.6.3 Yhl, / A I A I 1Li A 7 A r I i F: r 21 22 23 40 I I I I I I / I A P A A Pe I I 38 29 56 31 42 44 46 41 80 39 54 45 60 50 51 96 35 52 43 68 37 72 49 66 65 I I I I I I / I I I I I I I I I I I / 76 58 57 59 62 84 88 47 92 82 83 85 78 55 90 63 75 100 53 97 99 70 61 77 86 69 74 73 98 67 81 I I I II I I I 89 94 93 95 79 91 71 87 Fig. 14. A tree that minimizes the number of multiplications, for n 5 100. The length of this chain is m -2 + (k + 1)t; and it can often be reduced by de- leting certain elements of the first row that do not occur among the coefficients dj, plus elements among 2do, 4do, . . . that already appear in the first row. Whenever digit dJ is zero, the step at the right end of the corresponding line may, of course, be dropped. Furthermore, as E. C. Thurber has observed [Duke Math. J. 40 (1973), 907-9131, we can omit all the even numbers (except 2) in the first row, if we bring values of the form dj/2e into the computation e steps earlier. The simplest case of the m-ary method is the binary method (m = 2), when the general scheme (4) simplifies to the S and x rule mentioned at the beginning of this section: The binary addition chain for 2n is the binary chain for n followed by 2n; for 2n + 1 it is the binary chain for 2n followed by 2n + 1. From the binary method we conclude that l(aeo + 2e1 + . . . + 2e ) 5 e. + t, if eo > el > … > et 2 0. (5) Let us now define two auxiliary functions for convenience in our subsequent discussion: W = lk nJ; (6) v(n) = number of l s in the binary representation of n. (7) Thus X(17) = 4, ~(17) = 2; these functions may be defined by the recurrence relations X(1) = 0, X(2n) = X(2n + 1) = A(n) + 1; (8) Y(1) = 1, v(2n) = v(n), v(2n + 1) = v(n) + 1. (9)