Post office web site - 452 ARITHMETIC 4.6.3 Lemma P. Let b
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)