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
. 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
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 γ
ϕ .
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 )=
for c with γ ( c ). In other words we consider the input formula
x n
=0 .
x 1 ···∃
h> 0
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
[ u 1 ,...,u m ,x 1 ,...,x n− 1 ]with a h,d h
= 0. Assume for a moment
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 )
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