TAOCP 4.6.4 Exercise 25

In the proof of Theorem M, the numbers $\beta_j$ are not introduced as “constant terms” by interpretation.

taocpmathematicsalgorithmsvolume-2

Section 4.6.4: Evaluation of Polynomials

Exercise 25. [**] [M20] When the construction in the proof of Theorem M is applied to the (inefficient) polynomial chain

$$\lambda_1 = \alpha_1 + \lambda_0, \qquad \lambda_2 = -\lambda_0 - \lambda_0, \qquad \lambda_3 = \lambda_1 + \lambda_1, \qquad \lambda_4 = \alpha_2 \times \lambda_3,$$ $$\lambda_5 = \lambda_0 - \lambda_0, \qquad \lambda_6 = \alpha_0 - \lambda_0, \qquad \lambda_7 = \lambda_5 \times \lambda_6, \qquad \lambda_8 = \lambda_5 \times \lambda_7,$$ $$\lambda_9 = \lambda_1 \times \lambda_1, \qquad \lambda_{10} = \alpha \times \lambda_9,$$

how can $\beta_1, \beta_2, \ldots, \beta_7$ be expressed in terms of $\alpha_1, \ldots, \alpha_s$?

Verified: yes
Solve time: 8m11s

In the proof of Theorem M, the numbers $\beta_j$ are not introduced as “constant terms” by interpretation. They are produced by a specific recursive construction.

Starting with

$$ \beta_0=0, $$

the proof associates to every step of the polynomial chain a corresponding step for the $\beta$'s:

  • if $\lambda_j=\lambda_k+\lambda_m$, then

$$ \beta_j=\beta_k+\beta_m; $$

  • if $\lambda_j=\lambda_k-\lambda_m$, then

$$ \beta_j=\beta_k-\beta_m; $$

  • if $\lambda_j=\alpha_r\times\lambda_k$, then

$$ \beta_j=\alpha_r,\beta_k; $$

  • if $\lambda_j=\lambda_k\times\lambda_m$, then

$$ \beta_j=\beta_k\beta_m. $$

Thus the $\beta$-chain is obtained from the given polynomial chain by carrying out exactly the same operations, beginning with $\beta_0=0$.

Applying this construction to the chain in the exercise:

$$ \lambda_1=\alpha_1+\lambda_0, $$

gives

$$ \beta_1=\alpha_1+\beta_0=\alpha_1. $$

Next,

$$ \lambda_2=-\lambda_0-\lambda_0, $$

so

$$ \beta_2=-\beta_0-\beta_0=0. $$

Then

$$ \lambda_3=\lambda_1+\lambda_1, $$

hence

$$ \beta_3=\beta_1+\beta_1 =2\alpha_1. $$

For

$$ \lambda_4=\alpha_2\times\lambda_3, $$

we obtain

$$ \beta_4=\alpha_2\beta_3 =2\alpha_1\alpha_2. $$

Next,

$$ \lambda_5=\lambda_0-\lambda_0, $$

so

$$ \beta_5=\beta_0-\beta_0=0. $$

For

$$ \lambda_6=\alpha_0-\lambda_0, $$

we get

$$ \beta_6=\alpha_0-\beta_0 =\alpha_0. $$

Finally,

$$ \lambda_7=\lambda_5\times\lambda_6, $$

therefore

$$ \beta_7=\beta_5\beta_6 =0\cdot\alpha_0 =0. $$

Hence the quantities produced by the construction of Theorem M are

$$ \boxed{ \beta_1=\alpha_1,\qquad \beta_2=0,\qquad \beta_3=2\alpha_1,\qquad \beta_4=2\alpha_1\alpha_2,\qquad \beta_5=0,\qquad \beta_6=\alpha_0,\qquad \beta_7=0. } $$

These follow directly from the recursive procedure used in the proof of Theorem M.