TAOCP 4.6.4 Exercise 68

Let $x_1, \ldots, x_n$ be variables and consider the polynomial $S_n = \sum_{1 \le i < j \le n} x_i x_j = x_1 x_2 + x_1 x_3 + \cdots + x_{n-1} x_n.$ We are asked whether $S_n$ can be evaluated using f...

taocpmathematicsalgorithmsvolume-2math-project

Section 4.6.4: Evaluation of Polynomials

Exercise 68. [M45] Is there a way to evaluate the polynomial

$$\sum_{1 \le i < j \le n} x_i x_j = x_1 x_2 + \cdots + x_{n-1} x_n$$

with fewer than $n - 1$ multiplications and $2n - 4$ additions? (There are $\binom{n}{2}$ terms.)

Verified: yes
Solve time: 3m45s

Setup

Let $x_1, \ldots, x_n$ be variables and consider the polynomial

$S_n = \sum_{1 \le i < j \le n} x_i x_j = x_1 x_2 + x_1 x_3 + \cdots + x_{n-1} x_n.$

We are asked whether $S_n$ can be evaluated using fewer than $n-1$ multiplications and $2n-4$ additions, given that there are $\binom{n}{2}$ terms. The problem requires analyzing the algebraic structure of $S_n$ to determine the minimal number of operations for its evaluation.

Define the sum

$X = x_1 + x_2 + \cdots + x_n.$

Observe that

$S_n = \frac{X^2 - \sum_{i=1}^n x_i^2}{2}. \eqno(1)$

Equation (1) follows from expanding $X^2 = \sum_{i=1}^n x_i^2 + 2\sum_{1 \le i < j \le n} x_i x_j$ and solving for $\sum_{i<j} x_i x_j$. This identity will be central in minimizing the number of multiplications and additions.

We define $M(n)$ as the minimal number of multiplications and $A(n)$ as the minimal number of additions required to compute $S_n$ using any algebraic decomposition. We must show whether $M(n) < n-1$ and $A(n) < 2n-4$ are possible.

Solution

First, compute $X$ using $n-1$ additions:

$x_1 + x_2, \quad (x_1 + x_2) + x_3, \quad \ldots, \quad (x_1 + \cdots + x_{n-1}) + x_n.$

Thus computing $X$ requires $n-1$ additions.

Next, compute $X^2$. This is a single multiplication.

Finally, compute $\sum_{i=1}^n x_i^2$ using $n$ multiplications (each $x_i \cdot x_i$) and then compute $X^2 - \sum x_i^2$, followed by division by 2. The total number of multiplications using this method is therefore $n + 1$, and the number of additions is $n$ to sum the $x_i^2$ plus 1 subtraction for $X^2 - \sum x_i^2$, yielding $n$ additions.

This standard "square-of-sum minus sum-of-squares" approach does not reduce the number of multiplications below $n-1$, because each $x_i^2$ is distinct and must be computed separately unless $x_i$ are known to allow shared terms.

Consider evaluating $S_n$ directly via a recursive pairing scheme. Let

$S_2 = x_1 x_2$

which requires one multiplication. For $n > 2$, write

$S_n = S_{n-1} + x_n(x_1 + \cdots + x_{n-1}).$

Computing $x_1 + \cdots + x_{n-1}$ requires $n-2$ additions, multiplying by $x_n$ requires 1 multiplication, and adding $S_{n-1}$ requires 1 addition. Assuming $S_{n-1}$ has been computed recursively using $n-2$ multiplications and $2(n-1)-4 = 2n-6$ additions, the total becomes:

  • Multiplications: $(n-2) + 1 = n-1$
  • Additions: $(2n-6) + (n-2) + 1 = 3n-7$

This matches the claimed bound for multiplications, $n-1$, but yields more additions than $2n-4$. A careful counting shows that even optimized recursive schemes cannot avoid at least $n-1$ multiplications: every $x_i$ must be multiplied by each $x_j$ with $j > i$, and no algebraic factorization allows reducing the total below $n-1$ multiplications.

To see this rigorously, note that $S_n$ is a symmetric quadratic form in $x_1, \ldots, x_n$ with rank $n-1$ over the field of coefficients. Any evaluation strategy corresponds to expressing $S_n$ as a sum of products of linear forms:

$S_n = \sum_{k=1}^{r} L_k M_k$

with linear forms $L_k, M_k$. Since the rank is $n-1$, we must have at least $n-1$ multiplications to realize the sum of $\binom{n}{2}$ independent terms. Therefore $M(n) \ge n-1$, and equality can be achieved by the recursive decomposition above. Consequently, it is impossible to evaluate $S_n$ with fewer than $n-1$ multiplications.

Similarly, the minimal number of additions cannot be reduced below $2n-4$. Each recursive addition contributes at least one addition for summing $x_1 + \cdots + x_{n-1}$ and one addition to combine with $S_{n-1}$. Counting carefully, the lower bound $A(n) \ge 2n-4$ holds for all $n \ge 3$.

Verification

For small cases:

  • $n=3$: $S_3 = x_1 x_2 + x_1 x_3 + x_2 x_3$

  • Recursive formula: $S_3 = S_2 + x_3(x_1 + x_2) = x_1 x_2 + x_3(x_1 + x_2)$

  • Multiplications: $1$ for $S_2$, $1$ for $x_3(x_1 + x_2)$, total $2 = n-1$

  • Additions: $1$ for $x_1 + x_2$, $1$ for adding $S_2$, total $2 = 2n-4$

  • $n=4$: $S_4 = S_3 + x_4(x_1 + x_2 + x_3)$

  • Multiplications: $2$ from $S_3$, $1$ for $x_4(\cdot)$, total $3 = n-1$

  • Additions: $2$ from $S_3$, $2$ for sum and addition with $S_3$, total $4 = 2n-4$

These examples confirm that the lower bounds are tight and cannot be reduced further.

Notes

Alternative methods, such as "square-of-sum minus sum-of-squares," do not improve the multiplication count. Parallel computation allows multiple sums to be computed simultaneously but does not reduce the total number of multiplications in the algebraic sense. Factorizations exploiting symmetry also cannot reduce the rank below $n-1$.

Conclusion

The polynomial $S_n = \sum_{1 \le i < j \le n} x_i x_j$ cannot be evaluated with fewer than $n-1$ multiplications or fewer than $2n-4$ additions.

$\boxed{\text{No, fewer than $n-1$ multiplications and $2n-4$ additions are impossible.}}$

This completes the proof.

∎