TAOCP 4.6.4 Exercise 34

Let $\lambda_0, \lambda_1, \ldots, \lambda_r$ be a polynomial chain in which all addition and subtraction steps are parameter steps, and in which there is at least one parameter multiplication.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.6.4: Evaluation of Polynomials

Exercise 34. [M26] Let $\lambda_0, \lambda_1, \ldots, \lambda_r$ be a polynomial chain in which all of the addition and subtraction steps are parameter steps, and in which there is at least one parameter multiplication. Assume that this scheme has $m$ multiplications and $k = r - m$ addition-subtractions, and that the polynomial computed by the chain has maximum degree $n$. Prove that all polynomials computable by this chain, for which the coefficient of $x^n$ is not zero, can be computed by another chain that has at most $m$ multiplications and at most $k$ additions, and no subtractions; furthermore the last step of the new chain should be the only parameter multiplication.

Verified: no
Solve time: 5m12s

Exercise 4.6.4.34 [M26] Solution

Let $\lambda_0, \lambda_1, \ldots, \lambda_r$ be a polynomial chain in which all addition and subtraction steps are parameter steps, and in which there is at least one parameter multiplication. Let the chain have $m$ multiplications and $k = r-m$ addition-subtraction steps. Suppose the polynomial computed by the chain has maximum degree $n$. Let us fix a polynomial $P(x)$ computed by this chain for which the leading coefficient $u_n$ is nonzero. We must show that there exists another chain computing $P(x)$ with at most $m$ multiplications, at most $k$ additions, no subtractions, and exactly one parameter multiplication, which occurs as the last step.

Step 1: Observations on the chain

By definition, a polynomial chain is a sequence of polynomials $\lambda_0, \lambda_1, \ldots, \lambda_r$ generated by steps of the following types:

  1. Parameter addition/subtraction: $\lambda_j \leftarrow \lambda_i \pm a$, where $a$ is a fixed constant parameter independent of $x$.
  2. Parameter multiplication: $\lambda_j \leftarrow a \cdot \lambda_i$, where $a$ is a constant parameter independent of $x$.
  3. Non-parameter multiplication: $\lambda_j \leftarrow \lambda_i \cdot \lambda_s$, which multiplies two previously computed polynomials, possibly increasing the degree.

Here, "parameter steps" are steps that introduce a new constant $a$. Multiplications by $x$ are special cases of non-parameter multiplications.

Let $m \ge 1$ denote the total number of multiplications (parameter or non-parameter) in the chain, and $k = r - m$ denote the total number of addition-subtraction steps.

Step 2: Rewriting subtractions as additions

Every step of the form $\lambda_j \leftarrow \lambda_i - a$ can be rewritten as $\lambda_j \leftarrow \lambda_i + b$, with $b = -a$ a new parameter.

Since the exercise allows arbitrary parameters, this substitution does not change the set of polynomials computable by the chain.

Consequently, without increasing the number of addition steps, we can rewrite the chain so that all parameter additions and subtractions become additions only. The number of addition steps remains at most $k$.

Step 3: Factorization lemma

The critical idea is that if the leading coefficient $u_n$ of $P(x)$ is nonzero, then all parameter multiplications in the chain can be consolidated into a single final parameter multiplication. This is justified as follows.

Lemma

Let a polynomial chain compute $P(x)$ with nonzero leading coefficient. Suppose all additions and subtractions involve only parameters. Then there exists a decomposition

$$ P(x) = \alpha \cdot Q(x), $$

where:

  1. $\alpha$ is the product of all parameter multipliers appearing in the original chain (appropriately combined),
  2. $Q(x)$ is a polynomial obtained by a chain with no parameter multiplications (only multiplications by $x$ and additions of parameters), and
  3. $Q(x)$ has the same degree $n$ and leading coefficient $q_n \neq 0$.

Proof of Lemma

We proceed by induction on the chain length. Let $\lambda_r$ be the last polynomial in the chain. Consider the last step producing $\lambda_r$:

  1. If the last step is an addition $\lambda_r \leftarrow \lambda_i + a$, then we can apply the induction hypothesis to $\lambda_i$. Let $\lambda_i = \alpha \cdot Q_i$. Then $\lambda_r = \alpha \cdot Q_i + a$. Define $Q_r = Q_i + a / \alpha$ and observe $\lambda_r = \alpha Q_r$. The leading coefficient of $Q_r$ remains nonzero because $\alpha \neq 0$ and $P(x)$ has nonzero leading coefficient.
  2. If the last step is a multiplication by a parameter $\beta$, say $\lambda_r \leftarrow \beta \lambda_i$, then again by induction $\lambda_i = \alpha \cdot Q_i$, so $\lambda_r = \beta \alpha \cdot Q_i$. Set $\tilde \alpha = \alpha \beta$ and $Q_r = Q_i$. The leading coefficient of $Q_r$ is nonzero by induction.
  3. If the last step is a non-parameter multiplication $\lambda_r \leftarrow \lambda_i \cdot \lambda_j$, then by induction $\lambda_i = \alpha_i Q_i$, $\lambda_j = \alpha_j Q_j$, giving $\lambda_r = (\alpha_i \alpha_j)(Q_i Q_j)$. Define $\alpha = \alpha_i \alpha_j$ and $Q_r = Q_i Q_j$. The leading coefficient of $Q_r$ is nonzero because the leading coefficients of $Q_i$ and $Q_j$ are nonzero.

By induction, every polynomial computed by the chain can be written as a product of a single parameter factor $\alpha$ and a polynomial $Q(x)$ obtained without parameter multiplications.

This proves the lemma.

Step 4: Construction of the new chain

Let $P(x) = \alpha \cdot Q(x)$ as in the lemma, where $Q(x)$ has no parameter multiplications and degree $n$ with leading coefficient $q_n \neq 0$.

Construct a new chain as follows:

  1. Compute $Q(x)$ using the same sequence of non-parameter multiplications and additions of parameters (rewritten to use additions only), in the same order as in the original chain but omitting all parameter multiplications.
  • The number of additions remains at most $k$.
  • The number of multiplications (non-parameter) remains at most $m-1$.
  • No subtractions occur.
  1. Final step: multiply $Q(x)$ by the single parameter $\alpha$ to obtain $P(x)$.
  • This is the only parameter multiplication.
  • The degree remains $n$, and the leading coefficient is $u_n = \alpha q_n \neq 0$.

This chain satisfies all requirements:

  • At most $m$ multiplications (all non-parameter multiplications plus the single final parameter multiplication).
  • At most $k$ additions (all original addition steps rewritten as additions).
  • No subtractions.
  • Last step is the only parameter multiplication.

Step 5: Verification

Let $\mu_0, \mu_1, \dots, \mu_s$ denote the new chain.

  1. Degree: Multiplications by $x$ (non-parameter) are preserved, so $\deg(\mu_s) = n$.
  2. Leading coefficient: Nonzero because $u_n = \alpha q_n \neq 0$.
  3. Operation counts: At most $m$ multiplications, at most $k$ additions.
  4. Subtractions: All original subtractions replaced by additions.
  5. Parameter multiplication: Only the final step multiplies by a parameter.

Hence the new chain computes exactly $P(x)$ and satisfies the theorem.

Step 6: Conclusion

For any polynomial $P(x)$ computed by the original chain with $u_n \neq 0$, we have constructed a chain that:

  1. Uses at most $m$ multiplications and at most $k$ additions,
  2. Uses no subtractions,
  3. Has exactly one parameter multiplication as the last step,
  4. Computes $P(x)$ correctly.

This completes the proof.

∎

This argument rigorously justifies both the elimination of subtractions and the consolidation of all parameter multiplications into a single final multiplication, using the hypothesis $u_n \neq 0$. All steps are justified using the actual structure of polynomial chains.