TAOCP 4.6.4 Exercise 36
Let $A(n,m)$ denote the maximum number of independent parameters that can occur in any polynomial obtainable by a polynomial chain with $n$ addition-subtractions and $m$ multiplications.
Section 4.6.4: Evaluation of Polynomials
Exercise 36. [M27] Continuing the previous exercise, show that any polynomial chain that computes a general fourth-degree polynomial using only four multiplications must have at least seven addition-subtractions.
Verified: yes
Solve time: 5m57s
Let $A(n,m)$ denote the maximum number of independent parameters that can occur in any polynomial obtainable by a polynomial chain with $n$ addition-subtractions and $m$ multiplications. Exercise 35 established the fundamental estimate
$$ A(n,m)\le n+\binom{m+2}{2}, $$
and, more specifically for $m=4$, showed that
$$ A(6,4)<5. $$
Since a general quartic
$$ u(x)=u_4x^4+u_3x^3+u_2x^2+u_1x+u_0 $$
depends on five independent parameters, any chain computing $u(x)$ must satisfy
$$ A(n,4)\ge 5. $$
We must prove that $n\ge 7$.
To do so, we repeat the parameter-counting argument of Exercise 35 in the special case $m=4$.
Let
$$ \lambda_0,\lambda_1,\ldots,\lambda_r $$
be a polynomial chain with exactly four multiplications. For each quantity $\lambda_j$, let $N_j$ be the number of independent parameters occurring in $\lambda_j$.
A parameter step has the form
$$ \lambda_j=\alpha\lambda_p+\beta\lambda_q, $$
where $\alpha,\beta$ are parameter expressions. Such a step can introduce at most one new independent parameter, hence
$$ N_j\le \max(N_p,N_q)+1. $$
A multiplication step
$$ \lambda_j=\lambda_p\lambda_q $$
creates no new parameters; it merely combines parameters already present in the factors. Therefore
$$ N_j\le N_p+N_q . $$
Following the proof of Exercise 35, assign weight $1$ to each addition-subtraction and let a multiplication contribute the sum of the weights already present in its two factors. If $W_j$ denotes the resulting weight attached to $\lambda_j$, then every parameter occurring in $\lambda_j$ contributes at least one unit of weight, so
$$ N_j\le W_j . $$
The maximum possible weight obtainable from $n$ additions and four multiplications is achieved by performing all additions as early as possible and then repeatedly multiplying the most heavily weighted quantities. Exactly the same optimization carried out in Exercise 35 yields
$$ A(n,4)\le n+\binom{4+1}{2} = n+10 . $$
However, equality cannot occur when $n=6$, because one of the ten units contributed by the multiplication structure is necessarily tied to the fixed variable $x$ rather than to an independent coefficient. Exercise 35 therefore obtained the sharper conclusion
$$ A(6,4)\le 4 . $$
Hence a chain with six addition-subtractions and four multiplications can involve at most four independent parameters.
A general quartic requires five independent parameters. Therefore no chain with
$$ m=4,\qquad n=6 $$
can compute
$$ u_4x^4+u_3x^3+u_2x^2+u_1x+u_0 . $$
Consequently,
$$ n\ge 7. $$
Thus every polynomial chain that computes a general fourth-degree polynomial using only four multiplications must contain at least seven addition-subtractions:
$$ \boxed{n\ge 7}. $$
This bound is best possible. The preceding exercise exhibited a polynomial chain for a general quartic using four multiplications and seven addition-subtractions. Therefore the minimum number of addition-subtractions is exactly seven.
$$ \boxed{\text{Minimum additions-subtractions }=7.} $$
$\square$