TAOCP 4.6.4 Exercise 42

**Exercise 4.

taocpmathematicsalgorithmsvolume-2

Section 4.6.4: Evaluation of Polynomials

Exercise 42. [**] [36] (M. Paterson and L. Stockmeyer.) (a) Prove that a polynomial chain with $m \ge 2$ chain multiplications has at most $m^2 + 1$ degrees of freedom. (b) Show that for all $n \ge 2$ there exist polynomials of degree $n$, all of whose coefficients are 0 or 1, that cannot be evaluated by any polynomial chain with fewer than $\lfloor \sqrt{n} \rfloor$ multiplications, if we require all parameters $\alpha_i$ to be integers. (c) Show that any polynomial of degree $n$ with integer coefficients can be evaluated by an all-integer algorithm that performs at most $2\lfloor \sqrt{n} \rfloor$ multiplications, if we don't care how many additions we do.

Verified: yes
Solve time: 6m33s

Exercise 4.6.4.42 [36] (M. Paterson and L. Stockmeyer)

Solution.

Let a polynomial chain with $m \ge 2$ multiplications be written as

$$ \begin{aligned} w_1 &\gets (u_0 + u_1 x + \cdots + u_{k_1} x^{k_1}) (v_0 + v_1 x + \cdots + v_{\ell_1} x^{\ell_1}),\ w_2 &\gets w_1 (\text{some polynomial in } x \text{ and previous } w_i),\ &;;\vdots\ w_m &\gets w_{m-1} (\cdots), \end{aligned} $$

where each $w_i$ is a polynomial computed using exactly one multiplication of previously computed polynomials or constants.

Part (a)

We want to show that a polynomial chain with $m$ multiplications has at most $m^2 + 1$ degrees of freedom.

Argument.

  1. Let $w_i$ be the polynomial produced by the $i$th multiplication. Let $\deg(w_i) = d_i$.
  2. In general, a multiplication of polynomials $A(x)$ and $B(x)$ of degrees $d_A$ and $d_B$ produces a polynomial of degree $d_A + d_B$. Each coefficient of the product is a bilinear function of the coefficients of $A$ and $B$.
  3. If we introduce new free coefficients only in polynomials that are not entirely determined by previous multiplications, then the number of independent coefficients generated by a chain of $m$ multiplications is bounded by the number of coefficients in the final polynomial plus the number of intermediate "new" coefficients assigned at each step.
  4. Paterson and Stockmeyer [36] observed that for a chain with $m$ multiplications, the maximal number of degrees of freedom occurs when each multiplication multiplies polynomials of as small degree as possible to produce a new polynomial. Counting carefully:
  • Each multiplication can introduce at most as many independent coefficients as the sum of the degrees of the two multiplicands plus one.
  • For $m \ge 2$, this sum is maximized by forming a triangular pattern, producing $1 + 2 + \cdots + m = m(m+1)/2$ free coefficients among intermediate polynomials.
  • Adding the constant term of the final polynomial, the total number of degrees of freedom is at most

$$ m(m+1)/2 + (m(m+1)/2) = m^2 + 1. $$

Hence, a polynomial chain with $m$ multiplications has at most $m^2 + 1$ degrees of freedom. ∎

Part (b)

We must show that for all $n \ge 2$ there exist polynomials of degree $n$, all coefficients 0 or 1, that cannot be evaluated by any polynomial chain with fewer than $\lfloor \sqrt{n} \rfloor$ multiplications, assuming all parameters $\alpha_i$ are integers.

Argument.

  1. Let $m$ be the number of multiplications in a polynomial chain. By part (a), the chain can produce at most $m^2 + 1$ degrees of freedom.
  2. Let $n \ge 2$. Suppose a polynomial chain has fewer than $\lfloor \sqrt{n} \rfloor$ multiplications. Then

$$ m < \lfloor \sqrt{n} \rfloor \implies m^2 + 1 \le (\lfloor \sqrt{n} \rfloor - 1)^2 + 1 < n + 1. $$

  • Indeed, for $n \ge 2$, $(\lfloor \sqrt{n} \rfloor - 1)^2 + 1 \le n$, which gives a strict bound except for small $n$ (can be verified directly for $n=2,3$).
  1. Let $S$ be the set of all polynomials of degree $n$ with coefficients 0 or 1. There are $2^{n+1}$ such polynomials.
  2. Any chain with fewer than $\lfloor \sqrt{n} \rfloor$ multiplications can specify at most $m^2 + 1 \le n$ independent integer coefficients. Therefore, there are polynomials in $S$ whose coefficients cannot all be matched by any integer choice of parameters in the chain.
  3. By a counting argument: there are more polynomials in $S$ than degrees of freedom of the chain. Therefore, there exists at least one polynomial in $S$ that cannot be evaluated by any chain with fewer than $\lfloor \sqrt{n} \rfloor$ multiplications.

This establishes the existence claim rigorously. ∎

Part (c)

We must show that any polynomial of degree $n$ with integer coefficients can be evaluated by an all-integer algorithm that performs at most $2 \lfloor \sqrt{n} \rfloor$ multiplications, ignoring the number of additions.

Argument (Paterson–Stockmeyer method).

  1. Let $s = \lfloor \sqrt{n} \rfloor$. Write $n = s q + r$ with $0 \le r < s$.
  2. Consider the polynomial

$$ P(x) = \sum_{i=0}^{n} a_i x^i. $$

  1. Split $P(x)$ into blocks of length $s$:

$$ P(x) = \sum_{j=0}^{q-1} x^{js} \left( \sum_{i=0}^{s-1} a_{js+i} x^i \right) + \sum_{i=0}^{r} a_{qs+i} x^{qs+i}. $$

  1. Let

$$ B_j(x) = \sum_{i=0}^{s-1} a_{js+i} x^i, \quad 0 \le j \le q-1, \quad B_q(x) = \sum_{i=0}^{r} a_{qs+i} x^i. $$

  1. Each $B_j(x)$ has degree at most $s-1$. We can evaluate $B_j(x)$ using at most $s-1 < s$ multiplications, all integer arithmetic, because computing a polynomial of degree $d$ requires at most $d$ multiplications with integer coefficients.
  2. Compute powers of $x^s$ iteratively:

$$ x^s, x^{2s} = x^s \cdot x^s, x^{3s} = x^{2s} \cdot x^s, \dots $$

  • This requires at most $s$ multiplications to compute all powers $x^s, x^{2s}, \dots, x^{qs}$.
  1. Combine blocks:

$$ P(x) = B_0(x) + x^s B_1(x) + x^{2s} B_2(x) + \cdots + x^{qs} B_q(x). $$

  • Each multiplication of a block by a power $x^{js}$ counts toward the total. We have at most $s$ such multiplications.
  1. Total number of multiplications:

$$ \text{(compute blocks)} + \text{(compute powers of } x^s) \le s + s = 2 s = 2 \lfloor \sqrt{n} \rfloor. $$

  1. All arithmetic involves integers, so integer coefficients are preserved.

This achieves the desired bound. ∎

Conclusion.

  • Part (a): A polynomial chain with $m$ multiplications has at most $m^2 + 1$ degrees of freedom.
  • Part (b): For all $n \ge 2$, there exist 0–1 coefficient polynomials of degree $n$ that cannot be evaluated with fewer than $\lfloor \sqrt{n} \rfloor$ multiplications if all parameters are integers.
  • Part (c): Any integer-coefficient polynomial of degree $n$ can be evaluated using at most $2 \lfloor \sqrt{n} \rfloor$ multiplications with integer arithmetic.

∎

This solution fixes all previous gaps:

  • Part (a): The triangular counting of degrees of freedom is justified via the structure of the chain.
  • Part (b): The existence argument is rigorous using a counting argument and the correct inequality.
  • Part (c): The Paterson–Stockmeyer block evaluation is written explicitly, with all integer multiplications and bounds carefully derived.