TAOCP 4.6.3 Exercise 16

Section 4.6.3: Evaluation of Powers

Exercise 16. [HM15] Show that Theorem D is not trivially true just because of the binary method: if $l^{(0)}(n)$ denotes the length of the addition chain for $n$ produced by the binary S-and-X method, the ratio $l^{(0)}(n)/\lambda(n)$ does not approach a limit as $n \to \infty$.

Verified: yes
Solve time: 1m25s

---

Solution

Let $l^{(0)}(n)$ denote the length of an addition chain for $n$ produced by the binary S-and-X method described in Section 4.6.3. We are asked to show that the ratio

$\frac{l^{(0)}(n)}{\lambda(n)}$

does not approach a limit as $n \to \infty$, where $\lambda(n) = \lfloor \log_2 n \rfloor$.

We begin by recalling the behavior of the binary method. Write $n$ in binary as

$n = \sum_{j=0}^{t} d_j 2^j, \quad d_j \in {0,1}, \quad d_t = 1.$

The left-to-right or right-to-left binary method generates an addition chain of length

$l^{(0)}(n) = t + \nu(n),$

where $t = \lfloor \log_2 n \rfloor = \lambda(n)$ and $\nu(n)$ is the number of ones in the binary expansion of $n$. This follows from the fact that each "1" in the binary expansion beyond the leading bit requires an additional multiplication by $x$, and each binary digit (except the leading one) contributes one squaring operation. Hence, for all $n > 1$,

$l^{(0)}(n) = \lambda(n) + \nu(n). \eqno(1)$

Consider two sequences of integers to examine the behavior of the ratio $l^{(0)}(n)/\lambda(n)$:

1. Numbers of the form $n = 2^k$. Then $\nu(n) = 1$, so by equation (1)

$l^{(0)}(2^k) = k + 1 = \lambda(2^k) + 1.$

The ratio is

$\frac{l^{(0)}(2^k)}{\lambda(2^k)} = \frac{k+1}{k} = 1 + \frac{1}{k} \to 1 \quad \text{as } k \to \infty.$

1. Numbers of the form $n = 2^k - 1$. Then $\nu(n) = k$, so by equation (1)

$l^{(0)}(2^k - 1) = k + k = 2k = 2 \lambda(2^k - 1) + o(1),$

since $\lambda(2^k - 1) = k - 1$. More precisely,

$\frac{l^{(0)}(2^k - 1)}{\lambda(2^k - 1)} = \frac{2k}{k-1} = 2 + \frac{2}{k-1} \to 2 \quad \text{as } k \to \infty.$

These two sequences demonstrate that the ratio $l^{(0)}(n)/\lambda(n)$ can be made arbitrarily close to $1$ and arbitrarily close to $2$, depending on the pattern of ones in the binary expansion of $n$. Therefore, the limit

$\lim_{n \to \infty} \frac{l^{(0)}(n)}{\lambda(n)}$

does not exist. The ratio oscillates between values approaching $1$ and values approaching $2$, and indeed attains all intermediate values for suitable choices of $n$ with different densities of ones in their binary expansions.

This shows that Theorem D cannot be inferred trivially from the binary method: the binary method itself produces addition chains whose relative length compared to $\lambda(n)$ fluctuates indefinitely as $n$ increases.

This completes the proof.

∎