§1. Primitive Factorization  Lecture III  Page 1

Lecture III Subresultants

We extend the Euclidean algorithm to the polynomial ring D[X] where D is a unique factorization domain. The success of this enterprise depends on the theory of subresultants. Subresultant sequences are special remainder sequences which have many applications including Diophantine equations, Sturm theory, elimination theory, discriminants, and algebraic cell decompositions. Our approach to subresultants follows Ho and Yap [7], who introduced the pseudo-subresultants in order to carry out Loos’ original program in [3].

One of the most well-studied problems in the early days of computer algebra (circa 1970) is the problem of computing GCD in the polynomial ring D[X] where D is a UFD. See the surveys of Loos [3] and Collins [5]. The importance of this setting is underscored by the famous lemma of Gauss. This led to a development of efficient algorithms whose approach is quite distinct from the HGCD approach of the previous lecture. The reader may be surprised that any new ideas are needed: why not use the previous techniques to compute GCD in Q_{D}[X] (where Q_{D} is the quotient field of D) and then “clear denominators”? One problem is that computing remainders in Q_{D}[X] can be quite non-trivial for some D (say, D = F [X_{1},…, X_{d}]). Another problem is that clearing denominators is really a multiple GCD computation (in its dual form of a multiple LCM computation). Multiple GCD is expensive in practical terms, even when it is polynomial-time as in the case D = . Worst, in case D = F [X_{1},…, X_{d}], we are involved in a recursive situation of exponential complexity. Hence the challenge is to develop a direct method avoiding the above problems.

In this lecture, D refers to a unique factorization domain with quotient field Q_{D}. The reader may safely take D = and so Q_{D} = .

§1. Primitive Factorization

The goal of this section is to extend the arithmetic structure of a unique factorization domain D to its quotient field Q_{D} and to Q_{D}[X]. It becomes meaningful to speak of prime factorization in Q_{D} and Q_{D}[X].

Content of a polynomial. Let q ∈ D be an irreducible element. For any non-zero element a/b ∈ Q_{D} where a, b ∈ D are relatively prime, define the q-order of a/b to be

ord_{q}(a/b) := \{ \begin{matrix}n & if q^{n}|a but not q^{n+1}|a, \\ −n & if q^{n}|b but not q^{n+1}|b. \end{matrix}  (1)

Thus ord_{q}(a/b) = 0 iff q does not divide ab. For example, in D = we have ord_{2}(4/3) = 2, ord_{2}(3/7) = 0 and ord_{2}(7/2) = −1.

We extend this definition to polynomials. If P ∈ Q_{D}[X] \ {0}, define the q-order of P to be

ord_{q}(P) := min_{i}{ord_{q}(c_{i})}

where c_{i} ranges over all the non-zero coefficients of P. For example, ord_{2}(X^{3} − \frac{5}{4}X + 2) = −2 in [X]. Any associate of q^{ord_{q}(P)} is called a q-content of P. Finally, we define a content of P to be

u ∏_{q} q^{ord_{q}(P)}

where q ranges over all distinguished irreducible elements of D, u is any unit. This product is well-defined since all but finitely many ord_{q}(P) are zero. For the zero element, we define ord_{q}(0) = −∞ and the q-content and content of 0 are both 0.

Primitive polynomials. A polynomial of Q_{D}[X] is primitive if it has content 1; such polynomials are elements of D[X]. Thus every non-zero polynomial P has a factorization of the form

P = cQ

where c is a content of P and Q is primitive. We may always choose Q so that its leading coefficient is distinguished. In this case, c is called the content of P, and Q the primitive part of P. These are denoted cont(P) and prim(P), respectively. We call the product expression “cont(P)prim(P)” the primitive factorization of P.

If prim(P) = prim(Q), we say that P, Q are similar and denote this by

P ∼ Q.

Hence P ∼ Q iff there exist α, β ∈ D such that αP = βQ. In particular, if P, Q are associates then they are similar.

For instance, the following are primitive factorizations:

−4X^{3} − 2X + 6 = (−2) · (2X^{3} + X − 3)
(15/2)X^{2} − (10/3)X + 5 = (5/6) · (9X^{2} − 4X + 6).

Also the polynomials −4X^{3} − 2X + 6 and 6X^{3} + 3X − 9 are similar.

The following is one form of a famous little lemma^{1}:

Lemma 1 (Gauss’ Lemma) If D is a UFD and P, Q ∈ D[X] are primitive, then so is their product P Q.

Proof. We must show that for all irreducible q ∈ D, ord_{q}(P Q) = 0. We can uniquely write any polynomial P ∈ D[X] as

P = qP_{0} + P_{1}, (P_{0}, P_{1} ∈ D[X])

where X^{1+deg(P_{0})}|P_{1} and the tail coefficient (§0.10) of P_{1} is not divisible by q. Moreover,

ord_{q}(P) = 0 iff P_{1} ≠ 0.

Thus P_{1} ≠ 0. Let Q = qQ_{0} + Q_{1} be the similar expression for Q and again Q_{1} ≠ 0. Multiplying the expressions for P and Q, we get an expression of the form

P Q = qR_{0} + R_{1}, R_{1} = P_{1}Q_{1} ≠ 0.

1We refer to Edwards [6] for a deeper investigation of this innocuous lemma.

By the uniqueness of such expressions, we conclude that ord_{q}(P Q) = 0. Q.E.D.

If F_{i} = a_{i}G_{i} (i = 1, 2) is a primitive factorization, we have cont(F_{1}F_{2}) = cont(a_{1}G_{1}a_{2}G_{2}) = a_{1}a_{2}cont(G_{1}G_{2}) and prim(F_{1}F_{2}) = prim(G_{1}G_{2}). By Gauss’ lemma, cont(G_{1}G_{1}) = ϵ and prim(G_{1}G_{2}) = ϵ′G_{1}G_{2}, where ϵ, ϵ′ are units. Hence we have shown

Corollary 2

cont(F_{1}F_{2}) = ϵ · cont(F_{1})cont(F_{2}), prim(F_{1}F_{2}) = ϵ′ · prim(F_{1})prim(F_{2}).

Another corollary to Gauss’ lemma is this:

Corollary 3 If P (X) ∈ D[X] is primitive and P (X) is reducible in Q_{D}[X] then P (X) is reducible in D[X].

To see this, suppose P = QR with Q, R ∈ Q_{D}[X]. By the above corollary, cont(P) = ϵ · cont(Q)cont(R) = ϵ′′ for some unit ϵ′′. Then P = ϵ′′ · prim(P). By the same corollary again,

P = ϵ′′ · ϵ′ · prim(Q)prim(R).

Since prim(Q), prim(R) belongs to D[X], this shows P is reducible.

We are ready to prove the non-trivial direction of the theorem in §II.1: if D is a UFD, then D[X] is a UFD.

Proof. Suppose P ∈ D[X] and without loss of generality, assume P is not an element of D. Let its primitive factorization be P = aP′. Clearly P′ is a non-unit. We proceed to give a unique factorization of P′ (as usual, unique up to reordering and associates). In the last lecture, we proved that a ring of the form Q_{D}[X] (being Euclidean) is a UFD. So if we view P′ as an element of Q_{D}[X], we get a unique factorization, P′ = P′_{1}P′_{2} ⋯ P′_{ℓ} where each P′_{i} is an irreducible element of Q_{D}[X]. Letting the primitive factorization of each P′_{i} be c_{i}P_{i}, we get

P′ = c_{1} ⋯ c_{ℓ}P_{1} ⋯ P_{ℓ}.

But c_{1} ⋯ c_{ℓ} = ϵ (some unit). Thus

P′ = (ϵ · P_{1})P_{2} ⋯ P_{ℓ}

is a factorization of P into irreducible elements of D[X]. The uniqueness of this factorization follows from the fact that Q_{D}[X] is a UFD. If a is a unit, then

P = (a · ϵ · P_{1})P_{2} ⋯ P_{ℓ}

gives a unique factorization of P. Otherwise, since D is a UFD, a has a unique factorization, say a = a_{1} ⋯ a_{k}. Then

P = a_{1},…, a_{k}(ϵ · P_{1})P_{2} ⋯ P_{ℓ}

gives a factorization of P. It is easy to show uniqueness. Q.E.D.

§2. Pseudo-remainders  Lecture III  Page 4

The divide relation in a quotient field. We may extend the relation ‘b divides c’ to the quotient field of a UFD. For b, c ∈ Q_{D}, we say b divides c, written

b|c,

if for all irreducible q, either 0 ≤ ord_{q}(b) ≤ ord_{q}(c) or ord_{q}(c) ≤ ord_{q}(b) ≤ 0. Clearly Q_{D} is also a “unique factorization domain” whose irreducible elements are q, q^{−1} where q ∈ D is irreducible. Hence the concept of GCD is again applicable and we extend our previous definition to Q_{D} in a natural way. We call b a partial content of P if b divides cont(P).

Exercise 1.1: Assume that elements in Q_{D} are represented as a pair (a, b) of relatively prime elements of D. Reduce the problem of computing GCD in Q_{D} to the problem of GCD in D.

Exercise 1.2: (Eisenstein’s criterion) Let D be a UFD and f(X) = ∑_{i=0}^{n} a_{i}X^{i} be a primitive polynomial in D[X]. If there exists a prime element p ∈ D such that

a_{n} ≢ 0(mod p),
a_{i} ≡ 0(mod p)  (i = 0,…, n − 1),
a_{0} ≢ 0(mod p^{2}),

then f(X) is prime in D[X].

Exercise 1.3: (i) X^{n} − p is irreducible over [X] for all prime p ∈ .

(ii) f(X) = X^{p−1} + X^{p−2} + ⋯ + X + 1 (= \frac{X^{p}−1}{X−1}) is irreducible in [X] for all prime p ∈ . HINT: apply Eisenstein’s criteria to f(X + 1). (iii) Let ζ be a primitive 5-th root of unity. Then \sqrt{5} ∈ (ζ). (iv) The polynomial g(X) = X^{10}−5 is irreducible over [X] but factors as (X^{5}−\sqrt{5})(X^{5}+ \sqrt{5}) over (ζ)[X].

§2. Pseudo-remainders and PRS

Since D[X] is a UFD, the concept of GCD is meaningful. It easily follows from the definitions that for P, Q ∈ D[X],

cont(GCD(P, Q)) = ϵ · GCD(contP, contQ),  (ϵ = unit)  (2)
prim(GCD(P, Q)) = GCD(primP, primQ).  (3)

Thus the GCD problem in D[X] can be separated into the problem of multiple GCD’s in D (to extract contents and primitive parts) and the GCD of primitive polynomials in D[X].

To emulate the Euclidean remaindering process for GCD’s in D[X], we want a notion of remainders. We use a basic observation:

Let P, Q ∈ D[X] where d = deg P − deg Q ≥ 0 and α = lead(Q). Then rem(α^{d+1}P, Q) (the remainder function is defined if we regard α^{d+1}P and Q as elements in Q_{D}[X]) is in fact an element of D[X].

Exercise 2.1: Verify this observation.

So it is natural to define the pseudo-remainder of P and Q as follows:

prem(P, Q) := \{ \begin{matrix}P & if & deg P < deg Q \\ rem(α^{d+1}P, Q) & if & deg P − deg Q = d ≥ 0, α = lead(Q). \end{matrix}

Pseudo-remainders are elements of D[X] but they are not guaranteed to be primitive. We now generalize the concept of remainder sequences. A sequence of non-zero polynomials

(P_{0}, P_{1},…, P_{k}) (k ≥ 1)

is called a polynomial remainder sequence (abbreviated, PRS) of P, Q if P_{0} = P, P_{1} = Q and

P_{i+1} ∼ prem(P_{i−1}, P_{i}) (i = 2,…, k − 1)
0 = prem(P_{k−1}, P_{k}).

If d_{i} = deg P_{i} for i = 0,…, k, we call

(d_{0}, d_{1},…, d_{k})

the degree sequence of the PRS. The degree sequence of a PRS is determined by the first two elements of the PRS. The PRS is regular if d_{i} = 1 + d_{i+1} for i = 1,…, k − 1.

Discussion: We are usually happy to compute GCD’s up to similarity. The concept of a PRS captures this indifference: the last term of a PRS is similar to the GCD of the first two terms. Consider how we might compute a PRS. Even assuming we avoid the idea of computing in Q_{D}[X], we are presented with several strategies. Here are two obvious ones:

(a) Always maintain primitive polynomials. Each step of the PRS algorithm is implemented by a pseudo-remainder computation followed by primitive factorization of the result.

(b) Avoid all primitive factorizations until the last step. Repeatedly compute pseudoremainders, and at the end, extract the content with one primitive factorization. Both strategies have problems. In case (a), we are computing multiple GCD at each step, which we said is too expensive. In case (b), the final polynomial can have exponentially large coefficients (this will be demonstrated below). In this lecture, we present a solution of G.E. Collins involving an interesting middle ground between strategies (a) and (b), which is sufficient to avoid exponential growth of the coefficients without repeated multiple GCD computation.

The PRS sequences corresponding to strategies (a) and (b) above are:

a) Primitive PRS This is a PRS (P_{0},…, P_{k}) where each member (except possibly for the first two) is primitive:

P_{i+1} = prim(prem(P_{i−1}, P_{i})) (i = 1,…, k − 1).

b) Pseudo-Euclidean PRS This is a PRS (P_{0},…, P_{k}) where

P_{i+1} = prem(P_{i−1}, P_{i}) (i = 1,…, k − 1).

The following illustrates the explosive coefficient growth in the Pseudo-Euclidean PRS.

§3. Determinantal Polynomials  Lecture III  Page 6

Example: (Knuth’s example) Displaying only coefficients, the following is an Pseudo-Euclidean PRS in [X] where each polynomial is represented by its list of coefficients.

X^{8} X^{7} X^{6} X^{5} X^{4} X^{3}  X^{2}  X  1
1  0  1  0 −3 −3  8  2  −5
3  0  5  0  −4  −9  21
−15  0  3  0  −9
15795  30375  −59535
1254542875143750  −1654608338437500

12593338795500743100931141992187500

§3. Determinantal Polynomials

In this section, we introduce the connection between PRS and determinants. We emphasize that concept of “determinantal polynomials” introduced here is key to understanding the connection between elimination and remainders.

Let M be an m × n matrix, m ≤ n. The determinantal polynomial of M is

dpol(M) := det(M_{m})X^{n−m} + det(M_{m+1}) X^{n−m−1} + ⋯ + det(M_{n})

where M_{i} is the square submatrix of M consisting of the first m−1 columns and the i^{th} column of M (i = m,…, n). Call

det(M_{m})

the nominal leading coefficient and n − m the nominal degree of dpol(M). Of course the degree of dpol(M) could be less than its nominal degree.

Notation: If P_{1},…, P_{m} are polynomials and n ≥ 1 + max_{i}{deg P_{i}} then

mat_{n}(P_{1},…, P_{m})

is the m × n matrix whose ith row contains the coefficients of P_{i} listed in order of decreasing degree, treating P_{i} as having nominal degree n. Write

dpol_{n}(P_{1},…, P_{m})

for dpol(mat_{n}(P_{1},…, P_{m})). The subscript n is normally omitted when understood or equal to

1 + max_{i}{deg P_{i}}.

Sylvester’s matrix. Let us illustrate this notation. We often apply this notation to “shifted polynomials” (where we call X^{i}P a “shifted version” of the polynomial P). If P and Q are polynomials of degree m and n respectively then the following m + n by m + n square matrix is called Sylvester matrix of P and Q:

mat(\underbrace{X^{n−1}P, X^{n−2}P,…, X^{1}P, X^{0}P}_{n}, \underbrace{X^{m−1}Q, X^{m−2}Q,…, X^{0}Q}_{m})

= ( \begin{matrix}a_{m} & a_{m−1} & ⋯ & & a_{0} \\ & a_{m} & a_{m−1} & ⋯ & & a_{0} \\ & & ... & & & & ... \\ & & & a_{m} & a_{m−1} & ⋯ & & a_{0} \\ b_{n} & b_{n−1} & ⋯ & b_{0} \\ & b_{n} & b_{n−1} & ⋯ & b_{0} \\ & & ... & & & & ... \\ & & & & b_{n} & ⋯ & & b_{0} \end{matrix} )

where P = ∑_{i=0}^{m} a_{i}X^{i} and Q = ∑_{i=0}^{n} b_{i}X^{i}. The above matrix may also be written as

mat(X^{n−1}P, X^{n−2}P,…, X^{1}P, X^{0}P; X^{m−1}Q, X^{m−2}Q,…, X^{0}Q),

with a semicolon to separate the P′ from the Q’s. [In general, we may replace one or more commas with semicolons, purely as a visual aid to indicate groupings.] Since this matrix is square, its determinantal polynomial is a constant equal to it’s determinant. This constant is called the resultant of P and Q, and denoted res(P, Q). We shall return to resultants.

The basic connection between determinants and polynomials is revealed in the following:

Lemma 4 Let P, Q ∈ D[X], deg P = m ≥ n = deg Q. If

M = mat(\underbrace{X^{m−n}Q, X^{m−n−1}Q,…, X^{1}Q, X^{0}Q}_{m−n+1}, P)

then

dpol(M) = prem(P, Q).

Proof. Let

M′ = mat(\underbrace{X^{m−n}Q, X^{m−n−1}Q,…, XQ, Q}_{m−n+1}, β^{m−n+1}P),

where β = lead(Q).

1. Since M′ is obtained from the matrix M in the lemma by multiplying the last row by β^{m−n+1}, it follows that dpol(M′) = β^{m−n+1}dpol(M).

2. If we do Gaussian elimination on M′, by repeated elimination of leading coefficients of the last row we finally get a matrix

M′′ = ( \begin{matrix}b_{n} & b_{n−1} & & ⋯ & b_{0} \\ & b_{n} & b_{n−1} & & ⋯ & b_{0} \\ . & . & . \\ & & & b_{n} & b_{n−1} & ⋯ & & b_{0} \\ & & & & c_{n−1} & c_{n−2} & ⋯ & c_{0} \end{matrix} )

where the polynomial represented by the last row is R = ∑_{i=0}^{n−1} c_{i}X^{i} with nominal degree n − 1. It is seen that R = prem(P, Q).

3. From the definition of determinantal polynomials, dpol(M′′) = b_{n}^{m−n+1}prem(P, Q) (where b_{n} = β).

§4. Subresultant PRS  Lecture III  Page 8

4. Gaussian row operations on a matrix do not change the determinantal polynomial of a

matrix:

dpol(M′) = dpol(M′′).  (4)

The lemma follows from these remarks. Q.E.D.

Corollary 5 Let P, Q ∈ D[X], deg P = m ≥ n = deg Q and a, b ∈ D. Then

prem(aP, bQ) = ab^{m−n+1}prem(P, Q).

From equation (4) we conclude

Corollary 6

dpol(\underbrace{X^{m−n}Q,…, Q}, P) = dpol(\underbrace{X^{m−n}Q,…, Q}, β^{−(m−n+1)}prem(P, Q)).  (5)

Application. We show that coefficients in the Pseudo-Euclidean PRS can have sizes exponentially larger that those in the corresponding Primitive PRS. Suppose

(P_{0}, P_{1},…, P_{k})

is the Pseudo-Euclidean PRS and (d_{0}, d_{1},…, d_{k}) associated degree sequence. Write

(δ_{1},…, δ_{k})

where δ_{i} = d_{i−1} − d_{i}. Let α = cont(P_{2}), Q_{2} = prim(P_{2}):

P_{2} = αQ_{2}.

Then corollary 5 shows that

α^{δ_{2}+1}|prem(P_{1}, αQ_{2}) = P_{3}.

Writing P_{3} = α^{δ_{2}+1}Q_{3} for some Q_{3}, we get next

α^{(δ_{2}+1)(δ_{3}+1)}|prem(P_{2}, α^{δ_{2}+1}Q_{3}) = prem(P_{2}, P_{3}) = P_{4}.

Continuing in this way, we eventually obtain

α^{N}|P_{k}, (N = ∏_{i=2}^{k−1}(δ_{i} + 1)).

Since δ_{i} ≥ 1, we get α^{2^{k}}|P_{k}. Assuming that the size of an element α ∈ D is doubled by squaring, this yields the desired conclusion. Note that this exponential behavior arise even in a regular PRS (all δ_{i} equals 1).

Exercise 3.1:

a) The content of P_{k} is larger than the α^{N} indicated. [For instance, the contents of P_{4} is strictly larger than the α^{(δ_{2}+1)(δ_{3}+1)} indicated.] What is the correct bound for N? (Note that we are only accounting for the content arising from α.)

b) Give a general construction of Pseudo-Euclidean PRS’s with coefficient sizes growing at this exponential rate.

§4. The Subresultant PRS

We now present Collin’s PRS algorithm.

A PRS (P_{0}, P_{1},…, P_{k}) is said to be based on a sequence

(β_{1}, β_{2},…, β_{k−1}) (β_{i} ∈ D)  (6)

if

P_{i+1} = \frac{prem(P_{i−1}, P_{i})}{β_{i}} (i = 1,…, k − 1).  (7)

Note that the Pseudo-Euclidean PRS and Primitive PRS are based on the appropriate sequences. We objected to the Primitive PRS because it is based on a sequence whose entries β_{i} are relatively expensive to compute. We now describe one sequence that is easy to obtain (even in parallel). Define for i = 0,…, k − 1,

\{ \begin{matrix}δ_{i} := deg(P_{i}) − deg(P_{i+1}) \\ a_{i} := lead(P_{i}) \end{matrix}  (8)

Then let

β_{i+1} := \{ \begin{matrix}(−1)^{δ_{0}+1} & if & i = 0 \\ (−1)^{δ_{i}+1}(ψ_{i})^{δ_{i}}a_{i} & if & i = 1,…, k − 2 \end{matrix}  (9)

where (ψ_{0},…, ψ_{k−1}) is an auxillary sequence given by

\{ \begin{matrix}ψ_{0} & := & 1 \\ ψ_{i+1} & := & ψ_{i}(\frac{a_{i+1}}{ψ_{i}})^{δ_{i}} = \frac{(a_{i+1})^{δ_{i}}}{(ψ_{i})^{δ_{i}−1}} \end{matrix}  (10)

for i = 0,…, k − 2.

By definition, the subresultant PRS is based on the sequence (β_{1},…, β_{k−1}) just defined. This algorithm was discovered by Collins around 1967 [4] and subsequently simplified by Brown [2]. It is currently the best algorithm in the family of algorithms based on sequences of β’s.

It is not easy to see why this sequence of β_{i} works: Superficially, equation (7) implies that P_{i+1} lies in Q_{D}[x] rather than D[x]. Moreover, it is not clear from (10) that ψ_{i} (and hence β_{i+1}) belongs to D rather than Q_{D}. In fact the ψ_{i}’s turn out to be determinants of coefficients of P_{0} and P_{1}, a fact not known in the early papers on the subresultant PRS algorithm. This fact implies that the β_{i}’s have sizes that are polynomial in the input size. In other words, this algorithm succeeded in curbing the exponential growth of coefficients (unlike the Pseudo-Euclidean PRS) without incurring expensive multiple GCD computations (which was the bane of the primitive PRS).

The theory of subresultants will explain all this, and more. This is ostensibly the goal of the rest of this lecture. But subresultants have other uses as well.

It is easy to implement the subresultant PRS Algorithm in the style of the usual Euclidean algorithm: in the ith step, we compute the quintuple (in this order)

P_{i}, δ_{i}, a_{i}, β_{i}, ψ_{i}

according to (7),(8),(9) and (10), respectively. Such an implementation takes O(n^{2} log n) operations of D. It is possible to apply the Half-GCD idea in this setting to improve this to

§5. Subresultants  Lecture III  Page 10

O(n log^{2} n) operations, provided we only compute the sequence of partial quotients and coefficients of similarities

(Q_{1}, α_{1}, β_{1}),…, (Q_{k−1}, α_{k−1}, β_{k−1})

where α_{i}P_{i+1} = β_{i}P_{i−1} + P_{i}Q_{i}. This has been demonstrated by Schwartz [8] (although that version suffers from the same ills as the HGCD algorithm in [1]).

Exercise 4.1: Modify the HGCD algorithm to compute the subresultants.

§5. Subresultants

We introduce subresultants.

Definition: Let P, Q ∈ D[X] with

deg(P) = m > n = deg(Q) ≥ 0.

For i = 0, 1,…, n, the ith subresultant of P and Q is defined as

sres_{i}(P, Q) := dpol(\underbrace{X^{n−i−1}P, X^{n−i−2}P,…, P}_{n−i}, \underbrace{X^{m−i−1}Q, X^{m−i−2}Q,…, Q)}_{m−i} .  (11)

Observe that the defining matrix

mat(X^{n−i−1}P,…, P; X^{m−i−1}Q,…, Q)

has m + n − 2i rows and m + n − i columns. If n = 0, then i = 0 and P does not appear in the matrix and the matrix is m × m. The nominal degree of sres_{i}(P, Q) is i. The nominal leading coefficient of sres_{i}(P, Q) is called the ith principal subresultant coefficient of P and Q, denoted psc_{i}(P, Q).

Note that the zeroth subresultant is in fact the resultant,

sres_{0}(P, Q) = res(P, Q),

and thus subresultants are a generalization of resultants. Furthermore,

sres_{n}(P, Q) = lead(Q)^{m−n−1}Q ∼ Q.

It is convenient to extend the above definitions to cover the cases i = n + 1,…, m:

sres_{i}(P, Q) := \{ \begin{matrix}0 & if i = n + 1, n + 2,…, m − 2 \\ Q & if i = m − 1 \\ P & if i = m \end{matrix}  (12)

We point out that this extension is consistent with the definition (11) because in case n = m−1, the two definitions of sres_{n}(P, Q) agree. Although this extension may appear contrived, it will eventually prove to be the correct one. Again, the subscript in sres_{i}(P, Q) indicates its nominal degree. The sequence

(S_{m}, S_{m−1},…, S_{1}, S_{0}), where S_{i} = sres_{i}(P, Q),

§6. Pseudo-subresultants  Lecture III  Page 11

is called the subresultant chain of P and Q. A member sres_{i}(P, Q) in the chain is regular if its degree is equal to the nominal degree i; otherwise it is irregular. We say the chain is regular if sres_{i}(P, Q) is regular for all i = 0,…, n (we ignore i = n + 1,…, m).

Remark: This concept of a ‘regular’ polynomial is quite generic and will appear again: if a polynomial has a ‘nominal degree’ (which is invariably an upper bound on the actual degree), then its ‘regularity’ simply means that the nominal degree equals the actual degree. Otherwise the polynomial is ‘irregular’.

Likewise, we extend the definition of principal subresultant coefficient psc_{i}(P, Q) to the cases i = n + 1,…, m:

psc_{i}(P, Q) := \{ \begin{matrix}nominal leading coefficient of sres_{i}(P, Q) & for i = n + 1,…, m − 1 \\ 1 & for i = m. \end{matrix} (13)

Note that psc_{m}(P, Q) is not defined as lead(P) = lead(S_{m}(P, Q)) as one might have expected.

We will see that the subresultant PRS is just a subsequence of the corresponding subresultant chain.

§6. Pseudo-subresultants

Motivation. The key to understanding polynomial remainder sequences lies in the prediction of unavoidable contents of polynomials in the PRS. This prediction is simpler for regular subresultant chains. Regular chains can be studied using indeterminate coefficients. Precisely, suppose the given polynomials

P = ∑_{i=0}^{m} a_{i}X^{i}, Q = ∑_{i=0}^{n} b_{i}X^{i},  (n = m − 1)  (14)

come from the ring

[X; a_{m},…, a_{0}, b_{m−1},…, b_{0}] = [X][a_{m},…, a_{0}, b_{m−1},…, b_{0}]

where a_{i}, b_{i} are indeterminates. Assuming deg P = 1 + deg Q is without loss of generality for indeterminate coefficients. After obtaining the properties of subresultants in this setting, we can “specialize” the indeterminates a_{i}, b_{j} to values \overline{a}_{i}, \overline{b}_{i} in D. This induces a ring homorphism Φ from [X; a_{m},…, a_{0}, b_{m−1},…, b_{0}] to D[X]. We indicate the Φ-image of an element e ∈ [X; a_{m},…, a_{0}, b_{m−1},…, b_{0}] by \overline{e}, called the specialization of e. Thus if (S_{m},…, S_{0}) is the subresultant chain of P, Q, we can observe the behavior of the specialized chain^{2}

(\overline{S}_{m},…, \overline{S}_{0})  (15)

in D[X]. This approach was first used by Loos [3] who also noted that this has the advantage of separating out the two causes of irregularity in chains: (a) the irregularity effects caused by the specialization, and (b) the similarity relations among subresultants that are independent of the specialization. The similarity relations of (b) are captured in Habicht’s theorem (see exercise). The proper execution of this program is slightly complicated by the fact that in general,

\overline{S}_{i} = \overline{sres_{i}(P, Q)} ≠ sres_{i}(\overline{P} , \overline{Q}).  (16)

2For typographical esthetics, we write ‘\overline{S}_{j}’ instead of the more accurate ‘\overline{S_{j}}’.

Exercise 6.1: Construct an example showing (16).

To overcome this difficulty, the concept of “pseudo-subresultant chains” was introduced in [7]. It turns out that (15) is precisely the pseudo-subresultant chain of \overline{P} , \overline{Q}, provided deg \overline{P} = m. In this way, Loos’ approach of indeterminates is recaptured via pseudo-subresultants without an explicit use of specialization. We begin developing this approach by defining pseudo-subresultants.

Definition 1 Let P, Q ∈ D[X] and m = deg P > deg Q ≥ −∞. For i = 0, 1,…, m − 1, define the ith pseudo-subresultant of P and Q to be

psres_{i}(P, Q) := dpol_{2m−2i−1}(\underbrace{X^{m−i−2}P, X^{m−i−3}P,…, P}_{m−i−1}, \underbrace{X^{m−i−1}Q, X^{m−i−2}Q,…, Q}_{m−i}).

Note that

psres_{m−1}(P, Q) = Q.

Extending these definitions as before,

psres_{m}(P, Q) := P.

The sequence

(S_{m}, S_{m−1},…, S_{1}, S_{0}), where S_{i} = psres_{i}(P, Q)

is called the pseudo-subresultant chain of P and Q. The ith pseudo-principal subresultant coefficient of P and Q, denoted ppsc_{i}(P, Q) is defined to be the nominal leading coefficient of psres_{i}(P, Q) for i = 0,…, m − 1 but (again) ppsc_{m}(P, Q) := 1.

Pseudo-subresultants of P, Q are basically their subresultants except that we give Q a nominal degree of deg(P)−1. The defining matrix for psres_{i}(P, Q) has shape (2m−2i−1)×(2m−i−1). Note that this definition^{3} allows deg Q = −∞ (Q = 0), in which case psres_{i}(P, Q) = 0 for all i < m. It is not hard to see that

psres_{i}(aP, bQ) = a^{m−i−1}b^{m−i}psres_{i}(P, Q).

Furthermore, pseudo-subresultants are similar to subresultants:

psres_{i}(P, Q) = \{ \begin{matrix}lead(P)^{m−n−1}sres_{i}(P, Q) & for i = 0, 1,…, m − 2 \\ sres_{i}(P, Q) & for i = m − 1, m. \end{matrix}

Our initial goal is to prove a weak version of Subresultant Structure Theorem. We prepare with a key result.

Lemma 7 (Basic Lemma) Let P, Q ∈ D[X] with deg P = m > n = deg Q ≥ −∞. If a = lead(P), b = lead(Q) then for i = 0,…, m − 2:

psres_{i}(P, Q) = 0  if i ≥ n + 1  (17)
psres_{n}(P, Q) = (ab)^{m−n−1}Q  (18)
psres_{i}(P, Q) = a^{m−n−1}b^{−(m−n+1)(n−i−1)}(−1)^{(n−i)(m−i)}psres_{i}(Q, prem(P, Q)),
if i ≤ n − 1.  (19)

[figure: m − i rows of Q; m − i − 1 rows of P; 2m − i − 1; (m − n − 1) 0’s; n − i rows of P; n + 1]

Figure 1: The matrix associated to psres_{i}(P, Q)

Proof. The result is clearly true if Q = 0, so assume deg Q ≥ 0. We use the aid of Figure 1. Let column 1 refer to the rightmost column of the matrix

mat(X^{m−i−2}P,…, P; X^{m−i−1}Q,…, Q)

in the figure. Thus column m + 1 contains the leading coefficient of the row corresponding to P. The column containing the leading coefficient of the row corresponding to X^{m−i−1}Q is (m − i − 1) + (n + 1) = m + n − i. But P and X^{m−i−1}Q correspond to consecutive rows. Hence if i = n, the leftmost 2m − 2i − 1 columns form an upper triangular square matrix with determinant a^{m−n−1}b^{m−n}. It is not hard to see that this proves equation (18). If i > n then the last two rows of the leftmost 2m − 2i − 2 columns are identically zero. This means that any square matrix obtained by adding a column to these 2m − 2i − 2 columns will have zero determinant. This proves equation (17). Finally, to prove equation (19), suppose i ≤ n − 1. We get

psres_{i}(P, Q)

= dpol(\underbrace{X^{m−i−2}P,…, P}_{m−i−1}, \underbrace{X^{m−i−1}Q,…, Q}_{m−i})

= dpol(\underbrace{X^{m−i−2}P,…, X^{n−i}P}_{m−n−1}, \underbrace{X^{n−i−1}P,…, P}_{n−i}, \underbrace{X^{m−i−1}Q,…, Q}_{m−i})

= dpol(\underbrace{X^{n−i−1}P,…, P}_{n−i}, \underbrace{X^{m−i−1}Q,…, Q}_{m−i}) · a^{m−n−1}

(expanding the leftmost m − n − 1 columns)

= dpol(\underbrace{X^{n−i−1}b^{m−n+1}P,…, b^{m−n+1}P}_{n−i}, \underbrace{X^{m−i−1}Q,…, Q}_{m−i}) · a^{m−n−1} · b^{−(m−n+1)(n−i)}

= dpol(\underbrace{X^{n−i−1}prem(P, Q),…, prem(P, Q)}_{n−i}, \underbrace{X^{m−i−1}Q,…, Q}_{m−i}) · a^{m−n−1} · b^{−(m−n+1)(n−i)}

(by corollary 6)

3Unlike the definition of subresultants.

= dpol(\underbrace{X^{m−i−1}Q,…, X^{n−i−1}Q}_{m−n+1}, \underbrace{X^{n−i−2}Q,…, Q}_{n−i−1}, \underbrace{X^{n−i−1}prem(P, Q),…, prem(P, Q)}_{n−i})

·a^{m−n−1} · b^{−(m−n+1)(n−i)} · (−1)^{(n−i)(m−i)}

(transposing columns)

= dpol(\underbrace{X^{n−i−2}Q,…, Q}_{n−i−1}, \underbrace{X^{n−i−1}prem(P, Q),…, prem(P, Q)}_{n−i})

·a^{m−n−1} · b^{−(m−n+1)(n−i)} · (−1)^{(n−i)(m−i)} · b^{m−n+1} (expanding the leftmost m − n + 1 columns)

= psres_{i}(Q, prem(P, Q)) · a^{m−n−1} · b^{−(m−n+1)(n−i−1)} · (−1)^{(n−i)(m−i)}.

Q.E.D.

The case i = n − 1 in equation (19) is noteworthy:

psres_{n−1}(P, Q) = (−a)^{m−n−1}prem(P, Q).  (20)

We define a block to be a sequence

B = (P_{1}, P_{2},…, P_{k}), k ≥ 1

of polynomials where P_{1} ∼ P_{k} and 0 = P_{2} = P_{3} = ⋯ = P_{k−1}. We call P_{1} and P_{k} (respectively) the top and base of the block. Two special cases arise: In case k = 1, we call B a regular block; in case P_{1} = 0, we call B a zero block. Thus the top and the base of a regular block coincide.

Using the Basic Lemma, we can already deduce the general structure of a subresultant chain.

Theorem 8 (Block Structure Theorem) A subresultant or pseudo-subresultant chain

(S_{m}, S_{m−1},…, S_{0})

is uniquely partitioned into a sequence

B_{0}, B_{1},…, B_{k}, (k ≥ 1)

of blocks such that

a) B_{0} is a regular block.

b) If b_{i} is the base polynomial of block B_{i} then b_{i} is regular and b_{i+1} ∼ prem(b_{i−1}, b_{i}) (0 < i < k).

c) There is at most one zero block; if there is one, it must be B_{k}.

Proof. Since we are interested in relations up to similarity, it is sufficient to prove the theorem assuming (S_{m},…, S_{0}) is a pseudo-subresultant chain.

§7. Subresultant Structure  Lecture III  Page 15

Assertion a) is immediate since B_{0} = (S_{m}). We verify assertion b) by induction on i: If deg S_{m−1} = n, the Basic Lemma implies that (S_{m−1}, S_{m−2},…, S_{n}) forms the next block B_{1}. Moreover, S_{n} is regular and S_{n−1} ∼ prem(S_{m}, S_{m−1}) (equation (20)). Thus b_{2} ∼ prem(b_{0}, b_{1}). Inductively, assuming that block B_{i} has been defined and the polynomial following the base of B_{i} is similar to prem(b_{i−1}, b_{i}), we can repeat this argument to define the next block B_{i+1} and show that b_{i+1} is regular and b_{i+1} ∼ prem(b_{i−1}, b_{i}). This argument terminates when prem(b_{i−1}, b_{i}) = 0. Then the rest of the pseudo-subresultants are zero, forming the final zero block, which is assertion c). Q.E.D.

By definition, a sequence of polynomials that satisfies this Block Structure theorem is called block-structured. This structure easy to recall in this graphic form:

Figure 2. Block structure of subresultant chains

We infer some interesting consequences of this theorem. Suppose P, Q ∈ D[X], and we compare their remainder sequence (P_{0}, P_{1},…, P_{ℓ}) in Q_{D}[X] with their subresultant sequence. If the blocks of the subresultant sequence is B_{0}, B_{1},…, then we see that b_{i} ∼ P_{i} for i ≥ 0, where b_{i} is the base of block B_{i}. In particular, the last non-zero block is B_{ℓ}. But P_{ℓ} ∼ GCD(P_{0}, P_{1}). This proves the following, where each item in this corollary implies the next one.

Corollary 9 Consider P, Q ∈ D[X].

0. The number of non-zero blocks in the subresultant chain of P, Q is equal to the length of any remainder sequence of P, Q. Moreover, the base of each block is similar to the corresponding member of the remainder sequence.

1. The last non-zero element in the subresultant chain is similar to GCD(P, Q).

2. The smallest index i such that the principal subresultant coefficient i(P, Q) is non-zero is equal to the deg(GCD(P, Q)).

3. Two polynomials P, Q are relatively prime if and only if their subresultant does not vanish, res(P, Q) ≠ 0.

§7. Subresultant Structure Theorem

The Block Structure Theorem does not tell us the coefficients of similarity implied by the relation b_{i+1} ∼ prem(b_{i−1}, b_{i}). It is not difficult though tedious to track down these coefficients in some form; but it is another matter to present them in a useful form. It is hardly obvious that these coefficients bear simple relations to the principal pseudo-subresultant coefficients, but this insight comes from the simpler case of indeterminate coefficients (Habicht’s theorem, see exercise below). These relations, combined with the Block Structure Theorem, constitutes the Subresultant Structure Theorem which we will prove.

We begin with an analogue to Habicht’s theorem.

Theorem 10 (Pseudo Habicht’s theorem) Let (S_{m},…, S_{0}) be a pseudo-subresultant chain, and let (c_{m},…, c_{0}) be the corresponding sequence of principal pseudo-subresultant coefficients. If S_{k} is regular (1 ≤ k ≤ m) then

S_{i} = c_{k}^{−2(k−i−1)}psres_{i}(S_{k}, S_{k−1}), i = 0,…, k − 1.

Proof. We use induction on k. If k = m then the result is true by definition (recall c_{m} = 1). Let P = S_{m}, Q = S_{m−1}, n = deg Q, a = lead(P) and b = lead(Q). So S_{n} is the next regular pseudo-subresultant. Unfortunately, the argument is slightly different for k = n and for k < n.

CASE k = n:

1. The Basic Lemma implies

S_{n} = (ab)^{(m−n−1)}Q, S_{n−1} = (−a)^{(m−n−1)}prem(P, Q).

2. Taking coefficients of S_{n}, we get c_{n} = a^{m−n−1}b^{m−n}.

3. From the Basic Lemma (19),

a^{−(m−n−1)}b^{(m−n+1)(n−i−1)}(−1)^{−(n−i)(m−i)}S_{i}
= psres_{i}(Q, prem(P, Q)),  i = 0,…, n − 1
= psres_{i}((ab)^{−(m−n−1)}S_{n}, (−a)^{−(m−n−1)}S_{n−1})

(substituting for Q, prem(P, Q))

= (ab)^{−(m−n−1)(n−i−1)}(−a)^{−(m−n−1)(n−i)}psres_{i}(S_{n}, S_{n−1}).
S_{i} = a^{−2(m−n−1)(n−i−1)}b^{−2(m−n)(n−i−1)}psres_{i}(S_{n}, S_{n−1})
= c_{n}^{−2(n−i−1)}psres_{i}(S_{n}, S_{n−1}).

CASE k < n: We now assume the lemma is true for k. Let k′ = deg(S_{k−1}). If k′ = −∞, then the lemma is true since all pseudo-subresultants S_{i} following S_{k} must vanish because by inductive hypothesis, S_{i} ∼ psres_{i}(S_{k}, S_{k−1}). Hence assume k′ ≥ 0. By the Block Structure Theorem, we know that S_{k′} is the next regular pseudo-subresultant following S_{k}. So inductively we must prove that

S_{i} = c_{k′}^{−2(k′−i−1)}psres_{i}(S_{k′}, S_{k′−1}), (i = 0,…, k′ − 1).

1. We have

c_{k}^{2(k−k′−1)}S_{k′} = psres_{k′}(S_{k}, S_{k−1}),  (by induction)
= (c_{k}c_{k−1})^{k−k′−1}S_{k−1},  (Basic Lemma).
S_{k−1} = (c_{k}c_{k−1}^{−1})^{k−k′−1}S_{k′}.

2. Taking coefficients,

c_{k′} = c_{k}^{−(k−k′−1)}c_{k−1}^{k−k′}.

3. Again,

c_{k}^{2(k−k′)}S_{k′−1} = psres_{k′−1}(S_{k}, S_{k−1}),  (by induction)
= (−c_{k})^{k−k′−1}prem(S_{k}, S_{k−1}),  (by equation (20)).
prem(S_{k}, S_{k−1}) = (−c_{k})^{k−k′+1}S_{k′−1}.

4. Substituting the indicated expressions for S_{k}, S_{k−1}, c_{k′}:

c_{k}^{2(k−i−1)}S_{i}

= psres_{i}(S_{k}, S_{k−1}),  (by induction)
= c_{k}^{k−k′−1}c_{k−1}^{−(k−k′+1)(k′−i−1)}(−1)^{(k−i)(k′−i)}psres_{i}(S_{k−1}, prem(S_{k}, S_{k−1})),  (Basic Lemma).
= c_{k}^{k−k′−1}c_{k−1}^{−(k−k′+1)(k′−i−1)}(−1)^{(k−i)(k′−i)}psres_{i}((c_{k}c_{k−1}^{−1})^{k−k′−1}S_{k′}, (−c_{k})^{k−k′+1}S_{k′−1})
= c_{k}^{2(k′−i)(k−k′)}c_{k−1}^{−2(k−k′)(k′−i−1)}psres_{i}(S_{k′}, S_{k′−1}),  (more manipulations).
S_{i} = (c_{k})^{2(k−k′−1)(k′−i−1)}(c_{k−1})^{−2(k−k′)(k′−i−1)}psres_{i}(S_{k′}, S_{k′−1})
= (c_{k′})^{−2(k′−i−1)}psres_{i}(S_{k′}, S_{k′−1}),  (as desired).

Q.E.D.

It is straightforward to infer:

Theorem 11 (Pseudo-Subresultant Structure Theorem) Let (S_{m},…, S_{0}) be a pseudosubresultant chain, and let (a_{m},…, a_{0}) be the corresponding sequence of leading coefficients. This chain is block-structured such that if S_{k}, S_{k′} are two consecutive regular pseudosubresultants in this sequence (m ≥ k > k′ > 0) then:

S_{k′} = \{ \begin{matrix}(a_{k}a_{k−1})^{k−k′−1}S_{k−1} & if k = m, \\ (a_{k}^{−1}a_{k−1})^{k−k′−1}S_{k−1} & if k < m. \end{matrix}  (21)

S_{k′−1} = \{ \begin{matrix}(−a_{k})^{k−k′−1}prem(S_{k}, S_{k−1}) & if k = m, \\ (−a_{k})^{−(k−k′+1)}prem(S_{k}, S_{k−1}) & if k < m. \end{matrix}  (22)

Finally, we transfer the result from pseudo-subresultants to subresultants:

Theorem 12 (Subresultant Structure Theorem) Let (R_{m},…, R_{0}) be a subresultant chain, and let (c_{m},…, c_{0}) be the corresponding sequence of principal subresultant coefficients. This chain is block-structured such that if R_{k}, R_{k′} are two consecutive regular subresultants in this sequence (m ≥ k > k′ > 0) then:

R_{k′} = (c_{k}^{−1}lead(R_{k−1}))^{k−k′−1}R_{k−1},  (23)
R_{k′−1} = (−c_{k})^{k−k′+1}prem(R_{k}, R_{k−1})  (24)

Proof. Let (S_{m},…, S_{0}) be the corresponding pseudo-subresultant chain with leading coefficients (a_{m},…, a_{0}). Write a instead of a_{m} and let n = deg S_{m−1}. We exploit the relation

R_{i} = \{ \begin{matrix}a^{−(m−n−1)}S_{i} & if i = 0,…, m − 2 \\ S_{i} & if i = m − 1, m. \end{matrix}

Hence, if R_{i} is regular and i < m, we have

c_{i} = a^{−(m−n−1)}a_{i}.

From the Pseudo-Subresultant Structure Theorem (21),

a^{m−n−1}R_{k′} = S_{k′} = \{ \begin{matrix}(a_{k}a_{k−1})^{k−k′−1}S_{k−1} & if k = m \\ (a_{k}^{−1}a_{k−1})^{k−k′−1}S_{k−1} & if k < m \end{matrix}

§8. Correctness  Lecture III  Page 18

= \{ \begin{matrix}(a_{k}a_{k−1})^{k−k′−1}R_{k−1} & if k = m \\ (a_{k}^{−1}a_{k−1})^{k−k′−1}a^{m−n−1}R_{k−1} & if k < m \end{matrix}

R_{k′} = \{ \begin{matrix}(a_{k−1})^{k−k′−1}R_{k−1} & if k = m \\ (a_{k}^{−1}a_{k−1})^{k−k′−1}R_{k−1} & if k < m \end{matrix}
= (c_{k}^{−1}lead(R_{k−1}))^{k−k′−1}R_{k−1}  (if k = m − 1 then n = m − 1)

We leave the derivation for R_{k′−1} to the reader. Q.E.D.

So equation (23) gives the coefficients of similarity between the top and base polynomials in each block.

Exercise 7.1: Verify the Pseudo-Subresultant Structure Theorem, and complete the proof for the Subresultant Structure Theorem.

Exercise 7.2: Show that the problem of computing the GCD of two integer polynomials is in the complexity class NC = NC_{B}.

Exercise 7.3: Prove that if P, Q have indeterminate coefficients as in (14), then i) sres_{m−2}(P, Q) = prem(P, Q).

ii) For k = 0,…, m − 3,
b_{m−1}^{2(m−k−2)}sres_{k}(P, Q) = sres_{k}(Q, prem(P, Q)).

iii) [Habicht’s theorem] If S_{i} = sres_{i}(P, Q) and c_{i} = psc_{i}(P, Q), for j = 1,…, m − 1,
c_{j+1}^{2(j−k)}S_{k} = sres_{k}(S_{j+1}, S_{j}),  (k = 0,…, j − 1)  (25)
c_{j+1}^{2}S_{j−1} = prem(S_{j+1}, S_{j}).  (26)

§8. Correctness of the Subresultant PRS Algorithm

We relate the subresultant PRS

(P_{0}, P_{1},…, P_{k})  (27)

described in §4 (equations (9) and (10)) to the subresultant chain

(R_{m}, R_{m−1},…, R_{0})  (28)

where R_{m} = P_{0} and R_{m−1} = P_{1}. (Note that the convention for subscripting PRS’s in increasing order is opposite to that for subresultant chains.) The basic connection, up to similarity, is already captured in corollary 9. The real task is to determine the coefficients of similarity between the top of B_{i} and P_{i}. As a matter of fact, we have not even established that members of the Subresultant PRS is in D[X]. This is captured in the next theorem. We recall that the computation of P_{i} involves the following two auxiliary sequences

(β_{1},…, β_{k−1}), (ψ_{0},…, ψ_{k−1})

as given in (9) and (10), where

δ_{i} = deg P_{i} − deg P_{i+1}, a_{i} = lead(P_{i}).

Theorem 13 (Subresultant PRS Correctness) Let T_{i}, U_{i} be the top and base polynomials of block B_{i}, where (B_{0},…, B_{k}) are the non-zero blocks of our subresultant chain.

a) ψ_{i} = lead(U_{i}), i = 1,…, k. (Note that ψ_{0} = 1.)

b) The sequence (T_{0},…, T_{k}) is precisely the subresultant PRS (P_{0},…, P_{k}).

Proof. We use induction on i. BASIS: Part a): it is easy to verify from equation (23) that lead(U_{1}) = ψ_{1} (where ψ_{1} = (a_{1})^{δ_{0}}. Part b): By definition, T_{i} = P_{i} for i = 0, 1. Using the Subresultant Structure Theorem,

P_{2} = \frac{prem(P_{0}, P_{1})}{β_{1}} (by definition)
= \frac{prem(T_{0}, T_{1})}{β_{1}}
= \frac{(−1)^{δ_{0}+1}T_{2}}{(−1)^{δ_{0}+1}}  (from (24))
= T_{2}.
P_{3} = \frac{prem(P_{1}, P_{2})}{β_{2}}
= \frac{prem(T_{1}, T_{2})}{(−1)^{δ_{1}+1}ψ_{1}^{δ_{1}}a_{1}}
= \frac{prem(U_{1}, T_{2})}{(−1)^{δ_{1}+1}ψ_{1}^{δ_{1}}a_{1}^{δ_{0}}}  (since U_{1} = a_{1}^{δ_{0}−1}T_{1})

= \frac{(−ψ_{1})^{δ_{1}+1}T_{3}}{(−1)^{δ_{1}+1}ψ_{1}^{δ_{1}}a_{1}^{δ_{0}}}  (since prem(U_{1}, T_{2}) = (−ψ_{1})^{1+δ_{1}}T_{3})
= T_{3}  (since ψ_{1} = a_{1}^{δ_{0}}).

INDUCTION: Let i ≥ 2 and assume that part a) is true for i − 1 and part b) is true for i and i + 1. Rewriting equation (23) from the Subresultant Structure Theorem in the present terminology:

lead(U_{i−1})^{δ_{i−1}−1}U_{i} = lead(T_{i})^{δ_{i−1}−1}T_{i}.  (29)

By inductive hypothesis, (ψ_{i−1})^{δ_{i−1}−1}U_{i} = lead(P_{i})^{δ_{i−1}−1}P_{i}. Comparing leading coefficients, (ψ_{i−1})^{δ_{i−1}−1}lead(U_{i}) = a_{i}^{δ_{i−1}}. Hence,

lead(U_{i}) = \frac{a_{i}^{δ_{i−1}}}{ψ_{i−1}^{δ_{i−1}−1}} = ψ_{i},

extending the induction for part a). For part b), again rewrite the equation (24) from the Subresultant Structure Theorem:

(−lead(U_{i}))^{δ_{i}+1}T_{i+2} = prem(U_{i}, T_{i+1}).  (30)

Then

β_{i+1}P_{i+2} = prem(P_{i}, P_{i+1})
= prem(T_{i}, T_{i+1}) (by inductive hypothesis.)

= prem(\frac{lead(U_{i−1})^{δ_{i−1}−1}}{lead(T_{i})^{δ_{i−1}−1}} U_{i}, T_{i+1}) (by (29))

= \frac{ψ_{i−1}^{δ_{i−1}−1}}{a_{i}^{δ_{i−1}−1}} prem(U_{i}, T_{i+1}) (by inductive hypothesis)

= \frac{ψ_{i−1}^{δ_{i−1}−1}}{a_{i}^{δ_{i−1}−1}} (−ψ_{i})^{δ_{i}+1}T_{i+2} (by (30) and part a))
= β_{i+1}T_{i+2}.

So T_{i+2} = P_{i+2}, extending the induction for part b). Q.E.D.

Part a) in the above lemma may be reexpressed:

Corollary 14 The sequence of ψ_{i}’s in the Subresultant PRS Algorithm on input P_{0}, P_{1} are the principal subresultant coefficients of the subresultant chain of P_{0}, P_{1}.

This confirms the original claim that ψ_{i} ∈ D and that (being determinants) their sizes are polynomially bounded.

References

[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974.

[2] W. S. Brown. The subresultants PRS algorithm. ACM Transaction on Mathematical Software, 4:237–249, 1978.

[3] B. Buchberger, G. E. Collins, and R. Loos (eds.). Computer Algebra. Springer-Verlag, 1983.

[4] G. E. Collins. Subresultants and reduced polynomial remainder sequences. Journal of the ACM, 14:128–142, 1967.

[5] G. E. Collins. Computer algebra of polynomials and rational functions. American Mathematical Monthly, 80:725–755, 1975.

[6] Harold M. Edwards. Divisor Theory. Birkhauser, Boston, 1990.

[7] Chung-jen Ho and Chee Yap. Polynomial remainder sequences and theory of subresultants. Report 319, NYU-Courant Institute, Robotics Laboratory, 1987.

[8] Jacob T. Schwartz and Micha Sharir. On the piano movers’ problem: II. General techniques for computing topological properties of real algebraic manifolds. Advances in Appl. Math., 4:298–351, 1983.