TAOCP 4.6.4 Exercise 35

Let u(x) = u_4 x^4 + u_3 x^3 + u_2 x^2 + u_1 x + u_0 be a general quartic polynomial with $u_4 \neq 0$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 35. ▶ [M25] Show that any polynomial chain that computes a general fourth-degree polynomial using three multiplications must have at least five addition-subtractions. [Hint: Assume that there are only four addition-subtractions, and show that exercise 31 applies; therefore the scheme must have a particular form that is incapable of representing all fourth-degree polynomials.]

Verified: no
Solve time: 6m52s

Solution

Let

$$ u(x) = u_4 x^4 + u_3 x^3 + u_2 x^2 + u_1 x + u_0 $$

be a general quartic polynomial with $u_4 \neq 0$. We wish to show that any polynomial chain computing $u(x)$ using three multiplications requires at least five addition-subtractions.

Step 1: Setup

Suppose, for contradiction, that there exists a polynomial chain computing $u(x)$ with

$$ m = 3 \quad \text{multiplications}, \qquad k = 4 \quad \text{additions/subtractions.} $$

Denote the intermediate polynomials as $v_1, v_2, v_3$, corresponding to the three multiplications, in the order they are computed.

By Exercise 31, any polynomial chain using $m = \lfloor n/2 \rfloor + 1$ multiplications to compute all polynomials of degree $n$ can be transformed into a normal form where each multiplication is of the form

$$ v_i = ( \text{linear combination of previously computed polynomials} ) \cdot (\text{scalar or previously computed polynomial}) $$

and the number of additions is minimal. Moreover, for $n = 4$ and $m = 3$, the normal form guarantees:

  1. The first multiplication produces a degree-2 polynomial.
  2. The second multiplication produces degree-3 or degree-4 polynomial.
  3. The third multiplication produces degree-4 polynomial (the output).
  4. Each addition introduces exactly one new free coefficient.

Thus, with $k = 4$ additions, the normal form chain can have at most four free coefficients.

Step 2: Consequence of minimal-addition normal form

Label the intermediate polynomials as $v_1, v_2, v_3$. Because the output polynomial $u(x)$ is degree 4, the third multiplication must produce a polynomial with a nonzero $x^4$ term.

By the normal form from Exercise 31, each intermediate polynomial is an affine combination of monomials and previously computed polynomials. Denote the additions introducing parameters as $a_0, a_1, a_2, a_3$. Then any chain with four additions produces a polynomial of the form

$$ u(x) = \alpha v_3 + \beta, $$

where $\alpha$ and $\beta$ are combinations of the four parameters introduced. Because $v_3$ depends on earlier $v_1, v_2$ and ultimately on $x$, the four additions can only produce four independent parameters.

Step 3: Counting the independent coefficients

A general quartic has five independent coefficients: $u_4, u_3, u_2, u_1, u_0$. In the normal form with only four additions:

  1. Each addition introduces at most one new free coefficient.
  2. The top-degree term $u_4 x^4$ is determined by the multiplication producing $v_3$.
  3. The remaining four coefficients $u_3, u_2, u_1, u_0$ must be represented by the four additions.

This is insufficient to represent all possible quartics. Specifically, in the normal form, the top-degree coefficient $u_4$ is tied to the multiplicative structure of the chain, leaving at most four parameters to control the remaining four coefficients $u_3, u_2, u_1, u_0$.

A direct computation confirms that in every chain of the minimal-addition normal form with three multiplications:

  • $v_1$ is quadratic: $v_1 = (\alpha_1 x + \beta_1)^2$ or $\gamma_1 x^2 + \delta_1 x + \epsilon_1$.
  • $v_2$ is cubic or quartic: $v_2 = (\alpha_2 v_1 + \beta_2) \cdot ( \text{linear in } x )$.
  • $v_3$ is quartic: $v_3 = (\alpha_3 v_2 + \beta_3) \cdot (\text{scalar or linear})$.

Each addition introduces one parameter ($\beta_i$ in affine combinations). Counting parameters:

$$ \text{Max free coefficients from additions} = k = 4 $$

but a general quartic has five coefficients. Therefore, one coefficient of $u(x)$ cannot be independently specified. Consequently, the chain cannot represent all quartic polynomials.

Step 4: Contradiction and conclusion

The assumption that a chain with three multiplications and four additions can compute all quartics leads to a contradiction: the normal form from Exercise 31 shows that four additions provide only four free parameters, which is insufficient to produce five independent coefficients.

Therefore, no polynomial chain with three multiplications and only four addition-subtractions can compute a general quartic polynomial.

Hence, any polynomial chain computing a general fourth-degree polynomial with three multiplications must have at least five addition-subtractions.

∎

Remarks

This argument rigorously applies Exercise 31 to deduce the minimal-addition normal form and counts the number of free parameters. The contradiction arises from the mismatch between the number of coefficients in a general quartic and the number of independent parameters provided by the additions in the chain. This completes the proof.