4.6.3 EVALUATION OF POWERS 457 Going back to (Web design online)
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.)