Information Technology Reference
In-Depth Information
m with γ ( c ), we
cannot uniformly count Z + or Z for χ .Notethat χ ( c ) is of real type, i.e., there
are no zeroes in
While the computations used so far are all uniform in c
R
. For those polynomials we can compute the number of
positive and negative zeroes using Descartes rule of signs. It states that the
positive real zeroes of a polynomial χ ( c ) of real type are exactly the number of
sign changes in the list of coecients of χ ( c ) ignoring 0. By considering χ (
C \ R
c )
one can also compute the negative zeroes using Descartes rule of signs.
Let χ = i =0 a i /b i y i ,where a i ,b i Q
[ u 1 ,...,u m ]. For δ
∈{
<, = ,>
}
l let ϕ δ
be the formula
a l b l δ l 0 .
Using Descartes rule of signs we can now uniformly count the number Z + of
positive and the number Z δ
a 1 b 1 δ 1 0
∧···∧
m with γ ( c )
of negative zeroes of χ ( c ) for all c
R
and ϕ δ ( c ).
Finally define ϕ by
ϕ δ
=0 .
Z +
Z δ
δ∈{<, = ,>} l
Our formula ϕ states that the polynomial χ has exactly the same number of
positive as of negative real zeroes. A quantifier-free formula with this property is
called type formula for the polynomial χ . Recall from our discussion above that
in this situation G has no zeroes which satisfy the given side conditions. Thus
our final elimination result is γ
∧¬
ϕ .
2.3
Constructing Equations
We enter this case of the Hermitian quantifier elimination if the input formula
does not contain any equation or the dimension of Id G ( c ) is n , i.e., I ( G )=
{
0
}
for c with γ ( c ). In other words we consider the input formula
x n
h
=0 .
x 1 ···∃
h> 0
f
H
f
F
In this case, we can eliminate one quantifier, say x n , and the other quanti-
fiers of the considered block are eliminated by a recursive call of the Hermitian
quantifier elimination.
Let h have a representation of the form d k =0 a h,k x n
where each a h,k is a
polynomial in
Q
[ u 1 ,...,u m ,x 1 ,...,x n− 1 ]with a h,d h
= 0. Assume for a moment
r
that H =
{
h 1 ,...,h r }
and let D =
×
k =1 {
0 ,...,d h k }
.For δ
D we denote by
δ h the s -th element of δ such that h s = h . Define P =
{
( h i ,h j )
|
1
i<j
r
}
H 2 .
For h
let Γ d
H and d
∈{
0 ,...,d h }
be the following formula:
d h
a h,k =0
a h,d
=0 .
k = d +1
Search WWH ::

Custom Search