Generic Hermitian Quantifier Elimination - Artificial Intelligence and Symbolic Computation - page 85

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