第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
多项式实根个数的计算.pdf
REAL ALGEBRAIC GEOMETRY
KENNETH R. DRIESSEL
Hermite’s Root Counting Method
References: In this section I mainly follow the books Basu, Pollack and
Roy(2003) and Cox, Little and O’Shea(1991,1998) .
Notation: Throughout this section we use the following notation: K de-
notes a field with characteristic 0, R denotes a real closed extension of K
and C denotes an algebraically closed extension of R. In particular, we have
K ⊆ R ⊆ C.
The standard example is K := Q, R := R, C := C. (Here is another choice
for R and C: Take R to be the real algebraic numbers and take C to be the
algebraic numbers.)
This section is divided into three subsections with titles “Introduction”,
“The univariate case” and “ The multivariate case”.
Date: March 20, 2007.
1
2
KENNETH R. DRIESSEL
Subsection: Introduction. We consider the following
Problem: Given a finite set P of polynomials and a polynomial Q in
K[X1, . . . , Xk], determine the quantity
#{x ∈ Zero(P, Rk) : Q(x) > 0} − #{x ∈ Zero(P, Rk) : Q(x) < 0}
where Zero(P, Rk) := {x ∈ Rk : (∀P ∈ P)P (x) = 0}.
The difference between the number of solutions Zero(P, Rk) at which Q(x)
is positive and the number at which Q(x) is negative is called the Tarski
query or Sturm query of Q for P. We shall use TaQ(Q,P) to denote this
difference. If we can compute Tarski queries then we can compute many
other useful numbers. Here are a few examples:
Example: The number of solutions of P in Rk.
Let Q(X1, . . . , Xk) := 1 be the constant one polynomial. Then the num-
ber of solutions of P in Rk equals the Tarski query of Q for P; in symbols,
#Zero(P, Rk) = TaQ(1,P).
Example: The number of solutions of P in Rk at which Q is positive.
Note
#{x ∈ Zero(P, Rk) : Q(x) > 0} + #{x ∈ Zero(P, Rk) : Q(x) < 0}
= TaQ(1,P) − TaQ(1,P ∪ {Q}).
Hence
2 #{x ∈ Zero(P, Rk) : Q(x) > 0}
= TaQ(Q,P) + TaQ(1,P) − TaQ(1,P ∪ {Q}).
Example: The approximate location of solutions in Rk.
We can use the polynomials which define spheres to approximate the
location of solutions. For example, if k = 2, we can use
Q(X, Y ) := r2 − (X − a)2 − (X − b)2
where a, b and r are parameters. Then
#{(x, y) ∈ Zero(P, R2) : Q(x, y) > 0}
equals the number of solutions in the ball
{(x, y) ∈ R2 : (x − a)2 + (x − b)2 < r2}.
Definition: If the set Zero(P, Ck) of solutions in Ck is finite then we say
that P is zero-dimensional.
We shall usually assume that we are in this zero-dimensional setting.
Recall that we can algebraically determine if we are in this setting by means
of the following result.
P in K[X1, . . . , Xn] is denoted Ideal(P, K)
Proposition 1. Finiteness. Let A := K[X1, . . . , Xk]/Ideal(P, K). Then
Notation: The ideal in K[X1, . . . , Xk] generated by a set of polynomials
REAL ALGEBRAIC GEOMETRY
3
• The K-vector space A is finite dimensional if and only if P is zero-
• If the dimension of A is finite then the number of solutions of P in
dimensional.
Ck is less than or equal to this dimension.
Proof. See Cox, Little and O’Shea(1991,1998) or Basu, Pollack and Roy(2003)
for a proof.
Notation: Let A be a finite dimensional algebra over the field K. For
f in A, let L(f) : A → A be the linear multiplication map defined by
L(f)(g) := f g. For q ∈ A, let B(q) denote the quadratic form on A de-
fined by B(q)(f) := Trace(L(qf 2)). The notation used for this quadratic
form is somewhat different in the polynomial setting: Let P be a finite
subset of K[X1, . . . , Xn], let A := K[X1, . . . , Xn]/Ideal(P, K) and let Q
be an element of K[X1, . . . , Xn]. Then Herm(P, Q) denotes the quadratic
form on A (assumed to be finite dimensional) defined by Herm(P, Q)(f) :=
Trace(L(Qf 2)) and this form is called the Hermite quadratic form de-
termined by P and Q. We shall use the expressions Rank(Herm(P, Q))
and Signature(Herm(P, Q)) to denote the rank and signature of this qua-
dratic form.
The following result provides an answer to the problem raised above.
Proposition 2. Hermite’s root counting. Let P be a finite set of poly-
nomials which have a zero-dimensional solution set. Then the rank of the
quadratic form Herm(P, Q) equals the number of distinct roots of P in Ck
at which Q is different than zero; in symbols,
Rank(Herm(P, Q)) = #{x ∈ Zero(P, Ck) : Q(x) 6= 0}.
The signature of the quadratic form Herm(P, Q) equals the difference be-
tween the number of distinct roots of P in Rk at which Q is positive and the
number of distinct roots in Rk at which Q is negative; in symbols,
Signature(Herm(P, Q)) =
#{x ∈ Zero(P, Rk) : Q(x) > 0} − #{x ∈ Zero(P, Rk) : Q(x) < 0}.
***TODO: Perhaps insert a simple example here.
The following subsections provide proofs of this result. In particular, the
next subsection provides a proof in the univariate case. And the following
subsection deals with the multivariate case. The analyses of the two cases
are similar. We use the following result (which we proved in an earlier
section) in both cases.
Proposition 3. Decomposition using idempotents. Let A be a com-
mutative ring with identity. Let e1, . . . , en be elements of A which satisfy
the following conditions:
• e1 + e2 + ··· + en = 1 and
• if i 6= j then eiej = 0.
Then
4
KENNETH R. DRIESSEL
i = ei,
• e2
• eiA is a subring of A with identity, namely, ei, and
• A is the direct sum of the subrings eiA:
A = e1A ⊕ e2A ⊕ . . . enA.
Furthermore, for f ∈ A,
and, for q ∈ A,
L(f) = L(e1f) ⊕ ··· ⊕ L(enf)
B(q) = B(e1q) ⊕ ··· ⊕ B(enq).
Subsection: The univariate case. In this subsection we shall consider
the quotient algebra K[X]/I where I is an ideal in the univariate polynomial
ring K[X].
Proposition 4. Decomposition of a univariate quotient algebra us-
ing idempotents. Let P be a polynomial in the ring C[X] with distinct
roots x1, . . . , xn. Let Ideal(P, C) be the ideal generated by P . Then there
exist elements e1, . . . , en in the quotient ring C[X]/Ideal(P, C) such that
i = ei,
• e1 + e2 + ··· + en = 1,
• if i 6= j then eiej = 0,
• e2
• if i 6= j then ei(xj) = 0
• ei(xi) = 1,
• A = e1A ⊕ e2A ⊕ . . . enA, and
• dim(eiA) = µi where µi is the multiplicity of xi as a root of P .
For f ∈ A, let L(f) denote the linear multiplication map on A defined by
L(f)(g) := f g. Then
L(f) = L(e1f) ⊕ ··· ⊕ L(enf).
For q ∈ A let B(q) be the bilinear function defined on A by B(q)(g, h) :=
Trace(L(qgh)). Then
B(q) = B(e1q) ⊕ ··· ⊕ B(enq).
Definition: The element ei is called the idempotent associated with
the root xi.
Proof. We have
P (X) = (X − x1)µ1 . . . (X − xn)µn.
assertions of the proposition are then obvious.
If n = 1 we can simply take e1 to be the constant 1 polynomial. The
So we assume that n ≥ 2. For i = 1, . . . , n, let Si(X) be the Lagrange
interpolating polynomial which is defined to be the following product:
Si(X) := Π{ X − xj
xi − xj
: j 6= i}.
REAL ALGEBRAIC GEOMETRY
5
Note Si(xi) = 1 and, for j 6= i, Si(xj) = 0. For i = 1, . . . , n, let Ti := Sµ
i
where µ is the maximum of the multiplicities µ1, . . . , µn. Note that Ti(xi) =
1 and, for i 6= j, the polynomial P divides TiTj. Since the Ti are relatively
prime, there are polynomials Ui such that
U1T1 + ··· + UnTn = 1.
Set ei := UiTi + Ideal(P ). It is easy to see that these elements of A satisfy
the assertions of the proposition. Also note that the assertion that ei is an
idempotent follows from the first two assertions concerning the ei as in the
general idempotent decomposition result for rings. This general result also
provides a proof of the decomposition assertion given here.
TODO: Find a nice proof of the assertion relating dimensions and multi-
plicities.
***TODO: Include the alternative proof of the last result.
Example: This example illustrates the constructions of the last proof. Let
P (X) := X(X − 1). Note A := Q[X]/Ideal(P, Q) has dimension two. The
roots of P are 0 and 1. We shall use the roots as indices. The Lagrange
interpolating polynomials are:
• S0(X) := 1 − X and
• S1(X) := X.
We can take T0 := S0 and T1 := S1. Note:
(1 − X) + X = 1.
Consequently we take e0(X) := 1 − X and e1(X) := X. Then e0 + e1 =
1, e0e1 = 0, e0(0) = 1, e0(1) = 0, e1(0) = 0 and e1(1) = 1. Here is the
multiplication table for A for the basis e1, e2:
e1
0
e1
| e0
| e0
|
0
·
e0
e1
We have e0A = e0Span(e0, e1) = Span(e0) and e1A = e1Span(e1, e0) =
Span(e1).
Example: Here is another example which illustrates the constructions of
the last proof. Let P (X) := X 2(X − 1). Note A := Q[X]/Ideal(P, Q) has
dimension three. The roots of P are 0 and 1. We shall use the roots as
indices. The Lagrange interpolating polynomials are:
• S0(X) := 1 − X and
• S1(X) := X.
We can take T0 := S0 and T1 := S2
1. Note:
(1 + X)(1 − X) + X 2 = 1.
Consequently we take e0(X) := (1 + X)(1 − X) and e1(X) := X 2. Then
e0 + e1 = 1, e0e1 = 0, e0(0) = 1, e0(1) = 0, e1(0) = 0 and e1(1) = 1. Here is
6
KENNETH R. DRIESSEL
the multiplication table for A for the basis 1, X, X 2:
·
|
1 X X 2
|
1 X X 2
1
X | X X 2 X 2
| X 2 X 2 X 2
X 2
We compute e0A = Span(e0, Xe0) and e1A = Span(e1). Here is the multi-
plication table for A for the basis e0, Xe0, e1:
e0 Xe0
e0 Xe0
0
0
|
|
| Xe0
|
0
·
e0
Xe0
e1
e1
0
0
e1
Proposition 5. Eigenvalues of a multiplication map. Let P be a
polynomial in K[X] with roots x1, . . . , xn in C. Let A := K[X]/Ideal(P, K)
and let f be an element of A. Then the linear multiplication map L(f) on A
has eigenvalues f(xi) for i = 1, . . . , n. Furthermore, the multiplicity of f(xi)
as a root of the characteristic polynomial of L(f) equals the multiplicity of
xi as a root of the polynomial P .
Proof. Let e1, . . . , en be idempotents for A associated with the roots of P .
We consider the elements fi := ei(f − f(xi)) of A. Since fi vanishes at all
of the roots of P , there exists a natural number m such that P divides f m
.
It follows that the linear map L(fi) : eiA → eiA is nilpotent. Hence L(fi)
i
has a unique eigenvalue 0 with multiplicity dim(eiA) = µi. It follows that
L(eif) has exactly one eigenvalue f(xi) with multiplicity µi. We can use
the decomposition proposition to complete the proof.
Proposition 6. Stickelberger’s theorem in the univariate case. Let
P be an polynomial in K[X] with roots x1, . . . , xn in C with multiplicities
µ1, . . . , µn respectively. Let A := K[X]/Ideal(P, K), let f be an element of
A and let L(f) := A → A : g 7→ f g be the multiplication map associated
with f. Then
nX
Trace(L(f)) =
µif(xi).
i=1
Note the this trace is an element of K. In particular, note that the sum
is a symmetric function of the roots of P .
Proof. This result follows immediately from the result concerning the eigen-
values of L(f). In particular, there is a choice of basis for C[X]/Ideal(P, C)
for which the matrix of L(f) is diagonal.
Example: Let
P (X) := (X 2 + 1)(X − 2)2(X + 2) = X 5 − 2X 4 − 3X 3 + 6X 2 − 4X + 8.
Let A := Q[X]/Ideal(P, Q). We take the polynomials 1, X, X 2, X 3, X 4 as
an ordered basis of A. We consider the multiplication map L(X). Note
REAL ALGEBRAIC GEOMETRY
7
X · X i = X i+1 for i = 0, 1, 2, 3 and X · X 4 ≡ 2X 4 + 3X 3 − 6X 2 + 4X − 8.
Hence the matrix of L(X) with respect to the given basis is
0 0 0 0 −8
1 0 0 0
4
0 1 0 0 −6
3
0 0 1 0
0 0 0 1
2
.
M :=
This matrix is the companion matrix of the polynomial P . The eigenvalues
of L(X) are the roots of P :
x1 = −2, x2 = 2, x3 = i, x4 = −i
with multiplicities:
Note Trace(L(X)) = 2 = −2 + 2 + 2 + i − i.
µ1 = 1, µ2 = 2, µ3 = 1, µ4 = 1.
If f = f0 + f1X + f2X 2 + f3X 3 + f4X 4 is a general element of A then
L(f) = f0I + f1L(X) + f2L(X)2 + f3L(X)3 + f4L(X)4 and the matrix of
L(f) is f0I + f1M + f2M 2 + f3M 3 + f4M 4. The eigenvalues of L(f) are
f(xi) with multiplicities µi.
Subsection: The zero-dimensional multi-variate case. In this sub-
section we consider a quotient algebra K[X1, . . . , Xk]/I where I is an ideal
in the polynomial ring K[X1, . . . , Xk]. We considered the univariate case
earlier. Here we consider the multivariate case. Of course, the multivariate
case includes the univariate case but the analysis of the multivariate case is
somewhat more complicated.
Definition: Let V be a vector space over field K. Let Z := {z1, . . . , zn}
be a finite subset of V . Let V 0 := (V → K) denote the space of linear
functionals on V ; in other words, V 0 denotes the dual space of V . Then an
element a of V 0 is separating for Z if a has distinct values at the distinct
elements of Z; in symbols, i 6= j =⇒ a(zi) 6= a(zj).
Proposition 7. Separating a finite subset of a vector space. Let V
be a finite dimensional vector space over a field K with characteristic zero
and let Z be a finite subset of V . Then there is a separating linear functional
for Z.
Proof. This result is obvious since V 0 has infinitely many elements. Never-
theless, here is a “constructive” proof.
Let k be the dimension of V . Let v1, . . . , vk be a basis for V and let
w1, . . . , wk be a dual basis for V 0; in other words, wi(vj) = δij, where δ
is the Kronecker symbol. Let n be the number of elements in Z. For
0 ≤ i ≤ (k − 1)n
, let
2
ai := w1 + iw2 + i2w3 + . . . + ik−1wk.
8
Note there are (k − 1)n
KENNETH R. DRIESSEL
+ 1 linear functionals in this list. For distinct x
2
and y in Z let
E(x, y) := {ai : ai(x) = ai(y)}.
In other words, the set E(x, y) is the set of ai which do not separate x and
y. Note that ai(x) = ai(y) iff
w1(x − y) + iw2(x − y) + . . . + ik−1wk = 0.
Since the polynomial
P (T ) := w1(x − y) + w2(x − y)T + . . . + wkT k−1
has at most k − 1 roots, we see that E(x, y) has at most k − 1 elements.
Finally, since the number of distinct pairs in Z isn
, we have
n
2
.
2
# ∪ {E(x, y) : x ∈ Z ∧ y ∈ Z ∧ x 6= y} ≤ (k − 1)
Definition: Let P be a zero-dimensional set of polynomials in K[X1, . . . , Xk].
Then an element a in A := K[X1, . . . , Xk]/Ideal(P, K) is separating for
P if a has distinct values at the distinct roots of P in Ck.
arating for P if the number of roots of P in Ck is finite.
Proposition 8. Let P ⊆ K[X1, . . . , Xk] be a set of polynomials with a finite
solution set Zero(P, Ck). If this solution set has n elements then there is an
The next proposition says that there is a linear polynomial which is sep-
such that the linear polynomial
integer between 0 and (k − 1)n
2
ai := X1 + iX2 + i2X3 + ··· + ik−1Xk
is separating for P.
Proof. Note that each of the ai may be regarded as an element the dual
space (Ck)0. Apply the separating result for vector spaces. See also the
proof of that result.
Proposition 9. Independence of powers of a separating element.
Let A := K[X1, . . . , Xk]/Ideal(P, K) and assume n := #Zero(P, Ck) is
finite. If a ∈ A is a separating element then the elements 1, a, a2, . . . , an−1
are linearly independent in A.
Proof. Assume 0 = c0 + c1a + ··· + cn−1an−1 in A where the ci are in K.
Consider the polynomial b := c0+c1a+···+cn−1an−1 in K[X1, . . . , Xk]. Note
that b ∈ Ideal(P, K). Let x1, . . . , xn be the distinct roots of P in Ck. Note
that for every x in this list we have b(x) = 0. It follows that the univariate
polynomial p(T ) := c0 + c1T + ··· + cn−1T n−1 has n distinct roots (namely,
a(x1), a(x2), . . . , a(xn−1)). Hence p(T ) must be the zero polynomial, that
is, c0 = c1 = ··· = cn−1 = 0.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
