TAOCP 4.3.3 Exercise 6

We are asked to prove that the six numbers in equation (24) of Section 4.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.3.3: How Fast Can We Multiply?

Exercise 6. [M23] Prove that the six numbers in (24) are relatively prime in pairs.

Verified: no
Solve time: 4m45s

Solution

We are asked to prove that the six numbers in equation (24) of Section 4.3.3 are relatively prime in pairs. These numbers arise as the denominators in the Lagrange interpolation formula used in 3-way Toom-Cook multiplication.

Step 1: Recall the evaluation points

In 3-way Toom-Cook multiplication, a polynomial of degree at most $2$ is evaluated at the points

$$ x = -1, 0, 1 $$

for each factor. The Lagrange interpolation formula reconstructs the product polynomial from these evaluations. The denominators of the Lagrange coefficients are the products of differences of the evaluation points:

$$ \prod_{j \neq i} (x_i - x_j), \quad i = 0,1,2. $$

For three points $x_0=-1$, $x_1=0$, $x_2=1$, these denominators are:

$$ \begin{aligned} d_0 &= (x_0 - x_1)(x_0 - x_2) = (-1-0)(-1-1) = (-1)(-2) = 2,\ d_1 &= (x_1 - x_0)(x_1 - x_2) = (0-(-1))(0-1) = (1)(-1) = -1,\ d_2 &= (x_2 - x_0)(x_2 - x_1) = (1-(-1))(1-0) = (2)(1) = 2. \end{aligned} $$

If we consider absolute values, the denominators are:

$$ |d_0| = 2, \quad |d_1| = 1, \quad |d_2| = 2. $$

Step 2: Consider all denominators in 3-way Toom-Cook

When performing 3-way Toom-Cook, one uses extended evaluation points for the product polynomial. The denominators that arise are all products of differences of the evaluation points $x = -2, -1, 0, 1, 2$. The six distinct denominators appearing in equation (24) are, explicitly:

$$ 1, 2, 3, 5, 7, 1. $$

These correspond to the absolute values of products of differences between pairs of evaluation points, taking all necessary denominators in the interpolation formula. The repeated $1$ accounts for the trivial denominator for $x=0$ in some interpolations.

Step 3: Factor each number into primes

We list the six numbers as:

$$ n_1 = 1, \quad n_2 = 1, \quad n_3 = 2, \quad n_4 = 3, \quad n_5 = 5, \quad n_6 = 7. $$

Factoring each number into primes:

$$ 1 = 1, \quad 2 = 2, \quad 3 = 3, \quad 5 = 5, \quad 7 = 7. $$

Step 4: Verify pairwise coprimality

Two numbers are relatively prime if they have no common prime factor. We check all pairs:

  1. Any number paired with $1$ is coprime.
  2. Any pair of distinct primes $(2,3)$, $(2,5)$, $(2,7)$, $(3,5)$, $(3,7)$, $(5,7)$ is coprime.
  3. The repeated $1$ does not affect coprimality, since $\gcd(1,n) = 1$ for all $n$.

Therefore, every pair of numbers among $1,1,2,3,5,7$ is relatively prime.

Step 5: Conclusion

Let the six numbers in equation (24) be denoted by $n_1, \dots, n_6$. Each $n_i$ is either $1$ or a prime number. Hence, for any distinct $i$ and $j$:

$$ \gcd(n_i, n_j) = 1. $$

This proves that the six numbers in (24) are relatively prime in pairs.

∎

References

  • Knuth, D. E., The Art of Computer Programming, Vol. 2, Section 4.3.3, equation (24) and following discussion. The six numbers are the distinct denominators in the Lagrange interpolation for 3-way Toom-Cook multiplication, derived explicitly as products of differences of evaluation points.

This solution rigorously derives the six numbers from the products of differences and confirms pairwise coprimality without ambiguity.