§1. Hilbert Basis Theorem  Lecture XI  Page 1

Lecture XI Elimination Theory

Algebraic geometry has been reformulated several times and, by Dieudonné’s account [6], contains seven epochs^{1} leading to the present time. In an earlier incarnation, elimination theory and more generally, invariant theory, played a central role. Early invariant theory relies on constructive methods, as epitomized by the “master computer” Gordan. Hilbert’s non-constructive proof^{2} in 1888 of his basis theorem is said to kill invariant theory as an active area. Nevertheless, Emmy Noether wrote a thesis on the subject in 1907 under Gordon. Recent interest in constructive methods have revived interest in these topics. See Sturmfels [27] for a modern computational perspective on invariant theory. This lecture concerns elimination theory. Elimination theory is the study of conditions on coefficients of a system of polynomials that are necessary and sufficient for the system to have a solution. We are familiar with this idea in two important special cases:

• When there are n linear homogeneous equations in n unknowns, the vanishing of the determinantal function on the coefficients is a necessary and sufficient condition for solvability.

• When we have two univariate polynomials, the vanishing of the Sylvester resultant of these polynomials gives a necessary and sufficient condition for solvability.

These are both special cases of the fact that we can define a “resultant polynomial” R for any system Σ of n homogeneous polynomials in n variables such that R is a polynomial in the coefficients of these polynomials, and the vanishing of R is a necessary and sufficient condition for the solvability of the system (we prove this in §6). Elimination theory is useful in other unexpected ways. For instance, if F (x, y, λ) is a family of plane curves parameterized by λ, then the envelop curve of the family can be obtained by eliminating the parameter from the equations F = 0 and ∂F/∂λ = 0. This is a form of the implicitization problem, to compute a system of equations that defines an algebraic set given in some other form. The converse problem is the parameterization problem (or the construction of “generic solutions”, see §4).

The results in this lecture are updates of very classical work that goes back to Macaulay, Hurwitz and others. In recent years, Canny [5, 4] revisited this classical literature, showing its usefulness for efficient algorithms. This lecture is clearly influenced by his work. Because the classical background is scattered and perhaps unfamiliar to the modern reader, we have tried to be self-contained in this exposition (except in §10,11). There is a newer body of work on sparse elimination theory (e.g., Sturmfels [28], Gelfand, Kapranov and Zelevinsky [9], Emiris [8]) which we regretably omit. Furthermore, there has been a large output of recent material on techniques for solving algebraic systems.

Most results in this lecture pertain to a domain D (sometimes UFD or Noetherian). Its quotient field is denoted Q_{D}. We use X to denote the set of indeterminates {X_{1}, …, X_{n}}.

§1. Hilbert Basis Theorem

1The current interest in efficient computation seems to represent yet a different epoch.

2Which led Gordan to his famous remark “this is not mathematics, this is theology”. Gordan later admitted that “theology has its uses”. See Kline [12] for a fuller account of the period.

Hilbert proved three fundamental results that can be regarded as the starting point of modern algebraic geometry: the Basis Theorem, the Zero Theorem (Nullstellensatz) and the Syzygy Theorem. This section proves the Basis Theorem for polynomial rings, and a similar theorem for modules. The Zero Theorem is treated in the next section (see §XII.8 for a description of the Syzygy Theorem).

Let S ⊆ R[X] be an arbitrary set of polynomials, R is a ring. A basis for S is any subset B ⊆ S such that S ⊆ Ideal(B) ⊆ R[X]. Alternatively, if B is a basis if each f ∈ S can be expressed as a linear combination of elements of B:

f = ∑_{i=1}^{m} f_{i}b_{i}, (f_{i} ∈ R[X], b_{i} ∈ B).

Note that S is not necessarily an ideal. In case S is an ideal, modern terminology prefers to call B a generator set for S. A basis or generator set is finite if it has finitely many elements. A ring R is Noetherian if every ideal in R has a finite generator set. For example, if R is a field then it is Noetherian since R has only two ideals (0) and (1). It is also easy to see that ℤ is Noetherian.

Theorem 1 (Hilbert Basis Theorem) If R is Noetherian then R[X] is Noetherian.

Proof. It is enough^{3} to prove this for X = {X}. The theorem then follows by induction on the number of variables in X: if R[X_{1}, …, X_{n−1}] is Noetherian then so is R[X_{1}, …, X_{n−1}][X_{n}]. So we want to show that any given ideal I ⊆ R[X] has a finite basis. Let us construct a sequence of polynomials

f_{1}, f_{2}, f_{3}, …,

where f_{1} is a smallest degree polynomial in I, and in general f_{i+1} is a smallest degree polynomial in I \ Ideal(f_{1}, …, f_{i}). The result is proved if this process stops in a finite number of steps, i.e., when I = Ideal(f_{1}, …, f_{i}) for some i. So by way of contradiction, assume that the sequence f_{1}, f_{2}, …, is infinite. Consider the corresponding sequence

a_{1}, a_{2}, a_{3}, …,

where a_{i} = leadf_{i}. Since R is Noetherian, there exists a first value a_{k+1} such that

a_{k+1} ∈ Ideal(a_{1}, …, a_{k}) ⊆ R.  (1)

Hence a_{k+1} has the form

a_{k+1} = ∑_{j=1}^{k} c_{j}a_{j} (c_{j} ∈ R).

If the degree of f_{j} is n_{j} then n_{1} ≤ n_{2} ≤ n_{3} ≤ . . .. Note that polynomial

g:= ∑_{j=1}^{k} c_{j}X^{n_{k+1}−n_{j}}f_{j}

has leading coefficient a_{k+1}. Hence the degree of f_{k+1} − g is less than n_{k+1}. Since f_{k+1} − g ∈ I \ Ideal(f_{1}, …, f_{k}), this means f_{k+1} is not of minimum degree in I \Ideal(f_{1}, …, f_{k}), a contradiction.

Q.E.D.

3This proof of Heidrun Sarges (1976), like the original proof of Hilbert, is non-constructive. Hilbert’s proof was a tour de force in his time, much to the chagrin of constructivists like Gordon and Kronecker. Gordon, by involved arguments, only managed to construct finite bases for ideals in two variables. Some historians of mathematics have pin-pointed this proof as the genesis of the modern tendency to use non-constructive proofs. Hilbert subsequently returned to his proof to make it constructive [24]. For a modern constructive treatment see [27].

Corollary 2 If R is Noetherian, then every set S ⊆ R[X] has a finite basis.

Proof. By the theorem, Ideal(S) has a finite basis B′ ⊆ Ideal(S). Each b′ ∈ B′ is a linear combination of some finitely many elements of S. Hence there is a finite subset B ⊆ S such that each b′ ∈ B′ is a linear combination of B. Clearly B is a basis for S. Q.E.D.

This corollary is the original basis theorem shown by Hilbert. Modern texts usually only treat the case where S is an ideal. In an application below, we need this more general form.

The basis theorem has the following implication for solving polynomial equations in D[X_{1}, …, X_{n}] where D is a Noetherian domain. Note that if B is a basis for a set S ⊆ D[X_{1}, …, X_{n}] then (x_{1}, …, x_{n}) ∈ \overline{D}^{n} is a zero of S iff (x_{1}, …, x_{n}) is a zero of B. So it is without loss of generality to solve only finite systems of equations.

We now prove Hilbert’s basis theorem for modules. Let R be a ring and M an R-module. If x ∈ M, then xR denotes the set {xa : a ∈ R}. If M_{i} ⊆ M (i ∈ J where J is an index set) then ∑_{i∈J} M_{i} denotes the set of all sums of the form ∑_{i∈J} x_{i} where x_{i} ∈ M_{i} or x_{i} = 0, and moreover only finitely many x_{i}’s are non-zero. Say a set S ⊆ M generates M if ∑_{x∈S} xR = M. M is finitely generated if it has a finite set S as generator. M is Noetherian if every R-submodule of M is finitely generated. (Note that the concept of Noetherian modules generalizes the concept of Noetherian rings.)

Let us illustrate these definitions as well as the theorem to be stated: R = ℤ is a Noetherian ring and M = ℤ^{n} is a ℤ-module. Note that ℤ-submodule of M is also called a lattice (§VIII.1). Clearly, M is finitely generated. The next theorem implies that every ℤ-submodule of M is finitely generated.

One more definition. For R-modules M and N, a map φ : M → N is an R-module homomorphism if φ(x + y) = φ(x) + φ(y), φ(ax) = aφ(x) for all x, y ∈ M, a ∈ R.

Theorem 3 (Hilbert’s Basis Theorem for modules) If R is a Noetherian ring and M is a finitely generated R-module then M is Noetherian.

Proof. Let M = x_{1}R + ⋯ + x_{n}R. Then we have a canonical R-homomorphism

φ : R^{n} ⟶ M

where (a_{1}, …, a_{n}) ∈ R^{n} is mapped to ∑_{i=1}^{n} a_{i}x_{i} ∈ M. Let N ⊆ M be any submodule. We have to show N has a finite set of generators. Let

U = {a ∈ R^{n} : φ(a) ∈ N}.

One checks that U is a submodule of R^{n}. If U = a_{1}R + ⋯ + a_{m}R (a_{i} ∈ R^{n}) then N = φ(a_{1})R + ⋯ + φ(a_{n})R. So it suffices to show U is finitely generated. We first observe that the set of first components of members of U form an ideal I in R. Since R is Noetherian, I = (u_{1}, …, u_{k}) for some u_{1}, …, u_{k}. Pick a_{1}, …, a_{k} ∈ U such that the first component of a_{i} is u_{i} (i = 1, …, k). Let V ⊆ U be the set of those n-vectors with zero as first component. Then

U = a_{1}R + ⋯ + a_{k}R + V.

But V is isomorphic to a submodule of R^{n−1}. If n = 1, then we are done. Otherwise by induction, V has a finite set of generators and so does U. Q.E.D.

§2. Hilbert Nullstellensatz  Lecture XI  Page 4

Exercises Exercise 1.1: The following are standard facts:

(i) For I ⊆ R an ideal in a ring R, I is maximal (resp., prime, primary) iff R/I is a field (resp., domain, a ring in which all zero divisors are nilpotent). An element x is nilpotent if some power x^{m} is zero. (ii) An ideal is said to be irreducible if it is not the proper intersection of two ideals. Show that prime ideals are irreducible and under the ascending chain condition, irreducible ideals are primary. □

Exercise 1.2:

(i) The homomorphic image of a Noetherian ring is Noetherian.

(ii) Every non-unit in a Noetherian domain is a product of irreducible elements. □

§2. Hilbert Nullstellensatz

Let D be a fixed Noetherian domain . This section gives several forms of the Nullstellensatz of Hilbert for D. Basically, the Nullstellensatz is a theorem about the existence of zeros in the algebraic closure \overline{D} of D. Accordingly, for a set S ⊆ D[X_{1}, …, X_{n}], a zero of S is an element (x_{1}, …, x_{n}) ∈ \overline{D}^{n} such that p(x_{1}, …, x_{n}) = 0 for each polynomial p ∈ S. We also say S vanishes at (x_{1}, …, x_{n}). Denote the set of zeros of S by

Zero(S) ⊆ \overline{D}^{n}.

We begin with what is known as the field-theoretic version of Hilbert’s Nullstellensatz [14, 15]. By way of motivation, note that if D(ξ_{1}, …, ξ_{n}) is algebraic extension of D then D(ξ_{1}, …, ξ_{n}) is obtained as a ring adjunction of the quotient field Q_{D} of D, i.e., D(ξ_{1}, …, ξ_{n}) = Q_{D}[ξ_{1}, …, ξ_{n}]. We show the converse.

Theorem 4 (Nullstellensatz – field-theoretic form) Let D be a Noetherian UFD and E a field extension of D. If E = Q_{D}[ξ_{1}, …, ξ_{n}] for some ξ_{1}, …, ξ_{n}, then E is algebraic over D.

We first prove two lemmas.

Lemma 5 (Artin-Tate) Let R ⊆ S ⊆ T be rings, R Noetherian and T be finitely generated as an S-module. If T is finitely generated as a ring over R, i.e., T = R[ξ_{1}, …, ξ_{n}], then S is finitely generated as a ring over R.

Proof. Since T is a finitely generated S-module, let ω_{1}, …, ω_{m} ∈ T such that

T = Sω_{1} + Sω_{2} + ⋯ + Sω_{m}.  (2)

We may assume ξ_{1}, …, ξ_{n} is contained among ω_{1}, …, ω_{m}. Let

M = {a_{k}^{i,j} : i, j, k = 1, …, m}

be the multiplication table of ω_{1}, …, ω_{m}, that is,

ω_{i}ω_{j} = ∑_{k=1}^{m} a_{k}^{i,j}ω_{k}.

We may assume M ⊆ S because of (2). Consider the ring

S′:= R[M] ⊆ S.

From T = R[ξ_{1}, …, ξ_{n}] we conclude that T is generated as an R-module by the set of power products of ξ_{1}, …, ξ_{n}. But since the multiplication table of ξ_{1}, …, ξ_{n} is in S′ we get

T = S′ω_{1} + S′ω_{2} + ⋯ + S′ω_{m}.

Since R is Noetherian, Hilbert’s basis theorem (for polynomials) implies S′ is Noetherian. By Hilbert’s basis theorem (for modules) T is a Noetherian S′-module, and since S is a S′-submodule of T, S must be finitely generated over S′: for some {u_{1}, …, u_{t}} ∈ T,

S = S′u_{1} + S′u_{2} + ⋯ + S′u_{t}.

Hence S = R[M, u_{1}, u_{2}, …, u_{t}]. Q.E.D.

Lemma 6 Let S = D(Z_{1}, …, Z_{t}) be a rational function field over D with t ≥ 1 indeterminates. Then S is not finitely generated as a ring over Q_{D}.

Proof. Suppose S = Q_{D}[ξ_{1}, … ξ_{n}] where ξ_{i} = \frac{f_{i}(Z_{1},...,Z_{t})}{g_{i}(Z_{1},...,Z_{t})} and f_{i}, g_{i} ∈ D[Z_{1}, …, Z_{t}], (i = 1, …, n).

Then each element of Q_{D}[ξ, …, ξ_{n}] has the form \frac{f}{g} = \frac{f(Z_{1},...,Z_{t})}{g(Z_{1},...,Z_{t})} where

g(Z_{1}, …, Z_{t}) = a ∏_{i=1}^{n} g_{i}^{e_{i}}(Z_{1}, …, Z_{t}), a ∈ D, e_{i} ≥ 0.  (3)

There are infinitely many non-associated irreducible polynomials in Q_{D}[Z_{1}, …, Z_{t}] (see appendix B). Pick an irreducible polynomial p ∈ Q_{D}[Z_{1}, …, Z_{t}] that does not divide any g_{i}. Then 1/p ∈ S implies that it has a representation of the form f/g where g is given by (3). From 1/p = f/g, we obtain g = f ·p. Hence p divides some g_{i}, since Q_{D}[Z_{1}, …, Z_{t}] is a UFD. This contradicts our choice of p. Q.E.D.

We now prove the field version of the Nullstellensatz: If E = Q_{D}[ξ_{1}, …, ξ_{n}] is not algebraic, let Z_{1}, …, Z_{t} (t ≥ 1) be the maximal subset of {ξ_{1}, …, ξ_{n}} that is algebraically independent over Q_{D}. Set S = Q_{D}(Z_{1}, …, Z_{t}) = D(Z_{1}, …, Z_{t}). Then E is a finite algebraic extension of S. Since S is a field, E is finitely generated as an S-module. Applying the first lemma using R = D, S = D(Z_{1}, …, Z_{t}) and T = E = Q_{D}[ξ_{1}, …, ξ_{n}] implies D(Z_{1}, …, Z_{t}) is finitely generated as a ring over Q_{D}. This contradicts the second lemma, completing the proof.

Theorem 7 (Nullstellensatz – weak form) An ideal I ⊆ D[X_{1}, …, X_{n}] has no zeros iff I contains a non-zero element of D.

Proof. Clearly if I contains a non-zero element a ∈ D then I has no zero. Conversely, if I ∩D = {0}, we must show that Zero(I) is non-empty. We may (by the maximum principle) assume I is maximal. Then E = D[X]/I is a field. If b ∈ D[X] maps to \overline{b} under the canonical homomorphism D[X] ⟶ E then for a, b ∈ D, a ≠ b implies \overline{a}−\overline{b} ≠ 0 (otherwise a−b ∈ I). So we may assume D ⊆ E and indeed, Q_{D} ⊆ E. Since E = Q_{D}[\overline{X}_{1}, …, \overline{X}_{n}], the previous theorem shows that E is algebraic over D. Thus we may assume that E ⊆ \overline{D}. Now the canonical homomorphism takes p(X_{1}, …, X_{n}) ∈ D[X] to

\overline{p(X_{1}, X_{2}, …, X_{n})} = p(\overline{X}_{1}, …, \overline{X}_{n}).

Hence p(\overline{X}_{1}, …, \overline{X}_{n}) = 0 iff \overline{p(X_{1}, X_{2}, …, X_{n})} = 0 iff p(X_{1}, …, X_{n}) ∈ I. Hence (\overline{X}_{1}, …, \overline{X}_{n}) ∈ Zero(I). Q.E.D.

This theorem is equivalent to an apparently stronger version:

Theorem 8 (Nullstellensatz – strong form) Let I ⊆ D[X_{1}, …, X_{n}] be an ideal and p ∈ D[X_{1}, …, X_{n}]. Then p vanishes at all the zeros of I iff there is an m ≥ 0 and a non-zero a ∈ D such that

a · p^{m} ∈ I.

The strong Nullstellensatz implies the weak form: to show the non-trivial direction of the weak Nullstellensatz, suppose Zero(I) is empty. Then (vacuously) 1 vanishes at all the zeros of I. The strong form then implies that a = a · 1^{m} ∈ I for some m ≥ 0 and non-zero a ∈ D.

Conversely, the weak Nullstellensatz implies the strong form: again, in the nontrivial direction, we assume that p ∈ D[X] vanishes at Zero(I). Suppose I = Ideal(f_{1}, …, f_{r}). Using the “trick of Rabinowitz”, introduce a new variable Z and let

g:= 1 − Z · p.

Then the ideal (f_{1}, …, f_{r}, g) has no zeros since g will not vanish at any zero of f_{1}, …, f_{r}. Hence the weak Nullstellensatz implies the existence of some nonzero a ∈ D ∩ Ideal(f_{1}, …, f_{r}, g). Let

a = ∑_{i=1}^{r} α_{i}f_{i} + β(1 − Zp)

for suitable α_{i}, β ∈ D[X_{1}, …, X_{n}, Z]. Substituting Z = \frac{1}{p}, we get:

a = ∑_{i=1}^{r} α′_{i}f_{i}

where each α′_{i} ∈ D(X_{1}, …, X_{n}) is a rational function whose denominator is some power of p. Multiplying by a suitable power m ≥ 0 of p, we get

a · p^{m} = ∑_{i=1}^{r}(α′_{i}p^{m})f_{i}

where α′_{i}p^{m} ∈ D[X_{1}, …, X_{n}]. Thus a · p^{m} ∈ I, proving the non-trivial direction of the strong Nullstellensatz.

Quantitative Nullstellensatz. In recent years, starting from the work of Brownawell [3], “quantitative forms” of the Nullstellensatz began to appear. Such results gives explicit bounds on the number m appearing in the strong Nullstellensatz. Essentially the best possible bound is from Kollár [13] (see also [26]). Dubé [7] gives a purely combinatorial proof of similar bounds^{4}. We quote without proof the bound of Dubé (somewhat simplified).

Theorem 9 (Nullstellensatz – quantitative form) Let p vanish at all the zeros of an ideal I ⊆ D[X_{1}, …, X_{n}]. If I is generated by a set of polynomials of degrees at most d then there exists a ∈ D such that a · p^{N} ∈ I where

N = 13d^{n}.

4The bound of Dubé’s applies more generally to ideals generated by prime sequences.

§3. Specializations  Lecture XI  Page 7

Let the “Nullstellensatz bound”

N(n, d)  (4)

to be the least value for N for which this theorem holds. Thus N(n, d) ≤ 13d^{n}. We remark that Kollár’s formulation of the theorem generally gives better bounds (without the constant factor 13) but it is less suited for our purpose of defining N(n, d) because he has a technical requirement that the generators of I have degrees not equal to 2. The following easy extension of the strong Nullstellensatz will be useful:

Theorem 10 (Nullstellensatz – extended form) Let A_{1}, …, A_{r} ∈ D[X_{1}, …, X_{n}] be polynomials such that each A_{i} vanishes at all the zeros of an ideal I ∈ D[X_{1}, …, X_{n}]. If I is generated by polynomials of degrees at most d then there exists a non-zero a ∈ D such that

a · A_{1}^{e_{1}}A_{2}^{e_{2}} ⋯ A_{r}^{e_{r}} ∈ I

whenever ∑_{i=1}^{r} e_{i} ≥ 1 + r(N − 1), N = N(n, d) and e_{i} ≥ 0.

Proof. By definition of N = N(n, d), for each i, we have a_{i}A_{i}^{N} ∈ I for some non-zero a_{i} ∈ D. Let a = ∏_{i=1}^{r} a_{i}. If ∑_{i=1}^{r} e_{i} ≥ 1 + r(N − 1) then some e_{i} ≥ N and so a_{i}A_{i}^{e_{i}} ∈ I. Hence a · A_{1}^{e_{1}}A_{2}^{e_{2}} ⋯ A_{r}^{e_{r}} ∈ I.

Q.E.D.

Exercises

Exercise 2.1: (Corollaries to Hilbert’s Nullstellensatz)

(i) If D = \overline{D} then I is a maximal ideal iff I = Ideal(X_{1} − ξ_{1}, …, X_{n} − ξ_{n}) where ξ_{i} ∈ D. (ii) D[X_{1}, …, X_{n}]/I is a finite field extension of D iff I is a maximal ideal. (iii) Let Ideal be the map taking a set V ⊆ 𝔸^{n}(\overline{D}) = \overline{D}^{n} to the set

Ideal(V) = {f ∈ D[X_{1}, …, X_{n}] : f vanishes on V }.

Show that Ideal is a bijection between algebraic sets and radical ideals. □

Exercise 2.2: Show an exponent m in the Strong Nullstellensatz that depends only on I, and not on p. HINT: show that (\sqrt{I})^{e} ⊆ I for some e and p ∈ \sqrt{I}. □

Exercise 2.3: (Open) Assume D = ℤ. Obtain sub-primitive recursive bounds on |a| in the strong or quantitative form of the Nullstellensatz. NOTE: Mishra and Gallo (1992) show that there are primitive recursive bounds. □

§3. Specializations

The informal idea of specialization is that of “substitution for indeterminates quantities”. In most applications, this naive understanding suffices. But we wish to explore this concept in a more general setting. Specialization arises in three ways in solving systems of polynomial equations over D. In illustration, consider the system

F_{1} = F_{2} = 0  (5)

where F_{1}(X, Y, Z) = X − Y^{2} and F_{2}(X, Y, Z) = XY − Z are polynomials over D. We see that

(X, Y, Z) ⟶ (t^{2}, t, t^{3})  (6)

is a solution to the system (5), for any t ∈ \overline{D}. The “⟶” here means the right-hand quantities are substituted for the left-hand quantities. So (6) is a “specialization” of X, Y, Z. Next, suppose t is an indeterminate. Then we can express another important idea: solution (6) is the most general or “generic” solution to (5) in the following sense:

(i) For any “specialization” of t to a value α ∈ \overline{D}, the corresponding substitution (X, Y, Z) ⟶ (α^{2}, α, α^{3}) is a solution to (5). (ii) Moreover, every solution (α_{1}, α_{2}, α_{3}) ∈ \overline{D}^{3} of (5) can be obtained as in (i). The third way in which specialization arises is when we consider polynomials with indeterminate coefficients. We are interested in conditions under which specializations of these coefficients lead to solvability.

As discussed in Lecture 0, it is significant to ask where the solutions (α_{1}, α_{2}, α_{3}) come from. There are three natural cases: the α_{i}’s can come from D, or from its quotient field Q_{D}, or from the algebraic closure \overline{D}. These are, respectively, the Diophantine case, the rational case and the algebraic case of solving equations over D. The Nullstellensatz (§2) concerns the algebraic case. Following A. Weil, we may go beyond the algebraic case by asking for solutions in the universal field Ω of D. By definition Ω = Ω_{D} is defined to be

Ω_{D} = \overline{D}(t_{1}, t_{2}, …)

where the t_{i}’s is an infinite set of indeterminates. Call this the universal case of solving equations over D. Since within each normal context of discourse, we only have to deal with a finite number of these t_{i}’s, we may regard the infinite transcendence degree of Ω as a mere convenience. But the existence of transcendental elements in Ω allows us to accomplish more than the algebraic case: it affords the notion of a generic solution as seen in the above example.^{5} Finding generic solutions can be considered as another view of the parameterization problem, briefly noted in this lecture’s introduction.

As far as the existence of solutions goes, the universal case of solving polynomial equations does not add anything: a system of polynomial equations over D is solvable in \overline{D} iff it is solvable in Ω_{D}. This is because any transcendental solution can always be “specialized” to a non-trivial algebraic solution.

The concept of specialization. We formalize the above notions. In the following, let S ⊆ Ω. We write

D[S] and D(S)

to denote the smallest subring and subfield (respectively) of Ω containing D ∪ S. This is a natural extension of the standard notations, D[X] and D(X). Suppose

σ : S → Ω

is any function. We would like to extend σ into the canonical homomorphism

h_{σ} : D[S] → Ω

where, for each F (X_{1}, …, X_{n}) ∈ D[X] and x_{1}, …, x_{n} ∈ S,

h_{σ}(F (x_{1}, …, x_{n})) = F (σx_{1}, …, σx_{n}).

5Contemporary algebraic geometry often avoids the universal field, using instead the set of prime ideals of D[X_{1}, …, X_{n}] for Ω. But as in this example, the language of the universal field seems more intuitive and geometric.

But one must verify that h_{σ} is well-defined. A necessary condition is that σ(a) = a whenever a ∈ D. Clearly if h_{σ} were well-defined, it would be a homomorphism. In fact, it would be a D-homomorphism (i.e., it is the identity function when restricted to D).

Usually, S is a set of transcendental elements over D. (An element x is transcendental over D if F (x) ≠ 0 holds for any non-zero polynomial F (X) ∈ D[X].) If these transcendental elements are algebraically independent over D, meaning that F (x_{1}, …, x_{n}) ≠ 0 for any F (X_{1}, …, X_{n}) ∈ D[X_{1}, …, X_{n}] \ 0 and x_{1}, …, x_{n} ∈ S. In this case, we may call S a set of indeterminates and elements of S are called indeterminates. So the concept of an “indeterminate” is always relative to some such set S, which is often implicit. (This definition of indeterminates agrees with the usual informal uses of the term; of course, we have relied on this informal understanding in the earlier discussions.)

Example:

(i) If S is a set of indeterminates, h_{σ} is clearly well-defined for any σ.

(ii) S may contain algebraic relations among its members, as in our introductory example with S = {t, t^{2}, t^{3}}. (iii) S may even have algebraic elements. Consider D = ℝ and S = \{i\} (where i = \sqrt{−1}). The specialization which maps i to −i amounts to complex conjugation. (iv) Let S = {X, XY } where {X, Y } is a set of indeterminates. The map h_{σ} is well-defined provided σ(X) = 0 implies σ(XY) = 0.

Definition: Let S ⊆ Ω. An S-specialization (or simply, specialization) is a function σ : S → Ω such that for all F (X_{1}, …, X_{n}) ∈ D[X] (the X_{i} are variables) and for all x_{1}, …, x_{n} ∈ S,

F (x_{1}, …, x_{n}) = 0 ⟹ F (σx_{1}, …, σx_{n}) = 0.

We claim: h_{σ} is well-defined iff σ is a specialization. To show this in one direction, if F (x_{1}, …, x_{n}) = 0 and h_{σ}(F (x_{1}, …, x_{n})) ≠ 0, i.e., σ is not a specialization, then h_{σ}(0) is not well-defined. In the other direction, if σ is a specialization, we must show that for any F, G ∈ D[X], if F (x_{1}, …, x_{n}) = G(x_{1}, …, x_{n}) then h_{σ}(F (x_{1}, …, x_{n})) = h_{σ}(G(x_{1}, …, x_{n})). This is equivalent to showing that F (x_{1}, …, x_{n}) = 0 implies h_{σ}(F (x_{1}, …, x_{n})) = 0. But this is immediate since h_{σ}(F (x_{1}, …, x_{n})) = F (σ(x_{1}), …, σ(x_{n})) which equals 0 since σ is a specialization.

We may think of specializations as a type of ring homomorphism. We call h_{σ} the canonical σhomomorphism from D[S] to D[σ(S)] (or, to Ω). We say that h_{σ}(x) is the specialization of x (under σ). Since h_{σ} is an extension of σ, we often continue to use ‘σ’ instead of ‘h_{σ}’. In case σ(S) = S, we have a permutation (the older literature calls it a ‘substitution’). If σ(S) ⊆ D we call σ a ground specialization. We say a specialization σ is partial if for some x_{i}, σ(x_{i}) = x_{i}. A partial ground specialization is σ such that for each c ∈ S, either σ(c) = c or σ(c) ∈ D. If σ(S) ⊆ \overline{D} we call σ an algebraic specialization.

Generic points. Henceforth, assume S ⊆ Ω_{D} is a finite set. Fixing any enumeration x = (x_{1}, …, x_{n}) of S, we may represent a S-specialization σ by the sequence

y = (σ(x_{1}), …, σ(x_{n})).

Let us write (following Artin)

x ⟶^{σ} y or x ⟶^{S} y or x ⟶ y  (7)

to indicate that y is a S-specialization. If σ is a S-specialization and τ is an σ(S)-specialization then the composition τ ∘ σ is an S-specialization. In the arrow notation,

x ⟶ y ⟶ z implies x ⟶ z.

An element y ∈ Ω^{n} (n ≥ 1) is called a n-point, or, simply a point in the affine n-space

𝔸^{n}(Ω) := Ω^{n}.

Thus each x-specialization can be viewed as point. This gives a more geometric language for specialization.

For any subset U ⊆ Ω, the specialization of U under σ is the set σ(U) = {h_{σ}(a) : a ∈ U}, which we also denote by

U|_{σ}.

In case U|_{σ} = {0}, we simply write U|_{σ} = 0. In this case, we say that U vanishes under σ, or^{6} σ is an S-solution (or simply, solution) of U. The solution σ is non-trivial if σ is not identically zero. If τ is a another specialization, then we write

U|_{σ,τ}

instead of the more awkward (U|_{σ})|_{τ}.

Let V ⊆ 𝔸^{n}(Ω). We call y a generic point of a V and say y determines V if

V = {z ∈ 𝔸^{n}(Ω) : y ⟶^{S} z}.

For example, if t_{1}, …, t_{n} ∈ Ω are algebraically independent over D, then (t_{1}, …, t_{n}) determines V = 𝔸^{n}(Ω). Recalling an earlier example, (t^{2}, t, t^{3}) is a generic point of the {X, Y, Z}-solutions of U = {X − Y^{2}, X^{2} − Y Z}.

Lemma 11

(i) If x_{1}, …, x_{n} ∈ Ω, then the set I of polynomials in D[X_{1}, …, X_{n}] that vanishes at (x_{1}, …, x_{n}) is a prime ideal. (ii) If I ∈ D[X_{1}, …, X_{n}] is prime and 1 ∉ I then I has a generic zero.

Proof. Part (i) is immediate. To see (ii), consider the ring E = D[X]/I. This is a domain (§1, Exercise). As in the proof of the weak Nullstellensatz (§2), we can assume D is embedded in E via the canonical homomorphism p ↦ \overline{p} from D[X] to E. We may also assume E is embedded in Ω_{D}. For any p(X_{1}, …, X_{n}) ∈ D[X], we saw that p(\overline{X}_{1}, …, \overline{X}_{n}) = 0 iff p(X_{1}, …, X_{n}) ∈ I. Hence x = (\overline{X}_{1}, …, \overline{X}_{n}) ∈ Ω_{D}^{n} is a zero of I. We claim that x is a generic zero. Let a = (a_{1}, …, a_{n}) ∈ Ω_{D}^{n}. We must show that a is a zero of I iff

x ⟶ a,

§4. Resultant Systems  Lecture XI  Page 11

i.e., the function taking \overline{X}_{i} to a_{i} (i = 1, …, n) is a specialization. Suppose a is a zero of I. If p(X_{1}, …, X_{n}) ∈ D[X] and p(x) = 0 then p(X_{1}, …, X_{n}) ∈ I (property of canonical homomorphism) and hence p(a) = 0 (as a is a zero of I). This proves x ⟶ a. Conversely, assume x ⟶ a. If p(X_{1}, …, X_{n}) ∈ I then p(x) = 0 (property of canonical homomorphism) and so p(a) = 0 (definition of x ⟶ a). This means a is a zero of I. Q.E.D.

6When we call σ a “solution” of U, it is understood that we are considering the universal case of solving the system U = 0. In contrast, as in §3, we shall call σ a “zero” of U when we consider the algebraic case of solving the system U = 0.

This lemma justifies the treatment of the zero set of prime ideals as “points” in an abstract space. Exercises

Exercise 3.1: Let F_{1}(X, Y, Z) = X − Y^{2}, and F_{2}(X, Y, Z) = XY − Z.

i) Show that Ideal(F_{1}, F_{2}) is prime.

ii) Let F_{0}(X, Y, Z) = X^{2} − Y Z. Show that I_{0} := Ideal(F_{0}, F_{1}) is not prime.

iii) Show that I_{0} has two generic points, (t^{2}, t, t^{3}) and (0, 0, t). (See below for a definition of generic points.) iv) Consider the homogeneous polynomials f_{1}(X, Y, Z, U) = UX − Y^{2} and f_{2}(X, Y, Z, U) = XY − UZ. Is Ideal(f_{1}, f_{2}) prime? □

Exercise 3.2: If I ⊆ D[X] is the set of polynomials that vanishes at two distinct points in Ω_{D}^{n}, then I is not prime. □

§4. Resultant Systems

We introduce the concept of a resultant system for a system of homogeneous polynomials with indeterminate coefficients (this will be precisely defined). Using the extended Nullstellensatz (§2), we show the existence of resultant systems.

Forms. Let C, X be disjoint sets of indeterminates. We write D[C][X] instead of D[C ∪ X] to signal our intention to view F ∈ D[C ∪ X] as a polynomial in X with coefficients in D[C]. Hence the degree, deg(F), of F is understood to refer to the X-degree. If e = (e_{1}, …, e_{n}) ∈ ℕ^{n}, we shall write X^{e} for the power product ∏_{i=1}^{n} X_{i}^{e_{i}}. The set C will be used in a very special way as captured next:

Definition:

(i) A polynomial F ∈ D[C][X] is an indeterminate polynomial if it is the sum of terms such as

c_{0}X^{e} (c_{0} ∈ C, e ∈ ℕ^{n}).

We call c_{0} and X^{e} (respectively) the coefficient and power product of this term. Moreover, this association between coefficients c_{0} and power products X^{e} among the terms is a bijection . (ii) A form is an indeterminate polynomial that is homogeneous, i.e., each term has the same degree. (iv) If σ is a partial ground C-specialization, and F is an indeterminate polynomial, then F |_{σ} is called a partially indeterminate polynomial. So the coefficient of each power product in such a polynomial belongs to D or to C. A partial form is similarly defined. (iii) A system of indeterminate polynomials (of partial forms, etc) is a set of indeterminate polynomials (of partial forms, etc) such that distinct polynomials in the set have disjoint sets of indeterminate coefficients.

For instance, let X = {X, Y }, C = {c_{0}, c_{1}, c_{2}}. Then c_{0}X^{2} + c_{0}XY = c_{0}(X^{2} + XY) and c_{1}X + c_{2}X = (c_{1} + c_{2})X are not indeterminate polynomials as they fail the bijectivity requirement. Although c_{0}X^{2}Y and c_{0}X + c_{1}Y are both indeterminate polynomials, together, they do not constitute a “system” of indeterminate polynomials. The reason is, of course, because c_{0} occurs in both polynomials. Note that the underlying domain D is irrelevant in this definition.

Two indeterminate polynomials are equivalent if they are identical after a suitable renaming of the coefficients in the polynomials. A form F of degree d is generic if every power product of degree d occurs in F; clearly F have \binom{d+n−1}{n−1} terms. For any n, d, all generic forms of degree d on n variables are equivalent. Caveat: “forms” in the literature sometimes refers to homogeneous polynomials and sometimes refers to generic forms, neither agreeing with our definition.

More examples. The following are indeterminate polynomials:

c_{1}X + c_{2}XY, c_{0} + c_{2}X^{2}, c_{1}X^{2} + c_{2}Y^{2}.

The following are not indeterminate polynomials, but they are partially indeterminate:

X + 4X(= 5X), c_{1}X + XY, 4 + c_{0}X, 3X^{2} − 5XY + c_{2}Y^{2}.

The following are not even partially indeterminate:

c_{0}X − c_{1}Y, 4X^{3} + c_{0}X^{3} = (4 + c_{0})X^{3}, 1 + c_{0}, c_{1}^{2}XY, 8c_{1}Y.

Both c_{0} and c_{1}X^{2} + c_{0}XY + c_{2}Y^{2} are generic forms while c_{0}X^{2}Y is a non-generic form.

We come to the main definition:

Definition: Let Σ ⊆ D[C][X]. A set Γ ⊆ D[C] is called a resultant system of Σ if for any ground specialization

σ : C ⟶ D,

the vanishing of Γ|_{σ} is a necessary and sufficient condition for the existence of a non-trivial Xsolution of the set Σ|_{σ}. In case Γ is a singleton set {R}, then we call the polynomial R a resultant polynomial of Σ.

The resultant system Γ can be the empty set ∅ in which case Γ|_{σ} always vanish, by definition.

The classic example of a resultant polynomial is the determinant. More precisely, if Σ is a system of n generic linear forms in n variables, and det(Σ) is the determinant of a matrix whose ith row contains the coefficients of the ith form, then det(Σ) is a resultant polynomial for Σ. If σ is a ground specialization, it is conventional to call det(Σ)|_{σ} the “resultant of Σ|_{σ}”.

We note a simple fact: a set Γ is a resultant system iff any basis (§1) for Γ is a resultant system. In particular, if C is finite (the usual case), and there exists a resultant system, then the Hilbert basis theorem (§1) assures us there is a finite resultant system.

The following is immediate:

Lemma 12 Let Σ ⊆ D[C][X] be any set polynomials. If Γ ⊆ D[C] is a resultant system for Σ and σ is a partial C-specialization then Γ|_{σ} is a resultant system for Σ|_{σ}.

It will be shown that any system Σ of forms has a resultant system Γ. For any partial specialization Σ|_{σ} of Σ, we can of course compute its resultant system by first computing Γ and then specializing it to Γ|_{σ}. However, it may be more efficient to directly construct a resultant system for Σ|_{σ}. Recent results on sparse elimination are able to do this to some extent.

Construction of Resultant Systems. We now construct a resultant system for a system

Σ = {A_{1}, …, A_{r}} ⊆ D[C][X_{1}, …, X_{n}]

of forms. To avoid trivial cases, let us assume that n ≥ 2, r ≥ 1 and d ≥ 1 where d = max_{i=1}^{r} deg(A_{i}).

Recall PP = PP(X_{1}, …, X_{n}) is the set of power products in the X_{i}’s. There are

N_{m}:= \binom{m + n − 1}{n − 1}  (8)

power products in PP of total degree m. Let PP^{m} be a column vector of length N_{m} that enumerates all these power products. When convenient, we also view PP^{m} as a set. A homogeneous polynomial F ∈ D[C][X] of degree m can be identified with a row vector \overline{F} ∈ D[C]^{N_{m}} such that F is equal to the scalar product

⟨\overline{F} , PP^{m}⟩.

We are interested in the multiset Σ_{m} of homogeneous polynomials of degree m that are formed by^{7} multiplying each A_{i} ∈ Σ by various power products:

Σ_{m}:={uA : deg(uA) = m, A ∈ Σ, u ∈ PP}.

Let N_{m}^{∗} denote the number (with multiplicity counted) of polynomials in Σ_{m} (we estimate N_{m}^{∗} below). Let Q_{m} be the matrix that represents Σ_{m}: Q_{m} has N_{m}^{∗} rows and N_{m} columns, with the rows corresponding to the vectors \overline{F}, F ∈ Σ_{m}. So

Q_{m} · PP^{m}

is just a column vector enumerating all the members of the multiset Σ_{m}. Now let

Γ_{m} ⊆ D[C]

denote the set of N_{m} × N_{m} subdeterminants of Q_{m} (if N_{m}^{∗} < N_{m} then Γ_{m} is empty). Finally, let Γ be the union of the Γ_{m} for all m ≥ 1.

Example: Let Σ = {A_{1}, A_{2}} where A_{i} = a_{i}X + b_{i}Y + c_{i}Z. Let PP^{2} = (X^{2}, XY, Y^{2}, Y Z, Z^{2}, ZX)^{T}. Viewed as a set, Σ_{2} = {XA_{1}, Y A_{1}, ZA_{1}, XA_{2}, Y A_{2}, ZA_{2}}. Then

X^{2} XY Y^{2} Y Z Z^{2} ZX Q_{2} = [ \begin{matrix}a_{1} & b_{1} & & & & c_{1} \\ & a_{1} & b_{1} & c_{1} \\ & & & b_{1} & c_{1} & a_{1} \\ a_{2} & b_{2} & & & & c_{2} \\ & a_{2} & b_{2} & c_{2} \\ & & & b_{2} & c_{2} & a_{2} \end{matrix} ] . A_{1}X A_{1}Y A_{1}Z A_{2}X A_{2}Y A_{2}Z

Note that we have labeled the rows and columns of the matrix in the obvious way. Here N_{2}^{∗} = N_{2} = 6 and so Γ_{2} consists of just the determinant of Q_{2}. This determinant turns out to be 0.

Theorem 13 If Σ ⊆ D[C][X_{1}, …, X_{n}] be a system of forms of degrees at most d then Γ_{m} is a resultant system for Σ whenever

m ≥ 1 + n(N − 1)

where N = N(n, d) is the Nullstellensatz bound (§2).

7Macaulay calls these the elementary polynomials with respect to Σ.

Proof. Fix any ground specialization σ of the coefficients in Σ, and write Σ̃ for Σ|_{σ}, Γ̃_{m} for Γ_{m}|_{σ}, etc. We must show that Σ̃ has a non-trivial solution iff Γ̃_{m} = 0. (Recall that Γ_{m} may be empty in which case Γ̃_{m} = 0 is automatic.)

First suppose Σ̃ has only trivial solutions. By the extended form of the Nullstellensatz (§2), as each X_{i} (i = 1, …, n) vanishes at all the zeroes of Σ̃, there exists a ∈ D such that for all p_{i} ∈ PP^{m},

a · p_{i} ∈ Ideal(Σ̃).

This follows from our choice of m. This means that there exists an N_{m} × N_{m}^{∗} matrix U with entries in D such that

a · I = U · Q̃_{m},  (9)

where I is the identity matrix. [To see this, if PP^{m} = (p_{1}, p_{2}, …)^{T} then on translating a · p_{i} ∈ Ideal(Σ̃) to the matrix form

a · p_{i} = (u_{i1}, u_{i2}, …) · Q̃_{m} · PP^{m},

we make take the ith row of U to be (u_{i1}, u_{i2}, …).] This means that the rank of Q̃_{m} is N_{m} and some determinant in Γ̃_{m} is non-zero. (In particular, Γ_{m} is non-empty.)

Conversely, suppose Σ̃ has a nontrivial solution τ : X → Ω_{D}. By way of contradiction, let us assume that Γ̃_{m} ≠ 0. Then there exists a non-zero matrix U and a ∈ D such that equation (9) holds. [To see this, note that Γ_{m} is non-empty implies that N_{m}^{∗} ≥ N_{m}. We may assume the first N_{m} rows of Q̃_{m} is a square matrix V with nonzero determinant a. Then we set U = [adj(V)|0] where adj(V) denotes the adjoint of V and 0 is a matrix of zeros.] Then

a · PP^{m} = U · Q̃_{m} · PP^{m}.  (10)

The right hand side of this equation evaluates to a column vector: each element in this vector is a D-linear combination of the polynomials in Σ̃. Hence if we specialize this equation using τ, then the right-hand side vanishes (as τ is a solution of Σ̃). But the left-hand side does not vanish (as τ is a non-trivial solution), contradiction. Q.E.D.

Kapferer [11], without the benefit of the quantitative Nullstellensatz, already shows in 1929 that there is a resultant system whose polynomials have degree 2^{n−1}d^{2^{n−1}−1}.

Estimates for N_{m}^{∗}. For simplicity, assume m ≥ d in the following. First let us dispose of a simple case, when r = 1: then N_{m}^{∗} = N_{m−d} < N_{m} and Γ_{m} is empty. (So the above theorem shows that a single polynomial always has non-trivial solutions.) Henceforth, let r ≥ 2. The number of polynomials in Σ_{m} is

N_{m}^{∗} = ∑_{i=1}^{r} N_{m−d_{i}} ≥ rN_{m−d}.

Note that

\frac{N_{m}}{N_{m−d}} = \frac{(m + n − 1)(m + n − 2) ⋯ (m + 1)}{(m − d + n − 1)(m − d + n − 2) ⋯ (m − d + 1)} < (1 + \frac{d}{m − d})^{n−1} < r

for r ≥ 2 and m large enough. Hence N_{m}^{∗} ≥ rN_{m−d} > N_{m} and so Γ_{m} is non-empty. However, as a previous example shows, this does not guarantee that Γ contains a non-zero element. Precisely when this happens will be clarified shortly.

§5. Sylvester Resultant Revisited  Lecture XI  Page 15

Non-existence of Resultant Systems. We give an example of van der Waerden showing that if we drop the homogeneity requirement in the polynomials of Σ ⊆ D[X], then Σ may have no resultant systems. Assume D is an infinite field. Suppose Σ = {A, B} ⊆ D[a, b][x, y] where a = (a_{0}, a_{1}, a_{2}), b = (b_{0}, b_{1}, b_{2}) and

A = a_{0} + a_{1}x + a_{2}y,
B = b_{0} + b_{1}x + b_{2}y.

Consider any specialization σ of a, b such that

G_{1} = a_{0}^{2} + b_{0}^{2}, G_{2} = a_{1}b_{2} − a_{2}b_{1}

either both vanish, or both do not vanish under σ. Then by linear algebra, Σ|_{σ} has a nontrivial solution. It can be verified that converse also holds. We claim that Σ does not have a resultant system Γ. Assume to the contrary that Γ ⊆ D[a, b] is a resultant system. Now there exists a ground specialization σ_{0} of a, b such that

G_{1}|_{σ_{0}} = 0, G_{2}|_{σ_{0}} ≠ 0.

Thus Σ|_{σ_{0}} has no non-trivial solutions and hence Γ|_{σ_{0}} ≠ 0. But there are also infinitely many σ′ such that σ′ and σ_{0} agree at all values except that σ′(a_{0}) ≠ σ_{0}(a_{0}), and

G_{1}|_{σ′} ≠ 0,  G_{2}|_{σ′} ≠ 0.  (11)

Hence Γ|_{σ′} = 0. Since a_{1}, a_{2}, b_{0}, b_{1}, b_{2} are held fixed when considering assignments such as σ′, we can view elements of Γ as polynomials in the variable a_{0} with constant coefficients. But such polynomials can have infinitely many solutions only if it is identically zero. But this contradicts the fact that Γ|_{σ_{0}} ≠ 0. Thus Γ does not exist.

Resultant systems for a system of indeterminate (possibly non-homogeneous) polynomials exist if we modify our definition of a “resultant system” to exclude specializations that cause the leading coefficients to all vanish. See an exercise in the next section for the non-homogeneous version of the Sylvester resultant.

Exercises

Exercise 4.1:

(i) n^{m} ≥ N_{m} = \binom{m+n−1}{n−1}, with strict inequality if n ≥ 2 and m ≥ 2.

(ii) N_{m}^{∗} > N_{m} if m > d(1 + n/ ln r). □

Exercise 4.2: Construct the set Γ_{2} for Σ = {A_{0}, A_{1}, A_{2}} where A_{0} = aX^{2} + bY^{2} + cX^{2} and

A_{i} = a_{i}X + b_{i}Y + c_{i}Z, i = 1, 2.
□

Exercise 4.3: Show that Γ is a resultant system for Σ. □

§5. Sylvester Resultant Revisited

It is instructive to explicitly construct a resultant polynomial for a system of two forms in two variables. Unlike the general setting of the previous section, we do not use the Nullstellensatz. The reader will recognize that this is essentially the Sylvester matrix construction in §III.3.

Consider two generic forms A, B ∈ D[a, b][X, Y],

A(X, Y) = ∑_{i=0}^{m} a_{i} X^{i}Y^{m−i}

B(X, Y) = ∑_{i=0}^{n} b_{i} X^{i}Y^{n−i}.

The Sylvester matrix of A, B is the (m + n)-square matrix

S(A, B)

formed from the coefficients of A, B, in analogy to the non-homogeneous case in §III.3. The matrix in equation (13) below is S(A, B). The resultant res(A, B) of A, B is the determinant of S(A, B). Our main goal is to prove the following:

Theorem 14 The polynomial res(A, B) is a resultant polynomial for {A, B}.

Let σ be any ground specialization of a, b. Write Ã, B̃ and R̃ for A|_{σ}, B|_{σ} and res(A, B)|_{σ}, respectively.

Lemma 15 The following are equivalent:

(a) R̃ = 0.

(b) There exists homogeneous polynomials U, V ∈ D[X, Y] of degrees n − 1 and m − 1 (respectively) such that

U · Ã + V · B̃ = 0.  (12)

Proof. The equation 0 = U · A + V · B can be written as a matrix equation involving the Sylvester matrix S(A, B),

0 = (u_{n−1}u_{n−2}, …, u_{0}, v_{m−1}, v_{m−2}, …, v_{0}) · [ \begin{matrix}a_{0} & a_{1} & ⋯ & a_{m} \\ & a_{0} & a_{1} & ⋯ & a_{m} \\ & & ... & & & ... \\ & & & a_{0} & ⋯ & & a_{m} \\ b_{0} & b_{1} & ⋯ & & b_{n} \\ & ... & & & & ... \\ & & b_{0} & ⋯ & & & b_{n} \end{matrix} ] (13)

where the u_{i}’s and v_{j}’s are the coefficients of U, V, respectively. Thus equation (12) holds for U, V iff the determinant of S(A, B)|_{σ} vanishes, i.e., iff R̃ = 0. Q.E.D.

Lemma 16 R̃ = 0 implies {Ã, B̃} has a non-trivial solution.

Proof. If Ã is the zero polynomial, then clearly any non-trivial solution for B̃ is a non-trivial solution for {Ã, B̃}. So assume that σ(a_{k}) ≠ 0 for some k = 0, …, m, and σ(a_{i}) = 0 for i ≥ k + 1. Then Ã has the factorization

Ã = σ(a_{k})Y^{m−k} ∏_{i=1}^{k}(X − α_{i}Y), α_{i} ∈ \overline{D}.

From equation (12), we get UÃ = −V B̃. Since \overline{D}[X, Y] is a UFD and deg(V) = m − 1, at least one of the m linear factors, Y or X − α_{i}Y, divides B̃. Then either (1, 0) or (α_{i}, 1) would be a non-trivial zero {Ã, B̃}. Q.E.D.

Finally, our main result, theorem 14, is just a consequence of the following result:

Theorem 17 The following are equivalent:

(a) R̃ ≠ 0,

(b) There exists a non-zero c ∈ D such that for r = 1, …, m + n,

c · X^{r−1}Y^{m+n−r} ∈ Ideal(Ã, B̃).  (14)

(c) {Ã, B̃} has only the trivial solution.

Proof. (a)⇒(b): We set up m + n equations involving A and B:

[ \begin{matrix}a_{0} & a_{1} & ⋯ & a_{m} \\ & a_{0} & a_{1} & ⋯ & a_{m} \\ & & ... & & & ... \\ & & & a_{0} & ⋯ & & a_{m} \\ b_{0} & b_{1} & ⋯ & & b_{n} \\ & ... & & & & ... \\ & & b_{0} & ⋯ & & & b_{n} \end{matrix} ] [ Y^{m+n−1} ; XY^{m+n−2} ; ⋮ ; X^{m+n−2} Y ; X^{m+n−1} ] = [ Y^{n−1}A ; XY^{n−2}A ; ⋮ ; X^{n−2}Y · A ; X^{n−1}A ; Y^{m−1}B ; ⋮ ; X^{m−1}B ]  (15)

Note that the Sylvester matrix is again involved. Fix r = 1, …, m + n. Let C_{1}, …, C_{m+n} be the co-factors of the entries in the rth column. Multiply both sides of equation (15) on the left by the row (C_{1}, …, C_{m+n}). Equating the left and right side of this multiplication,

X^{r−1}Y^{m+n−r}res(A, B) = U_{r}(X, Y) · A(X, Y) + V_{r}(X, Y) · B(X, Y).  (16)

where U_{r}, V_{r} ∈ D[a, b][X, Y] are forms of degrees n − 1 and m − 1. Assertion (b) follows with the choice c = res(A, B)|_{σ}. (b)⇒(c): Any non-trivial solution (X, Y) ⟶ (x, y) of {A, B}|_{σ} will make the right-hand side of equation (16) vanish, but the left-hand side will not vanish for either r = 1 or r = m + n, contradiction. (c)⇒(a): This is the contrapositive of the previous lemma. Q.E.D.

Remarks. The element c in (14) is called an inertial element of {A, B} (see next section). An important application of resultants is in the elimination of variables from a system of equations. Although the multivariate resultant of Macaulay may be more efficient in an asymptotic sense, it seems that for actual examples, eliminating one variable at a time using Sylvester resultants may be faster. An exercise below illustrates this application.

§6. Inertial Ideal  Lecture XI  Page 18

Exercises

Exercise 5.1: (Resultant  system  for  non-homogeneous  polynomi-

als) Let A(X) = ∑_{i=0}^{m} a_{i}X^{i}, B(X) = ∑_{i=0}^{n} b_{i}X^{i} ∈ D[a, b][X]. For all specializations σ of a, b, such that σ(a_{m}) ≠ 0 or σ(b_{n}) ≠ 0, the system {A, B}|_{σ} has a solution iff R|_{σ} = 0, where R is the Sylvester resultant of A, B. □

Exercise 5.2: How many terms are there in res(A, B)? □

Exercise 5.3: Elimination of variables.

(a) If F, G are polynomials in X_{1}, X_{2}, …, X_{n}, we can compute the Sylvester resultant of F and G with respect to the variable X_{1} (so the resultant is a polynomial in X_{2}, …, X_{n}). Interpret this as a projection of the intersection of two hypersurfaces.

(b) Suppose C_{1} : F (X, Y) = 0 and C_{2} : G(X, Y) = 0 are two plane curves. We want to define the locus V of points v = (v_{x}, v_{y}) such that the largest disk D_{v} whose interior avoids these curves simultaneously touches both C_{1} and C_{2}. This locus V is called the Voronoi diagram defined by C_{1}, C_{2}. Let a = (a_{x}, a_{y}) and b = (b_{x}, b_{y}) denote points on C_{1} and C_{2} respectively where D_{v} touches C_{1} and C_{2}. The relevant equations are

F_{0} :  |v − a|^{2} − |v − b|^{2} = 0,
F_{1} :  F (a) = 0,
F_{2} :  G(b) = 0,
F_{3} :  (v_{x} − a_{x})F_{x}(a) − (v_{y} − a_{y})F_{y}(a) = 0,
F_{4} :  (v_{x} − b_{x})G_{x}(b) − (v_{y} − b_{y})G_{y}(b) = 0,

Suppose that F, G are polynomials of degrees m. Show by pairwise elimination that V is, in general, an algebraic curve of degree at most 4m^{5}. (HINT: Eliminate variables successively in carefully chosen order.)

(c) Compute the Voronoi diagram for the following pair of curves, C_{1} : X + Y − 9 = 0 and C_{2} : 2X^{2} + Y^{2} − 3 = 0.

(d) Why do you get different degree bounds with different order of elimination? What happens if your resultant vanishes? Can you prove that this is the best possible using “this method”?

□

§6. Inertial Ideal

In this section, fix

Σ = {A_{1}, …, A_{r}}, r ≥ 1  (17)

to be a system of partial forms in D[C][X] where deg A_{i} = d_{i} ≥ 1. Partial forms are convenient here because they are preserved by partial specializations. We say that a partial form A of degree t is regular in variable X_{j} if the coefficient of its power X_{j}^{m} in A is an indeterminate. We say Σ is regular in X_{j} if each A ∈ Σ is regular in X_{j}. Finally, we say Σ is regular if each Σ is regular in each variable X_{j}.

We will assume that Σ is regular unless a less strict condition is explicitly mentioned (e.g., when we explicitly say “Σ is regular in X_{1}” then the more general assumption is dropped).

In the following, whenever Σ is regular in variable X_{1}, we assume that the indeterminate coefficients

C = (c_{1}, c_{2} …)

are relabeled so that c_{i} is the coefficient of X_{1}^{d_{i}} in A_{i}. We further write

A_{i} = A_{i}^{∗} + c_{i}X_{1}^{d_{i}},  (18)

where A_{i}^{∗} ∈ D[C][X].

Let us reëxamine our proof that any system Σ of forms has a resultant system Γ_{m} (§4). If

Γ_{m} \ {0} = {a_{1}, a_{2}, a_{3}, …}

is non-empty, then as in the proof, there are N_{m} × N_{m} matrices U_{1}, U_{2}, U_{3}, … with entries in D[C], such that

a_{i} · I = U_{i} · Q_{m}.

Therefore

a_{i} · PP^{m} = U_{i} · Q_{m} · PP^{m}.

The entries on the right-hand side are D[C]-linear combinations of polynomials from the set Σ_{m}. In particular, this shows that

a_{i}X_{1}^{m} ∈ Ideal(Σ).

In general, following Hurwitz, for any set of polynomials Σ′ ⊆ D[C][X], we call R ∈ D[C] an inertial element of Σ′ if

R · X_{1}^{m} ∈ Ideal(Σ′)  (19)

for some m ≥ 0. Note that Ideal(Σ)′ here is generated in the ring D[C][X], and the special role of X_{1} in this definition. The following is immediate:

Lemma 18 For any Σ:

(i) The set of inertial elements is an ideal. (ii) If R is an inertial element of Σ and σ is a partial specialization of C then R|_{σ} is an inertial element of Σ|_{σ}.

Hence, we may speak of the inertial ideal of Σ. When Σ is a system of forms, we constructed in §4 a resultant system Γ consisting of inertial elements. We conclude from this lemma and lemma 12, §4:

Corollary 19 Every system of partial forms has a resultant system consisting of inertial elements.

We next give a characterization of inertial elements:

Lemma 20 Let Σ be regular in variable X_{1} and R(C) ∈ D[C]. Then R is an inertial element of Σ iff under the partial specialization

σ^{∗} : c_{i} ⟼ \frac{−A_{i}^{∗}}{X_{1}^{d_{i}}}  (i = 1, …, r)  (20)

the polynomial R(C), regarded as an element of D(C)(X), vanishes:

R|_{σ^{∗}} = R (−\frac{A_{1}^{∗}}{X_{1}^{d_{1}}} , −\frac{A_{2}^{∗}}{X_{1}^{d_{2}}} , …, −\frac{A_{r}^{∗}}{X_{1}^{d_{r}}} , c_{r+1}, …) = 0  (21)

Proof. Suppose R is an inertial element. Then (18) and (20) show that Ideal(Σ|_{σ^{∗}}) = (0). So R|_{σ^{∗}} = 0 by (19). Conversely assume that (21) holds. Then

R(c_{1}, …, c_{r}, c_{r+1}, …) = R (\frac{A_{1} − A_{1}^{∗}}{X_{1}^{d_{1}}} , …, \frac{A_{r} − A_{r}^{∗}}{X_{1}^{d_{r}}} , c_{r+1}, …)

= R (−\frac{A_{1}^{∗}}{X_{1}^{d_{1}}} , …, −\frac{A_{r}^{∗}}{X_{1}^{d_{r}}} , c_{r+1}, …)

+ ∑_{i=1}^{r} \frac{A_{i}}{X_{1}^{d_{i}}} · B_{i} (−\frac{A_{1}^{∗}}{X_{1}^{d_{1}}} , …, −\frac{A_{r}^{∗}}{X_{1}^{d_{r}}} , c_{r+1}, …) ,

for some B_{i}(c_{1}, c_{2}, …). The last expression for R(c_{1}, …, c_{r}, …) represents an expansion of R into 2 parts: the first part containing terms that are not divisible by any A_{i}/X_{1}^{d_{i}} (i = 1, …, r and treating A_{i}/X_{1}^{d_{i}} as a new symbol), and the second part for the remaining terms. But the first part is just R|_{σ^{∗}}, which is assumed to vanish. Multiplying the last equation by a suitable power of X_{1}, it follows that R satisfies (19). Hence R is an inertial element. Q.E.D.

The special role of X_{1} in the definition of inertial elements can be replaced by another X_{j} under the following conditions:

Lemma 21 Suppose Σ is regular in variable X_{1} and in X_{j} (for some 1 < j ≤ n). Then X_{1}^{m}R ∈ Ideal(Σ) (for some m ≥ 0) iff X_{j}^{k}R ∈ Ideal(Σ) (for some k ≥ 0).

Proof. Let σ^{∗} be the specialization in equation (20). If X_{j}^{k}R ∈ Ideal(Σ) then R|_{σ^{∗}} = 0 (since Σ|_{σ^{∗}} vanishes). Then X_{1}^{m}R ∈ Ideal(Σ) as in the proof of lemma 20. The reverse implication is similarly shown. Q.E.D.

Theorem 22 If Σ is a system of partial forms that is regular in X_{1} then the set of inertial elements of Σ is a prime ideal of D[C].

Proof. To see that the inertial ideal is prime, consider R, S, ∈ D[C]. If R · S is an inertial element, then by lemma 20, R · S vanishes under the specialization (20). Hence either R or S vanishes under the specialization. Again by lemma 20, this means R or S is an inertial element. Q.E.D.

Theorem 23 Let Σ be a system of partial forms that is regular. Then the inertial ideal I of Σ is a resultant system for Σ.

Proof. Let Γ ⊆ I be a resultant system for Σ. For any ground specialization σ of C, if I|_{σ} vanishes then Γ|_{σ} vanishes. As Γ is a resultant system for Σ, we conclude that Σ|_{σ} has a non-trivial solution. Conversely, suppose Σ|_{σ} has a non-trivial X-solution, say τ. Suppose τ(X_{j}) ≠ 0. Now for each R ∈ I, for some m ≥ 0,

X_{j}^{m}R ∈ Ideal(Σ).

Since Σ|_{σ,τ} = 0, and X_{j}^{m}|_{τ} ≠ 0, it follows that R|_{σ,τ} = 0. But R does not depend on X, so R|_{σ} = 0. This proves that I|_{σ} = 0. Q.E.D.

Lemma 24 Let Σ be regular in X_{1} and c_{1}, …, c_{r} be given by (18). Let c ∈ C be different from c_{1}, …, c_{r} and σ be a partial C-specialization that maps c to some α ∈ D (leaving all other indeterminates in C fixed). Suppose the inertial ideal I of Σ is non-trivial.

(a) The inertial ideal of Σ|_{σ} is also non-trivial.

(b) Every non-zero element R ∈ I contains a factor P that does not vanish under σ.

Proof. Part (a) follows immediately from part (b). To show (b), suppose R ∈ I is a non-zero element such that R|_{σ} = 0. By the pseudo-division property (§III.2), β^{m}R = (c − α)P + Q for some m ≥ 1, β ∈ D[C], and P, Q ∈ D[C] such that Q and β do not depend on c (actually β = 1 here). But R|_{σ} = 0 implies Q|_{σ} = Q = 0. Thus (c−α)P is an inertial element. Note that c−α is not an inertial element of Σ, by lemma 20. Hence P must be a non-zero inertial element of Σ. We can repeat this argument (choosing P in place of R) until eventually R|_{σ} ≠ 0. Q.E.D.

Lemma 25 If R is a non-zero inertial element of Σ then R depends on at least n of the coefficients among c_{1}, …, c_{r}. In particular, r ≥ n.

Proof. By way of contradiction, suppose that R depends on m < n elements among c_{1}, …, c_{r}. Without loss of generality, assume R depends on c_{1}, …, c_{m} only. Consider the partial specialization

(c_{n+1}, c_{n+2}, …) ⟶^{σ} (α_{n+1}, α_{n+2}, …),  (α_{j} ∈ D).  (22)

Repeated application of the previous lemma shows that R|_{σ} ≠ 0. Write R̃ for R|_{σ}. So R̃ = R̃(c_{1}, …, c_{m}) is an inertial element of Σ|_{σ}. Since Σ is regular, we may choose the α_{j}’s in (22) so that A_{i}^{∗}|_{σ} = −X_{i+1}^{d_{i}} for i = 1, …, m (using the fact that i ≤ m < n). Let σ^{∗} be the {c_{1}, …, c_{n}}- specialization for Σ|_{σ}, defined as in (20). It follows that

σ^{∗}(σ(c_{i})) = σ^{∗}(c_{i}) = (X_{i+1}/X_{1})^{d_{i}}.

Since R̃|_{σ^{∗}} vanishes, we have

R̃|_{σ^{∗}} = R̃ ((\frac{X_{2}}{X_{1}} )^{d_{1}} , (\frac{X_{3}}{X_{1}} )^{d_{2}} , …, (\frac{X_{m+1}}{X_{1}} )^{d_{m}}) = 0.

But renaming each (X_{i+1}/X_{1})^{d_{i}} as a new indeterminate Y_{i}, we conclude that R̃(Y_{1}, …, Y_{m}) = 0. But a non-zero polynomial cannot vanish by renaming, contradiction. Q.E.D.

This yields:

Theorem 26

(i) If the number r of polynomials in Σ is less than the number n of variables then the inertial ideal of Σ is trivial. (ii) Any system of homogeneous equations in D[X] with fewer equations than unknowns has a nontrivial zero.

Proof. (i) If Σ has a non-zero inertial element then the previous lemma shows that r ≥ n. So r < n implies such elements do not exist. (ii) Let Σ′ ⊆ D[X] be the homogeneous system under consideration. If Σ′ = Σ|_{σ} where Σ is the system in part (i), then any resultant system Γ for Σ specializes to a resultant system Γ|_{σ} for Σ′. But such a Γ is necessarily trivial (we may always assume Γ is comprised of inertial elements). Q.E.D.

An ideal I ∈ D[C] is pseudo-principal if there exist R ∈ I and α ∈ D such that for all S ∈ I, R divides α · S. Of course, if α = 1, then I is principal in the usual sense.

Theorem 27 If Σ has many polynomials as variables, then its inertial ideal I is a non-trivial pseudo-principal ideal. In particular, Σ has a resultant polynomial.

Proof. First let us show that I ≠ (0). If I = (0) then under every C-specialization σ, the system Σ|_{σ} has a non-trivial solution. In particular, since n = r, we may specialize Σ to

Σ|_{σ} = {X_{i}^{d_{i}} : i = 1, …, n}.

But it is patently false that Σ|_{σ} has a non-trivial solution. This shows I ≠ (0). By lemma 25, any non-zero element of I must depend on c_{1}, …, c_{n}. We now operate in the UFD D′ = Q_{D}[C] where Q_{D} is the quotient field of D. Choose R_{0} ∈ Ideal_{D′}(I) to be an irreducible element whose c_{n}-degree, say d ≥ 1, is minimum. We claim that

Ideal_{D′}(R_{0}) = Ideal_{D′}(I).

The forward inclusion is immediate. In the reverse direction, pick any non-zero S ∈ Ideal_{D′}(I) and let e be the c_{n}-degree of S. Then e ≥ d and by the pseudo-division property, γ^{m}S = AR_{0} + B for some m ≥ 1 and γ, A, B ∈ Q_{D}[C] where the c_{n}-degree of B is less then d and γ does not depend on c_{n}. But B = γ^{m}S − AR_{0} ∈ Ideal_{D′}(I). So B = 0 since the c_{n}-degree of B is less than d; this in turn means R_{0} divides γ^{m}S. As R_{0} is irreducible in D′ which is a UFD, it must divide γ or S. Since the c_{n}-degree of γ is 0, R_{0} cannot divide γ and so it divides S. This proves our claim. Note that for some α ∈ D, α · R_{0} ∈ I. This means that for all S ∈ I, αR_{0} divides αS, proving that I is pseudo-principal.

This immediately implies that α · R_{0} can serve as a resultant polynomial for Σ (since the inertial ideal is a resultant system for Σ). Q.E.D.

Definition of Macaulay Resultant. We call α·R_{0} in the preceding proof the Macaulay resultant of Σ, and denote it by

res(Σ).

Although α · R_{0} in the proof is only defined up to associates in D, we will next show that α can be taken to be 1 for a regular system of n forms. Thus res(Σ) is unique with this convention.

Suppose now Σ = {A_{1}, …, A_{n}} is a system of partial forms, not necessarily regular. Its Macaulay resultant can be defined naturally to be an appropriate specialization: namely, if Σ′ = {A′_{1}, …, A′_{n}} is any regular system such that deg A′_{i} = deg A_{i} and there is a partial specialization σ such that Σ′|_{σ} = Σ then define the Macaulay resultant res(Σ) of Σ to be res(Σ′)|_{σ}. We leave it as an exercise to show that this does not depend on the choice of Σ′.

Exercises

Exercise 6.1: (Bloemer) Let Γ be the inertial ideal of Σ. Show by an example that the inertial ideal of Σ|_{σ} may be a proper superset of Γ|_{σ}. HINT: let Γ be trivial. □

§7. The Macaulay Resultant  Lecture XI  Page 23

§7. The Macaulay Resultant

We derive properties of the Macaulay resultant

R_{0} := res(Σ)

where

Σ = {A_{1}, …, A_{n}} ⊆ D[C][X_{1}, …, X_{n}]

is a regular system of n ≥ 2 forms.

We can already infer from theorem 22 that R_{0} is irreducible. For further properties, we give an explicit construction which van der Waerden [29] attributed to Hurwitz. Let

d_{i}:= deg(A_{i}) ≥ 1, (i = 1, …, n).

Unlike the previous section, we now let c_{i} denote the coefficient of X_{i}^{d_{i}} in A_{i}, and call c_{i} the main coefficient of A_{i}. In §4, we constructed the matrix Q_{m} of shape N_{m}^{∗}×N_{m}. We revisit this construction in more detail. As usual, X^{e} denotes the power product ∏_{i=1}^{n} X_{i}^{e_{i}} where e = (e_{1}, …, e_{n}) ∈ ℕ^{n}. We first partition the set PP^{d} of power products of degree d into the following sets:

PP_{1}^{d} := {X^{e} ∈ PP^{d} : e_{1} ≥ d_{1}},
PP_{2}^{d} := {X^{e} ∈ PP^{d} : e_{1} < d_{1} and e_{2} ≥ d_{2}},
⋮
PP_{i}^{d} := {X^{e} ∈ PP^{d} : e_{1} < d_{1}, e_{2} < d_{2}, …, e_{i−1} < d_{i−1} and e_{i} ≥ d_{i}},
⋮
PP_{n}^{d} := {X^{e} ∈ PP^{d} : e_{1} < d_{1}, e_{2} < d_{2}, …, e_{n−1} < d_{n−1} and e_{n} ≥ d_{n}}.

Finally, let

PP_{n+1}^{d}:={X^{e} ∈ PP^{d} : e_{i} < d_{i} for i = 1, …, n}.

These n + 1 sets constitute a partition of PP^{d} because not only is PP_{i}^{d} disjoint from PP_{j}^{d} for i ≠ j, but every X^{e} ∈ PP^{d} must fall into some PP_{i}^{d}.

We say X^{e} is reduced in X_{i} if e_{i} < d_{i}. We say X^{e} is reduced if it is reduced in every X_{i}. Finally, if X^{e} is reduced in all but one of the variables, we say it is almost-reduced.

E.g., PP_{i}^{d} comprises those power products (in PP^{d}) that are reduced in X_{1}, …, X_{i−1} but not reduced in X^{i}. PP_{n+1}^{d} comprises the reduced power products. Every element in PP_{n}^{d} is almost-reduced. Note that

PP_{i}^{d} ∪ PP_{i+1}^{d} ∪ ⋯ ∪ PP_{n+1}^{d}

comprises the power products that are reduced in X_{1}, …, X_{i−1}.

It is easy to verify that PP_{n+1}^{d} is empty iff d ≥ 1 + ∑_{i=1}^{n}(d_{i} − 1). Henceforth, assume

d:= 1 + ∑_{i=1}^{n}(d_{i} − 1).  (23)

Further let

d̂_{i}:= (∏_{j=1}^{n} d_{j}) /d_{i}.  (24)

Then for i = 1, …, n,

|PP_{i}^{d}| ≥ d̂_{i}, with equality when i = n.  (25)

Its demonstration is an exercise. Next, for each i = 1, …, n, let

S_{i}:= \frac{PP_{i}^{d}}{X_{i}^{d_{i}}} · A_{i} = \{X^{e} · A_{i} : X^{e} · X_{i}^{d_{i}} ∈ PP_{i}^{d}\}.

So the set

S:= S_{1} ∪ ⋯ ∪ S_{n}

has N_{d} = \binom{d+n−1}{n−1} polynomials. Since the polynomials in S have degree d, each polynomial corresponds to a row in the matrix Σ_{d}. The corresponding N_{d} × N_{d} submatrix M of Σ_{d} made up of these rows will be called a Macaulay matrix of Σ. Of course, the determinant of M is an element of Γ_{d} (§5) and so is an inertial element of Σ.

Example: Let

Σ = {A_{1}, A_{2}, A_{3}}  (26)

where A_{3} = a_{3}X^{2} + b_{3}Y^{2} + c_{3}Z^{2} and A_{i} = a_{i}X + b_{i}Y + c_{i}Z for i = 1, 2. Then (d_{1}, d_{2}, d_{3}) = (1, 1, 2). So d = 3 and

PP_{1}^{2} = {X^{2}, XY, XZ}, PP_{2}^{2} = {Y^{2}, Y Z}, PP_{3}^{2} = {Z^{2}},
S_{1} = {XA_{1}, Y A_{1}, ZA_{1}}, S_{2} = {Y A_{2}, ZA_{2}}, S_{3} = {A_{3}}.

Finally, M is given by

X^{2} XY XZ Y^{2} Y Z Z^{2} M = [ \begin{matrix}a_{1} & b_{1} & c_{1} \\ & a_{1} & & b_{1} & c_{1} \\ & & a_{1} & & b_{1} & c_{1} \\ & a_{2} & & b_{2} & c_{2} \\ & & a_{2} & & b_{2} & c_{2} \\ a_{3} & & & b_{3} & & c_{3} \end{matrix} ] . XA_{1} Y A_{1} ZA_{1} Y A_{2} ZA_{2} A_{3}

Notice that the main coefficients are a_{1}, b_{2}, c_{3} and these occur along the main diagonal of M. We have labeled the columns of M by elements of PP^{d} and the rows by elements of S. The matrix is also partitioned into blocks. All these illustrate a general convention.

Labeling convention for Macaulay Matrix. It is expedient for subsequent exposition that we construct M by first listing the rows corresponding to S_{1}, followed by the rows corresponding to S_{2}, and so on. The columns of M are labeled by elements of PP^{d} according to the following scheme: for each F ∈ S_{j}, call the power product X^{e} in F whose coefficient is c_{j} the main power product. Observe that distinct polynomials in S have distinct main power products. Thus the c_{j}’s occur in distinct columns of M, and we may arrange so c_{1}, …, c_{n} appear along the main diagonal of M. We therefore label a column by the unique main power product X^{e} that appears in that column (and in a main diagonal position). Notice that the main power products of elements in S_{j} comprise the set PP_{j}^{d}. This means that the columns of M are labeled first by the elements of PP_{1}^{d}, followed by elements of PP_{2}^{d}, etc. Thus M can be given the block structure:

M = [ \begin{matrix}M_{11} & M_{12} & ⋯ & M_{1n} \\ M_{21} & M_{22} & & M_{2n} \\ ⋮ & & ... & ⋮ \\ M_{n1} & M_{n2} & ⋯ & M_{nn} \end{matrix} ] ,  (27)

where M_{ij} is |PP_{i}^{d}| by |PP_{j}^{d}| and contains coefficients from A_{i} only. This is schematically shown in figure 1.

⋯ S_{1} ⋮⋮ S_{n} N^{d}  N_{d}^{PP_{1}^{d}}  ^{PP_{2}^{d}}  ^{PP_{n}^{d}} S_{2}

Figure 1: The Macaulay matrix M for Σ.

Lemma 28 For each j = 1, …, n, the determinant det(M) is homogeneous of degree h_{j} in the coefficients of A_{j} ∈ Σ where h_{j} = |PP_{j}^{d}|. In fact, det(M) contains the monic monomial

c_{1}^{h_{1}}c_{2}^{h_{2}} ⋯ c_{n}^{h_{n}}  (28)

where c_{j} is the main coefficient of A_{j}.

Proof. It is clear that det(M) is homogeneous in the coefficients of each A_{j}. If det(M) ≠ 0 then it has the claimed degree h_{j} in the coefficients of A_{j} since there exactly h_{j} rows in M containing only coefficients of A_{j}. So it remains to show that det(M) ≠ 0. This follows if det(M) contains the monomial (28). Let σ be the specialization yielding A_{j}|_{σ} = c_{j}X_{j}^{d_{j}} for each j. The non-zero entries of M|_{σ} is therefore confined to its main diagonal (by construction of M), and hence det(M|_{σ}) is given by (28). Q.E.D.

Our preceding construction of the sets PP_{i}^{d} is arbitrary in two ways:

(a) We associated the variable X_{i} with A_{i}. (Macaulay suggests that we regard A_{i} as a polynomial in X_{i}.)

(b) The definition of PP_{i}^{d} (and of S_{i}) depended on a fixed enumeration of the variables, from X_{1} to X_{n}.

The assertion (25) depends on these choices only to the extent that we enumerated the variable (viz., X_{n}) associated with A_{n} last. To indicate this special role of A_{n} in our construction of S and M, let us introduce the notations S^{(n)} and M^{(n)} to refer to them. Let us now vary the construction of S and M by preserving (a) but varying (b) so that the variable X_{i} associated with A_{i} is enumerated last. Call the corresponding set S^{(i)} and matrix M^{(i)}. Set

G^{(i)} := det(M^{(i)}).

We have the following analogue of (25) and lemma 28:

Corollary 29 Fix i = 1, …, n. Then G^{(i)} is homogeneous in the coefficients of each A_{j} ∈ Σ. If G^{(i)} is of degree d_{j}^{(i)} in the coefficients of A_{j} then

d_{j}^{(i)} ≥ d̂_{j}, with equality when j = i.

Moreover, G^{(i)} contains the monic monomial

±c_{1}^{d_{1}^{(i)}}c_{2}^{d_{2}^{(i)}} ⋯ c_{n}^{d_{n}^{(i)}}.  (29)

Since Q_{D}[C] is an UFD, we may define the GCD of G^{(1)}, …, G^{(n)} in Q_{D}[C]. Our goal is to show that R_{0} is (up to similarity, §III.1) equal to

G:= GCD(G^{(1)}, …, G^{(n)}).  (30)

Let B_{1} and B_{2} be forms in the variables X but involving indeterminate coefficients C′ and such that deg(B_{1}B_{2}) = deg(A_{1}). We assume C′ is disjoint from C. We need an unusual specialization:

Lemma 30 Suppose σ is a partial specialization such that

A_{1}|_{σ} = B_{1}B_{2}

and which leaves the coefficients of the other A_{j}’s untouched. Then some associate of R_{0}|_{σ} is divisible by R_{1}R_{2} where R_{j} := res(B_{j}, A_{2}, A_{3}, …, A_{n}) (j = 1, 2).

Proof. Note that X_{1}^{e}R_{0} ∈ Ideal(A_{1}, A_{2}, …, A_{n}) for some e ≥ 0. Hence X_{1}^{e}R_{0}|_{σ} ∈ Ideal(B_{1}B_{2}, A_{2}, …, A_{n}) where this ideal is generated in the ring D[C, C′][X]. Hence X_{1}^{e}R_{0}|_{σ} ∈ Ideal(B_{j}, A_{2}, …, A_{n}), j = 1, 2. This means R_{0}|_{σ} is divisible by R_{j} in the ring Q_{D}[C, C′]. But R_{1} and R_{2} are each irreducible, and so R_{0}|_{σ} is in fact divisible by the product R_{1}R_{2} in Q_{D}[C, C′].

Q.E.D.

Theorem 31

(a) The Macaulay resultant R_{0} is (up to similarity) equal to G.

(b) R_{0} is homogeneous of degree d̂_{i} in the coefficients of A_{i}.

(c) R_{0} contains a monomial of the form

α · c_{d_{1}} ; 1c_{d_{2}} ; 2 ⋯ c_{d_{n}} ; n,

where α is a unit in D. W.l.o.g., assume α = 1.

Proof. We first assume that Σ consists of generic polynomials.

(a) Clearly R_{0} divides G, since R_{0} divides each G^{(i)} in Q_{D}[C]. To show (a), it suffices (in view of corollary 29) to show that the degree of R_{0} in the coefficients of A_{i} is equal to d̂_{i}. By symmetry, it suffices to prove that the degree of R_{0} in the coefficients of A_{n} is equal to d̂_{n}. To see this, choose a specialization σ such that each

A_{i}|_{σ}, i = 1, …, n − 1

factors into d_{i} linear forms that are regular in all variables. We assume these linear forms involve brand new indeterminate coefficients. For instance, we may choose σ such that

A_{1}|_{σ} = L_{1}L_{2} ⋯ L_{d_{1}}

where L_{i} = ∑_{j=1}^{n} a_{ij}X_{j} and a_{ij}’s are new indeterminates. This is possible since A_{1} is generic. If B_{i} (i = 1, …, n − 1) is a linear factor of A_{i}|_{σ}, then the Macaulay resultant R′ = res(B_{1}, B_{2}, …, B_{n−1}, A_{n}) divides some associate of R_{0}|_{σ}, by the obvious extension to the previous lemma. But there are d̂_{n} such resultants R′, and they all divide some associate of R_{0}|_{σ}. Since each R′ is irreducible, their product must divide some associate of R_{0}|_{σ}. By corollary 29, we know that each R′ is of degree at most 1 in the coefficients of A_{n}. By lemma 25, R′ must depend on the coefficients of A_{n}, and so it has degree exactly 1. Hence their product is of degree exactly d̂_{n} in the coefficients of A_{n}. So R_{0}|_{σ} is of degree (at least, and hence equal to) d̂_{n} in the coefficients of A_{n}. Since σ does not affect the coefficients of A_{n}, we conclude that R_{0} also has degree d̂_{n} in the coefficients of A_{n}.

(b) With respect to the coefficients of A_{i}, G^{(i)} is homogeneous and R_{0} divides G^{(i)} implies R_{0} is also homogeneous; the argument in part (a) shows that R_{0} has degree d̂_{i}.

(c) Let σ be the specialization such that A_{i}|_{σ} = c_{i}X^{d_{i}} for i = 1, …, n. Then R_{0}|_{σ} divides

G^{(i)}|_{σ} = c_{1}^{d_{1}^{(i)}} ⋯ c_{n}^{d_{n}^{(i)}} implies that R_{0}|_{σ} = α · c_{1}^{e_{1}} ⋯ c_{n}^{e_{n}} for some e_{i}’s and α is a unit. Now σ(c_{i}) = c_{i} for all i = 1, …, n implies that R_{0}|_{σ} is a monomial in R_{0}. Since R_{0} is homogeneous of degree d̂_{i} in the coefficients of A_{i} (from part (b)), this means e_{i} = d̂_{i} for each i = 1, …, n.

Finally, we remove the assumption that Σ has only generic polynomials: since G and R_{0} are obtained from the generic case by a common specialization, any equality would be preserved. In particular,

(a) holds generally. Next (b) holds since the degree d̂_{i} in the coefficients of A_{i} is preserved under any specialization in which Σ remains a set of forms (such specializations sends each c_{i} to 0 or c_{i}). Finally (c) is preserved by specializations in which Σ remains regular. Q.E.D.

Macaulay’s Theorem. At this point, we have a method a computing the Macaulay resultant, using the GCD formula of (30). Actually, it turns out that we can avoid GCD computation and obtain R_{0} as a sequence of 2n divisions involving minors of the M^{(i)}’s (§9). But a better method follows from an important result of Macaulay [17]. Let M be a Macaulay matrix of Σ (for instance, take M = M^{(n)}) and let L be the principal submatrix of M obtained by deleting all the columns that are labeled by almost-reduced power products, and also deleting the rows corresponding to the deleted columns. Note that an almost-reduced power product can be characterized as one that labels some column in the last block of the matrix M^{(i)}, for some i = 1, …, n. Hence there are exactly d̂ almost-reduced power products in PP^{d} where (see equation (24))

d̂:= ∑_{i=1}^{n} d̂_{i}.  (31)

We cite without proof:

Theorem 32 (Macaulay)

R_{0} = det(M)/ det(L).  (32)

§8. U-Resultant  Lecture XI  Page 28

For example, if M = M^{(3)} is the Macaulay matrix for the system (26) above, then the only power product in PP^{2} that is not almost-reduced is XY. In this case, L is a 1 × 1 matrix containing the entry a_{1}. Note that it is hardly obvious from an examination of the matrix M that such a factor a_{1} exists in det(M).

Remark. The basic properties of the Macaulay resultant goes back to Mertens [21]. It was also treated by Hurwitz [10] and Perron [23]. The only proof in print of Macaulay’s theorem seems to be his original paper [17]. This paper contains the construction of the matrix M above. These ideas apparently trace back to Bezout (1779). See also [18]. For improved constructions when all the polynomials have the same degree, see [19].

Exercises

Exercise 7.1: Verify (25). Give necessary and sufficient conditions on the d_{i}’s so that |PP_{i}^{d}| = d̂_{i} implies i = n. □

Exercise 7.2: Construct the partition of PP^{d} = ⊎_{i=1}^{n}PP_{i}^{d} in the following cases:

(i) Let n = 3, (d_{1}, d_{2}, d_{3}) = (2, 4, 2). So d = 6. (ii) Let (d_{1}, …, d_{n}) = (1, 1, …, 1, m). So d = m. □

Exercise 7.3: Consider the Macaulay resultant for the following:

(i) A system of n generic linear forms in n variables. Verify that this is the standard determinant. (ii) A system of 2 generic forms in 2 variables. Verify that this is the Sylvester resultant. (iii) A system of n − 1 generic linear forms and 1 arbitrary generic form, in n variables. □

Exercise 7.4: Consider the system in equation (26).

(i) Compute its Macaulay resultant in two ways: the formula of Macaulay (32) and by the division scheme (previous exercise). Show intermediate results. HINT: the Macaulay resultant is

R_{0} = a_{2}^{2}b_{1}^{2}c_{3}−2a_{1}a_{2}b_{1}b_{2}c_{3}+a_{1}^{2}b_{2}^{2}c_{3}+a_{2}^{2}b_{3}c_{1}^{2}+a_{3}b_{2}^{2}c_{1}^{2}−2a_{1}a_{2}b_{3}c_{1}c_{2}−2a_{3}b_{1}b_{2}c_{1}c_{2}+a_{1}^{2}b_{3}c_{2}^{2}+a_{3}b_{1}^{2}c_{2}^{2}

(ii) What are the elements of Γ_{2} (see §4, exercise 4.2) expressed in terms of R_{0}? □

Exercise 7.5: Consider the system Σ = {A_{1}, A_{2}, A_{3}} where A_{1}(X, Y, Z) is a generic of degree 1 and A_{2}(X, Y, Z), A_{3}(X, Y, Z) are generic of degree 2 (i.e., quadrics). Write down a Macaulay matrix M for Σ and its associated matrix L. Compute its Macaulay resultant. HINT: do not expect to explicitly write down the final resultant by hand — use some computer algebra system. □

Exercise 7.6: The Macaulay matrix M of Σ has shape N_{d}×N_{d} where d depends only on the degrees d_{1}, …, d_{n}. We want to exploit the sparsity structure of the actual forms in Σ. Describe an infinite family of systems Σ such that we can set up similar matrices M whose size is smaller than the corresponding Macaulay matrix. E.g., suppose each A_{i} ∈ Σ is a sum of powers: A_{i} = ∑_{j=1}^{n} c_{ij}X_{j}^{d_{i}}. □

§8. U-Resultant

Let Σ = {A_{1}, …, A_{r}} be a system of homogeneous polynomials in D[X_{1}, …, X_{n}] with a finite number s ≥ 1 of non-trivial zeros in the algebraic closure \overline{D}, say,

ξ^{(j)} = (ξ_{1}^{(j)}, …, ξ_{n}^{(j)}) , (j = 1, …, s),  (33)

such that every other zero of Σ is proportional to one of these zeros. Such a set {ξ^{(1)}, …, ξ^{(s)}} is called a representative set of solutions for Σ. We consider the problem of computing a representative set. A useful tool for this purpose is U-resultants.

The above “finiteness condition” is clearly the best that one can impose on the zero set of Σ, since if ξ = (ξ_{1}, …, ξ_{n}) is any zero, so is any multiple αξ = (αξ_{1}, …, αξ_{n}), α ∈ D. The set

D · ξ = {αξ : α ∈ D}

is called a solution line. So our assumption on the zero set of Σ amounts to saying that it has finitely many solution lines. Such a system Σ is also called a projective zero-dimensional system. Two solutions are said to be proportional if they belong to the same solution line.

We first introduce the polynomial

A_{0} = U_{1}X_{1} + ⋯ + U_{n}X_{n}

in the new indeterminates U = (U_{1}, …, U_{n}) and in X. Let Γ ⊆ D[U] be a resultant system of Σ′, where

Σ′:={A_{0}, A_{1}, …, A_{r}}.

We may assume that Γ is an ideal. Note that Γ is non-trivial (otherwise, for any j, we get that ∑_{i=1}^{n} α_{i}ξ_{i}^{(j)} = 0 for any specialization U_{i} → α_{i}, i = 1, …, n which is clearly false). Consider

G(U) := ∏_{j=1}^{s} g_{j}(U),  where g_{j}(U) := U_{1}ξ_{1}^{(j)} + ⋯ + U_{n}ξ_{n}^{(j)}.  (34)

We shall say that g_{j}(U) “encodes” the solution line corresponding to ξ^{(j)}.

Lemma 33 For any ground U-specialization σ, Γ|_{σ} = 0 iff G(U)|_{σ} = 0.

Proof. (⇒) If Γ|_{σ} vanishes, then Σ′|_{σ} has an X-solution. But since any X-solution is proportional to some solution ξ^{(j)} in (33), this means for some j,

A_{0}(ξ^{(j)}, U)|_{σ} = g_{j}(U)|_{σ} = 0,

which implies G(U)|_{σ} = 0. (⇐) If G|_{σ} vanishes then for some j, g_{j}(U)|_{σ} = 0. Then Σ′|_{σ} has the non-trivial solution ξ^{(j)}. Hence Γ|_{σ} vanishes. Q.E.D.

So Γ and G have precisely the same set of zeroes. By the Nullstellensatz (in the coefficient ring \overline{D}), for each R ∈ Γ, there is some e ∈ ℕ such that

R^{e} ∈ Ideal\overline{D}(G(U))  (35)

and there is some d ∈ ℕ such that

G(U)^{d} ∈ Ideal\overline{D}(Γ).  (36)

Note that

R_{0} := GCD(Γ).

is well-defined, assuming the GCD takes place in the UFD Q_{D}[U]. We will construct R_{0} explicitly as follows: for each i = 1, …, s, let e_{i} ≥ 0 be the maximum value such that g_{i}^{e_{i}} divides each R ∈ Γ. Since G(U) is a product of the irreducible linear forms g_{1}, …, g_{s}, it follows from (35) that each R is divisible by each g_{i}. This proves that each e_{i} ≥ 1. Next we pick H_{1}, …, H_{s} ∈ Γ such that g_{i}^{1+e_{i}} does not divide H_{i} (by definition, g_{i}^{e_{i}} divides H_{i}). From equation (36), there exists G_{1}, …, G_{t} ∈ Γ such that G(U)^{d} ∈ Ideal\overline{D}(G_{1}, …, G_{t}). Consider

R_{1} := GCD(H_{1}, …, H_{s}, G_{1}, …, G_{t})

where the GCD takes place in the UFD Q_{D}[U]. Clearly R_{1} = βg_{1}^{e_{1}} ⋯ g_{n}^{e_{n}} for some β ∈ Q_{D}[U]. We show that, in fact, β = 1. From our choice of G_{1}, …, G_{t}, we have GCD(G_{1}, …, G_{t})|G(U)^{d}. Hence R_{1}|G(U)^{d}, and so β is a power product in g_{1}, …, g_{n}. But no positive power of any g_{i} can divide β (otherwise βg_{i}^{e_{i}}|H_{i} implies g_{i}^{1+e_{i}}|H_{i}). This proves β ∈ Q_{D}, but this means β = 1, by the usual conventions for the GCD function. We define R_{0} as an element of D[U] by multiplying R_{1} with a suitable α ∈ D,

R_{0} := α · R_{1} ∈ D[U].

Clearly R_{1} (and hence R_{0}) is a GCD of Γ over Q_{D}[U].

We call R_{0} the U-resultant of Σ, and this is defined up to similarity (multiplication by elements of D). The resultant terminology for R_{0} is justified because R_{0} is a resultant polynomial of Σ: if Σ|_{σ} has a solution iff Γ|_{σ} = 0, iff G|_{σ} = 0, iff R_{0}|_{σ} = 0. We summarize all this:

Theorem 34 The U-resultant R_{0} of Σ is a resultant polynomial of {A_{0}, A_{1}, …, A_{r}}. It factors into linear factors of the form

g_{j} = U_{1}ξ_{1}^{(j)} + ⋯ + U_{n}ξ_{n}^{(j)}

(with some multiplicity e_{j} ≥ 1) in \overline{D}[U]. The distinct linear factors in this factorization correspond to the s solution lines D · ξ^{(j)} (j = 1, …, s) of Σ.

Solving Projective Zero-dimensional Systems. Thus solving Σ is reduced to factoring the U-resultant over \overline{D}. Let us now assume D = ℤ. We indicate how to use univariate real root isolation techniques and avoid factoring over ℂ. Our goal is to compute a representative set (33) of solutions for Σ in case r = n − 1. Let us first assume that ξ_{1}^{(j)} ≠ 0 for all j. We may proceed as follows.

(1) Compute R_{0} as the Macaulay resultant of Σ′.

(2) Define the partial U-specialization σ_{k} (for 2 ≤ k ≤ n) as follows:

σ_{k}(U_{ℓ}) = \{ \begin{matrix}U_{1}, & if ℓ = 1, \\ −1 & if ℓ = k, \\ 0 & else. \end{matrix}  (37)

Now isolate the roots of the specialized U-resultant,

R_{0}|_{σ_{k}} = ∏_{j=1}^{s}(U_{1}ξ_{1}^{(j)} − ξ_{k}^{(j)})^{e_{j}}.

Then each ξ_{k}^{(j)}/ξ_{1}^{(j)} (j = 1, …, s) appears as a root of R_{0}|_{σ_{k}}. Let T_{k} denote this set of roots.

§9. Generalized Characteristic Polynomial  Lecture XI  Page 31

(3) Finally, we need to check for each element ξ = (1, ξ_{2}, …, ξ_{n}) ∈ {1} × ∏_{k=2}^{n} T_{k} whether ξ is a zero of Σ. The ξ_{i}’s are algebraic numbers and so, in principal, we know how to check this. For instance, ξ_{i} may represented via isolating intervals or it may be represented by a sufficiently good approximation (cf. §IX.6). In any case, we need some root bounds on ξ_{i}. This is derived below.

Note that if the 1st and kth components of any root ξ^{(j)} both vanish, then R_{0} vanishes under the specialization σ_{k} and the method fails. In this case, we may be able to replace the special role of the first coordinate by the ith coordinate if the following holds: for all k, k ≠ i, and for all j = 1, …, s, either ξ_{k}^{(j)} or ξ_{i}^{(j)} is non-zero. Otherwise, we need further techniques. Since D = ℤ, we may assume that R_{0}(U) is a primitive polynomial (§III.1). Hence the U-resultant is determined up to sign. We first factor R_{0} over the ℤ:

Lemma 35 Let W ⊆ {1, …, n}. Then R_{0}(U) ∈ ℤ[U] factors over ℤ into two polynomials

R_{0} = R_{W} \overline{R}_{W}

with the following property: for all j = 1, …, s,

\frac{R_{W}}{g_{j}} ∈ ℂ[U] iff (∃i ∈ W)[ξ_{i}^{(j)} ≠ 0].

Proof. We may choose \overline{R}_{W} (U) ∈ ℤ[U] to be the U-resultant of

Σ_{W} := Σ ∪ {X_{i} : i ∈ W }.

Note that \overline{R}_{W} |R_{0} since each zero of Σ_{W} is a zero of Σ. Q.E.D.

Choosing W = {1, k}, we may apply now the substitution (37) to R_{W} (U), etc, as before. But how do we know R_{W} (U)? After factoring R_{0}(U) into its irreducible factors over ℤ, we can easily discover which of these factors are factors of R_{W} (U): these are precisely the factors that do not vanish under the specialization (37). See also [16, 4].

Exercises

Exercise 8.1: We may assume that Γ consists of inertial elements. Show that Γ is a homogeneous ideal in U. □

Exercise 8.2: The U-resultant of X^{2} + Y^{2} − Z^{2} and (X − Y − Z)(X − Y + Z) is U_{1}^{2}U_{2}^{2} − U_{1}^{2}U_{3}^{2} − U_{2}^{2}U_{3}^{2} + U_{3}^{4}. What are the linear factors of this U-resultant? Give a geometric interpretation of this system. □

Exercise 8.3: Complete the above outline of a method to solve a projective zero-dimensional system of n − 1 equations in n variables. □

§9. Generalized Characteristic Polynomial

Let

Σ = {A_{1}, …, A_{n}} ⊆ ℤ[C][X_{1}, …, X_{n}]  (38)

be a system of n partial forms in n variables. Let d_{i} = deg A_{i} ≥ 1. The “main coefficient” of A_{i} is again the coefficient a_{i} ∈ ℤ∪C of X_{i}^{d_{i}} in A_{i}. Note that a_{i} may be 0. We are interested in computing the Macaulay resultant R_{0} = res(Σ), and its applications for solving zero-dimensional polynomial systems.

First consider the problem of computing R_{0}. In the two extreme cases, Σ may be a system of generic polynomials or it may be a system of homogeneous polynomials in ℤ[X_{1}, …, X_{n}]. In case Σ is a system of generic forms, we may use Macaulay’s formula det(M)/ det(L) (equation (32)) to compute the resultant. If Σ is not generic, we can still use compute Macaulay’s resultant for the generic case and then specialize. The problem is that the generic case is not computationally feasible, except for very small systems. Ideally, we should try to compute directly with the specializations M̃, L̃ of the matrices M, L. Unfortunately, the specialized determinants det(M̃) and det(L̃) may both vanish so that the division cannot be carried out.

To avoid this problem, Canny [4] introduced the (generalized) characteristic polynomial χ^{Σ}(λ) of Σ where λ is a new indeterminate. This is defined to be the Macaulay resultant of the system

Σ_{λ}:={λX_{i}^{d_{i}} − A_{i} : A_{i} ∈ Σ}.  (39)

Let M be a Macaulay matrix of Σ_{λ} (this can be one of the M^{(i)}’s in §7). Let χ^{M}(λ) be the characteristic polynomial of M. Recall that in general, for any square matrix M, the characteristic polynomial of M (in the indeterminate λ) may be defined to be

χ^{M}(λ) := det(λI − M)

where I is the identity matrix. In analogy to equation (32), we see that

χ^{Σ}(λ) = \frac{χ^{M}(λ)}{χ^{L}(λ)}.  (40)

Note that while (32) assumes a regular system of forms, the formula (40) is also valid^{8} for any M, L constructed from partial forms because of the presence of λ. There are well-known methods for computing the characteristic polynomials of matrices. Indeed, we can adapt Bareiss’ algorithm (§X.2) if we want a polynomial-time algorithm. Efficient parallel algorithms^{9} by Berkowitz [1] is also available for this computation. Once we have computed χ^{Σ}(λ), we can recover the Macaulay resultant R_{0} = res(Σ) via the formula

R_{0} = ±χ^{Σ}(0).

In other words, up to sign, R_{0} is just the constant term in the polynomial χ^{Σ}.

Division Scheme for χ^{Σ}(λ). We derive an alternative method suggested by Canny with the attractive feature that it only involves a sequence of 2n exact divisions. Let

Σ′ = {A′_{1}, …, A′_{n}} ⊆ ℤ[C, c_{1}, …, c_{n}][X_{1}, …, X_{n}]

where A′_{i} is obtained from A_{i} by replacing a_{i} with a new indeterminate c_{i}. We first develop the scheme to compute the Macaulay resultant of Σ′ since its correctness is more transparent. Then we specialize Σ′ to Σ(λ) by replacing each c_{i} with λ − a_{i}.

8More precisely, the only concern when we partially specialize the numerator and denominator in formula (40) is that the denominator may vanishes. But this cannot happen because of the introduction of λ.

9The method of Berkowitz explicitly avoids division in the underlying domain. A comparable algorithm of Csanky does not have this property (but may be adapted to yield an extra factor of n!, see [25, appendix]).

As in §7, let G^{(i)} (i = 1, …, n) denote the determinant of the Macaulay matrix M^{(i)} with respect to the system Σ′. Writing χ_{0} for the Macaulay resultant of Σ′, we let

H^{(i)} := \frac{G^{(i)}}{χ_{0}} .  (41)

Clearly, H^{(i)} is a polynomial in ℤ[C, c_{1}, …, c_{n}]. We make the important observation:

H^{(i)} is independent of c_{i}.  (42)

This is because the c_{i}-degree of G^{(i)}, and of χ_{0}, are both equal to d̂_{i}. Next, define

G_{j}^{(i)}, H_{j}^{(i)}, χ_{j}, (j = 0, …, n)

to be the leading coefficients (respectively) of G^{(i)}, H^{(i)}, χ_{0} when viewed as polynomials in c_{1}, …, c_{j}. Strictly speaking, it is nonsense to speak of the “leading coefficient” of a multivariate polynomial. But G^{(i)}, χ_{0} are “rectangular” and hence has a “leading coefficient” in the following sense:

Definition. A polynomial P = P (c_{1}, …, c_{n}) ∈ D[c_{1}, …, c_{n}] is rectangular if it contains a monomial of the form αc_{1}^{d_{1}} ⋯ c_{n}^{d_{n}} for some α ∈ D where each d_{i} is the degree of P in the indeterminate c_{i}. We say P is monic rectangular if, in addition, α = 1. The leading coefficient of a rectangular P, when viewed as an element of D′[c_{1}, …, c_{i}] where D′ = D[c_{i+1}, …, c_{n}], refers to the element β ∈ D′ such that βc_{1}^{d_{1}} ⋯ c_{i}^{d_{i}} is a monomial of P.

Now each G_{j}^{(i)}, H_{j}^{(i)}, χ_{j} is, in turn, a rectangular monic polynomial in c_{j+1}, …, c_{n}. The notation “χ_{j}” agrees with our original subscript “0” in χ_{0}. From (41), we obtain at once the corresponding equations

H_{j}^{(i)} = \frac{G_{j}^{(i)}}{χ_{j}} ,  (j = 0, …, n).  (43)

In view of (42), we obtain a series of equations and recurrences for the χ_{i}’s:

H_{i}^{(i)} = H_{i−1}^{(i)},  (i = 1, …, n),
\frac{G_{i}^{(i)}}{χ_{i}} = \frac{G_{i−1}^{(i)}}{χ_{i−1}} ,

χ_{i−1} = \frac{G_{i−1}^{(i)}}{G_{i}^{(i)}} χ_{i}.

Telescoping,

χ_{0} = \frac{G_{0}^{(1)}}{G_{1}^{(1)}} \frac{G_{1}^{(2)}}{G_{2}^{(2)}} ⋯ \frac{G_{n−1}^{(n)}}{G_{n}^{(n)}} χ_{n}.  (44)

Since χ_{n} = 1 and each G_{j}^{(i)} is a minor of M^{(i)}, this formula leads to scheme to compute χ_{0} by a sequence of exact divisions as follows.

Division Scheme: Input: G_{i}^{(i)} and G_{i−1}^{(i)} for i = 1, …, n. Output: χ_{0}(λ), the generalized characteristic polynomial. Method:

Initialization:χ_{n} ← 1. for i ← n downto 1, do

1. H_{i−1}^{(i)} ← \frac{G_{i}^{(i)}}{χ_{i}}.
2. χ_{i−1} ← \frac{G_{i−1}^{(i)}}{H_{i−1}^{(i)}} .

Now let σ be the specialization that takes c_{i} to λ−a_{i}. We could have carried the above computation for indeterminate c_{i}’s and then specialize using σ. But this is inefficient. If G̃_{j}^{(i)}, H̃_{j}^{(i)}, etc, denote the σ-specialization of G_{j}^{(i)}, H_{j}^{(i)}, etc, then notice that G̃_{j}^{(i)} can be obtained as an appropriate minor of M̃^{(i)}. Then the H̃_{j}^{(i)}’s and R̃_{j}’s can be computed using the same scheme. Of course, R̃_{0} is just the desired characteristic polynomial χ^{Σ}(λ).

Computing the Constant Term of χ^{Σ}(λ). Suppose we only want to compute R_{0}, without computing the entire characteristic polynomial χ_{0}. We observe that χ^{M}(λ) and χ^{L}(λ) are monic polynomials in λ. As such, the coefficients of their quotient can be directly obtained as suitable subdeterminants according to §III.4. To be explicit, suppose

C(X) = ∑_{i=0}^{m−n} c_{i}X^{i}  (45)

is the quotient of A divided by B where

A(X) = ∑_{i=0}^{m} a_{i}X^{i}, B(X) = ∑_{i=0}^{n} b_{i}X^{i},  m ≥ n.  (46)

are monic polynomials. Then (§III.4) the coefficient c_{i} is, up to sign, the (m − n − i + 1)st principal minors of the following matrix:

M := [ \begin{matrix}a_{m} & a_{m−1} & a_{m−2} & ⋯ & a_{m−n} & ⋯ & a_{1} & a_{0} \\ b_{n} & b_{n−1} & b_{n−2} & ⋯ & b_{0} & ⋯ & 0 & 0 \\ & b_{n} & b_{n−1} & ⋯ & b_{1} & ⋯ & 0 & 0 \\ & & ... & & & & & ⋮ \\ & & & b_{n} & b_{n−1} & ⋯ & b_{1} & b_{0} \end{matrix} ] .  (47)

For instance, the leading coefficient c_{m−n} of C is given by the 1st principal minor, which is a_{m} = 1.

The next coefficient c_{m−n−1} is given by det [ \begin{matrix}a_{m} & a_{m−1} \\ b_{n} & b_{n−1} \end{matrix} ]. For i = 1, …, m − n, the coefficient

c_{m−n−i} depends only on a_{m−1}, …, a_{m−i} and b_{n−1}, …, b_{min{0,n−i}}. In particular, the constant term c_{0} depends only on the leading m − n + 1 coefficients of polynomials A and B. Note that these remarks do not assume that B divides A exactly.

Now return to our goal of computing the constant term R_{0} of χ^{M}/χ^{L}. First, recall that M is an N_{d} × N_{d} matrix where N_{d} = \binom{d+n−1}{d} and d = 1 + ∑_{i=1}^{n} d_{i} (see §7). Also L is a (N_{d} − d̂) × (N_{d} − d̂) submatrix of M where d̂= ∑_{i=1}^{n} d̂_{i} and d̂_{i} = (∏_{j=1}^{n} d_{j})/d_{i}. Hence χ^{M}/χ^{L} is a polynomial of degree d̂. Therefore to compute the constant term of χ^{M}/χ^{L}, it is sufficient to compute the leading d̂+ 1 coefficients of χ^{M} and χ^{L}.

Solving Zero-dimensional Systems. In the rest of this section, assume the system

Σ = {A_{1}, …, A_{n}} ⊆ ℤ[X_{1}, …, X_{n}],  (48)

not necessarily homogeneous, has a finite number of zeros in ℂ^{n}. Our goal is to find these zeros. We may first homogenize each A_{i} to Â_{i} using a new variable X_{0}. Let Σ̂ = {Â_{1}, …, Â_{n}}. Assuming that Σ̂ has finitely many solution lines in ℂ^{n}, then we may compute its U-resultant R(U_{1}, …, U_{n}), which is just the Macaulay resultant of

Σ̂ ∪ {A_{0}},  where A_{0} = X_{0}U_{0} + X_{1}U_{1} + ⋯ + X_{n}U_{n}.  (49)

Using R(U), we may compute a representative set of Σ̂, as in §8. From among this representative set, any zero

ξ′ = (ξ′_{0}, ξ′_{1}, …, ξ′_{n})

where ξ′_{0} ≠ 0 will yield a zero (ξ′_{1}/ξ′_{0}, …, ξ′_{n}/ξ′_{0}) of Σ. We say ξ′ is a “zero at infinity” or a “finite zero” for Σ̂, depending on whether ξ′_{0} = 0 or not. In terms of solution lines, we speak of “solution lines at infinity” or “finite solution line”. Conversely, any zero ξ = (ξ_{1}, …, ξ_{n}) of Σ is proportional to a finite zero in the representative set. Hence, the system (48) is solved.

The problem is that Σ̂ may have infinitely many solution lines at infinity (Exercise). That is, its zero set has dimension at least 1 in the projective n-space, ℙ^{n}(ℂ). For any U-specialization σ, the equation A_{0}|_{σ} = 0 defines a hyperplane, which is a zero set of dimension n−1, in projective n-space. If the zero set of Σ̂ is dimension at least 1, it must intersect this hyperplane. This is because of the general result^{10} that two zero sets in projective n-space of dimensions i and j (respectively) have non-empty intersection provided i + j ≥ n. This means that the system (49) has a common solution when specialized by σ, and so R(U)|_{σ} = 0. Since σ is arbitrary, we conclude that R(U) is identically zero. Combined with §9, we conclude:

Lemma 36 The U-resultant of Σ̂ does not vanish iff Σ̂ is projective zero-dimensional.

This result can be the basis of a method for testing if Σ̂ is projective zero-dimensional. If Σ̂ vanishes, U-resultants is useless for our purposes. The next section shows how to overcome this.

Exercises

Exercise 9.1: Verify that the following system has finitely many solutions, and solve it.

Σ = {X^{3} − X^{2} + X − 1, XY − Y − X^{2} + X, Y^{2} − X^{2}}
□

Exercise 9.2: (Hinternaus) Compute the U-resultant of A_{1} = Y^{3} − 2t^{3} and A_{2} = Y^{3} + 3XY^{2} + 3X^{2}Y + X^{3} − 2t^{3}, and solve this system. HINT: there are 9 solutions. □

Exercise 9.3: Construct a system Σ with finitely many zeros, but where Σ̂ has infinitely many solution lines. □

10See, e.g., Mumford [22]. This is a generalization of a more familiar fact on the intersection of linear subspaces: if S, T are linear subspaces of Euclidean n-space, then dim(S∩T) = dim(S)+dim(T)−dim(S∪T). If dim(S)+dim(T) ≥ n then the intersection S ∩ T is necessary non-empty since dim(S ∪ T) ≤ n.

§10. Generalized U-resultant  Lecture XI  Page 36

Exercise 9.4: Try to adapt Berkowitz’ algorithm [1] to compute only the first k (for any given k ≥ 1) leading coefficients of the characteristic polynomial of a matrix. □

Exercise 9.5: Study conditions under which one can directly use the Macaulay quotient formula (without introducing extra indeterminates). □

§10. Generalized U-resultant

Let Σ = {A_{1}, …, A_{n}} ⊆ ℤ[X_{1}, …, X_{n}] have finitely many zeros in ℂ^{n} and let Σ̂ = {Â_{1}, …, Â_{n}} ⊆ ℤ[X_{0}, X_{1}, …, X_{n}]. Assume the U-resultant of Σ̂ vanishes. We now introduce a non-vanishing substitute for the U-resultant.

Let λ be a new indeterminate and compute the U-resultant of

Σ(λ) :={λX_{1}^{d_{1}} − Â_{1}, λX_{2}^{d_{2}} − Â_{2}, …, λX_{n}^{d_{n}} − Â_{n}}.  (50)

The result, denoted

χ(λ, U),

is almost the characteristic polynomial of the system (49). In fact, under the partial specialization taking U_{0} to λ − U_{0}, χ(λ, U) is transformed to the characteristic polynomial of (49). This implies χ(λ, U) is non-zero. Viewing χ(λ, U) as a polynomial in λ, let R̂(U) be its tail coefficient. Alternatively, if i_{0} ≥ 0 is the largest index such that λ^{i_{0}} divides χ(λ, U), then

χ′(λ, U) := χ(λ, U)λ^{−i_{0}}  (51)

is a polynomial (the “reduced characteristic polynomial”) with R̂(U) as constant term. It turns out that R̂(U) can now play the role of the U-resultant. Note that the constant term of χ(λ, U) is just the usual U-resultant of Σ̂. When this constant term is non-zero, R̂(U) is equal to this U-resultant. It is therefore appropriate to call R̂(U) the generalized U-resultant of Σ̂.

Lemma 37 R̂(U) is homogeneous of degree D = ∏_{i=1}^{n} d_{i} in U_{0}, …, U_{n}.

Proof. Suppose Σ^{∧} denote the system (50) where we replace each non-zero coefficient of a power product of X by a new indeterminate, and suppose σ is the specialization such that Σ^{∧}|_{σ} = Σ(λ). [For instance if the coefficient of X_{1}^{d_{1}} in Â is c_{1} ∈ ℤ, then we replace λ − c_{1} by a new indeterminate c′_{1}, and σ(c′_{1}) = λ−c_{1}.] The U-resultant of Σ^{∧}, denoted R^{∧}, is the Macaulay resultant of Σ^{∧} ∪{A_{0}}. By theorem 31 (§7), R^{∧} is homogeneous of degree D = ∏_{i=1}^{n} d_{i} in the coefficients U of A_{0}. Since R^{∧}|_{σ} = χ(λ, U) and since σ does not affect the U_{i}’s, it follows that χ(λ, U) is homogeneous of degree D in U. The lemma follows since R̂λ^{i} (for some i ≥ 0, perhaps with an integer coefficient) is a monomial of χ(λ, U) and λ does not occur in A_{0}. Q.E.D.

Lemma 38 For all α ∈ ℂ \ {0}, χ(α, U) ≠ 0 and factors completely into D = ∏_{i=1}^{n} d_{i} linear homogeneous factors in U.

Proof. Pick any u = (u_{0}, …, u_{n}) ∈ ℂ^{n+1} such that R̂(u) ≠ 0. Then as α → 0, the non-constant monomials in the “reduced characteristic polynomial” (see (51)) χ′(α, U) approach 0. Hence for α small enough, χ′(α, u) ≠ 0 and so χ′(α, U) ≠ 0. This implies χ(α, U) ≠ 0. But in fact, this argument works for any α ≠ 0 because we can make R̂(u) arbitrarily large by multiplication with a large constant K, since R̂(Ku) = K^{D}R̂(u).

To see that χ(α, U) completely factors, note that χ(α, U) is the U-resultant of the system (50) under the specialization λ ⟶ α. It follows from lemma 36 that this specialized system has finitely many solution lines. These solution lines correspond to the complete factorization of χ(α, U) into linear homogeneous factors in U. By lemma 37, the number (with multiplicity of factors counted) of linear factors is D = ∏_{i=1}^{n} d_{i}. Q.E.D.

Consider the zero set of the characteristic polynomial,

V := Zero(χ(λ, U)) ⊆ ℂ × ℂ^{n+1}.

Clearly

V = V_{0} ∪ V_{1}  (52)

where V_{0} := Zero(λ^{i_{0}}) and V_{1} := Zero(χ′(λ, U)) (see (51)). Note that if i_{0} = 0 then V_{0} is the empty set, otherwise it is the hyperplane {0} × ℂ^{n+1}. By lemma 38, we have V_{1} ⊈ V_{0}. It follows that (see [14, p.131])

dim(V_{1} ∩ V_{0}) ≤ n.

Also, let

W := Zero(R̂(U)) ⊆ ℂ^{n+1}.

The following simple observation is a useful tool.

Lemma 39 Let u ∈ ℂ^{n+1}. If there exists a sequence {(λ_{i}, u_{i})}_{i≥1} in V_{1} \ V_{0} that converges to (0, u) then u ∈ W.

Proof. By choice of λ_{i}, u_{i}, χ′(λ_{i}, u_{i}) = 0. Since {(λ_{i}, u_{i})}_{i≥0} converges to (0, u), we conclude by continuity that χ′(0, u) = 0. But χ′(0, u) = 0 implies R̂(u) = 0. Q.E.D.

Let

π_{U} : ℂ × ℂ^{n+1} → ℂ^{n+1}

be the projection map onto the U-coordinates. Thus π(α, u_{0}, u_{1}, …, u_{n}) = (u_{0}, …, u_{n}). In view of lemma 38, for all α ≠ 0 small enough, the set

W (α) := π_{U}(V ∩ ({α} × ℂ^{n+1})

is a union of D (not necessarily distinct) hyperplanes in ℂ^{n+1}. Now we may view W (λ) as a parametrized system of D hyperplanes. In a suitable sense, the function W (λ) is continuous in the neighborhood λ = 0. To see this, view the D hyperplanes dually, as the multiset of D solution lines of a homogeneous polynomial χ_{λ}(U) in U with coefficients depending on λ. The multiset of D solution lines vary continuously with λ provided the (homogeneous) degree is constant. In our case, this provision amounts to λ ≠ 0. We may take the distance between two solution lines to be the Euclidean distance between their respective intersection points with the unit sphere. Continuity of the D lines means that for any ϵ > 0 small enough, there is a δ > 0 such that if λ varies by less than δ then for each solution line ℓ with multiplicity μ ≥ 1, there are exactly μ perturbed solutions lines (counting multiplicity) that are within ϵ of ℓ. Take any sequence \overline{λ} = \{λ_{i}\}_{i≥1} that converges to 0. The systems W (λ_{i}) converge as i → ∞. By compactness of the space of hyperplanes (this is a Grassmanian space, or the fact that the space of solution lines is topologically the unit sphere with antipodal points identified), there exists a limit system of D hyperplanes which we may denote by

W (0).

We show W (0) is unique, in fact, it is equal to W, the zero set of R̂(U). To see this, consider any u = (u_{0}, …, u_{n}) ∈ W (0) \ 0. Note that u occurs in W (0) with a given multiplicity. From our definition of W (0), there is a sequence {ζ_{i}}_{i≥1} in V_{1} \ V_{0} that approaches (0, u). In fact, we may choose ζ_{i} ∈ ({λ_{i}} × W (λ_{i})) ⊆ V_{1} for all i ≥ 1. By lemma 39, this implies u ∈ W (with its multiplicity intact). Thus W contains the D hyperplanes of W (0). Since W = Zero(R̂(U)) and R̂(U) has degree D, we conclude:

Lemma 40 We have the equality W (0) = W = Zero(R̂(U)).

Unfortunately, this result does not establish that the zeros of Σ are encoded (in the sense of Uresultants) among the linear factors of R̂(U). We need a more careful analysis of the behaviour of the system as λ goes to 0, using an argument similar to Renegar [25].

Pick any u ∈ ℝ^{n+1} such that R̂(u) ≠ 0. Let e_{i} ∈ ℝ^{n+1} (i = 0, …, n) be the elementary unit vector with 1 at the (i + 1)st coordinate and 0 elsewhere. With t a new indeterminate, consider the polynomial

r_{i}(λ, t) := χ′(λ, tu − e_{i}),

where we view r_{i}(λ, t) as a polynomial in t with coefficients parametrized by λ. To avoid excessive notations, we may by reason of symmetry focus on i = 1, in which case we simply write r_{1}(λ, t) as r(λ, t).

Lemma 41 In a small enough neighborhood N_{0} of 0, for all λ ∈ N_{0}:

(i) The polynomial r(λ, t) is non-vanishing of degree D in t.

(ii) We have χ′(λ, u) ≠ 0. In particular, χ′(0, u) ≠ 0.

Proof. (i) Note that

R̂(tu − e_{1}) = t^{D}R̂(u) + R̂(−e_{1}) + t · q(t, u)

where q(t, u) is a polynomial whose t-degree is less than D − 1. Hence R̂(tu − e_{1}) is non-vanishing of degree t. Then, arguing as in lemma 38, we conclude that χ′(λ, tu − e_{1}) does not vanish for small enough λ. In fact, r(λ, t) has the form t^{D}(R̂(u) + λh(λ, u)) + l.o.t., for some h(λ, u) and “l.o.t” indicates lower order terms in t. Thus the leading coefficient of r(λ, t) tends to R̂(u) when λ is small enough. This establishes the existence of exactly D roots. (ii) Furthermore, when λ is small enough, χ′(λ, u) tends to R̂(u), a non-zero value. Q.E.D.

By lemma 38,

χ′(λ, U) = ∏_{j=1}^{D} g_{j}(λ, U), where g_{j}(λ, U) = ∑_{ℓ=0}^{n} U_{ℓ}ξ_{ℓ}^{(j)}(λ),

where ξ^{(j)}(λ) = (ξ_{0}^{(j)}(λ), …, ξ_{n}^{(j)}(λ)). It is immediate from

r(λ, t) = ∏_{j=1}^{D} g_{j}(λ, tu − e_{1}),

that the zeros of r(λ, t) are precisely those t such that

g_{j}(λ, tu − e_{1}) = tg_{j}(λ, u) − ξ_{1}^{(j)}(λ) = 0  (53)

for some j = 1, …, D. Since χ′(λ, u) ≠ 0 (for λ ∈ N_{0}), we conclude that g_{j}(λ, u) ≠ 0 for all j. It follows that r(λ, t) has exact D roots (possibly non-distinct) that can be expressed (via (53)) in the form

t_{1}^{(j)}(λ) = \frac{ξ_{1}^{(j)}(λ)}{g_{j}(λ, u)},  (j = 1, …, D).  (54)

We now use a well-known fact: if r(λ, t) is a polynomial in t whose coefficients vary continuously with λ within an open interval N_{0}, and the degree D of r(λ, t) is invariant for λ ∈ N_{0}, then the D roots (with multiplicity counted) of r(λ, t) varies continuously in the following precise sense:

For all λ_{0}, there exist ε > 0 and δ > 0 such that for all λ′, if |λ′ − λ_{0}| < δ then for each root t_{0} of multiplicity μ ≥ 1 of r(λ_{0}, t), there are exactly μ roots (with multiplicity counted) of r(λ′, t) that are within distance ε of t_{0}.

We may therefore define the limits of these root functions,

τ_{1}^{(j)} := lim_{λ→0} t_{1}^{(j)}(λ).

Note that τ_{1}^{(j)} is finite because the denominator in (54) approaches a non-zero value g_{j}(0, u). Returning to the general notation r_{i}(λ, t) (for i = 0, …, n, not just i = 1), we have thus established the existence of the continuous root functions

t_{i}^{(j)}(λ), (i = 0, …, n; j = 1, …, D)

for λ ∈ N_{0}. Again, we can take their limits as λ approaches 0. But we need something more. We really want to ensure that the “j” superscripts are assigned consistently, so that

(t_{0}^{(j)}(λ), …, t_{n}^{(j)}(λ)) · g_{j}(λ, u) = (t_{0}^{(j)}(λ) · g_{j}(λ, u), …, t_{n}^{(j)}(λ) · g_{j}(λ, u))  (55)

are indeed zeros of Σ(λ) (cf. (54)).

Each time a multiple root splits, we have to decide which of the branches should a particular t_{i}^{(j)}(λ) follow. There can be a problem if these D roots merge and split indefinitely. More precisely, let us temporarily fix i = 0, 1, …, n. For any λ ∈ N_{0}, let us say that the multiset of roots

S_{i}(λ) :={t_{i}^{(j)}(λ) : j = 1, …, D}

has generalized multiplicity (or simply, multiplicity) μ = (μ_{1}, μ_{2}, …, μ_{D}) ∈ ℕ^{D} if there are exactly μ_{1} simple roots, exactly μ_{2} roots of multiplicity 2, and in general, μ_{i} roots of multiplicity i. So ∑_{i=1}^{D} i · μ_{i} = D. If the generalized multiplicity is constant for λ ∈ N_{0}, then we clearly can define t^{(j)}(λ) unambiguously, and thus the limiting ξ^{(j)} are unique. We will show that the generalized multiplicity of S_{i}(λ) can only change a finite number of times as λ approaches 0. Again, it is sufficient to focus on case S_{1}(λ), and let μ(λ) denote the generalized multiplicity of S_{1}(λ). We call λ′ ∈ ℂ a critical value for S_{1}(λ) if for all neighborhoods N′ of λ′, there exists λ′′ ∈ N′ such that μ(λ′′) ≠ μ(λ′). Let the derivative of r be

r′(λ, t) = \frac{dr(λ, t)}{dt}.

Let p_{j}(λ) denote the pseudo-principal subresultant coefficient ppsc_{j}(r, r′) (for j = 0, …, D − 1) of r(λ, t) and r′(λ, t) (§III.7). For any λ′, the degree of GCD(r, r′) is the smallest j such that p_{j}(λ′) ≠ 0 (§III.8, Exercise). Hence the number of distinct roots of r is equal to D − j (property C5, §VI.1). Let j_{1} be the least index such that p_{j}(λ) is non-vanishing. Define C_{1}(λ) := p_{j_{1}}(λ). Clearly j_{1} and C_{1}(λ) are well-defined.

Lemma 42

(i) A value λ′ is a critical for S_{1}(λ) iff λ′ is a root of C_{1}(λ).

(ii) If λ_{0} < λ_{1} and μ(λ_{0}) ≠ μ(λ_{1}) then there is a critical value λ′, λ_{0} ≤ λ′ ≤ λ_{1}.

(iii) For small enough neighborhood N_{0} of 0, the polynomial r(λ, t) has exactly D − j_{1} distinct roots when λ ∈ N_{0}.

Proof. (i) Let us note that if λ′ is critical then every neighborhood of λ′ contains a λ′′ such that r(λ′′, t) has a different number of distinct roots than r(λ′, t). Hence, if C_{1}(λ′) = 0 then λ′ is critical. Conversely, if C_{1}(λ′) ≠ 0 then there is a neighborhood N′ of λ′ such that for all λ′′ ∈ N′, p_{j}(λ′′) ≠ 0 for j ∈ I. Then the number of distinct roots of r(λ, t) is constant for λ ∈ N′. So such a λ′ is not critical. (ii) If either λ_{0} or λ_{1} is critical then we are done. Otherwise, let λ′ = sup{λ ∈ (λ_{0}, λ_{1}) : μ(λ) = μ(λ_{0})}. If μ(λ′) = μ(λ_{0}) then for all ε > 0 sufficiently small, μ(λ′ + ε) ≠ μ(λ′). If μ(λ′) ≠ μ(λ_{0}) then for all ε > 0 sufficiently small, μ(λ′ − ε) ≠ μ(λ′). In either case, λ′ is critical. (iii) Choose N_{0} small enough to avoid all the roots of C_{1}(λ). By (i) and (ii), μ(λ) is invariant for λ ∈ N_{0}. Q.E.D.

The above focused on the multiset S_{1}(λ). Now assume N_{0} is small enough to ensure that the previous two lemmas hold for each S_{i}(λ) (i = 0, 1, …, n). Restricting λ to N_{0}, we can now define unambiguously the continuous functions t_{i}^{(j)}(λ) for each i = 0, …, n and j = 1, …, D. Moreover, we will choose the indexes so that for each λ ∈ N_{0}, the point in (55) is a zero of Σ(λ). Now we may define

ξ^{(j)} = (ξ_{0}^{(j)}, …, ξ_{n}^{(j)})  where ξ_{i}^{(j)} := τ_{i}^{(j)}g_{j}(0, u).  (56)

It is immediate that each ξ^{(j)} is a zero of Σ(0). But Σ(0) = Σ̂∪{A_{0}}. By a suitable renumbering, let us assume that {ξ^{(i)} : i = 1, …, s} comprises the multiset of finite zeros, i.e., whose first component ξ_{0}^{(j)} ≠ 0. Write

\overline{ξ}^{(i)} = (\overline{ξ}_{1}^{(i)}, …, \overline{ξ}_{n}^{(i)}) :=(ξ_{1}^{(i)}/ξ_{0}^{(i)}, …, ξ_{n}^{(i)}/ξ_{0}^{(i)}),  (i = 1, …, s).  (57)

We have therefore shown each \overline{ξ}^{(i)} is a solution of Σ (the original system). We still need to show that every solution to Σ is among the \overline{ξ}’s in (57). Towards this end, and in analogy to (34), define the polynomial

G(U) := ∏_{j=1}^{s} \overline{g}_{j}(U), where \overline{g}_{j}(U) := U_{0} + ∑_{i=1}^{n} U_{i}\overline{ξ}_{i}^{(j)}.

We say that \overline{g}_{j}(U) “encodes” the solution \overline{ξ}^{(j)}. Finally, here is the main result on generalized U-resultant (cf. §8, theorem 34):

Theorem 43 The generalized U-resultant R̂(U) of Σ has the following properties:

(i) R̂(U) factors completely into linear factors over in ℂ.

(ii) The polynomial G(U) divides the R̂(U).

(iii) The linear factors of G(U) encode all, and only, the solutions of Σ.

Proof.

(i) This is just a restatement of lemma 40.

(ii) Each \overline{ξ}^{(j)} defines the hyperplane \overline{g}_{j}(U) = 0 in U-space. Suppose \overline{g}_{j}(u) = 0 for some u. Then the specialization

σ_{0} : (λ; X; U) ⟶ (0; 1, \overline{ξ}^{(j)}; u),  X = (X_{0}, X_{1}, …, X_{n})  (58)

is a zero of A_{0}(X, U), and hence of Σ(0). Take any sequence {λ_{ℓ}}_{ℓ≥1} that approaches zero. Then we get a corresponding sequence \{(1, \overline{ξ}^{(j)}(λ_{ℓ}))\}_{ℓ≥1} that approaches X = (1, \overline{ξ}^{(j)}). CLAIM: we can construct a corresponding sequence

{(λ_{ℓ}, u_{ℓ})}_{ℓ≥1}

in V_{1} \ V_{0} (see (52)) that approaches (λ, U) = (0, u).

Before verifying the CLAIM, note that the claim implies R̂(u) = 0, by lemma 39. In other words, \overline{g}_{j}(U) divides R̂(U) and part (ii) is proved.

It remains to show the CLAIM. It suffices to choose a sequence u_{ℓ} (ℓ ≥ 1) so that

A_{0}(1, \overline{ξ}^{(j)}(λ_{ℓ}), u_{ℓ}) = 0.

and u_{ℓ} approaches u. This would mean Σ(λ_{ℓ}) has the solution

σ_{ℓ} : (λ; X; U) ⟶ (0; 1, \overline{ξ}^{(j)}(λ_{ℓ}); v_{ℓ}).

and hence χ′(λ_{ℓ}, v_{ℓ}) = 0. This shows (λ_{ℓ}, v_{ℓ}) ∈ V_{1} \ V_{0}, as desired by the claim. By going to a subsequence of \{u_{ℓ}\}_{ℓ} if necessary, we assume that ∥\overline{ξ}^{(j)}(λ_{ℓ}) − \overline{ξ}^{(j)}∥_{∞} is at most 1/ℓ. Initially, u_{1} is arbitrary. It is not hard to see that we can ensure that ∥u_{ℓ} − u∥_{∞} is O(1/ℓ). This implies u_{ℓ} approaches u. (iii) We already noted that each \overline{ξ}^{(j)} is a zero of Σ. Conversely, let ζ = (ζ_{1}, …, ζ_{n}) be a zero of Σ. Then (1, ζ) is a zero of Σ̂. This (1, ζ) defines the U-hyperplane g(U) = U_{0} + ∑_{i=1}^{n} ζ_{i}U_{i} = 0. By the same argument as part (ii), g(U) divides R̂(U). By definition, G(U) contains all linear factors of R̂(U) in which U_{0} has a non-zero coefficient. Hence g(U) divides G(U). Q.E.D.

Finally, let us consider how to extract the zeros of Σ without factoring over ℂ. We need an analog of lemma 35. As usual, g_{j}(U) = ∑_{i=0}^{n} ξ_{i}^{(j)}U_{i}.

Lemma 44 Let W ⊆ \{1, …, n\}. Then R̂(U) factors over ℤ into R_{W} \overline{R}_{W} where, for all j = 1, …, s, R_{W} /g_{j} ∈ ℂ[U] iff for some i ∈ W, ξ_{i}^{(j)} ≠ 0.

Proof. Consider the system Σ_{W} := Σ ∪ {X_{i} : i ∈ W }. This system has a finite number of zeros. We cannot directly construct the generalized U-resultant of Σ_{W} since this is only defined for a system of n homogeneous polynomials in n + 1 variables. But by a result of Eisenbud and Evans [14, p. 126, corollary 1.5], there are n polynomials B_{1}, …, B_{n} ∈ ℤ[X_{1}, …, X_{n}] whose zero set is precisely these zeros (not necessarily with the same multiplicities). We homogenize these B_{i}’s and construct their generalized U-resultant R′_{W}. By taking a large enough power (R′_{W})^{k} (k ≥ 1), we see that GCD((R′_{W})^{k}, R̂) ∈ ℤ[U] has the property we desire of \overline{R}_{W}. Q.E.D.

To find the kth components of \overline{ξ}^{(j)} (j = 1, …, s), set W = \{k\}. We factor R̂ into irreducible polynomials over ℤ. Such a polynomial F divides R_{W} iff F depends on U_{k}. The product of all these F ’s that depend on U_{k} therefore constitute R_{W}. We may now proceed as before (§8) to find the kth components of zeros by root isolation, etc.

§11. Multivariate Root Bound  Lecture XI  Page 42

Finally, the notion of U-resultant can be generalized to the concept of Chow forms of projective varieties (e.g., see Gelfand, Kapranov and Zelevinsky [9]).

Exercises

Exercise 10.1: Prove that the roots of a polynomial A(λ, t) in t with coefficients parameterized continuously by λ vary continuously with λ. □

§11. A Multivariate Root Bound

Let Σ = {A_{1}, …, A_{n}} ⊆ ℤ[X_{1}, …, X_{n}] be a system of n polynomials, not necessarily homogeneous. Suppose Σ has finitely many complex zeros and (ξ_{1}, …, ξ_{n}) ∈ ℂ^{n} is one of these zeros. We provide bounds on |ξ_{i}|. Assume d_{i} = deg(A_{i}) and let

K:= max\{\sqrt{n + 1}, max\{∥A_{i}∥_{2} : i = 1, …, n\}\}.  (59)

The main result of this section is:

Theorem 45 If (ξ_{1}, …, ξ_{n}) is a zero of Σ and |ξ_{i}| ≠ 0, i = 1, …, n, then

|ξ_{i}| > (2^{3/2}NK)^{−D}2^{−(n+1)d_{1}···d_{n}}

where

N := \binom{1 + ∑_{i=1}^{n} d_{i}}{n},  D:= (1 + ∑_{i=1}^{n} \frac{1}{d_{i}} ) ∏_{i=1}^{n} d_{i}.  (60)

Before we present the proof, it is worthwhile understanding the basic order of growth of this root bound. First, we claim:

N = (cd̃)^{n},  (for some 1 < c < e),  (61)

where d̃= (∑_{i=1}^{n} d_{i})/n is the “average degree” and e = 2.718 … is the base of the natural logarithm. To see this, it is easy to check that N > (d̃)^{n}. Conversely, we see that N < (∑_{i=1}^{n} d_{i})^{n}/(n!) for n ≥ 3. Since n! > (n/e)^{n}, this implies N < ((∑_{i=1}^{n} d_{i})e/n)^{n} = (d̃e)^{n}. In fact, the last inequality holds even when n = 2. This verifies our claim (61). We next want to show that N ≫ D. More precisely,

D = o(N).  (62)

First let us write D = C ∏_{i=1}^{n} d_{i} for some 1 < C ≤ n + 1. Note that ∏_{i=1}^{n} d_{i} ≤ d̃^{n} with equality iff all d_{i}’s are equal. [This is easily shown by induction on n.] It follows that D/N ≤ C/c^{n} → 0 as n → ∞, as we wanted to show in (62). Our bound can be simplified to

|ξ_{i}| > (2^{5/2}(d̃e)^{n}K)^{−(n+1)(∏_{i=1}^{n} d_{i})} .

In case all the d_{i}’s are equal to d, this gives

|ξ_{i}| > (2^{5/2}(de)^{n}K)^{−(n+1)d^{n}} .

In terms of bit-sizes, we take logs, leading to a single exponential bit-size bound.

Basic Approach. The strategy is to express 1/ξ_{i} as the root of a suitably specialized U-resultant. As in the previous section, we first homogenize Σ to Σ̂ = {Â_{1}, …, Â_{n}} ⊆ ℤ[X_{0}, X_{1}, …, X_{n}], then define Σ(λ), as in (50). Let R(U_{0}, U_{1}, …, U_{n}) = R(U) be the generalized U-resultant of Σ(λ): this is the tail coefficient of the Macaulay resultant of Σ̂ ∪ {A_{0}} where A_{0} = U_{0}X_{0} + ⋯ + U_{n}X_{n}. Let σ = σ_{i} be the U-specialization such that

σ(U_{ℓ}) = σ_{i}(U_{ℓ}) = \{ \begin{matrix}−U_{i} & if ℓ = i, \\ 1 & if ℓ = 0, \\ 0 & else. \end{matrix}  (63)

By lemma 44, with W = {i}, the polynomial R_{W} (U)|_{σ} is non-vanishing. Moreover, 1/ξ_{i} is a root of R_{W} (U)|_{σ}. We need a bound on multivariate polynomials^{11} from Mahler [20], stated here without proof:

Lemma 46 Let A, B ∈ ℂ[X_{1}, …, X_{n}]. Suppose B|A and the degree of A in X_{i} is δ_{i}. Then ∥B∥_{1} ≤ 2^{δ_{1}+···+δ_{n}}∥A∥_{1}.

Since R_{W} |R and the total degree of R is d_{1}d_{2} ⋯ d_{n}, we conclude

∥R_{W} ∥_{1} ≤ 2^{(n+1)d_{1}d_{2}···d_{n}}∥R∥_{1}.

It follows that

∥(R_{W})_{σ}∥_{1} ≤ 2^{(n+1)d_{1}d_{2}···d_{n}}∥R∥_{1}.  (64)

Hence theorem 45 follows from Cauchy’s root bound and the following:

Lemma 47 The 1-norm, ∥R(U)∥_{1}, is at most (2^{3/2}NK)^{D−1}.

Bounding R(U). Recall that R(U) is the tail coefficient of the exact quotient χ^{M}(λ)/χ^{L}(λ) for a suitable Macaulay matrix M, with L a submatrix of M (cf. (40)). Let us assume that R(U) is, in fact, the constant term of χ^{M}/χ^{L}, since we will see that this is the worst case for our bounding method. In fact, one can easily verify that (see §7) M is N × N and L is (N − D) × (N − D). Write

χ^{M}(λ, U) = ∑_{i=0}^{N} a_{i}(U)λ^{i}.

Each a_{i}(U) is the sum of all the principal minors of M of order N −i. There are \binom{N}{i} such minors, so

that we may write a_{i}(U) = ∑\binom{N}{i}_{j=1} a_{i,j}(U). Now we need a generalization of the Goldstein-Graham Hadamard bound (§VI.8) to multivariate polynomials.

Lemma 48 Let M(U) be a square matrix whose (i, j)th entry M_{i,j}(U) is a polynomial in ℂ[U]. If W = [w_{i,j}]_{i,j} is the matrix where w_{i,j} = ∥M_{i,j}(U)∥_{1} then ∥ det M(U)∥_{2} ≤ H(W) where H(W) is the product of the 2-norms of the rows of W.

Proof. Suppose det(M(U)) = ∑_{α} c_{α}U^{α} where α = (α_{0}, …, α_{n}) range over a suitable subset of ℤ^{n+1} and c_{α} ∈ ℂ. Then

∥ det M(U)∥_{2}^{2} = ∑_{α} |c_{α}|^{2}  (by definition)

11Note that the k-norms ∥A∥_{k} for univariate polynomials extend to multivariate polynomials in the obvious way.

In particular, when k = 1 this is just the sum of the absolute values of the coefficients of A.

= ∫_{0}^{1} dt_{1} ⋯ ∫_{0}^{1} | det(M(e^{2πit_{1}}, …, e^{2πit_{n}})|^{2}  (Parseval’s identity)
≤ ∫_{0}^{1} dt_{1} ⋯ ∫_{0}^{1} H(W)^{2}  (Hadamard’s bound)
= H(W)^{2}.

Q.E.D.

To apply this bound, we construct the “W -matrix” corresponding to M: let W :=[w_{ij}]_{i,j=1}^{N} ∈ ℤ^{N×N} where w_{ij} is the 1-norm of the (i, j)th entry of M. If the non-zero entries in a row of W are the coefficients from a polynomial in Σ, then the 2-norm of the row is bounded by K, by assumption. If the row arises the polynomial A_{0} then its 2-norm is \sqrt{n + 1}, which is also ≤ K. Let a_{i,j}(U) be one of the minors of M. If W_{i,j} is the corresponding submatrix of W, and H(W_{i,j}) denotes (as in §VI.8) the product of the 2-norms of all the rows of W_{i,j}, then the generalized Hadamard bound says that

∥a_{i,j}(U)∥_{2} ≤ H(W_{i,j}) ≤ K^{N−i}.

Since a_{i}(U) has degree at most N − i, we obtain

∥a_{i,j}(U)∥_{1} ≤ ∥a_{i,j}(U)∥_{2}\sqrt{N − i + 1} ≤ K^{N−i}\sqrt{N − i + 1}.

The first inequality is a general relation between 1-norms and 2-norms (§0.10). Next, since generally

∥a(U) + b(U)∥_{1} ≤ ∥a(U)∥_{1} + ∥b(U)∥_{1},

we infer that

∥a_{i}(U)∥_{1} ≤ \binom{N}{i}K^{N−i}\sqrt{N − i + 1}.

Similarly, if we write

χ^{L}(λ) = ∑_{i=0}^{N−D} b_{i}(U)λ^{i}.

then we may deduce that

∥b_{i}(U)∥_{1} ≤ \binom{N − D}{i}K^{N−D−i}\sqrt{N − D − i + 1}.

Now R is equal (see §9) to the determinant of the following (D + 1) × (D + 1) matrix:

M_{0} := [ \begin{matrix}a_{N} & a_{N−1} & a_{N−2} & ⋯ & a_{N−D} \\ b_{N−D} & b_{N−D−1} & b_{N−D−2} & ⋯ & b_{N−2D} \\ & b_{N−D} & b_{N−D−1} & ⋯ & b_{N−2D+1} \\ & & ... & & ⋮ \\ & & & b_{N−D} & b_{N−D−1} \end{matrix} ] .  (65)

Note that a_{N} = b_{N−D} = 1. Instead of using the generalized Hadamard bound again, we now use the bound

∥R∥_{1} ≤ per(W_{D})

where per(W_{D}) denotes^{12} the permanent of W_{D}, and W_{D} is analoguous to the W -matrix of M_{0} (65):

W_{D}:= [ \begin{matrix}1 & \binom{N}{1}K\sqrt{2} & \binom{N}{2}K^{2}\sqrt{3} & ⋯ & \binom{N}{D−1}K^{D−1}\sqrt{D} & \binom{N}{D}K^{D}\sqrt{D + 1} \\ 1 & \binom{N}{1}K\sqrt{2} & \binom{N}{2}K^{2}\sqrt{3} & ⋯ & \binom{N}{D−1}K^{D−1}\sqrt{D} & \binom{N}{D}K^{D}\sqrt{D + 1} \\ & 1 & \binom{N}{1}K\sqrt{2} & ⋯ & \binom{N}{D−2}K^{D−2}\sqrt{D − 1} & \binom{N}{D−1}K^{D−1}\sqrt{D} \\ & & ... & & & ⋮ \\ & & & 1 & \binom{N}{1}K\sqrt{2} & \binom{N}{2}K^{2}\sqrt{3} \\ & & & & 1 & \binom{N}{1}K\sqrt{2} \end{matrix} ] .  (66)

Note that the first two rows of W_{D} is identical. It remains to evaluate this permanent. If we delete the first row and first column of W_{D}, we obtain the following D × D matrix

W′_{D}:= [ \begin{matrix}\binom{N}{1}K\sqrt{2} & \binom{N}{2}K^{2}\sqrt{3} & \binom{N}{3}K^{3}\sqrt{4} & ⋯ & \binom{N}{D−1}K^{D−1}\sqrt{D} & \binom{N}{D}K^{D}\sqrt{D + 1} \\ 1 & \binom{N}{1}K\sqrt{2} & \binom{N}{2}K^{2}\sqrt{3} & ⋯ & \binom{N}{D−2}K^{D−2}\sqrt{D − 1} & \binom{N}{D−1}K^{D−1}\sqrt{D} \\ & 1 & \binom{N}{1}K\sqrt{2} & ⋯ & \binom{N}{D−3}K^{D−3}\sqrt{D − 2} & \binom{N}{D−2}K^{D−2}\sqrt{D − 1} \\ & & ... & & & ⋮ \\ & & & 1 & \binom{N}{1}K\sqrt{2} & \binom{N}{2}K^{2}\sqrt{3} \\ & & & & 1 & \binom{N}{1}K\sqrt{2} \end{matrix} ] .

(67)

If we expand the permanent of W_{D} by the first column, we obtain

per(W_{D}) = 2per(W′_{D}).  (68)

But if we divide the first row of W′_{D} by NK\sqrt{2} we see that the resulting row is component-wise upper-bounded by the first row of W_{D−1}. This is because the ith entry in the resulting row is

\frac{\binom{N}{i}K^{i}\sqrt{i + 1}}{NK\sqrt{2}}

and this is upper bounded by the ith entry of the first row of W_{D−1}, thus:

\frac{\binom{N}{i}K^{i}\sqrt{i + 1}}{NK\sqrt{2}} ≤ \binom{N}{i − 1}K^{i−1}\sqrt{i}.

It follows that that per(W′_{D}) ≤ (NK\sqrt{2})per(W_{D−1}). Substituted into (68), we obtain the recurrence per(W_{D}) = (2^{3/2}NK)per(W_{D−1}). Since per(W_{2}) = 2^{3/2}NK, we obtain

per(W_{D}) ≤ (2^{3/2}NK)^{D−1}.

This concludes our proof of lemma 47.

Upper Bound on Roots. It is clear that we can also make ξ_{i} a root of a suitable specialization of R_{W} (U), and this specialization has the same bound on its 1-norm as in (64). Therefore:

Corollary 49 With the notation of theorem 45, we also have

|ξ_{i}| < (2^{3/2}NK)^{D}2^{(n+1)d_{1}···d_{n}}

12The permanent of a n-square matrix [a_{ij}]_{i,j=1}^{n} is defined rather like as a determinant, being a sum of n! terms.

Each term in the permanent has the form + ∏_{i=1}^{n} a_{i,π(i)} where π is a permutation of {1, 2, …, n}. For instance, per([ \begin{matrix}a & b \\ c & d \end{matrix} ]) = ad + bc. Note that each term is given a positive sign; in contrast, for determinants, we may attach a negative sign to the term.

Remarks. Our basic approach is similar to Canny’s [5]. Instead of using Macaulay’s formula, he uses the division scheme (§9). Canny only treats the special where R(U) is the standard U-resultant.

Exercises

Exercise 11.1: Simplify the above root bounds but giving sharper estimates than in the text. E.g., use the Stirling approximation of Robbins: n! = (n/e)^{n}\sqrt{2πn}e^{α} where (12n + 1)^{−1} < α < (12n)^{−1}. A simpler approximation is n! = Θ((n/e)^{n+(1/2)}. □

Exercise 11.2: Assuming the case where the generalized U-resultant is the standard U-resultant, improve our root bound above. □

Exercise 11.3: (Canny) Define the Z-height of a polynomial A(X) = ∑_{i=0}^{m} a_{i}X^{i}, a_{m} ≠ 0, to be

h_{Z}(A) := max \{\frac{|a_{m−1}|}{|a_{m}|}, \sqrt{\frac{|a_{m−2}|}{|a_{m}|}}, ^{3} \sqrt{\frac{|a_{m−3}|}{|a_{m}|}}, …, ^{m} \sqrt{\frac{|a_{0}|}{|a_{m}|}}\} .

Alternatively, h_{Z}(A) is the smallest value β such that β^{i} ≥ |a_{m−i}/a_{m}| for all i = 1, …, m. ^{13} In the following proofs, it is often easiest to assume the polynomials are already monic, since this does not affect the Z-height.

(i) If K = ∥M∥_{∞} where of a matrix M ∈ ℝ^{n×n}, then h_{Z}(χ^{M}(λ)) ≤ nK. (ii) h_{Z}(AB) ≤ h_{Z}(A) + h_{Z}(B). (iii) Assuming A, B are monic, h_{Z}(A + B) ≤ h_{Z}(A) + h_{Z}(B). (iv) h_{Z}(C) ≤ h_{Z}(A) + 2h_{Z}(B).

(v) Bound h_{Z}(R̂) and conclude with an alternative multivariate root bound. □

References

[1] S.J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18:147–150, 1984.

[2] Elwyn R. Berlekamp. Algebraic Coding Theory. McGraw-Hill Book Company, New York, 1968.

[3] W. D. Brownawell. Bounds for the degrees in Nullstellensatz. Ann. of Math., 126:577–592, 1987.

[4] John F. Canny. Generalized characteristic polynomials. Journal of Symbolic Computation, 9:241–250, 1990.

[5] John Francis Canny. The complexity of robot motion planning. ACM Doctoral Dissertion Awardi Series. The MIT Press, 1988. Ph.D thesis, M.I.T.

[6] Jean Dieudonné. History of algebraic geometry. Wadsworth Advanced Books & Software, 1985. (trans. from French, Judith D. Sally).

[7] Thomas W. Dubé. A combinatorial proof of the effective Nullstellensatz. Journal of Symbolic Computation, 15:277–296, 1993.

13This terminology recalls the notion of “height” for a polynomial. The “Z” here refers to a lemma attributed to Zassenhaus (§VI.2) showing that if A(α) = 0 then |α| < 2h_{Z}(A).

[8] Ioannis Zacharias Emiris. Sparse Elimination and Applications in Kinematics. PhD thesis, Department of Computer Science, University of California, Berkeley, 1989.

[9] I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston, 1994.

[10] A. Hurwitz. Über die Trägheitsformem eines algebraischen Moduls. Ann. Mat. Pura Appl., 3(20):113–151, 1913.

[11] H. Kapferer. Über Resultanten und Resultanen-Systeme. Sitzungsber. Bayer. Akad. München, pages 179–200, 1929.

[12] Morris Kline. Mathematical thought from ancient to modern times, volume 3. Oxford University Press, New York, 1972.

[13] János Kollár. Sharp effective Nullstellensatz. J. American Math. Soc., 1(4):963–975, 1988.

[14] Ernst Kunz. Introduction to Commutative Algebra and Algebraic Geometry. Birkhäuser, Boston, 1985.

[15] Serge Lang. Algebra. Addison-Wesley, 1971.

[16] D. Lazard. Résolution des systémes d’équations algébriques. Theoretical Computer Science, 15:146–156, 1981.

[17] F. S. Macaulay. Some formulae in elimination. Proc. London Math. Soc., 35(1):3–27, 1903.

[18] F. S. Macaulay. The algebraic theory of modular systems. Cambridge University Press, 1916.

[19] F. S. Macaulay. Note on the resultant of a number of polynomials of the same degree. Proc. London Math. Soc, pages 14–21, 1921.

[20] Kurt Mahler. On some inequalities for polynomials in several variables. J. London Math. Soc., 37:341–344, 1962.

[21] F. Mertens. Zur Eliminationtheorie. Sitzungsber. K. Akad. Wiss. Wien, Math. Naturw. Kl. 108, pages 1178–1228, 1244–1386, 1899.

[22] David Mumford. Algebraic Geometry, I. Complex Projective Varieties. Springer-Verlag, Berlin, 1976.

[23] Oskar Perron. Algebra, volume 1. de Gruyter, Berlin, 3rd edition edition, 1951.

[24] Constance Reid. Hilbert-Courant. Springer-Verlag, 2000.

[25] James Renegar. On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals. Journal of Symbolic Computation, 13(3):255–300, March 1992.

[26] Bernard Shiffman. Degree bounds for the division problem in polynomial ideal. Mich. Math. J., 36:162–171, 1988.

[27] Bernd Sturmfels. Algorithms in Invariant Theory. Springer-Verlag, Vienna, 1993.

[28] Bernd Sturmfels. Sparse elimination theory. In D. Eisenbud and L. Robbiano, editors, Proc. Computational Algebraic Geometry and Commutative Algebra 1991, pages 377–397. Cambridge Univ. Press, 1993.

[29] B.L. van der Waerden. Modern Algebra, volume 2. Frederick Ungar Publishing Co., 1950. (Translated by T.J.Benac, from the second revised German edition).

§A. APPENDIX A: Power Series  Lecture XI  Page 48

§A. APPENDIX A: Power Series

We introduce the ring of power series over a ring R and describe some basic properties, mainly to facilitate the proof in appendix B. In particular, we describe what it means to form infinite sums and products.

A (formal) power series in the variable Z and with coefficients from a ring R is a formal infinite sum of the form

G(Z) = ∑_{i=0}^{∞} a_{i}Z^{i}, (a_{i} ∈ R).

Let R[[Z]] denote the set of such power series. These power series are said to be “formal” because, unlike their use in mathematical analysis, we do not evaluate them to a definite value and so there is no discussion of convergence properties. Two power series are deemed equal if their corresponding coefficients are equal. The polynomial ring R[Z] is embedded in R[[Z]] in a natural way. We can add and multiply two power series in the obvious term-wise fashion. Hence R[[Z]] is a ring.

In the rest of this appendix, assume that R is a domain D. We proceed to state some easily verifiable properties of D[[Z]]. Then it is easily seen that G(Z)H(Z) = 0 iff G(Z) = 0 or H(Z) = 0. This shows that D[[Z]] is a domain, with 0 and 1 as the zero and unity elements. The inverse of G(Z) is the power series H(Z) such that G(Z)H(Z) = 1. As in any domain, inverses are unique when they exist. The inverse of G is denoted by H(Z) = 1/G(Z) or G^{−1}(Z). It is not hard to see that G(Z) has an inverse iff a_{0} is a unit in D: this amounts to an inductive construction of each of the coefficients of G^{−1}(Z).

Formal differentiation of G(Z) is also defined,

G′(Z) = ∑_{i≥1} i · a_{i}Z^{i−1}.

The usual rules of differentiation holds. For instance, the product rule can be verified:

(G(Z)H(Z))′ = G′(Z)H(Z) + G(Z)H′(Z).

We now derive an important formula using differentiation. If A is a finite product of power series,

A(Z) = ∏_{i=1}^{k} G_{i}(Z)

then extension of the above product rule gives

A′(Z) = ∑_{i=1}^{k} G′_{i}(Z) ∏_{j≠i} G_{j}(Z).

Assuming that A(Z) is invertible, then each G_{i}(Z) is also seen to be invertible. So we can divide both sides by A(Z) to give the “logarithmic derivative formula” for A(Z):

\frac{A′(Z)}{A(Z)} = ∑_{i=1}^{k} \frac{G′_{i}(Z)}{G_{i}(Z)}.  (69)

Recall that A′(Z)/A(Z) is the “logarithmic derivative” of A(Z) (§VI.1). The power of this formula to turn a product into a sum will be useful.

The smallest i such that a_{i} ≠ 0 is called the order of G(Z), denoted ord(G). When G is a polynomial, ord(G) is just its tail degree (§0.10). Hence we will call a_{i} the tail coefficient of G when i = ord(G). By definition, ord(0) = ∞. It is easily seen that ord(G · H) = ord(G) + ord(H) and ord(G ± H) ≥ min{ord(G), ord(H)} with equality whenever ord(G) ≠ ord(H). The theory of divisibility is extremely simple for power series: G|H iff ord(G) ≤ ord(H) and the tail coefficient of G divides the tail coefficient of H.

Infinite Sums and Products. The domain D[[Z]] only guarantees that finite sums and finite products are well-defined. The fact that a power series is an infinite sum will tempt us to use infinite sums and products. Especially in combinatorial enumeration, infinite sums and infinite products are extremely useful. Clearly they are not always well-defined. Our goal here is to define an unambiguous meaning for the following infinite product and sum

P = ∏_{i=0}^{∞} G_{i}(Z),  S = ∑_{i=0}^{∞} G_{i}(Z),  (G_{i}(Z) ∈ D[[Z]]).  (70)

Towards this end, we define G(Z) and H(Z) to be equivalent modulo Z^{n} if Z^{n} divides G(Z)−H(Z). This is written

G(Z) ≡ H(Z) (mod Z^{n}).

We also write

G(Z) mod Z^{n}

for the polynomial obtained by eliminating all terms in G(Z) that are divisible by Z^{n}. Thus G(Z) mod Z^{n} is a polynomial of degree at most n − 1 and G ≡ H (mod Z^{n}) iff (G mod Z^{n}) = (H mod Z^{n}). Furthermore, G = H iff for all n ≥ 0,

G ≡ H (mod Z^{n}).  (71)

Definition 1

(a) The infinite product P in equation (70) is defined if for all n ≥ 0, there exists a finite bound b(n) such that for all i > b(n), G_{i}(Z) mod Z^{n} = 1. In this case P is the power series P (Z) ∈ D[[Z]] such that for each n ≥ 0,

P (Z) ≡ ∏_{i=0}^{b(n)} G_{i}(Z) (mod Z^{n}).  (72)

(b) The infinite sum S in equation (70) is defined if for all n ≥ 0, there exists a finite bound b(n) such that for all i > b(n), G_{i}(Z) mod Z^{n} = 0. In this case S is the power series S(Z) ∈ D[[Z]] such that for each n ≥ 0,

S(Z) ≡ ∑_{i=0}^{b(n)} G_{i}(Z) (mod Z^{n}).  (73)

Clearly P (Z), S(Z) are unique when defined; in particular, they do not depend on the choice of the bounds b(n).

Lemma 50 If ∏_{i=0}^{∞} G_{i}(Z) is defined and H_{0}, H_{1}, … is any rearrangement of the factors G_{0}, G_{1}, … then ∏_{i=0}^{∞} H_{i}(Z) is defined and equal to ∏_{i=0}^{∞} G_{i}(Z).

The proof is left as an exercise. In view of this rearrangement lemma, we can define the product of a set of power series: if W = {G_{0}, G_{1}, …} ⊆ D[[Z]], the product ∏ W or ∏_{G∈W} G can be defined to be ∏_{i=0}^{∞} G_{i}, provided this is defined. We now extend the logarithmic derivative formula to infinite products:

§B. APPENDIX B: Irreducible Polynomials  Lecture XI  Page 50

Lemma 51 If P (Z) = ∏_{i=0}^{∞} G_{i}(Z) is defined, and P (Z) is invertible then

\frac{P′(Z)}{P (Z)} = ∑_{i=0}^{∞} \frac{G′_{i}(Z)}{G_{i}(Z)}.  (74)

Proof. First we show that the infinite sum in equation (74) is defined. Since P (Z) is invertible, we conclude that G_{i} is also invertible for all i (pf: for any n, if i > b(n) then the constant term in G_{i} is 1, and if i ≤ b(n) then equation (72) shows that the constant term in G_{i} is invertible). Next for each n ≥ 1 and i > b(n), G_{i}(Z) mod Z^{n} = 1 implies G′_{i}(Z) mod Z^{n−1} = 0; then G′_{i}(Z)/G_{i}(Z) mod Z^{n−1} = 0, and so the infinite sum of equation (74) is defined.

It remains to show that the infinite sum equals P′(Z)/P (Z). For each n, equation (72) holds; applying the logarithmic derivative formula yields

\frac{P′(Z)}{P (Z)} ≡ ∑_{i=0}^{b(n)} \frac{G′_{i}(Z)}{G_{i}(Z)} (mod Z^{n−1}).  (75)

On the other hand, if S(Z) is defined to be the infinite sum ∑_{i=0}^{∞} G′_{i}(Z)/G_{i}(Z), then since G′_{i}(Z)/G_{i}(Z) mod Z^{n−1} = 0 for i > b(n), we conclude that S(Z) ≡ ∑_{i=0}^{b(n)} \frac{G′_{i}(Z)}{G_{i}(Z)} (mod Z^{n−1}). This, with equation (75), shows that S(Z) ≡ P′(Z)/P (Z) (mod Z^{n−1}) for all n ≥ 0. So S(Z) = P′(Z)/P (Z). Q.E.D.

Exercises

Exercise A.1: Verify the unproved assertions about D[[Z]]. □

Exercise A.2:

(a) If D is a field then D[[Z]] is an Euclidean domain (§II.3) with φ(G) = ord(G).

(b) If D is a UFD, is D[[Z]] a UFD? □

Exercise A.3: Show lemma 50. □

Exercise A.4: If F_{1} ≡ F_{2} and G_{1} ≡ G_{2} then F_{1} ± G_{1} ≡ F_{2} ± G_{2} and F_{1}G_{1} ≡ F_{2}G_{2}, all modulo Z^{n}. □

§B. APPENDIX B: Counting Irreducible Polynomials

We prove the following result:

Theorem 52 D[X] has infinitely many non-associated irreducible polynomials.

This result is used in §2. It is also of independent interest for applications in coding theory and cryptography. In case D is an infinite set, this theorem is immediate since the set {X − a : a ∈ D} is clearly an infinite set of pairwise non-associated irreducible polynomials. Henceforth, let us assume that D is finite. In fact, we have: a finite domain D is a field. To see this, for any non-zero a ∈ D, consider the sequence

1, a, a^{2}, …, a^{r}, a^{r+1}, …, a^{r+s}

where a^{r+s} is the first time that the sequence repeats, and a^{r+s} = a^{r}. Then a^{r}(1 − a^{s}) = 0 and so a^{s} = 1. Hence a^{s−1} is the inverse of a. So D must be a Galois field with q elements where q is a prime power.

Assuming we have picked a distinguished element in each equivalence class of associates of D[X] (§II.1), our problem amounts to counting the number of distinguished irreducible polynomials in D[X]. We follow Berlekamp’s approach [2] of using generating functions. This approach yields much more information than just the stated theorem.

Generating Functions. The power series G(Z) = ∑_{i≥0} a_{i}Z^{i} is called a generating function for the sequence.

a_{0}, a_{1}, a_{2}, …, (a_{i} ∈ D).

For any set S ⊆ D[X], the counting function G_{S}(Z) for S is the generating function for the sequence

|S_{0}|, |S_{1}|, |S_{2}|, …

where S_{i} ⊆ S is the set elements in S of degree i. Let I be the set of distinguished irreducible polynomials in D[X]. According to the convention in §II.1, the distinguished polynomials are precisely the monic ones. Denote the counting function of I by

G_{I}(Z) := ∑_{i=0}^{∞} d_{i}Z^{i}.  (76)

Our original goal of showing that I is infinite follows from the following stronger claim:

Theorem 53 For all i ≥ 0, d_{i} ≥ 1.

Towards a proof of theorem 53, note that if f ∈ D[X] has degree d ≥ 0 then

H_{d}(Z) := \frac{1}{1 − Z^{d}} = 1 + Z^{d} + Z^{2d} + ⋯

is the counting function for the set

S(f) :={f^{i} : i = 0, 1, 2, …}.

Next, if f, g ∈ D[X] are relatively prime and have degrees d, e ≥ 0, then similarly

H_{d}(Z)H_{e}(Z) = \frac{1}{1 − Z^{d}} · \frac{1}{1 − Z^{e}}

is the counting function for the set

S(f, g) :={f^{i}g^{j} : i, j = 0, 1, 2, …}.

Note that this remark depends on the fact that D[X] is a UFD (recall that D is a Galois field). By induction on k, if f_{1}, …, f_{k} are pairwise relatively prime of degrees d_{1}, …, d_{k} ≥ 0 then

H_{d_{1}}(Z)H_{d_{2}}(Z) ⋯ H_{d_{k}}(Z) = ∏_{i=1}^{k} \frac{1}{1 − Z^{d_{i}}}

is the counting function for the set

S(f_{1}, …, f_{k})

of power products of f_{1}, …, f_{k}. Now we make an essential leap to the infinite case:

Lemma 54 Let S(I) be the set of power products of elements in I. Its counting function G_{S(I)} is given by

G_{S(I)} = ∏_{u∈I} H_{deg(u)}(Z)  (77)

= ∏_{i=0}^{∞}(H_{i}(Z))^{d_{i}}.  (78)

Proof. It is easy to see that the infinite product

P = ∏_{u∈I} H_{deg(u)}(Z) = ∏_{u∈I} \frac{1}{1 − Z^{deg(u)}} .

is defined (cf. lemma 50). We can verify routinely that each coefficient of P is equal to the corresponding coefficient of G_{S(I)}, by looking at a finite number of terms in P. Since there are d_{i} (see equation (76)) elements in I of degree i, P can also be written as in equation (78) (this also needs verification). Q.E.D.

Note that the set S(I) is precisely the set of distinguished elements in D[X]. On the other hand, the number of distinguished elements of degree n is just |D|^{n} = q^{n}. Thus the counting function of S(I) is equal to

G_{S(I)} = 1 + qZ + q^{2}Z^{2} + ⋯ = \frac{1}{1 − qZ} .

Combining this equation for G_{S(I)}(Z) with the previous lemma, we have shown:

Lemma 55 The counting function for the set of distinguished elements in D[X] is

G_{S(I)}(Z) = ∏_{i=0}^{∞} (\frac{1}{1 − Z^{i}} )^{d_{i}}  (79)

= \frac{1}{1 − qZ} .  (80)

Taking the logarithmic derivative G′_{S(I)}(Z)/G_{S(I)}(Z) of the two expressions in the lemma and equating them,

\frac{q}{1 − qZ} = ∑_{i=0}^{∞} d_{i} \frac{i · Z^{i−1}}{1 − Z^{i}} ,

\frac{qZ}{1 − qZ} = ∑_{i=0}^{∞} d_{i} \frac{i · Z^{i}}{1 − Z^{i}}

= ∑_{i=0}^{∞} i · d_{i} (∑_{j≥1} Z^{ji})

= ∑_{i=0}^{∞} i · d_{i} ( ∑_{n≥1;i|n} Z^{n})  (putting n = ji)

= ∑_{n=1}^{∞} Z^{n} ( ∑_{i≥1;i|n} i · d_{i}) .

Equating coefficients of Z^{n}, we have

Theorem 56 The number d_{i} of distinguished irreducible polynomials of degree i in D[X] satisfies the equation

q^{n} = ∑_{i≥1;i|n} i · d_{i},  q = |D|.  (81)

This theorem immediately shows that d_{1} = q (interprete this). Also, d_{2} = \frac{q^{2}−q}{2} ≥ 1. For general d_{n}, we have the following upper and lower bounds:

Corollary 57

\frac{q^{n} − q^{1+(n/2)}}{n} ≤ d_{n} ≤ \frac{q^{n} − q}{n} .  (82)

Proof. For the upper bound, we ignore all but the first and last terms in the sum in equation (81), giving q^{n} ≥ n · d_{n} + d_{1}. For the lower bound, we extract the term involving d_{n} in equation (81) and note that the remaining terms involve d_{i} for i ≤ n/2:

q^{n} ≤ n · d_{n} + ∑_{i=1}^{n/2} id_{i} < n · d_{n} + ∑_{i=1}^{n/2} q^{i} < n · d_{n} + q^{1+(n/2)}.

Q.E.D.

Now theorem 53 is immediate since the lower bound in equation (82) shows that d_{n} > 0 for n ≥ 3. This corollary also shows that

|d_{n} − \frac{q^{n}}{n} | = o (\frac{q^{n}}{n} ) .

Exercises

Exercise B.1: For any prime p, X^{p} − X − 1 is irreducible in ℤ_{p}[X]. □

Exercise B.2:

(a) Apply Möbius inversion to the formula equation (81).

(b) Use the inversion formula to compute d_{n} for n = 1, …, 10, when D = GF (2). □

Exercise B.3: Count the number of irreducible polynomials in D[X, Y] using the same method. □