TAOCP 4.6.1 Exercise 11

Section 4.6.1: Division of Polynomials

Exercise 11. [M22] What row names would have appeared in Table 1 if the sequence of degrees had been 9, 6, 5, 2, $-\infty$ instead of 8, 6, 4, 2, 1, 0?

Verified: yes
Solve time: 4m17s

Solution

Table 1 in Section 4.6.1 records the steps of Algorithm D (division of polynomials) and, in particular, the row names, which correspond to the degrees of successive remainders $r_k(x)$ in the sequence of divisions. The row names are determined by the degrees of the remainders that appear when performing the division algorithm recursively, or equivalently, by the sequence of degrees of the polynomials involved in the Euclidean algorithm on the original sequence.

The original sequence of degrees in the table was $8, 6, 4, 2, 1, 0$. For each row, the row name was the degree of the polynomial at that step. If the sequence of degrees is now changed to $9, 6, 5, 2, -\infty$, we must assign row names in the same manner, corresponding to the successive remainders in Algorithm D.

Let the sequence of degrees be denoted

$d_0 = 9, \quad d_1 = 6, \quad d_2 = 5, \quad d_3 = 2, \quad d_4 = -\infty.$

Algorithm D proceeds by subtracting multiples of the divisor to reduce the degree. The row names are the degrees of the polynomials at the start of each iteration of the division loop, which correspond exactly to $d_0, d_1, d_2, \dots, d_4$. Therefore, the row names are

$9, 6, 5, 2, -\infty.$

No further computation is required, since the row names are taken directly from the degree sequence of the remainders.

Hence the complete list of row names that would appear in Table 1 is

$\boxed{9, 6, 5, 2, -\infty}.$