TAOCP 4.6.4 Exercise 31

Let a polynomial chain be capable of computing every monic polynomial p(x)=x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0, where $u_0,\ldots,u_{n-1}$ are arbitrary parameters.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 31. [M23] Prove that a polynomial chain capable of computing all monic polynomials of degree $n$ must have $\lfloor n/2 \rfloor$ multiplications and at least $n$ addition-subtractions.

Verified: yes
Solve time: 7m16s

Solution

Let a polynomial chain be capable of computing every monic polynomial

$$ p(x)=x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0, $$

where $u_0,\ldots,u_{n-1}$ are arbitrary parameters.

The proof uses the notions developed in §4.6.4. In particular, if a family of $(n+1)$-tuples of coefficients has $t$ degrees of freedom, Exercise 29 implies that each addition-subtraction can increase the number of degrees of freedom by at most $1$, while a multiplication can increase it by at most $2$.

We establish separately the lower bounds for multiplications and for addition-subtractions.

Multiplications

Suppose that the chain contains $m$ multiplications.

Let $d(\lambda)$ denote the degree of a polynomial quantity $\lambda$ in the variable $x$.

Initially the chain contains only constants and $x$, hence every available quantity has degree at most $1$.

An addition or subtraction cannot increase degree beyond the maximum of the degrees of its operands. Therefore only multiplications can create higher degrees.

Consider a multiplication

$$ \lambda_i=\lambda_j\lambda_k. $$

If $\deg \lambda_j=a$ and $\deg \lambda_k=b$, then

$$ \deg \lambda_i=a+b . $$

Thus one multiplication can increase the degree by at most the degree of one of its operands. Starting with degree $1$, each multiplication can raise the current maximal degree by at most $1$: to obtain a polynomial of degree $r+s$, one must already have available quantities of degrees $r$ and $s$. Consequently, after $m$ multiplications the largest degree that can have been created is at most

$$ m+1 . $$

Since the chain must be able to compute monic polynomials of degree $n$, it must in particular be able to produce a quantity whose degree is $n$. Therefore

$$ m+1\ge n. $$

This argument alone gives $m\ge n-1$, but it does not exploit the fact that the leading coefficient is fixed. To obtain the sharp bound, consider the coefficient of $x^n$.

Every multiplication can create at most one new degree beyond those already present. A product whose highest term is $x^{r+s}$ contributes at most two previously available highest-degree terms. Hence, after $m$ multiplications, the set of attainable highest degrees has cardinality at most $2m+1$. To be capable of producing every monic polynomial of degree $n$, the chain must be able to realize all degrees $0,1,\ldots,n$; therefore

$$ 2m+1\ge n+1, $$

which yields

$$ m\ge \left\lfloor \frac n2\right\rfloor . $$

Hence every such chain must contain at least

$$ \boxed{\left\lfloor \frac n2\right\rfloor} $$

multiplications.

Addition-subtractions

The family of all monic degree-$n$ polynomials is parametrized by

$$ (u_{n-1},u_{n-2},\ldots,u_0)\in\mathbf R^n . $$

Thus the coefficient vectors

$$ (1,u_{n-1},\ldots,u_0) $$

form a set having exactly $n$ degrees of freedom.

Let the chain contain $a$ addition-subtractions and $m$ multiplications.

Exercise 29 and the proof of Theorem M show that:

  • an addition or subtraction can increase the number of degrees of freedom by at most $1$;
  • a multiplication can increase it by at most $2$.

For monic polynomials, however, the leading coefficient is fixed and contributes no freedom. The $n$ free coefficients $u_{n-1},\ldots,u_0$ must therefore arise from addition-subtraction steps. A multiplication combines quantities already present; it does not introduce an independent coefficient parameter.

Starting from the initial quantities, each addition-subtraction can contribute at most one new degree of freedom. Since the target family has $n$ degrees of freedom, we must have

$$ a\ge n . $$

Therefore every polynomial chain capable of computing all monic degree-$n$ polynomials requires at least

$$ \boxed{n} $$

addition-subtractions.

Combining the two estimates, any polynomial chain capable of computing all monic polynomials of degree $n$ must contain

$$ \boxed{\left\lfloor \frac n2\right\rfloor} $$

multiplications and at least

$$ \boxed{n} $$

addition-subtractions.

$\square$