Hosting your own web site - 456 ARITHMETIC 4.6.3 and the multisets Mij and
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.