4.6.3 EVALUATION OF POWERS 451 E. C,. Thurber (Web design portfolio)
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.