TAOCP 4.6.3 Exercise 28

Section 4.6.3: Evaluation of Powers

Exercise 28. [**] [HM33] (A. Schönhage.) The object of this exercise is to give a fairly short proof that $l(n) \ge \Lambda(n) + \lg \nu(n) - O(\log \log(\nu(n) + 1))$.

a) When $x = (x_1 \ldots x_0 \cdot x_{-1} \ldots)2$ and $y = (y_k \ldots y_0 \cdot y{-1} \ldots)_2$ are real numbers written in binary notation, let us write $x \le y$ if $x_j \le y_j$ for all $j$. Give a simple rule for constructing the smallest number $z$ with the property that $x' \le z$ and $y' \le y$ implies $x' + y' \le z$. Denoting this number by $x \nabla y$, prove that $v(x \nabla y) \le v(x) + v(y)$.

b) Given any addition chain $(1)$ with $r = \lambda(n)$, let the sequence $d_0, d_1, \ldots, d_r$ be defined as in (35), and define the sequence $A_0, A_1, \ldots, A_r$ by the following rules: $A_0 = 1$; if $a_i = 2a_{i-1}$, then $A_i = 2A_{i-1}$; otherwise if $a_i = a_j + a_k$ for some $0 \le k \le j < i$, then $A_i = A_j \cdot \nabla(A_j/2^{d_j - d_k})$. Prove that this sequence "covers" the given chain, in the sense that $a_i \le A_i$ for $0 \le i \le r$.

c) Let $\delta$ be a positive integer (to be selected later). Call the nondoubling step $a_i = a_j + a_k$ a "baby step" if $d_j - d_k \ge \delta$, otherwise call it a "close step." Let $B_0 = 1$; $B_i = 2B_{i-1}$ if $a_i = 2a_{i-1}$; $B_i = B_j \cdot \nabla(B_j/2^{\rho(j) - \delta})$ if $a_i = a_j + a_k$ is a baby step; and $B_i = \rho(2B_{i-1})$ otherwise, where $\rho(j)$ is the least number $y$ such that $j/2^y \le y$ for $0 \le j \le \delta \cdot 2^{\delta}$. Show that $\nu(B_i) \le (1 + 4c_i)2^{\delta}$ for $0 \le i \le r$, where $b_i$ and $c_i$ respectively denote the number of baby steps and close steps $\le i$. [Hint: Show that the $1$s in $B_i$ appear in consecutive blocks of size $\ge 1 + 4c_i$.]

d) We now have $l(n) = r = b_r + c_r + d_r$ and $\nu(n) \le \nu(B_r) \le (1 + 4c_r)2^{\delta}$. Explain how to choose $\delta$ in order to obtain the inequality stated at the beginning of this exercise. [Hint: See (16), and note that $n \le 2^{d_r} a^{b_r}$ for some $a < 1$ depending on $\delta$.]

Verified: yes
Solve time: 1m18s

---

For (a), the smallest $z=x\nabla y$ is obtained by binary addition with carries propagated maximally: at each digit position, $z_j=1$ whenever a $1$ can occur there in some sum $x'+y'$ with $x'\le x$ and $y'\le y$. Equivalently, if $c_j$ denotes the carry into position $j$, then

$$ z_j=\min(1,x_j+y_j+c_j),\qquad c_{j+1}=\Bigl\lfloor\frac{x_j+y_j+c_j}{2}\Bigr\rfloor . $$

Since every $1$ in $z$ arises either from a $1$ already present in $x$ or $y$, or from a carry generated by such digits, the binary blocks of $z$ are obtained by merging blocks from $x$ and $y$; hence

$$ \nu(x\nabla y)\le \nu(x)+\nu(y). $$

For (b), induction on $i$ proves $a_i\le A_i$. The doubling case is immediate. If $a_i=a_j+a_k$, then $a_k\le a_j/2^{,d_j-d_k}$; by the induction hypothesis,

$$ a_i\le A_j+\frac{A_j}{2^{,d_j-d_k}} \le A_j\cdot \nabla!\Bigl(A_j/2^{,d_j-d_k}\Bigr) =A_i. $$

Thus $A_i$ covers the chain. For (c), induction on $i$ shows that the $1$-bits of $B_i$ occur in consecutive blocks, each of length at least $1+4c_i$. A baby step can increase the number of blocks by at most a factor $2^\delta$, while a close step enlarges every block by at least four positions. Therefore

$$ \nu(B_i)\le (1+4c_i)2^\delta . $$

For (d), with $r=l(n)=b_r+c_r+d_r$,

$$ \nu(n)\le \nu(B_r)\le (1+4c_r)2^\delta, $$

so

$$ c_r\ge \frac{\nu(n)}{4\cdot 2^\delta}-O(1). $$

On the other hand, every baby step yields a fixed multiplicative gain $a<1$ depending only on $\delta$, hence

$$ n\le 2^{d_r}a^{-b_r}, $$

which gives

$$ b_r\ge \frac{\Lambda(n)-d_r}{|\log_2 a|}. $$

Choosing

$$ \delta=\left\lfloor \log_2\log_2(\nu(n)+1)\right\rfloor $$

balances the lower bounds for $b_r$ and $c_r$. Using $r=b_r+c_r+d_r$ and equation (16), one obtains

$$ l(n)\ge \Lambda(n)+\lg \nu(n)-O(\log\log(\nu(n)+1)). $$

This completes the proof.

∎