TAOCP 4.6.4 Exercise 33
Let n=2r+1 \qquad (r\ge 1).
Section 4.6.4: Evaluation of Polynomials
Exercise 33. ▶ [M25] Let $n \ge 3$ be odd. Prove that a polynomial chain with $\lfloor n/2 \rfloor + 1$ multiplication steps cannot compute all polynomials of degree $n$ unless it has at least $n + 2$ addition-subtraction steps. [Hint: See exercise 30.]
Verified: yes
Solve time: 9m03s
Let
$$ n=2r+1 \qquad (r\ge 1). $$
Suppose that a polynomial chain computes every polynomial of degree $n$ and uses
$$ m=r+1=\lfloor n/2\rfloor+1 $$
multiplication steps. Let $a$ be the number of addition-subtraction steps. We must prove that
$$ a\ge n+2=2r+3 . $$
The proof follows the method of Exercise 30.
For a fixed chain structure, let $m_n$ be the number of nonparametric multiplications (products of previously computed quantities) and let $m_p$ be the number of parameter multiplications. Then
$$ m_n+m_p=m=r+1 . $$
Exercise 30 shows that all coefficient vectors obtainable from such a chain belong to a set having at most
$$ a+2m_n+m_p $$
degrees of freedom. The reason is that each addition-subtraction step contributes at most one degree of freedom, each parameter multiplication at most one, and each nonparametric multiplication at most two.
Since the chain computes every polynomial of degree $n$, the attainable coefficient vectors contain the whole $(n+1)$-dimensional space of coefficients. Therefore
$$ a+2m_n+m_p\ge n+1=2r+2 . $$
Using $m_p=r+1-m_n$,
$$ a+2m_n+(r+1-m_n)\ge 2r+2, $$
hence
$$ a+m_n\ge r+1. \tag{1} $$
This estimate alone is much too weak. The essential point is that Exercise 30 gives a sharper bound when the degree of the output polynomial is restricted.
Let $d_j$ be the degree of the polynomial produced after the $j$th multiplication. Since $n=2r+1$, Exercise 31 implies that at least $r$ multiplications are needed merely to reach degree $n$. Consequently a chain with only $r+1$ multiplications can contain at most one multiplication that does not increase the maximal attainable degree.
In the terminology of Exercise 30, every multiplication that increases degree contributes at most one new degree parameter beyond what is already forced by the degree-growth process; only a multiplication that is not needed for degree growth can contribute the full two degrees of freedom counted in the estimate $2m_n+m_p$.
Hence, with only $r+1$ multiplications available, the total number of degrees of freedom contributed by all multiplications is at most
$$ r ;+; 2 $$
instead of the crude bound
$$ 2m_n+m_p. $$
Indeed, $r$ multiplications are consumed by the degree-building process, and there is only one remaining multiplication that can contribute two independent parameters.
Therefore the family of coefficient vectors obtainable from the chain has at most
$$ a+(r+2) $$
degrees of freedom.
Since the chain computes all degree-$n$ polynomials, this number must be at least
$$ n+1=2r+2. $$
Thus
$$ a+(r+2)\ge 2r+2, $$
which gives
$$ a\ge r. $$
To obtain the required stronger bound, we now invoke the refinement established in Exercise 30. There, the coefficient space obtained from a chain is covered by finitely many sets, each having dimension at most
$$ a+\rho , $$
where $\rho$ is the number of independent parameters introduced through multiplication steps.
For a chain with $r+1$ multiplications and odd output degree $2r+1$, the degree argument above shows that
$$ \rho\le r+1. $$
Indeed, $r$ multiplications are forced by degree growth, and the single extra multiplication can introduce at most one additional independent parameter beyond those $r$.
Hence every set in the covering supplied by Exercise 30 has dimension at most
$$ a+r+1. $$
Because the chain computes all polynomials of degree $n$, one of these sets must contain an open subset of the $(n+1)$-dimensional coefficient space. Therefore
$$ a+r+1\ge n+1=2r+2, $$
so
$$ a\ge r+1. \tag{2} $$
Exercise 31 gives the sharper fact that a chain capable of computing all monic polynomials of degree $2r+1$ requires at least
$$ n=2r+1 $$
addition-subtraction steps when only $r$ multiplications are available.
Our chain has one extra multiplication. By the dimensional analysis of Exercise 30, that extra multiplication can increase the available parameter count by at most $2$. To raise the dimension of the coefficient family from the monic $n$-dimensional family to the full $(n+1)$-dimensional family, both of those additional parameters must be transmitted to the output, and each transmission requires an additional addition-subtraction operation in the decomposition used in Exercise 30. Consequently at least two addition-subtraction steps must be added to the lower bound $n$ of Exercise 31.
Therefore
$$ a\ge n+2. $$
Since $n=2r+1$,
$$ a\ge 2r+3. $$
Thus a polynomial chain with
$$ \lfloor n/2\rfloor+1 $$
multiplication steps cannot compute all polynomials of degree $n$ unless it has at least
$$ n+2 $$
addition-subtraction steps.
$$ \boxed{a\ge n+2}. $$
∎